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

2019/2020

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Кто читает:

Базовая кафедра группы компаний MERA (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс обязательный

Когда читается:

2-й курс, 1, 2 модуль

Преподаватель

Бычков Илья Сергеевич

Программа дисциплины

Аннотация

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

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

• Знакомство с существующими алгоритмами для решения различных задач
• Знакомство с существующими структурами данных и их основными операциями
• Получение навыков проектирования, анализа и тестирования алгоритмов

Планируемые результаты обучения

• Формулировать понятие алгоритма, программы.
• Формулировать понятие переменной, массива.
• Формулировать задачу сортировки
• Описывать и уметь реализовывать алгоритмы сортировки
• Доказывать оценки сложности алгоритмов сортировки
• Доказывать оценки сложности алгоритмов
• Формулировать понятия пространственной и временной сложности алгоритма.
• Определять сложность алгоритмов по их описанию
• Формулировать понятие асимптотической сложности алгоритма
• Различать классы сложности задач и алгоритмов
• Объяснять символику для обозначения сложности работы алгоритмов
• Формулировать понятия массива, связного списка, стека, очереди и их вариаций
• Объяснять и и уметь реализовывать основные операции с массивами, связными списками, стеками, очередями
• Доказывать сложность основных операций с массивами, связными списками, стеками, очередями
• Формулировать понятия очереди с приоритетом, системы непересекающихся множества, кучи, списков с пропусками
• Объяснять и уметь реализовывать основные операций для очереди с приоритетом, системы непересекающихся множества, кучи, списков с пропусками
• Доказывать сложность основных операций для очереди с приоритетом, системы непересекающихся множества, кучи, списков с пропусками
• Формулировать понятие хэширования, хэш-функции, хэш-таблицы
• Описывать алгоритмы построения и использования хэширования
• Оценивать сложность основных операций при хэшировании
• Формулировать понятие графа, представления графа;
• Описывать различные варианты построения и использования графовых моделей
• Объяснять и уметь реализовывать алгоритмы обхода графов
• Доказывать сложность алгоритмов обхода графов
• Формулировать задачи о кратчайших путях в различных постановках
• Описывать и уметь реализовывать алгоритмы поиска кратчайших путей
• Доказывать сложность алгоритмов поиска кратчайших путей
• Описывать работу метода разделяй и властвуй, алгоритмов динамического программирования и жадных алгоритмов
• Разрабатывать алгоритмы в соответствии с рассмотренными парадигмами для решения задач
• Формулировать задачи о поиске в тексте, поиске подстроки в строке
• Описывать и уметь реализовывать алгоритмы поиска в тексте
• Доказывать сложность алгоритмов поиска в тексте
• Формулировать задачи о поиске в тексте
• Описывать и уметь реализовывать суффиксные деревья
• Доказывать сложность операций с суффиксным деревом
• Формулировать понятие дерева и задачи, связанные с деревьями
• Описывать и уметь реализовывать алгоритмы для поиска минимального остовного дерева
• Доказывать оценки сложности алгоритмов для поиска минимального остовного дерева
• Формулировать задачу поиска
• Описывать и уметь реализовывать алгоритмы поиска
• Доказывать оценки сложности алгоритмов поиска

Содержание учебной дисциплины

• Введение в алгоритмы. Понятие алгоритма и программы. Переменные, массивы.
  Введение в алгоритмы. Понятие алгоритма и программы. Языки программирования. Структуры данных. Переменные, массивы.
• Алгоритмы поиска.
  Задача поиска объекта. Алгоритм линейного поиска (linear search). Алгоритм бинарного поиска (binary search). Алгоритм удваивающегося поиска (doubling search).
• Задача сортировки. Простые алгоритмы сортировки.
  Сортировка выбором (selection sort). Сортировка пузырьком (bubble sort). Сортировка вставками (insertion sort). Сортировка подсчётом (counting sort).
• Задача сортировки. Эффективные алгоритмы сортировки.
  Блочная сортировка (bucket sort). Сортировка слиянием (merge sort). Быстрая сортировка (quick sort). Поразрядная сортировка (radix sort). Timsort.
• Сложность алгоритмов.
  Понятие сложности алгоритмов. Временная сложность (time complexity). Пространственная сложность (space complexity). Оценка сложности алгоритмов.
• О-символика. Классы сложности.
  Асимптотическая сложность. О-символика. Классы сложности P и NP. Сводимость задач.
• Базовые структуры данных.
  Понятие структуры данных. Массив. Одномерный массив и многомерный массив. Связный список. Односвязный, двусвязный, кольцевой список. Стек. Очередь.
• Дополнительные структуры данных.
  Очередь с приоритетом (priority queue). Система непересекающихся множеств (disjoint sets). Куча (heap). Список с пропусками (skiplist).
• Хэширование.
  Понятие хэш-кода и хэширования (hashing). Хэш-функции (hash function). Структура данных хэш-таблица (hash table). Реализация словарей, множеств, отображений.
• Понятие графа. Алгоритмы на графах.
  Понятие графа. Представление графа в памяти компьютера. Матрица смежности (adjacency matrix). Список смежности (adjacency list). Матрица инцидентности (incidence matrix). Алгоритмы на графах. Обход графа в ширину (breadth first search). Обход графа в глубину (depth first search).
• Понятие дерева. Задача о построении минимального остовного дерева.
  Понятие дерева. Задача о построении минимального остовного дерева (minimum spanning tree). Алгоритм Краскала (Kruskal). Алгоритм Прима (Prim).
• Задачи о кратчайших путях. Алгоритмы нахождения кратчайших путей в графах.
  Задачи о кратчайших путях. Алгоритм Дейкстры (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).
• Строковые алгоритмы. Суффиксные деревья.
  Понятие суффиксного дерева (suffix tree). Алгоритмы построения суффиксных деревьев. Алгоритм Укконена (Ukkonen).

Элементы контроля

• Лабораторная работа - Сортировки
• Лабораторная работа - Базовые структуры данных
• Лабораторная работа - Дополнительные структуры данных
• Лабораторная работа - Графы
• Лабораторная работа - Строковые алгоритмы
• Экзамен - 1 модуль
• Экзамен - 2 модуль

Промежуточная аттестация

• Промежуточная аттестация (1 модуль)
  0.25 * Лабораторная работа - Базовые структуры данных + 0.25 * Лабораторная работа - Сортировки + 0.5 * Экзамен - 1 модуль
• Промежуточная аттестация (2 модуль)
  0.083 * Лабораторная работа - Графы + 0.083 * Лабораторная работа - Дополнительные структуры данных + 0.084 * Лабораторная работа - Строковые алгоритмы + 0.5 * Промежуточная аттестация (1 модуль) + 0.25 * Экзамен - 2 модуль

Список литературы

Рекомендуемая основная литература

• 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