"Продвинутые" алгоритмы для школьников
В курсе рассказывается о "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматриваются вопросы сортировки, поиски в ширину и глубину, алгоритмы на графах, динамическое программирование. Демонстрируются алгоритмы работы с графическими объектами, отрезками и строками.

Лекция 1 Сортировки
Рассматриваются вопросы сортировки: быстрая, сортировка слиянием, устойчивость сортировки, цифровая сортировка. Списки, операции с элементами массива

Введение
Сортировки
Быстрая сортировка
Сортировка слиянием
Устойчивость сортировка
Подсчет числа инверсий
Сортировка подсчетом
Цифровая сортировка
Списки
Операции с элементами массива

Лекция 2 Поиск в ширину
В лекции даются алгоритмы поиска в ширину. Рассматриваются подвешенные и двоичные деревья. Дается пример решения задачи нахождения самого длинного пути

Введение
Поиск в ширину
Деревья
Подвешенное дерево
Двоичное дерево
Задача нахождения самого длинного пути

Лекция 3 Графы. Задача максимальных или минимальных остовных деревьев
Дается алгоритм поиска минимального остовного дерева. Алгоритм Прима. Рассматриваются другие алгоритмы нахождения минимального остовного дерева

Введение
Поиск минимального остовного дерева
Алгоритм Прима
Хип
Удаление минимума
Уменьшение значений эелементов
Другой алгоритм нахождения минимального остовного дерева

Лекция 4 Матрицы. Поиск кратчайших путей в графах
Матрицы и операции с ними. Числа Фибоначчи. Дается алгоритм поиска кратчайших путей в графах. Алгоритм Форда-Беллмана. Алгоритм Флойда.

Введение
Матрицы
Умножение матриц
Числа Фибоначчи
Поиск кратчайших путей в графах
Алгоритм поиска кратчайшех путей в графах
Хип
Отрицательные ребра
Алгоритм Форда-Беллмана
Алгоритм Флойда
Сводка по алгоритмам

Лекция 5 Поиск в глубину и его применение
В лекции рассматриваются Эйлеровы циклы и Эйлеровы пути. Поиск в глубину. Неориентированные графы.

Введение
Эйлеровы циклы и Эйлеровы пути
Эйлеровы циклы
Эйлеров путь
Применение поиска в глубина
Топологическая сортировка
Нахождение компонентов сильной связанности
Неориентированные графы
Компоненты связанности
Компоненты реберной двусвязанности
Точки сочленения

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

Введение
Независимые множества. Паросочетания. Вершинные покрытия.
Определения
Проверка графа на двудольность
Связь независимых множеств и вершинных покрытий
Сочетание минимальных вершинных покрытий и максимальных паросочетаний
Поиск максимального паросочетания
Связь между паросочетаниями и вершинными покрытиями
Алгоритм Куна
Заключение
Ответы на вопросы

Лекция 7 Динамическое программирование
В данной лекции дается сравнение динамического программирования с перебором. Даются примеры решения различных задач с применением динамического программирования

Введение
Сравнение динамического программирования с перебором
Классический пример с числами Фибоначчи
Задачи
Задача получения суммы S из набора n монет
Задача вывода k-ой 0-1 последовательности
Заключение

Лекция 8: Простейшие геометрические объекты
В лекции даются определения простейших геометрических объектов, операции с ними. Рассматриваются примеры пересечения прямых. Окружности.

Введение
Определения и операции с простейшими геометрическими объектами
Точка
Вектор
Прямые, способы задания
Нормаль
Уравнение прямой
Векторы. Операции с векторами
Изменение способов задания прямых
Пересечение прямых
Способы пересечения прямых
Пример пересечения прямых
Рассчет расстояния от точки до прямой
Окружности

Лекция 9: Строки
Даются определения, рассматривается алгоритм Кнута-Морриса-Пратта. Бор: Базовые операции. Хэш.

Введение
Определения
Префикс строки
Суффикс строки
Подстрока
Задачи и алгоритмы
Алгоритм Кнута-Морриса-Пратта
Полный код КМП
Z-функция
Бор
Определение
Базовые операции
Хэш

Лекция 10 Отрезки
Рассматриваются задачи на отрезках, операции при наличии обновлений на отрезке, построение дерева отрезков, подсчет суммы чисел на отрезке

Введение
Построение выпуклой оболочки
Отрезки
Задачи на отрезках
Операции при наличии обновлений на отрезке
Построение дерево отрезков
Сумма чисел на отрезке
Задача

Лекция 11 Задачи на отрезках
Рассматриваются задачи на отрезках, построение дерева отрезков, подсчет сумм чисел на отрезке. Решение задач.

Введение
Построение выпуклой области
Отрезки. Задачи на отрезках
Операции при наличии обновлений на отрезке
Построение дерева отрезков
Подсчет суммы чисел на отрезке
Задача