Олимпиадное программирование модуль 3

“Алгоритмы. Олимпиадное программирование”. Модуль 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)

  • Устройство
  • Реализация
  • Пирамидальная сортировка
  • Очередь с приоритетами