BSc: BasicProgramDevelopmentConcepts

Алгоритмы и структуры данных 2

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а): Станкевич А.С.

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области разработки и анализа алгоритмов и структур данных, их применения для решения различных прикладных задач в рамках профессиональной деятельности. Дисциплина является второй частью курса, в ходе освоения дисциплины обучающиеся рассматривают более сложные алгоритмы и структуры данных, а также получают навыки программирования на языках Python и C++. Изучаются стандартные контейнеры, основные принципы структур данных, лежащих в основе реализации этих контейнеров, алгоритмы на графах, алгоритмы на строках, а также элементы теории формальных языков: использование регулярных выражений, конечных автоматов, контекстно-свободных грамматик и алгоритмы их обработки. Курс включает в себя лекции по алгоритмам и структурам данных, семинары по программированию, практические занятия с разбором теоретических ДЗ и лабораторные работы по реализации изученных алгоритмов на языках программирования Python и C++.

2. Перечень планируемых результатов обучения

Цели освоения дисциплины

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

2. Изучение различных структур данных: студенты учатся выбирать и применять подходящие структуры данных для эффективного решения конкретных задач.

3. Приобретение навыков программирования на Python и C++: изучение языков программирования позволяет студентам реализовывать изученные алгоритмы и применять их на практике.

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

Задачами дисциплины являются:

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

2. Применение структур данных: Осваивая различные структуры данных, студенты учатся выбирать и применять наиболее подходящие для конкретных задач, что позволяет им эффективно управлять данными и решать сложные задачи.

3. Разработка программного обеспечения: Изучение языков программирования Python и C++ позволяет студентам разрабатывать программное обеспечение, включая реализацию алгоритмов и работу со структурами данных.

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

5. Развитие алгоритмического и аналитического мышления: Изучение алгоритмов и их реализация на практике способствует развитию у студентов алгоритмического мышления, а также аналитических навыков, необходимых для эффективного решения различных задач.

Общая характеристика результата обучения по дисциплине

Знания: сформированы систематические знания:

- структуры данных, лежащие в основе стандартных контейнеров библиотеки шаблонов языка программирования С++

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

- алгоритмы обработки строк

- понятие регулярного языка и регулярного выражения

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

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

- информация о реализованных в стандартной библиотеке языка Python алгоритмах обработки различных форматов файлов, содержащих данные

Умения:сформированы умения

1. выбирать подходящую структуру данных и алгоритм для решения задачи
2. формулировать задачу предметной области как задачу анализа графа, в том числе задачу поиска кратчайшего пути в графе
3. реализовывать, а также при необходимости модифицировать алгоритмы на графах
4. использовать алгоритмы обработки строковых данных для решения задач
5. применять алгоритмы обработки конечных автоматов, использовать конечные автоматы для решения задач
6. применять алгоритмы обработки контекстно-свободных грамматик, использовать контекстно-свободные грамматики для решения задач

Навыки (владения): сформировано владение навыками

