2023
2022
2021
2020
2018
2017
2016
2015
Семестр 5. Введение в алгоритмы
Там есть ошибки (до сих пор).
Рекомендованная литература
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ. - подробный учебник, охватывающий весь курс и содержащий много дополнительных материалов
Р. Седжвик. Алгоритмы на C++. - подробный учебник, некоторые темы расписаны лучше чем в Кормене, некоторые хуже. Единственный минус учебника - код в нем написан на C++, но автор сопровождает каждый алгоритм очень подробными объяснениями.
С. Скиена. Алгоритмы. Руководство по разработке - Учебник хорош детальным изложением процесса приидумывания алгоритма и решения алгоритмических задач. Есть интересные примеры из практики самого автора. Из немногих минусов - довольно беглое знакомство со структурами данных.
С. Дасгупта, Х. Пападимитриу, У. Вазирани - Алгоритмы - краткий учебник, много материала по графам. Не содержит некоторых важных тем
Б. Миллер и Д. Рэнум. Problem Solving with Algorithms and Data Structures using python Онлайн-учебниик с примерами на Python оригинал, перевод.
Л. Лакман Макдауэлл. Карьера программиста. - Больше не учебник, а задачник. Но перед задачами есть короткие выжимки теории.
А. Бхаргава - Грокаем алгоритмы. - Краткий учебник, больше популяризация нежели реальный учебник. На оценку "отлично" его не хватит, но он поможет решить проблемы с пониманием некоторых тем
Д. Кнут - Искусство программирования (3 с половиной тома). - хорошая энциклопедия, как учебник - слишком трудно для большинства. Но если интересует конкретная тема - у Кнута она будет рассказана со всеми возможными подробностями.
Расписание
- (3 сентября). Сложность алгоритма. Элементарные операции. Кэши и устройство современного компьютера. Параллелизация. Битовые операции. Массив.
- (10 сентября). Динамический массив. Амортизационная сложность. Рекурсия. Бинарный поиск. Модификации.
- (17 сентября). Сортированный массив. Сортировка слиянием. Быстрая сортировка. Partition. Поиск k-й порядковой статистики. Теорема о нижней границе сортировки. сравнениями. Сортировка подсчетом.
[ Семинар, презентация | ДЗ, ejudge | ДЗ, условие ] Дедлайн: 04.10.2021
- (24 сентября). Односвязный список. Двусвязный список. Стек. Очередь. Циклический массив. Замена системной рекурсии стеком. Задачи на стек.
- (1 октября). Разбор формул при помощи стека с приоритетом. Бинарные деревья. Бинарные деревья поиска. Рандомизированные алгоритмы. Рандомизированное дерево поиска.
[ ДЗ, условие | ejudge | Семинар, презентация ]
- (8 октября). Сбалансированные деревья. Красно-черные деревья. Хэш-функция и требования к ней. Хэш-таблицы - закрытая и [открытая] адресация. Фильтр Блума.
- (15 октября). Контрольная работа №1
- (22 октября). Поиск в строке. Наивный алгоритм. Алгоритм Рабина-Карпа. Префикс-функция. Кнут-Моррис-Пратт. Время работы алгоритма КМП.
[ Презентация | ДЗ, условие | ejudge ]
- (29 октября) Конечные автоматы. Недетерминированные автоматы. Нагруженное дерево. Ахо-Корасик. Суффиксные ссылки и хорошие суффиксные ссылки.
[ Семинар, презентация | ejudge ] Дедлайн: 23.11.2021
- (12 ноября) Суффиксный бор. Суффиксное дерево. Суффиксный массив.
[ Семинар, презентация | ejudge ] Дедлайн: 23.11.2021
(19 ноября) Графы. Виды графов. Поиск в ширину, глубину, поиск связной компоненты. [ Семинар, презентация ]
(26 ноября) Взвешенные графы. Поиск кратчайшего пути. Динамическое программирование на DAG. Подсчет числа путей. [ Семинар, презентация ]
(3 декабря) Понятие жадного алгоритма. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Проверка графа на наличие циклов отрицательного веса. Кодирование. Код Хаффмана. Лемпель-Зив. Лемпель-Зив-Велч. [ Семинар, презентация ] [ Условия дз ] [ ejudge ] Дедлайн: 24.12.2021
- (10 декабря) Контрольная работа №2
- (17 декабря) Неразрешимые задачи. Сложность по Колмогорову. Задача остановки. P-задачи. NP-полные задачи. Доказательство NP-полноты. Метод ветвей и границ.
- (24 декабря) Методы приближенного решения задач. Точные алгоритмы, дающие решение, отличающееся от оптимального не более чем на множитель. Монте-Карло алгоритмы. Генетические алгоритмы.