2024
2023
2022
2021
2020
2019
2017
2016
Семестр 5. Введение в алгоритмы
Там есть ошибки (до сих пор).
Рекомендованная литература
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ. - подробный учебник, охватывающий весь курс и содержащий много дополнительных материалов
Р. Седжвик. Алгоритмы на C++. - подробный учебник, некоторые темы расписаны лучше чем в Кормене, некоторые хуже. Единственный минус учебника - код в нем написан на C++, но автор сопровождает каждый алгоритм очень подробными объяснениями.
С. Скиена. Алгоритмы. Руководство по разработке - Учебник хорош детальным изложением процесса приидумывания алгоритма и решения алгоритмических задач. Есть интересные примеры из практики самого автора. Из немногих минусов - довольно беглое знакомство со структурами данных.
С. Дасгупта, Х. Пападимитриу, У. Вазирани - Алгоритмы - краткий учебник, много материала по графам. Не содержит некоторых важных тем
Б. Миллер и Д. Рэнум. Problem Solving with Algorithms and Data Structures using python Онлайн-учебниик с примерами на Python оригинал, перевод.
Л. Лакман Макдауэлл. Карьера программиста. - Больше не учебник, а задачник. Но перед задачами есть короткие выжимки теории.
А. Бхаргава - Грокаем алгоритмы. - Краткий учебник, больше популяризация нежели реальный учебник. На оценку "отлично" его не хватит, но он поможет решить проблемы с пониманием некоторых тем
Д. Кнут - Искусство программирования (3 с половиной тома). - хорошая энциклопедия, как учебник - слишком трудно для большинства. Но если интересует конкретная тема - у Кнута она будет рассказана со всеми возможными подробностями.
Расписание
- Машина Тьюринга. Сложность алгоритма. Элементарные операции. Кэши и устройство современного компьютера. Параллелизация. Альтернативы сложности алгоритма для современных компьютеров.
[ Презентация | Задание ]
- Битовые операции. Массив. Динамический массив. Амортизационная сложность. Рекурсия. Бинарный поиск. Модификации (поиск левого крайнего, правого крайнего, поиск участка равных значений)
- Сортированный массив. Сортировка вставками. Сортировка слиянием. Быстрая сортировка. Partition. Поиск k-й порядковой статистики. Рандомизированные алгоритмы.
[ Презентация | ejudge ] Дедлайн по дз: 23:59 06.10.2020
- Сортировка подсчетом. Односвязный список. Двусвязный список. Стек. Очередь. [Стек с минимумом за O(1).] Циклический массив.
[ Презентация | ejudge ] Дедлайн по дз: 23:59 17.10.2020
- Замена системной рекурсии стеком. Разбор формул при помощи стека - без приоритета и с приоритетом. Бинарные деревья. Бинарные деревья поиска. Рандомизированное дерево поиска.
[ Презентация | Условия дз | ejudge ] Дедлайн по дз: 23:59 29.10.2020
- Сбалансированные деревья. Красно-черные деревья. Хэш-функция и требования к ней. Хэш-таблицы - закрытая и [открытая] адресация. Фильтр Блума.
[ Презентация, деревья | Презентация, хэш-таблицы | Домашнее задание | ejudge ] Дедлайн по дз: 23:59 04.11.2020
- Контрольная работа 1.
- Поиск в строке. Наивный алгоритм. Алгоритм Рабина-Карпа. Префикс-функция. Кнут-Моррис-Пратт. Время работы алгоритма КМП.
[ Презентация | Домашнее задание | ejudge ] Дедлайн по дз: 23:59 11.11.2020
- Конечные автоматы. [Построение суффикс функции за линейное время]. Недетерминированные автоматы.
[ Презентация, автоматы ] [ ejudge ] Дедлайн по дз: 23:59 22.11.2020
- Нагруженное дерево. Ахо-Корасик. Суффиксные ссылки и хорошие суффиксные ссылки.
[ Презентация, Ахо-Корасик, начало ] [ Презентация, Ахо-Корасик, продолжение ]
- Суффиксный массив. Суффиксный бор. Суффиксное дерево.
[ Презентация ] [ Домашнее задание ] Дедлайн. по дз: 23:59 06.12.2020 [ ejudge ]
- Контрольная работа 2.
- Графы. Виды графов. Поиск в ширину, глубину, поиск связной компоненты.
[ Презентация ]
- Взвешенные графы. Поиск кратчайшего пути. Динамическое программирование на DAG. Подсчет числа путей.
[ Презентация ] [ Условия ДЗ ] [ ejudge ]
- Понятие жадного алгоритма. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Проверка графа на наличие циклов отрицательного веса. Сложность по Колмогорову. Кодирование. Код Хаффмана. [Лемпель-Зив. Лемпель-Зив-Велч. Сети и потоки в них]
[ Презентация ] [ Условия ДЗ ] [ ejudge ]
- Контрольная работа 3.
- Неразрешимые задачи. P-задачи. NP-полные задачи. Доказательство NP-полноты. Метод ветвей и границ. [Методы приближенного решения задач. Точные алгоритмы, дающие решение, отличающееся от оптимального не более чем на множитель. Монте-Rарло алгоритмы. Генетические алгоритмы]