Бакалавриат
2019/2020![Цель освоения дисциплины](/f/src/global/i/edu/objectives.svg)
![Планируемые результаты обучения](/f/src/global/i/edu/results.svg)
![Содержание учебной дисциплины](/f/src/global/i/edu/sections.svg)
![Элементы контроля](/f/src/global/i/edu/controls.svg)
![Промежуточная аттестация](/f/src/global/i/edu/intermediate_certification.svg)
![Список литературы](/f/src/global/i/edu/library.svg)
Алгоритмы и структуры данных
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Программная инженерия)
Направление:
09.03.04. Программная инженерия
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Бычков Илья Сергеевич
Язык:
русский
Кредиты:
8
Контактные часы:
60
Программа дисциплины
Аннотация
Дисциплина "Алгоритмы и структуры данных" знакомит студентов с базовыми алгоритмами, теорий сложности, а также структурами данных. В курсе рассматриваются вопросы поиска данных, их хранения, построение, анализ алгоритмов и их использование для эффективного решения разнообразных задач.
Цель освоения дисциплины
- Знакомство с существующими алгоритмами для решения различных задач
- Знакомство с существующими структурами данных и их основными операциями
- Получение навыков проектирования, анализа и тестирования алгоритмов
Планируемые результаты обучения
- Формулировать понятие алгоритма, программы.
- Формулировать задачу сортировки
- Описывать и уметь реализовывать алгоритмы сортировки
- Доказывать оценки сложности алгоритмов сортировки
- Формулировать понятия пространственной и временной сложности алгоритма.
- Формулировать понятия массива, связного списка, стека, очереди и их вариаций
- Объяснять и и уметь реализовывать основные операции с массивами, связными списками, стеками, очередями
- Доказывать сложность основных операций с массивами, связными списками, стеками, очередями
- Формулировать понятие графа, представления графа;
- Описывать различные варианты построения и использования графовых моделей
- Объяснять и уметь реализовывать алгоритмы обхода графов
- Доказывать сложность алгоритмов обхода графов
- Формулировать задачи о кратчайших путях в различных постановках
- Описывать и уметь реализовывать алгоритмы поиска кратчайших путей
- Доказывать сложность алгоритмов поиска кратчайших путей
- Описывать работу метода разделяй и властвуй, алгоритмов динамического программирования и жадных алгоритмов
- Разрабатывать алгоритмы в соответствии с рассмотренными парадигмами для решения задач
- Формулировать задачи о поиске в тексте, поиске подстроки в строке
- Описывать и уметь реализовывать алгоритмы поиска в тексте
- Доказывать сложность алгоритмов поиска в тексте
- Формулировать задачу поиска
- Описывать и уметь реализовывать алгоритмы поиска
- Доказывать оценки сложности алгоритмов поиска
- Формулировать понятие переменной, массива.
- Доказывать оценки сложности алгоритмов
- Определять сложность алгоритмов по их описанию
Содержание учебной дисциплины
- Введение в алгоритмы. Понятие алгоритма и программы. Переменные, массивы.Введение в алгоритмы. Понятие алгоритма и программы. Языки программирования. Структуры данных. Переменные, массивы.
- Задача сортировки. Простые алгоритмы сортировки.Сортировка выбором (selection sort). Сортировка пузырьком (bubble sort). Сортировка вставками (insertion sort). Сортировка подсчётом (counting sort).
- Задача сортировки. Эффективные алгоритмы сортировки.Блочная сортировка (bucket sort). Сортировка слиянием (merge sort). Быстрая сортировка (quick sort). Поразрядная сортировка (radix sort). Timsort.
- Сложность алгоритмов.Понятие сложности алгоритмов. Временная сложность (time complexity). Пространственная сложность (space complexity). Оценка сложности алгоритмов.
- Алгоритмы поиска.Задача поиска объекта. Алгоритм линейного поиска (linear search). Алгоритм бинарного поиска (binary search). Алгоритм удваивающегося поиска (doubling search).
- Базовые структуры данных.Понятие структуры данных. Массив. Одномерный массив и многомерный массив. Связный список. Односвязный, двусвязный, кольцевой список. Стек. Очередь.
- Понятие графа. Алгоритмы на графах.Понятие графа. Представление графа в памяти компьютера. Матрица смежности (adjacency matrix). Список смежности (adjacency list). Матрица инцидентности (incidence matrix). Алгоритмы на графах. Обход графа в ширину (breadth first search). Обход графа в глубину (depth first search).
- Задачи о кратчайших путях. Алгоритмы нахождения кратчайших путей в графах.Задачи о кратчайших путях. Алгоритм Дейкстры (Dijkstra's algorithm). Алгоритм Беллмана-Форда (Bellman–Ford algorithm). Алгоритм Флойда-Уоршелла (Floyd–Warshall algorithm). Алгоритм A* (A star).
- Алгоритмические парадигмы.Алгоритмические парадигмы. Метод разделяй и властвуй (divide-and-conquer). Динамическое программирование (dynamic programming). Жадные алгоритмы (greedy algorithms)
- Строковые алгоритмыПоиск в тексте. Наивный алгоритм поиска подстроки в строке (naive algorithm). Алгоритм Рабина-Карпа (Rabin-Karp). Алгоритм Бойера-Мура (Boyer–Moore). Префиксная функция, алгоритм Кнута-Морриса-Пратта (Knuth–Morris–Pratt).
Элементы контроля
- Лабораторная работа - Сортировки
- Лабораторная работа - Структуры данных
- Лабораторная работа - Алгоритмы на графах
- Лабораторная работа - Алгоритмические парадигмы
- Лабораторная работа - Поиск в тексте
- Экзамен
- Активность на практических занятиях
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.1 * Лабораторная работа - Алгоритмические парадигмы + 0.1 * Лабораторная работа - Алгоритмы на графах + 0.1 * Лабораторная работа - Поиск в тексте + 0.1 * Лабораторная работа - Сортировки + 0.1 * Лабораторная работа - Структуры данных + 0.5 * Экзамен
Список литературы
Рекомендуемая основная литература
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
- Robert Sedgewick, & Kevin Wayne. (2014). Algorithms : Part I. [N.p.]: Addison-Wesley Professional. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1600534
- Седжвик Р. - Алгоритмы на С++ - Национальный Открытый Университет "ИНТУИТ" - 2016 - 1772с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100565
Рекомендуемая дополнительная литература
- Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613