Алгоритмы: построение и анализ
Курс посвящён теории алгоритмов и элементам дискретной математики. Основная цель курса - научиться эффективно решать алгоритмические задачи, вооружиться фундаментальными идеями и методами, выработать системный подход к решению алгоритмических задач.
Курс знакомит с классическими методами и задачами теории алгоритмов, а также важнейшими современными задачами информатики. Курс ориентирован на математиков и программистов, студентов 1-5 курсов, предполагающих активно использовать компьютеры для решения прикладных или теоретических задач.

Лекция 1 Жадный алгоритм
Лекция посвящена задачам, решаемым жадным алгоритмом. Приводится задача выбора подмножества из множества точек трехмерного пространства, задача нахождения максимальной системы линейно-независимых строк матрицы, задача из теории графов. Рассказывается об алгоритме Крускала, о структуре непересекающихся множеств, о системе представителей, о матроидах.

Введение
Жадный алгоритм
Задача выбора подсистемы точек общего положения максимального веса из множества точек стандартного трехмерного пространства
Симплекс
Задача нахождения максимальной (по весу) системы линейно-независимых строк матрицы A
Задача из теории графов
Алгоритм Крускала
Структура непересекающихся множеств
Постановка задачи
Система представителей
Реализация структуры
Создание алгоритма
Амортизированное время
Почему жадный алгоритм выбора линейно-независимой системы работает?
Изначальные утверждения
Доказательство правильности работы жадного алгоритма по шагам
Матроиды

Лекция 2 Задачи минимального покрывающего дерева и задачи с весовыми функциями
Лекция посвящена нескольким задачам: задаче минимального покрывающего дерева, задаче с двумя весовыми функциями на одном графе, задаче с одной весовой функцией и двумя покрывающими деревьями. В лекции рассказывается также об алгоритме Крускала и алгоритме Прима.

Введение
Задача минимального покрывающего дерева
Условие задачи
Минимальное покрывающее дерево
Доказательство утверждения, что самое легкое ребро графа содержится в каком-либо из минимальных покрывающих деревьев
Понятие разрезов в графе
Построение покрывающего дерева
Алгоритм Крускала
Вид
Почему этот алгоритм работает
Реализация алгоритма
Структура непересекающихся множеств
Сжатие путей
Распределение памяти и учетное время
Алгоритм Прима
Схема алгоритма
Аналогия с алгоритмом Дейкстры
Задача с двумя весовыми функциями на одном графе
Начальные условия и допущения
Обоснование утверждения, что если изменить веса всех ребер графа, сохраняя их отношения, то минимальные покрывающие деревья графа таковыми и останутся
Структура порядка и структура операции сложения
Задача с одной весовой фукцией и двумя минимальными покрывающими деревьями
Мощность множества

Лекция 3 Максимальный поток
Лекция посвящена вопросу максимального потока. В ней рассказывается о сети, о потоке, о величине потока, об определении максимального потока. Также, приводятся алгоритмы Форда-Фалкерсона и Эдмондса-Карпа. Кроме этого, даются задачи, использующие максимальный поток (задача о максимальном паросочетании и о минимальном контролирующем множестве).

Введение
Максимальный поток
Понятие сети
Что такое поток
Соотношение потока и пропускной способности ребра
Величина потока и ее определение
Задача определения максимального потока в заданной сети
Исходные данные
Обоснование нахождения в сети максимального потока
Доказательство того, что величина максимального потока равна величине минимального разреза
Алгоритм нахождения максимального потока для целых весов
Понятие остаточной сети
Нахождение положительного потока в остаточной сети
Алгоритм Форда-Фалкерсона
Доказательство того, что в любой (произвольной) сети найдется максимальный поток
Поиск пути в остаточной сети в ширину, алгоритм Эдмондса-Карпа
Задачи, использующие максимальный поток
Задача о максимальном паросочетании
Симметрическая разность двух множеств
Нахождение чередующейся цепи для двудольного графа
Время работы алгоритма
Задача о минимальном контролирующем множестве

