Образовательная сессия по информатике

Обучение школьников по дополнительной образовательной программе «Информатика и программирование» будет способствовать реализации их потенциальных способностей в области информатики и информационных технологий. Большим стимулом для школьников является также участие в конкурсах и научно-практических конференциях, где они могут продемонстрировать результаты своего труда:

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

План

1 сессия (40 часов)

Входное тестирование (4 ч.)
Теория вычислимости (2 ч.)
Программирование для распределенных систем (8 ч.)
Теория сложности (2 ч.)
Функциональное программирование (8 ч.)
Методы трансляции (12 ч.)
Проектная и исследовательская работа (4 ч.)
2 сессия (40 часов)

Алгоритмы на строках (20 ч.)
Комбинаторная оптимизация (16 ч.)
Проектная и исследовательская работа (4 ч.)
3 сессия (40 часов)

Методы оптимизации задач динамического программирования (6 ч.)
Игры на графах (6 ч.)
Алгоритмы линейной алгебры и теории чисел (10 ч.)
Алгоритмы рекурсивного перебора (6 ч.)
Проектная и исследовательская работа (12 ч.)
4 сессия (40 часов)

Задачи на деревьях (12 ч.)
Матроиды (12 ч.)
Итоговое тестирование (4 ч.)
Проектная и исследовательская работа (12 ч.)

Цели

Подготовить школьников к участию в заключительных этапах Всероссийской олимпиады школьников, Всероссийской командной олимпиады школьников и в международных соревнованиях;
провести обзор разделов теоретической информатики, в том числе теории сложности, теории вычислимости, методов синтаксического разбора, параллельного программирования, функционального программирования;
изучить алгоритмы работы со строками, в том числе алгоритмы построения суффиксных структур данных: суффиксного массива, суффиксного дерева, суффиксного автомата, и научиться решать задачи с их использованием;
изучить алгоритмы комбинаторной оптимизации, в том числе алгоритмы построения максимального паросочетания, максимального потока и потока минимальной стоимости, научиться решать задачи с их использованием;
изучить динамическое программирование, методы оптимизации динамического программирования, в том числе трюк с выпуклой оболочкой, метод разделяй и властвуй,
изучить основы теории комбинаторных игр, теории Шпрага-Гранди и Смита, научиться решать задачи с их использованием;
изучить алгоритмы, связанные с линейной алгеброй и теорией чисел, в том числе алгоритм Гаусса, алгоритм факторизации многочленов, быстрые способы факторизации, быстрый алгоритм проверки на простоту, алгоритм быстрого преобразования Фурье, научиться решать задачи с их использованием;
изучить метод перебора с отсечением, связанные с ним методы рекурсивного перебора, метода ветвей и границ, применение методов для определения победителя в комбинаторных играх с оценкой позиции, использование альфа-бета отсечения, научиться решать задачи с их использованием;
изучить алгоритмы обработки деревьев, включая поиск наименьшего общего предка, решение задач на путях с использованием heavy-light декомпозиции;
изучить основы теории матроидов и ее применение для обоснования корректности жадных алгоритмов;
научиться реализовывать изученные методы и алгоритмы на практике, включая оценку трудоемкости реализации, владение стандартной библиотекой выбранного языка программирования, написание программы на выбранном языке программирования, проведение тестирования и отладки программы;
научиться определять тему задачи и подбирать необходимые методы решения, включая задачи на жадные алгоритмы, динамическое программирование, строковые алгоритмы, геометрические задачи, задачи на комбинаторику, задачи на алгоритмы на графах.
изучить навыки командной работы и взаимодействия на командной олимпиаде.

Ожидаемые результаты

В результате освоения образовательной программы школьники:

узнают о различных разделах информатики, актуальных проблемах и направлениях их решения;
получат опыт программирования многопроцессорных систем, функционального программирования, использования методов разбора;
узнают базовые понятия теории вычислимости и теории сложности;
научатся решать задачи с использованием алгоритмов на строках и суффиксных структур данных;
научатся решать задачи с использованием алгоритмов поиска максимального потока и потока минимальной стоимости,
научатся решать задачи с использованием динамического программирования и добиваться асимптотически лучшего времени работы с использованием методов оптимизации динамического программирования;
научатся решать задачи о комбинаторных играх на графах;
научатся решать задачи с использованием алгоритмов линейной алгебры и теории чисел;
научатся использовать перебор с отсечениями для решения задач;
научатся решать задачи на деревьях с использованием алгоритмов поиска наименьшего общего предка и heavy-light декомпозиции;
научатся применять теорию матроидов для обоснования применения жадных алгоритмов;
получат опыт реализации изложенных алгоритмов на выбранном языке программирования, тестирования и отладки программ;
получат опыт работы в команде, научатся организовывать взаимодействие на кома олимпиаде.

Длительность

6 дней

Стоимость

Бесплатно

Материально-техническая база

Для проведения практических занятий требуются компьютерные классы с доступом в Интернет, в том числе мобильные, оснащенные ноутбуками, подключаемыми к Интернету через сеть WI-FI. Количество компьютеров должно соответствовать количеству обучающихся. Для ряда теоретических занятий требуются помещения вместимостью до 100 человек, оборудованные стульями, маркерной доской с маркерами, проектором. Количество стульев должно соответствовать количеству обучающихся.