Факультатив «Спортивне програмування і Алгоритми»
Цілі:
Підготовка абітурієнтів і студентів ХАІ до різних змагань і олімпіад з програмування, підвищення рівня практичної алгоритмічної підготовки молодих програмістів, викладання фундаментальної теоретичної підготовки в алгоритмах на рівні кращих вузів США і Європи.
Список потенційних змагань:
- Міжнародна студентська олімпіада «ACM ICPC», http://icpc.baylor.edu
- Міжнародна відкрита студентська олімпіада з програмування ім. С.А. Лебедєва і В.М. Глушкова «KPI-Open», http://kpi-open.org
- Відкритий Кубок імені О.В. Панкратьєва з програмування, http://www.opencup.ru
- Зимова школа з програмування, ХНУРЕ, http://wschool.kharkov.ua
- Марафони та інші змагання на TopCoder, http://topcoder.com/tc
- Індивідуальні турніри як "Google Code Jam", http://code.google.com/codejam/
- Відкритий чемпіонат Харкова зі спортивного програмування, http://khcup.qbit.org.ua
Формат:
- Щотижнева лекційна зустріч з розбором тематичного домашнього завдання. Лекції можуть чергуватися з семінарами, на яких студенти представляють свої рішення (реалізації) і результати.
- Домашні завдання можуть включати рішення алгоритмічних задач, математичні докази, пошук відповідної літератури і програмування завдань з «online judge»-ресурсів як http://acm.timus.ru, http://uva.onlinejudge.org та інших.
- Практичне змагання раз в два тижні. Студенти організовуються в групи до 3-х чоловік і змагаються на базі архівів як http://codeforces.com, https://icpcarchive.ecs.baylor.edu та інших.
- Щомісячний індивідуальний проект у вигляді пошуку цікавої завдання з олімпіадних архівів і збірників рішень, її презентація перед класом, що включає аналіз і порівняння варіантів рішення.
Керівники:
- Старов Олексій Олександрович - онлайн керівник (підготовка лекцій і тренувальних матеріалів, розбір рішень, щомісячні віддалені презентації).
- Русин Дмитро Олегович - онсайт керівник (проведення зустрічей на базі ХАІ, організація навчального процесу, допомогу в лекціях і рішеннях).
План розглянутих тем:
- Вступ до спортивне програмування, приклади різних олімпіадних завдань, зв'язок алгоритмів з практичним програмуванням
- Класифікація олімпіадних завдань з прикладами, необхідні розділи математики для повторення - 2 заняття
- Поняття складності алгоритмів, O-нотація і інші.
- Алгебра і теорія чисел (від Решето Ератосфена до Довгої арифметики) - мінімум 3 лекції
- Парадигма «Розділяй-і-володарюй», практичне застосування - мінімум 3 лекції
- Прості алгоритми на графах - мінімум 2 лекції
- Додаток алгоритмів на графах - мінімум 2 заняття
- Потоки в теорії графів і олімпіадних задачах
- Приклади складних алгоритмів на графах (RMQ, Угорський алгоритм і інші)
- Завдання пошуку з точки зору Штучного інтелекту та теорії ігор - мінімум 2 лекції жадібні алгоритми
- Парадигма «Динамічне програмування» - мінімум 3 заняття
- Вступ до комбінаторики
- Основи обчислювальної геометріі- мінімум 2 заняття
- Більш складні алгоритмічні завдання
- Чисельні методи
- Рядки і послідовності - мінімум 2 заняття
- Розумні структури даних - мінімум 3 заняття
- NP-повнота і як з цим боротися
- Огляд програмістів трюків
Дані теми будуть розглядатися в перетині, а повний цикл - итеративно повторяться заглиблюючись в теорію і складність. Дуже важливо, що б у початківця олімпіадника знання і досвід розвивалися паралельно в кожному напрямку. Список тим не фінальний (від деяких протягом року доведеться відмовитися, а інші додати, деяким скоротити годинник і навпаки).
Література:
- Алгоритми. Побудова і аналіз - Кормен Т., Лейзерсон Ч., Ривест Р.
- Алготіми на C ++ / Алгоритми на Java - Седжвік Р.
- Олімпіадні завдання з програмування / Алгоритми. Керівництво по розробці - Скіена С.
- Алгоритми і програми. Рішення олімпіадних завдань - Порублев І.М., Cтавровскій А.Б.
- Матеріали Зимової школи з програмування ХНУРЕ.
- Алгоритми ХАІ http://ostarov.github.io/Algorithms_KhAI/
Даний список книг є тільки базовим і буде значно розширено в ході занять.