2023
2022
2020
2019
2018
2017
2016
2015
Введение в алгоритмы.
Рекомендованная литература
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ. - подробный учебник, охватывающий весь курс и содержащий много дополнительных материалов
Р. Седжвик. Алгоритмы на C++. - подробный учебник, некоторые темы расписаны лучше чем в Кормене, некоторые хуже. Единственный минус учебника - код в нем написан на C++, но автор сопровождает каждый алгоритм очень подробными объяснениями.
С. Скиена. Алгоритмы. Руководство по разработке - Учебник хорош детальным изложением процесса приидумывания алгоритма и решения алгоритмических задач. Есть интересные примеры из практики самого автора. Из немногих минусов - довольно беглое знакомство со структурами данных.
С. Дасгупта, Х. Пападимитриу, У. Вазирани - Алгоритмы - краткий учебник, много материала по графам. Не содержит некоторых важных тем
Б. Миллер и Д. Рэнум. Problem Solving with Algorithms and Data Structures using python Онлайн-учебниик с примерами на Python оригинал, перевод.
Л. Лакман Макдауэлл. Карьера программиста. - Больше не учебник, а задачник. Но перед задачами есть короткие выжимки теории.
А. Бхаргава - Грокаем алгоритмы. - Краткий учебник, больше популяризация нежели реальный учебник. На оценку "отлично" его не хватит, но он поможет решить проблемы с пониманием некоторых тем
Д. Кнут - Искусство программирования (3 с половиной тома). - хорошая энциклопедия, как учебник - слишком трудно для большинства. Но если интересует конкретная тема - у Кнута она будет рассказана со всеми возможными подробностями.
Конспект лекций А.А. Миронова
В конспекте есть опечатки и неточности, в случае расхождения материала лекций, семинаров и конспекта - задавайте вопросы в чате.
Расписание семинаров
1. (1 сентября) Сложность алгоритма. Элементарные операции. Кэши и устройство современного компьютера. Параллелизация. Битовые операции. Массив.
Материалы: Семинар 1. Асимптотика | Семинар 1. Битовые операции и массив
Домашнее задание: в системе ejudge
Дедлайн: 18 сентября 23:59
2. (9 сентября) Динамический массив. Амортизационная сложность. Рекурсия. Бинарный поиск. Наивный бинарный поиск в строковом массиве. Стратегия: разделяй и властвуй.
Материалы: Семинар 2. Динамический массив, бинарный поиск, разделяй и властвуй Семинар 2. Амортизационный анализ
Домашнее задание: ejudge
3. (16 сентября) Сортированный массив. Сортировка слиянием. Быстрая сортировка. Partition. Рандомизированные алгоритмы. Поиск k-й порядковой статистики. Теорема о нижней ##границе сортировки. сравнениями.
Материалы: Презентация
Домашнее задание: ejudge
Дедлайн: 4 октября 23:58.
4. (23 сентября) Односвязный список. Двусвязный список. Понятие интерфейса. Стек. Реализация с помощью массива и связного списка. Очередь. Реализация с помощью списка и циклического массива. Задачи на стек и очередь.
Материалы: Презентация
Домашнее задание: ejudge
Дедлайн: 11 октября 23:57.
5. (29 сентября) Замена системной рекурсии стеком. Реализация быстрой сортировки (или другого алгоритма) с использованием стека без рекурсии. Min-Max стек. Задача на него. Задачи на рекурсию. Бэктрекинг.
Материалы: Презентация
Домашнее задание ejudge
Дедлайн: 19 октября 23:59.
6. (6 октября) Бинарные деревья. Бинарные деревья поиска. Сбалансированные деревья. Определение красно-черных деревьев. Поиск минимального и максимального элементов, поворот, обход дерева. Поиск Lowest common ancestor.
Материалы: Презентация
Домашнее задание: ejudge
Дедлайн: 25 октября 23:56.
8. (13 октября) Сортировка подсчетом. Бинарная куча. Сортировка кучей. Очередь с приоритетом. Префиксные суммы.
Материалы: Презентация
7. (20 октября) Имплементация ассоциативного массива с помощью дерева. Хэш-функция и требования к ней. Хэш-таблицы с [закрытой и] открытой адресацией. Задачи на хэш-таблицы. ##Фильтр Блума. Разобрать на примере задачи.
Материалы: Презентация
Домашнее задание: ejudge
Дедлайн: 9 ноября 23:59.
8. (27 октября) Контрольная работа по материалу первой части семестра
9. (3 ноября) Поиск в строке. Наивный алгоритм. Катящийся хэш, k-меры и палиндром. Префикс-функция. Алгоритм Кнута-Морриса-Пратта. Время работы алгоритма КМП. Конечные ##автоматы как концепт.
Материалы: Презентация
Домашнее задание: доступно по ссылке
Дедлайн: 21 ноября, 11:59.
11. (10 ноября) Конечный автомат для поиск одного паттерна. Нагруженное дерево. Ахо-Корасик. Суффиксные ссылки и хорошие суффиксные ссылки. Ахо-Корасик как конечный автомат.
Материалы: Презентация
Домашнее задание: будет слито со следуюшим домашним заданием.
12. (17 ноября) Суффиксный бор. Суффиксное дерево. Задачи на суффиксное дерево.
Материалы: Презентация
Домашнее задание: доступно по ссылке
Дедлайн: 14 декабря, 11:59
13. (24 ноября) Задача о существовании пути между двумя городами. Система непересекающихся множеств. Графы. Виды графов. Поиск в ширину, глубину. Поиск связной компоненты.
Материалы: Презентация
Домашнее задание в ejudge: объединено со следующими.
14. (1 декабря) Взвешенные графы. Поиск кратчайшего пути. Направленный ациклический граф (DAG). Динамическое программирование на DAG. Подсчет числа путей. Представление задачи как DAG и ее решение при помощи динамического программирования.
Материалы: Презентация
Домашнее задание в ejudge: доступно по ссылке
Дедлайн: 28 декабря, 11:59
15. (8 декабря) Графы без отрицательных ребер. Понятие жадного алгоритма. Простая задача на жадный алгоритм (размен монет) в различных системах. Очередь с приоритетом. Activity selection (задача о докладах на конференции). Алгоритм Крускала. Алгоритм Прима. Алгоритм Дейкстры. Код Хаффмана.
Материалы: Презентация
Материалы: Алгоритм Прима
Материалы: Алгоритм Крускала
Материалы: Задача о выборе докладов
16. (15 декабря) Неразрешимые задачи. Сложность по Колмогорову. Задача остановки. P-задачи. NP-полные задачи. Доказательство NP-полноты. Метод ветвей и границ.
17. (25 декабря) Контрольная работа по 2й части семестра.
18. (30 декабря) P-задачи. NP-полные задачи. Доказательство NP-полноты. Некоторые рандомизированные алгоритмы.
Материалы: Презентация