Факультатив «Спортивное программирование и Алгоритмы»

Цели:

Подготовка абитуриентов и студентов ХАИ к различным соревнованиям и олимпиадам по программированию, повышение уровня практической алгоритмической подготовки молодых программистов, преподавание фундаментальной теоретической подготовки в алгоритмах на уровне лучших вузов США и Европы.

Список потенциальных соревнований:

  1. Международная студенческая олимпиада «ACM ICPC», http://icpc.baylor.edu
  2. Международная открытая студенческая олимпиада по программированию им. С.А. Лебедева и В.М. Глушкова «KPI-Open», http://kpi-open.org
  3. Открытый Кубок имени Е.В. Панкратьева по программированию, http://www.opencup.ru
  4. Зимняя школа по программированию, ХНУРЭ, http://wschool.kharkov.ua
  5. Марафоны и другие соревнования на TopCoder, http://topcoder.com/tc
  6. Индивидуальные турниры как "Google Code Jam", http://code.google.com/codejam/
  7. Открытый чемпионат Харькова по спортивному программированию, http://khcup.qbit.org.ua

Формат:

  1. Еженедельная лекционная встреча с разбором тематического домашнего задания. Лекции могут чередоваться с семинарами, на которых студенты представляют свои решения (реализации) и результаты.
  2. Домашние задания могут включать решение алгоритмических задач, математические доказательства, поиск соответствующей литературы и программирование заданий с «online judge»-ресурсов как http://acm.timus.ru, http://uva.onlinejudge.org и других.
  3. Практическое соревнование раз в две недели. Студенты организовываются в группы до 3-х человек и соревнуются на базе архивов как http://codeforces.com, https://icpcarchive.ecs.baylor.edu и других. 
  4. Ежемесячный индивидуальный проект в виде поиска интересной задачи с олимпиадных архивов и сборников решений, ее презентация перед классом, включающая анализ и сравнение вариантов решения.

Руководители:

  1. Старов Алексей Александрович – онлайн руководитель (подготовка лекций и тренировочных материалов, разбор решений, ежемесячные удаленные презентации).
  2. Русин Дмитрий Олегович – онсайт руководитель (проведение встреч на базе ХАИ, организация учебного процесса, помощь в лекциях и решениях).

План рассматриваемых тем:

  1. Вступление в спортивное программирование, примеры различных олимпиадных задач, связь алгоритмов с практическим программированием
  2. Классификация олимпиадных задач с примерами, необходимые разделы математики для повторения – 2 занятия
  3. Понятие сложности алгоритмов, O-нотация и другие.
  4. Алгебра и теория чисел (от Решета Эратосфена до Длинной арифметики) – минимум 3 лекции
  5. Парадигма «Разделяй-и-властвуй», практическое применение – минимум 3 лекции
  6. Простые алгоритмы на Графах – минимум 2 лекции
  7. Приложение алгоритмов на Графах – минимум 2 занятия
  8. Потоки в теории Графов и олимпиадных задачах
  9. Примеры сложных алгоритмов на Графах (RMQ, Венгерский алгоритм и другие)
  10. Задача поиска с точки зрения Искусственного интеллекта и теории Игр – минимум 2 лекции
  11. Жадные алгоритмы
  12. Парадигма «Динамическое программирование» - минимум 3 занятия
  13. Вступление в комбинаторику
  14. Основы вычислительной геометрии– минимум 2 занятия
  15. Более сложные алгоритмические задачи
  16. Численные методы
  17. Строки и последовательности – минимум 2 занятия
  18. Умные структуры данных – минимум 3 занятия
  19. NP-полнота и как с этим бороться
  20. Обзор программистских трюков

Данные темы будут рассматриваться в пересечении, а полный цикл – итеративно повторятся углубляясь в теорию и сложность. Очень важно, что бы у начинающего олимпиадника знания и опыт развивались параллельно в каждом направлении. Список тем не финальный (от некоторых в течении года придется отказаться, а другие добавить, некоторым сократить часы и наоборот).

Литература:

  1. Алгоритмы. Построение и анализ – Кормен Т., Лейзерсон Ч., Ривест Р.
  2. Алготимы на C++ / Алгоритмы на Java – Седжвик Р.
  3. Олимпиадные задачи по программированию / Алгоритмы. Руководство по разработке – Скиена С.
  4. Алгоритмы и программы. Решение олимпиадных задач – Порублев И.Н., Cтавровский А.Б.
  5. Материалы Зимней школы по программированию ХНУРЭ.
  6. Алгоритмы ХАИ http://ostarov.github.io/Algorithms_KhAI/

Данный список книг является только базовым и будет значительно расширен в ходе занятий.