1. реализовывать хранение графа в программе
2. реализовывать алгоритмы обработки графов
3. реализовывать алгоритмы обработки строк
4. пользоваться стандартной библиотекой языка Python для работы с регулярными выражениями, обработки данных в стандартных форматах JSON и XML
5. пользоваться стандартной библиотекой шаблонов языка С++, встроенными алгоритмами и структурами данных
6. реализовывать метод рекурсивного спуска для разбора выражений и вычисления значений

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Коллекции и их реализация	- коллекции в языке программирования С++ - std::vector, std::set, std::map, std::unordered_set, std::unordered_map - модуль algorithm в С++ - реализация коллекций: соответствующие структуры данных - саморасширяющийся массив - деревья поиска - хеширование, хеш-функции
2.	Алгоритмы на графах	- хранение графов - обход графа в глубину и его применения - минимальное остовное дерево, алгоритм Прима, алгоритм Краскала
3.	Кратчайшие пути в графах	- обход графа в ширину - алгоритм Дейкстры - алгоритм Флойда - алгоритм Беллмана-Форда
4.	Обработка строк	- представление строк - задача о поиске подстроки в строке - префикс-функция - Z-функция - хранение коллекции строк, бор
5.	Автоматы и регулярные языки	- регулярные языки - регулярные выражения - детерминированные конечные автоматы - недетерминированные конечные автоматы - детерминизация автомата - связь конечных автоматов и регулярных выражений, теорема Клини - минимизация ДКА - работа с регулярными выражениями в языке Python
6.	Контекстно-свободные грамматики	- контекстно-свободные грамматики и языки - обработка КС-языков - алгоритм Кока-Янгера-Касами - нисходящий разбор - рекурсивный спуск, ручная реализация на языке Python - вычисление значений выражений
7.	Стандартные средства работы с файлами	- разбор JSON-файлов в языке Python - разбор XML-файлов в языке Python

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Коллекции и их реализация	Решение задач с текстовой постановкой с использованием стандартных коллекций Использование нестандартных ключей и методов сравнения для стандартных коллекций Реализация структур данных, используемых в стандартных коллекциях, вручную
2.	Алгоритмы на графах	Реализация алгоритма поиска компонент связности Реализация алгоритма поиска цикла Реализация алгоритма топологической сортировки Реализация алгоритма поиска компонент сильной связности
3.	Кратчайшие пути в графах	Реализация алгоритма обхода в ширину Реализация алгоритма Дейкстры Реализация алгоритма Флойда Реализация алгоритма Беллмана-Форда
4.	Обработка строк	Реализация наивного алгоритма поиска подстроки в строке Реализация алгоритма Кнута-Морриса-Пратта построения префикс-функции Реализация алгоритма Манакера построения Z-функции
5.	Автоматы и регулярные языки	Решение теоретических заданий на анализ свойств регулярных языков Реализация алгоритмов анализа и преобразования конечных автоматов Решение задач на соответствие регулярному выражению с использованием стандартной библиотеки языка программирования Python
6.	Контекстно-свободные грамматики	Решение теоретических заданий на анализ свойств контекстно-свободных языков Реализация алгоритма Кока-Янгера-Касами Реализация алгоритма рекурсивного спуска для вычисления выражений
7.	Стандартные средства работы с файлами	Реализация чтения данных из JSON-файла с использованием стандартных библиотек Реализация чтения данных из XML-файла с использованием стандартных библиотек

Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Коллекции и их реализация	Решение заданий по программированию с автоматической проверкой	Задания по программированию с автоматической проверкой: - решение заданий с использованием стандартных коллекций - реализация структур данных, используемых в стандартных коллекциях, вручную
2.	Алгоритмы на графах	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов на графах Задания по программированию с автоматической проверкой: - реализация алгоритма поиска компонент связности - реализация алгоритма поиска цикла - реализация алгоритма топологической сортировки - реализация алгоритма поиска компонент сильной связности
3.	Кратчайшие пути в графах	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов поиска кратчайшего пути в графе Задания по программированию с автоматической проверкой: - реализация алгоритма обхода в ширину - реализация алгоритма Дейкстры - реализация алгоритма Флойда - реализация алгоритма Беллмана-Форда
4.	Обработка строк	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов на строках Задания по программированию с автоматической проверкой: - реализация наивного алгоритма поиска подстроки в строке - реализация алгоритма Кнута-Морриса-Пратта построения префикс-функции - реализация алгоритма Манакера построения Z-функции
5.	Автоматы и регулярные языки	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - анализ свойств регулярных языков Задания по программированию с автоматической проверкой: - реализация алгоритма проверки допуска строки детерминированным автоматом - реализация алгоритма проверки допуска строки недетерминированным автоматом - реализация алгоритма детерминизации автомата - реализация алгоритма минимизации автомата - решение задач на соответствие регулярному выражению с использованием стандартной библиотеки языка программирования Python
6.	Контекстно-свободные грамматики	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - анализ свойств контекстно-свободных языков Задания по программированию с автоматической проверкой: - реализация алгоритма Кока-Янгера-Касами - реализация алгоритма рекурсивного спуска для вычисления выражений
7.	Стандартные средства работы с файлами	Решение заданий по программированию с автоматической проверкой	Задания по программированию с автоматической проверкой: - реализация чтения данных из JSON-файла с использованием стандартных библиотек - реализация чтения данных из XML-файла с использованием стандартных библиотек

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1	Коллекции и их реализация	Как устроена коллекция (std::vector, std::set, std::map, std::unordered_set, std::unordered_map) в C++? Проведите амортизационный анализ std::vector Какие хеш-функции удачно применить для хеширования строк?
2	Алгоритмы на графах	Хранение графа. Двухцветный и трехцветный обход в глубину. Применение обхода в глубину для выделения компонент связности графа. Применение обхода в глубину для поиска цикла в ориентированном и неориентированном графе. Топологическая сортировка ориентированных графов.
3	Кратчайшие пути в графах	Обход графа в ширину. Алгоритм Дейкстры. Алгоритм Флойда. Алгоритм Беллмана-Форда. Поиск отрицательного цикла в графе.
4	Обработка строк	Задача о поиске подстроки в строке Префикс-функция Z-функция Хранение коллекции строк, бор
5	Автоматы и регулярные языки	Построение регулярного выражения по текстовому описанию языка. Построение конечного автомата по текстовому описанию языка. Построение детерминированного автомата по недетерминированному. Теорема Клини
6	Контекстно-свободные грамматики	Контекстно-свободные грамматики и языки Построение КС-грамматики по текстовому описанию языка. Алгоритм Кока-Янгера-Касами
7	Стандартные средства работы с файлами	Написание программы обработки JSON-файлов. Написание программы обработки XML-файлов.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Коллекции C++. std::vector, std::set, std::map, std::unordered_set, std::unordered_map
2. Амортизационный анализ. Саморасширяющийся массив
3. Деревья поиска
4. Хеширование, хеш-функции
5. Обход графа в глубину и его применения для поиска компонент связности и цикла.
6. Обход графа в глубину и его применения для топологической сортировки и поиска компонент сильной связности
7. Минимальное остовное дерево, алгоритм Прима, алгоритм Краскала
8. Обход графа в ширину
9. Алгоритм Дейкстры
10. Алгоритм Флойда
11. Алгоритм Беллмана-Форда
12. Задача о поиске подстроки в строке. Префикс-функция.
13. Задача о поиске подстроки в строке. Z-функция
14. Хранение коллекции строк, бор
15. Регулярные языки
16. Детерминированные конечные автоматы
17. Недетерминированные конечные автоматы, детерминизация автомата
18. Связь конечных автоматов и регулярных выражений, теорема Клини
19. Минимизация ДКА
20. Контекстно-свободные грамматики и языки
21. Алгоритм Кока-Янгера-Касами
22. Нисходящий разбор. Рекурсивный спуск.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

