5009
.pdfМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего образования «Нижегородский государственный архитектурно-
строительный университет»
О.В. Любимцев
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Учебно-методическое пособие
по подготовке к лекциям, практическим занятиям (включая рекомендации по организации самостоятельной работы) для обучающихся по дисциплине «Алгоритмы и структуры данных» по направлению подготовки 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике
Нижний Новгород
2016
УДК 004.9
Любимцев О.В. Алгоритмы и структуры данных [Электронный ресурс]: учеб. - метод. пос. / Любимцев О. В.; Нижегор. гос. архитектур. - строит. ун - т – Н. Новгород: ННГАСУ, 2016. – 21 с;
В данном учебно-методическом пособии по дисциплине «Алгоритмы и структуры данных» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебно-методического пособия — это помощь в усвоении лекций и подготовке к практическим занятиям. Учебнометодическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Алгоритмы и структуры данных» по направлению подготовки 09.03.03 Прикладная информатика. Учебно-методическое пособие ориентировано на обучение в соответствии с календарным учебным графиком и учебным планом по основной профессиональной образовательной программе направления 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике, утверждённым решением учёного совета ННГАСУ от 03.07.2015 г. (протокол № 9).
© О. В. Любимцев, 2016
© ННГАСУ, 2016.
2
Оглавление
1. Общие положения…………………………………………………..……..4
1.1Цели изучения дисциплины и результаты обучения ……………..…..4
1.2Содержание дисциплины…………………………………………..……5
1.3Порядок освоения материала…………………….………………..…….6
2.Методические указания по подготовке к лекциям………...………….....6
2.1Общие рекомендации по работе на лекциях………….……………..…6
2.2Общие рекомендации при работе с конспектом лекций…….……...…7
2.3Общие рекомендации по изучению материала лекций………..............8
2.4Контрольные вопросы…………………………….…………………..…9
3. Методические указания по подготовке к практическим занятиям…...11
3.1 Общие рекомендации по подготовке к практическим занятиям…….11 3.2 Примеры задач для практических занятий…………………..………..12
4. Методические указания по организации самостоятельной работы…..15
4.1Общие рекомендации для самостоятельной работы…………............15
4.2Темы для самостоятельного изучения………………...........................18
4.3Учебно-методическое обеспечение самостоятельной работы………18
4.4Задания для самостоятельной работы………………………...............19
3
1. Общие положения
1.1 Цели изучения дисциплины и результаты обучения
Целями освоения учебной дисциплины Б.1.12. Алгоритмы и структу-
ры данных являются:
изучение характеристик сложности алгоритма, знакомство со струк-
турами данных, их представлениями и алгоритмами обработки, без знания которых невозможно современное компьютерное программирование. Рас-
сматриваются различные алгоритмы для работы с очередями, стеками,
списками, деревьями, таблицами, графами. Подробно рассматриваются ал-
горитмы внутренней и внешней сортировки и поиска данных в таблицах. В процессе освоения дисциплины студент должен
Знать основные понятия, методы, алгоритмы, способы решения задач учебной дисциплины «Алгоритмы и структуры данных»; описание структур хранения данных: вектор, список, сеть, массив, строки и записи, множества;
описание линейных структур: стек, очередь, дек; описание нелинейных структур: дерево, лес, граф; алгоритмы внутренней и внешней сортировки;
Уметь перевести содержательную задачу на математический язык, найти подходящий метод решения задачи, содержательно проанализировать ре-
зультаты решения и применить их на практике; компьютерной техникой и информационными технологиями; навыками создания, отладки и тестиро-
вания программ.
Владеть техникой решения задач сортировок и поиска; навыками абстракт-
ных рассуждений, технологиями использования современных программных средств, работы пользователя и программиста в интегрированных средах,
использующих «оконный интерфейс».
Данная дисциплина позволит студентам не только систематизиро-
вать полученные теоретические знания, укрепить исследовательские навы-
ки, но и даст возможность ориентироваться в новом предметном поле информатики.
4
1.2 Содержание дисциплины
Материал дисциплины сгруппирован по следующим разделам:
1. Алгоритмы и данные.
Понятие алгоритма и его свойства. Способы записи алгоритма. Постановка задачи. Построение модели задачи. Разработка алгоритма. Реализация ал-
горитма в виде программы. Проверка правильности алгоритма. Простей-
шая модель вычислений: машина Тьюринга. Определение временной и емкостной сложности алгоритма. Значение эффективных алгоритмов в вы-
числительных задачах. Асимптотики. Оценка сложности алгоритмов для задач сортировок. Детерминированные и недетерминированные алгоритмы. P и NP сложные задачи.
2. Линейные структуры данных.
Стеки: структуры стека, операции над стеками, применение стеков при разработке приложений. Очереди: структуры очереди, операции над очередью, применение очереди при разработке приложений. Деки.
3. Типы данных. Структуры хранения данных.
Характеристика данных тремя качествами: семантикой, синтаксисом и прагматикой. Данные скалярных типов. Данные структурных типов. Опре-
деление структуры данных. Определение структуры хранения данных.
Представление адреса в языках программирования с помощью указателей.
Типизированные и нетипизированные указатели. Статическая и динамиче-
ская память. Вектор. Список. Сеть.
5
1.3 Порядок освоения материала
Материал дисциплины изучается в соответствии с порядком, опреде-
лённым в следующей таблице:
|
|
|
Таблица 1 |
|
Порядок освоения дисциплины |
|
|
|
|
|
|
№ |
Раздел дисциплины |
|
№№ предшествующих раздело |
|
|
|
|
1 |
Алгоритмы и данные |
|
- |
|
|
|
|
2 |
Линейные структуры данных |
|
1 |
|
|
|
|
3 |
Типы данных. Структуры хранения данных |
|
1,2 |
|
|
|
|
2. Методические указания по подготовке к лекциям
2.1 Общие рекомендации по работе на лекциях
Лекция является главным звеном дидактического цикла обучения. Ее цель — формирование основы для последующего усвоения учебного мате-
риала. В ходе лекции преподаватель в устной форме, а также с помощью презентаций передает обучаемым знания по основным, фундаментальным вопросам изучаемой дисциплины.
Назначение лекции состоит в том, чтобы доходчиво изложить основ-
ные положения изучаемой дисциплины, ориентировать на наиболее важ-
ные вопросы учебной дисциплины и оказать помощь в овладении необхо-
димых знаний и применения их на практике.
Личное общение на лекции преподавателя со студентами предоставля-
ет большие возможности для реализации образовательных и воспитатель-
ных целей.
При подготовке к лекционным занятиям студенты должны ознако-
6
миться с презентаций, предлагаемой преподавателем, отметить непонятные термины и положения, подготовить вопросы с целью уточнения правиль-
ности понимания. Рекомендуется приходить на лекцию подготовленным,
так как в этом случае лекция может быть проведена в интерактивном ре-
жиме, что способствует повышению эффективности лекционных занятий.
2.2Общие рекомендации при работе с конспектом лекций
Входе лекционных занятий необходимо вести конспектирование учебного материала. Конспект помогает внимательно слушать, лучше за-
поминать в процессе осмысленного записывания, обеспечивает наличие опорных материалов при подготовке к семинару, зачету, экзамену.
Полезно оставить в рабочих конспектах поля, на которых делать по-
метки из рекомендованной литературы, дополняющие материал прослу-
шанной лекции, а также подчеркивающие особую важность тех или иных теоретических положений.
В случае неясности по тем или иным вопросам необходимо задавать преподавателю уточняющие вопросы. Следует ясно понимать, что отсут-
ствие вопросов без обсуждения означает в большинстве случаев непони-
мание материала дисциплины.
7
2.3 Общие рекомендации по изучению материала лекций
Раздел 1: “Алгоритмы и данные " – 3 лекции.
Цель: Освоить построение модели задачи, разработку алгоритма. Реализовывать классические алгоритмы в виде программы.
На лекциях приводятся понятие алгоритма и его свойства; проверка правильности алг рекурсия. Предлагаются простые сортировки массива: сортировка пузырь-
ком, сортировка вставками, сортировка выбором. Быстрые сортировки:
сортировка с помощью кучи, быстрая сортировка.
Раздел 2: " Линейные структуры данных" – 3 лекции.
Цель: Освоить и использовать на практике основные линейные структуры данных
На лекциях описывается создание односвязного списка; функция вы-
вода списка на консоль; операции добавления и удаления элементов из списка; линейный двусвязный список; создание двусвязного списка; функ-
ция вывода списка на консоль. Даются операции добавления и удаления элементов из двусвязного списка. Приводится структура стека; очереди;
дека. Вводятся функции Push и Pop.
Раздел 3: " Типы данных. Структуры хранения данных" - 2 лекции.
Цель: Определение структуры данных. Определение структуры хранения данных.
На лекции дается характеристика данных тремя качествами: семан-
тикой, синтаксисом и прагматикой, данные скалярных типов, данные
8
структурных типов, представление адреса в языках программирования с помощью указателей, типизированные и нетипизированные указатели, ста-
тическая и динамическая память, вектор, список, сеть. Предлагаются алго-
ритмы на графах: поиск в глубину, топологическая сортировка, поиск циклов в графах, поиск в ширину, кратчайшие пути в графах.
2.4 Контрольные вопросы
Контрольные вопросы к разделу 1: Алгоритмы и данные
1.Алгоритмы простого поиска в массиве.
2.Бинарный поиск.
3.Простые сортировки массивов.
4.Быстрые сортировки массивов.
5.Оценка сложности алгоритмов для задач сортировок.
6.Простейшая модель вычислений: машина Тьюринга.
Контрольные вопросы к разделу 2: Линейные структуры данных
1.Односвязные списки.
2.Стек. Примеры использования стека при решении задач.
3.Стек: функции Push и Pop.
4.Двусвязные списки.
5.Очередь. Функции Push и Pop.
6.Дек: функции Push и Pop.
9
Контрольные вопросы к разделу 3: Типы данных. Структуры хра-
нения данных
1. Характеристика данных тремя качествами: семантикой, синтакси-
сом и прагматикой.
2. Представление адреса в языках программирования с помощью ука-
зателей.
3.Статическая и динамическая память.
4.Вектор, список, сеть
5.Алгоритмы на графах: поиск в глубину, топологическая сортировка.
6.Алгоритмы на графах: поиск в ширину, кратчайшие пути в графах.
10