4912

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования

«Нижегородский государственный архитектурно-строительный университет»

О.В. Любимцев

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

Учебно-методическое пособие

по подготовке к лекционным и практическим занятиям (включая рекомендации по организации самостоятельной работы)

для обучающихся по дисциплине «Алгоритмы и структуры данных» по направлению подготовки 09.03.04 Программная инженерия профиль Разработка программно-информационных систем

Нижний Новгород

2018

УДК 004.9

Любимцев О.В. Алгоритмы и структуры данных [Электронный ресурс]: учеб. - метод. пос. / Любимцев О. В.; Нижегор. гос. архитектур. - строит. ун - т – Н. Новгород: ННГАСУ, 2018. – 21 с;

В данном учебно-методическом пособии по дисциплине «Алгоритмы и структуры данных» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебнометодического пособия — это помощь в усвоении лекций и подготовке к практическим занятиям.

Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Алгоритмы и структуры данных» по направлению подготовки 09.03.04 Программная инженерия. Учебно-методическое пособие ориентировано на обучение в соответствии с календарным учебным графиком и учебным планом по основной профессиональной образовательной программе направления 09.03.04 Программная инженерия, утверждённым решением учёного совета ННГАСУ от 02.03.2018 г. (протокол № 3).

© О.В., Любимцев, 2018 © ННГАСУ, 2018

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.2 Содержание дисциплины

Материал дисциплины сгруппирован по следующим разделам:

4

1. Алгоритмы и данные.

Понятие алгоритма и его свойства. Способы записи алгоритма. Постановка за-

дачи. Построение модели задачи. Разработка алгоритма. Реализация алгоритма в виде программы. Проверка правильности алгоритма. Простейшая модель вычисле-

ний: машина Тьюринга. Определение временной и емкостной сложности алгорит-

ма. Значение эффективных алгоритмов в вычислительных задачах. Асимптотики.

Оценка сложности алгоритмов для задач сортировок. Детерминированные и неде-

терминированные алгоритмы. P и NP сложные задачи.

2. Линейные структуры данных.

Стеки: структуры стека, операции над стеками, применение стеков при разра-

ботке приложений. Очереди: структуры очереди, операции над очередью, примене-

ние очереди при разработке приложений. Деки.

3. Типы данных. Структуры хранения данных.

Характеристика данных тремя качествами: семантикой, синтаксисом и праг-

матикой. Данные скалярных типов. Данные структурных типов. Определение струк-

туры данных. Определение структуры хранения данных. Представление адреса в языках программирования с помощью указателей. Типизированные и нетипизиро-

ванные указатели. Статическая и динамическая память. Вектор. Список. Сеть.

1.3 Порядок освоения материала

Материал дисциплины изучается в соответствии с порядком, определённым в следующей таблице:

2. Методические указания по подготовке к лекциям

2.1 Общие рекомендации по работе на лекциях

Лекция является главным звеном дидактического цикла обучения. Ее цель — формирование основы для последующего усвоения учебного материала. В ходе лек-

ции преподаватель в устной форме, а также с помощью презентаций передает обуча-

емым знания по основным, фундаментальным вопросам изучаемой дисциплины.

Назначение лекции состоит в том, чтобы доходчиво изложить основные поло-

жения изучаемой дисциплины, ориентировать на наиболее важные вопросы учебной дисциплины и оказать помощь в овладении необходимых знаний и применения их на практике.

Личное общение на лекции преподавателя со студентами предоставляет боль-

шие возможности для реализации образовательных и воспитательных целей.

При подготовке к лекционным занятиям студенты должны ознакомиться с пре-

зентаций, предлагаемой преподавателем, отметить непонятные термины и положе-

ния, подготовить вопросы с целью уточнения правильности понимания. Рекоменду-

ется приходить на лекцию подготовленным, так как в этом случае лекция может быть проведена в интерактивном режиме, что способствует повышению эффектив-

ности лекционных занятий.

2.2 Общие рекомендации при работе с конспектом лекций

В ходе лекционных занятий необходимо вести конспектирование учебного ма-

териала. Конспект помогает внимательно слушать, лучше запоминать в процессе осмысленного записывания, обеспечивает наличие опорных материалов при подго-

товке к семинару, зачету, экзамену.

Полезно оставить в рабочих конспектах поля, на которых делать пометки из ре-

комендованной литературы, дополняющие материал прослушанной лекции, а также подчеркивающие особую важность тех или иных теоретических положений.

В случае неясности по тем или иным вопросам необходимо задавать преподава-

телю уточняющие вопросы. Следует ясно понимать, что отсутствие вопросов без

6

обсуждения означает в большинстве случаев непонимание материала дисциплины.

2.3 Общие рекомендации по изучению материала лекций

Раздел 1: “Алгоритмы и данные « – 3 лекции.

Цель: Освоить построение модели задачи, разработку алгоритма. Реализовы-

вать классические алгоритмы в виде программы.

На лекциях приводятся понятие алгоритма и его свойства; проверка правиль-

ности алгоритма; определение временной сложности алгоритма; задание матриц в программе; функция swap; последовательный поиск в массиве; поиск с барьером;

бинарный поиск; рекурсия. Предлагаются простые сортировки массива: сортировка пузырьком, сортировка вставками, сортировка выбором. Быстрые сортировки: сор-

тировка с помощью кучи, быстрая сортировка.

Раздел 2: «Линейные структуры данных» – 3 лекции.

Цель: Освоить и использовать на практике основные линейные структуры данных

На лекциях описывается создание односвязного списка; функция вывода списка на консоль; операции добавления и удаления элементов из списка; линейный дву-