Лекция 4 Общие подходы к задачам программирования
Лекция посвящена некоторым компьютерным играм и их программированию. Рассказывается также об общих подходах к задачам программирования, об основных используемых тегах, об альфа-бета отсечении и его особенностях.

Введение
Игра в шахматы ("middle game")
Постановка задачи
Реализация с помощью рекурсивной функции
Альфа-бета отсечение
Механизм отсечения
Упорядочивание ходов по эвристическому признаку
Кэширование вычисленного значения
Узкое окно, пристрелка
Преодоление эффекта горизонта
Общие подходы к задачам программирования
Полиномиальные алгоритмы
Эвристики - как рабочие моменты
Тег local
Тег macro
Тег scale
Теги meta, gready, competition
Задача организации подсказок
Задача "Эндшпиль"
Постановка задачи, входные и выходные данные
Пути решения
Динамическое программирование, тэги cache, reduce, decompose
Задача "Мосты"

Лекция 5 Задача о минимальном контролирующем множестве вершин и венгерский алгоритм
В лекции рассказывается о ходе решения задачи о минимальном контролирующем множестве вершин, а также о венгерском методе, его сути и недостатках. Кроме этого рассматривается венгерский алгоритм, его общая схема и частные случаи.

Введение
Задача о минимальном контролирующем множестве вершин
Постановка задачи
Ход решения
Мощность минимального контролирующего множества
Находим максимальное паросочетание
Отмечаем левые концы ребер в максимальном паросочетании
Запускаем цикл для каждой вершины
После переотметки вершин в новом графе отмеченные вершины будут образовывать контролирующее множество
Случай, если вершина несвободна
Время работы алгоритма
Венгерский метод
Задача о назначениях
Квадратная матрица
Нахождение максимального независимого подмножества с минимальным весом
Преобразование матрицы
Проведение аналогии с двудольным графом, в котором ребра соответствуют нулям матрицы
Находим контролирующее множество
Недостатки метода
Венгерский алгоритм
Общая схема
Рассмотрим первые несколько строк матрицы
Коллизия для двух строк матрицы и ее устранение
Коллизия и метод ее устранения в более общем случае
Вид алгоритма

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

Введение
Повторение основных формулировок
Исходная сеть
Переход к новой модели
Поток в сети
Остаточная сеть
Алгоритм Форда-Фалкерсона (поиски путей в остаточной сети)
Метод проталкивания предпотока
Исходные допущения и проблемы
Предпоток
Излишек в вершине
Переполненные вершины
Модифицирование предпотока и устранение переполненных вершин
Высотная функция
Условия корректности
Операция PUSH(проталкивания)
Операция LIFT(поднятия)
Алгоритм проталкивания предпотока
Замечания после остановки алгоритма
Почему же алгоритм остановится?
Замечания по операции LIFT
Замечания по операции PUSH
Время выполнения алгоритма
Операция DISCHARGE(обслуживание вершины)
Алгоритм "поднять-и-в начало" ("LIFT-TO-FRONT")

Лекция 7 Метод проталкивания предпотока и поиск образца в строке
В первой половине лекции заканчивается рассмотрение алгоритма проталкивания предпотока. Вторая половина лекции посвящена вопросу поиска подстрок в тексте. Рассматривается алгоритм Кнута-Морриса-Пратта, дается понятие префикса, суффикса, префикс-функции, а также решается задача ее нахождения.

