4428

МИНОБРНАУКИ РОССИИ

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

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

Платов А.Ю.

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

Учебно-методическое пособие по подготовке к лекциям, практическим занятиям

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

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

направленность (профиль) Разработка программно-информационных систем

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

2022

УДК 004.9

Платов А.Ю. / Алгоритмы и структуры данных: учебно-методическое пособие / А.Ю. Платов; Нижегородский государственный архитектурно-строительный университет – Нижний Новгород: ННГАСУ, 2022. – 14 с.– Текст: электронный.

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

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

© А.Ю. Платов, 2022

© ННГАСУ, 2022

2

Оглавление

3

1. Общие положения

1.1 Цели изучения дисциплины и результаты обучения

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

Знать:

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

Уметь:

программировать базовые алгоритмы на языках С, С++ или Питон;

отлаживать программы с базовыми алгоритмами,

программировать базовые алгоритмы на языках С, С++ или Питон,

отлаживать программы с базовыми алгоритмами.

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

4

5.Поиск в глубину и ширину.Алгоритмы поиска в глубину и ширину. Рекурсивная и нерекурсивная версии. Временная сложность поиска.

6.Связность и достижимостьПоиск простого пути. Поиск эйлерова цикла. Поиск гамильтонова цикла. Временная сложность

7. Кратчайший путьАлгоритм Дейкстры. Топологическая сортировка. Определение критического пути.

1.3Вспомогательная литература для изучения дисциплины

1.Лебеденко, Л. Ф.. Информатика. Ч.2 : учебно-методическое пособие. / Лебеденко, Л. Ф., Парначева, Т. И. ; Л. Ф. Лебеденко, Т. И. Парначева. – Новосибирск : Сибирский государственный университет телекоммуникаций и информатики, 2019. – 137 с. – URL: URL: http://www.iprbookshop.ru/102155.html. – ISBN ISBN 2227-8397.

2.Рябкова Светлана Львовна. Основы алгоритмизации : учебное пособие для иностранных граждан. / Рябкова Светлана Львовна, Скопина Юлия Игоревна ; Нижегородский государственный архитектурно-строительный университет. – Нижний Новгород : ННГАСУ, 2021. – 1 CD ROM. – URL: URL: http://catalog.nngasu.ru/MarcWeb2/. – ISBN ISBN 978-5-528-00433-4.

6

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

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

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

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

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

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

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

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

что способствует повышению эффективности лекционных занятий.

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

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

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

экзамену.

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

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

7

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

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

1.Перечислить основные свойства алгоритма

2.Какова временная сложность алгоритмов поиска

3.Какова минимальная временная сложность алгоритмов сортировки

4.Какова временная сложность алгоритмов простой сортировки

5.Какова временная сложность алгоритмов сортировки с переменным шагом

6.Какова временная сложность алгоритмов слияния и быстрого поиска

7.Какова временная сложность алгоритма пирамидальной сортировки

8.Перечислить классы абстрактных типов данных

9.Определить преимущества односвязных и двусвязных списков

10.Применение дека и стека.

11.Преимущества разных типов представления графов

12.Временная сложность поиска

13.Временная сложность построения циклов Эйлера и Гамильтона

14.Временная сложность поиска кратчайшего пути

8

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

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

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

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

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

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

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

1.Что такое структура данных.

2.Перечислить структуры хранения данных.

3.Ориентированные и неориентированные графы, цепи, циклы, пути и контуры графов

4.Связь между логической и физической структур массива

5.Особенность физической организации массива.

6.Описать структуру хранения двумерного массива

7.Принцип организации структуры – стек.

8.Линейная структура – очередь

9.Принцип организации структуры – очередь.

10.Структура дек.

11.Алгоритм Дейкстры

9

12.Алгоритм поиска цикла Гамильнона

13.Алгоритм топологической сортировки

14.Пирамидальная сортировка

15.Быстрая сортировка

10