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