связный список; создание двусвязного списка; функция вывода списка на консоль.

Даются операции добавления и удаления элементов из двусвязного списка. Приво-

дится структура стека; очереди; дека. Вводятся функции Push и Pop.

Раздел 3: « Типы данных. Структуры хранения данных» - 2 лекции.

Цель: Определение структуры данных. Определение структуры хранения дан-

ных.

На лекции дается характеристика данных тремя качествами: семантикой, син-

таксисом и прагматикой, данные скалярных типов, данные структурных типов,

представление адреса в языках программирования с помощью указателей, типизи-

рованные и нетипизированные указатели, статическая и динамическая память, век-

7

тор, список, сеть. Предлагаются алгоритмы на графах: поиск в глубину, топологиче-

ская сортировка, поиск циклов в графах, поиск в ширину, кратчайшие пути в гра-

фах.

2.4 Контрольные вопросы

Контрольные вопросы к разделу 1: Алгоритмы и данные

1.Алгоритмы простого поиска в массиве.

2.Бинарный поиск.

3.Простые сортировки массивов.

4.Быстрые сортировки массивов.

5.Оценка сложности алгоритмов для задач сортировок.

6.Простейшая модель вычислений: машина Тьюринга.

Контрольные вопросы к разделу 2: Линейные структуры данных

1.Односвязные списки.

2.Стек. Примеры использования стека при решении задач.

3.Стек: функции Push и Pop.

4.Двусвязные списки.

5.Очередь. Функции Push и Pop.

6.Дек: функции Push и Pop.

Контрольные вопросы к разделу 3: Типы данных. Структуры хранения дан-

ных

1. Характеристика данных тремя качествами: семантикой, синтаксисом и прагмати-

кой.

2.Представление адреса в языках программирования с помощью указателей.

3.Статическая и динамическая память.

4.Вектор, список, сеть

5.Алгоритмы на графах: поиск в глубину, топологическая сортировка.

6.Алгоритмы на графах: поиск в ширину, кратчайшие пути в графах.

8

3.Методические указания по подготовке к практическим занятиям

3.1Общие рекомендации по подготовке к практическим занятиям

В ходе подготовки к практическим занятиям необходимо изучать основную ли-

тературу, знакомиться с дополнительной литературой, а также с новыми публикаци-

ями в периодических изданиях: журналах, газетах и т.д. При этом необходимо учесть рекомендации преподавателя и требования учебной программы.

В соответствии с этими рекомендациями и подготовкой полезно дорабатывать свои конспекты лекции, делая в нем соответствующие записи из литературы, реко-

мендованной преподавателем и предусмотренной учебной программой. Целесооб-

разно также подготовить тезисы для возможного выступления по всем учебным во-

просам, выносимым на практическое занятие.

При подготовке к занятиям можно также подготовить краткие конспекты по во-

просам темы. Очень эффективным приемом является составление схем и презента-

ций.

Готовясь к докладу или реферативному сообщению, желательно обращаться за методической помощью к преподавателю. Составить план-конспект своего выступ-

ления. Продумать примеры с целью обеспечения тесной связи изучаемой теории с реальной жизнью. Своевременное и качественное выполнение самостоятельной ра-

боты базируется на соблюдении настоящих рекомендаций и изучении рекомендо-

ванной литературы. Студент может дополнить список использованной литературы современными источниками, не представленными в списке рекомендованной лите-

ратуры, и в дальнейшем использовать собственные подготовленные учебные мате-

риалы при написании курсовых и дипломных работ.

3.2 Примеры задач для практических занятий

Задачи для раздела 1.

Задача 1. Написать процедуру Insert вставки элемента в упорядоченный массив.

Задача 2. Написать функцию поиска второго максимума в массиве (за один проход по массиву).

Задача 3. Написать функцию Search поиска с барьером элемента в массиве.

9

Задача 4. Написать процедуру бинарного поиска элемента в массиве.

Задача 5. Написать процедуру Sort_insert сортировки массива вставками, используя процедуру Insert вставки элемента в упорядоченный массив.

Задача 6. Написать процедуру Sort_bubble сортировки массива пузырьком.

Задача 7. Сортировка массива Heap_sort (сортировка кучей на месте).

Задача 8. Написать процедуру Quick_sort быстрой сортировки.

Задача 9. При различных входных данных сравнить время работы Quick_sort,

Bubble_sort, Heap_sort.

Задача 10. Дано n отрезков [a[i], b[i]] на прямой (i = 1 . . . n). Найти максимальное k,

для которого существует точка прямой, покрытая k отрезками («максимальное чис-

ло слоев»). Число действий — порядка n log n.

Задача 11. Оптимизировать сортировку пузырьком по направлению пузырьков

(шейкерная сортировка).

Задача 12. Отсортировать массив с помощью кучи на минимум, используя два мас-

сива.

Задачи для раздела 2.

Задача 1. Написать функции Push и Pop для стека, хранящегося в массиве.

Задача 2. Решить задачу о правильной скобочной последовательности, используя стек, хранящегося в массиве.

Задача 3 Реализовать операции с очередью ограниченной длины так, чтобы количе-

ство действий для каждой операции было ограничено константой, независящей от длины очереди.

Задача 4. Написать процедуру инициализации односвязного списка.

Задача 5. Написать функцию удаления элемента из односвязного списка.

Задача 6. Написать функцию добавления элемента в конец двусвязного списка.

Задача 7. Деком называют структуру, сочетающую очередь и стек: класть и заби-

рать элементы можно с обоих концов. Как реализовать дек ограниченного размера на базе массива так, чтобы каждая операция требовала ограниченного числа дей-

ствий?

10