Введение
Алгоритм "поднять-и-в начало" ("LIFT-TO-FRONT")
Работа алгоритма
Избавляемся от избытка для переполненных вершин (операция DISCHARGE)
Почему, когда алгоритм закончит работу, переполненных вершин не будет?
Обоснование утверждения, что в ходе алгоритма допустимые ребра всегда направлены направо
Время работы алгоритма
Поиск образца (подстроки) в строке (алгоритм Кнута — Морриса — Пратта)
Постановка задачи
Префикс и суффикс
Простейший алгоритм
Префикс-функция
Оптимизация поиска
Время работы алгоритма
Нахождение префикс-функции
Ход рассуждений
Написание кода
Время работы кода
Задача с применением алгоритма Кнута — Морриса — Пратта

Лекция 8 Суффиксные деревья
Лекция посвящена вопросам суффиксных деревьев. В ней рассказывается о конечном автомате, о суффиксных ссылках, о построении бора, структур суффиксных деревьев и структур с суффиксными ссылками.

Введение
Задача индексации набора строк
Исходные данные
Конечный автомат
Модификация алгоритма
Параметры алгоритма
Построение структуры
Оптимизация задачи, построение бора
Другой алгоритм построения структуры
Программная реализация хранения состояний, суффиксные ссылки
Построение структуры с суффиксными ссылками
Задача на построение бора
Задача "Антиплагиат-2"

Лекция 9 Суффиксные деревья и алгоритм Укконена
Лекция посвящена алгоритму Укконена. В ней еще раз напоминается, что такое суффиксный бор, суффиксное дерево, суффиксные ссылки, приводится алгоритм построения суффиксного бора, дается понятие конечной вершины и граничного пути. Рассматривается также, как построить суффиксное дерево, как выбрать явные и неявные вершины, дается понятие активной вершины. Кроме того, в лекции рассказывается о суффиксных массивах.

Введение
Суффиксный бор, суффиксное дерево
Построение суффиксного бора
Алгоритм построения суффиксного бора, суффиксные ссылки
Видоизменения алгоритма
Конечная вершина, граничный путь
Добавление вершины-пустышки
Построение суффиксного дерева
Явные и неявные вершины
Исходная ситуация
Рассмотрим все классы явных вершин
Проблемы с листьями
Модификации структуры
Активная вершина
Три этапа построения бора
Наращивание производительности
Листья
Явные и неявные вершины в суффиксном дереве
Рост и разбивка ребер
Суффиксные ссылки
Нахождение активной вершины
Комментарии к псевдокоду
Время работы алгоритма
Суффиксные массивы

Лекция 10 Нейтральные и конечные игры
Лекция посвящена вопросам создания алгоритма нейтральной конечной игры, суммы игр. В ней также рассказывается о цветных играх, о числах Конвея и их определении.

Введение
Игра "Ним"
Суть игры и постановка задачи
Построение графа игры
Конечность игры
Нейтральность игры
Нейтральные и конечные игры
Начальные условия для теоремы определения нимбера
Сумма игр
Запись игры Ним в двоичном виде, вычисление нимбера для этой игры и определение по нему статуса игроков (кто выиграет)
Значение нимбера для любой нейтральной конечной игры или суммы игр
Задача "Ромашка"
Другие примеры нейтральных конечных игр
Цветные игры
Какие игры называют "цветными"?
Числа Конвея
Задачи, которые можно решать с помощью суффиксного дерева

Лекция 11 Преобразование Фурье
Лекция посвящена преобразованию Фурье. В ней рассказывается об интерполяционном многочлене Лагранжа, о геометрической интерпретации умножения, о формуле Эйлера, о прямом и обратном преобразованиях Фурье.

Введение
Область применения
Алгоритм умножения, основанный на быстром преобразовании Фурье
Исходные данные
Интерполяционный многочлен Лагранжа
Выбор формы представления многочлена
Комлексные числа
Геометрическая интерпретация умножения
Формула Эйлера
Корни из единицы
Дискретное преобразование Фурье
Обратное дискретное преобразование Фурье
Выполнение прямого преобразования Фурье
Время работы алгоритма
Организация вычислений без комплексных чисел

Леции можно скачать отдельно!
Размер одной лекции: 210-270 МБ