«Алгоритмы. Олимпиадное программирование». Модуль 3.
Занятие 1. Вспомнить всё — 2!
Занятие 2. Основные понятия и формулы комбинаторики
- Правила суммы и произведения
- Формулы основных комбинаторных чисел
- Теоретические задачи
Занятие 3. Генерация комбинаторных объектов
- Универсальный алгоритм генерации всех заданных объектов
- Генерация следующей перестановки в лексикографическом порядке
- Генерация перестановки по номеру
- Генерация номера размещения по объекту
Занятие 4. Задачи динамического программирования I (НВП)
- Наибольшая возрастающая подпоследовательность
- Код на Java Вывод самой НВП
- Сложность алгоритма поиска и вывода НВП
Занятие 5. Динамическое программирование II (НОП)
Занятие 6. Задачи динамического программирования III (расстояние Левенштейна)
- Определение и применения
- Редакционное предписание
Занятие 7. Алгоритм Флойда-Уоршалла
- Взвешенные графы
- Описание алгоритма Рекуррентное соотношение
- Код алгоритма
- Восстановление ответа
- Циклы отрицательного веса
Занятие 8. Алгоритм Дейкстры
- Описание алгоритма
- Пример работы
- Код алгоритма
- Сложность алгоритма
- Вывод ответа
Занятие 9. Олимпиада
- Состав команды
- Подготовка к соревнованиям
- Стратегия и тактика поведения во время тура
- Рекомендации по процессу практического программирования олимпиадной задачи
- Как бороться со штрафным временем
- Как потратить последние 15 минут тура
- Как вести себя после тура
Занятие 10. Бинарный поиск
- Сложность метода
- Метод дихотомии
- Бинарный поиск по ответу
Занятие 11. Игры I. Ним
- Ограничения
- Выигрышные и проигрышные позиции
- Игра «Ним»
Занятие 12. Игры II. Сумма игр
- Постановка задачи
- Сведение любой игры к Ниму
- Функция Шпрага-Гранди для одной игры
- Функция Шпрага-Гранди для суммы игр
- Суммы игр «на практике»
- Реализация
Занятие 13. Геометрия. Основы
- Действительные числа
- Основные объекты
- Линейное взаиморасположение объектов
- Углы GeomVis
Занятие 14. Геометрия. Окружности и многоугольники
- Окружность
- Многоугольник
- Выпуклость многоугольника
- Площадь многоугольника
- GeomVis
Занятие 15. Выпуклая оболочка
- Наивный алгоритм
- Алгоритм Джарвиса
- Алгоритм Грэхэма
Занятие 16. Куча (HEAP)
- Устройство
- Реализация
- Пирамидальная сортировка
- Очередь с приоритетами