1. Кормен T., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2012. — 1296 с.
2. Асанов М., Баранский В., Расин В. Дискретная математика: графы, матроиды, алгоритмы. — Лань, 2010. — 368 с.
3. Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. — М.: Вильямс, 2010. — 400 с.
4. Седжвик Р. Фундаментальные алгоритмы на C++. — Вильямс, 2011. — 1056 с.
5. Страуструп Б. Язык программирования С++. Специальное издание. — М.: Бином, 2011. — 1136 с.
6. Страуструп Б. Дизайн и эволюция С++. — ДМК Пресс, 2011. — 446 с.
7. Саттер Г. Решение сложных задач на С++. — М.: Вильямс, 2015. — 400 с.
8. Саттер Г. Новые сложные задачи на C++. — М.: Вильямс, 2015. — 272 с.
9. Саттер Г., Александреску А. Стандарты программирования на С++. — М.: Вильямс, 2015. — 224 с.
10. Александреску А. Современное проектирование на С++. — М.: Вильямс, 2015. — 336 с.
11. Саммерфилд М. Python на практике [Электронный ресурс] : учебное пособие. — Электрон. дан. — М. : ДМК Пресс, 2014. — 338 с.
12. Сузи, Р. А. Язык программирования Python : учебное пособие / Р. А. Сузи. — 2-е изд. — Москва : ИНТУИТ, 2016. — 350 с. — ISBN 5-9556-0058-2.
13. Хопкрофт Д. , Мотвани Р., Ульман Д., Введение в теорию автоматов, языков и вычислений. — Вильямс, 2016. — 528 с.

Список дополнительной литературы:
1. Вики-конспекты. — http://neerc.ifmo.ru/wiki/index.php?title=Заглавная_страница
2. Документация к языку Python – https://docs.python.org/3/
Документация к языку программирования С++ — https://en.cppreference.com/w/

Методические указания для обучающихся по освоению дисциплины

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

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Подготовка к промежуточной аттестации	При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Практические (лабораторные) занятия	Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции