Расписание на 4 ноября (суббота)
10.00 Сбор участников, открытие сборов
10.30–16.00 Командный практический тур (с перерывом на обед)
сдача решений таблица результатов сдача решений таблица результатов 16.30–18.00 Лекции (все лекции читаются параллельно)
Лекция С: Как эффективно и без ошибок решать олимпиадные задачи по информатике
1. Порядок решения олимпиадной задачи во время тура
2. Оптимальное использование типов данных
3. Программистские ошибки и способы их контроля
4. Эффективное управление директивами компилятора
Лекция B: Инварианты. Введение в numbers. Динамическое программирование и метод деления пополам.
Понятие инварианта. Инвариант в математике. Математическая задача о вещественных числах.
Понятие инварианта а программировании на примере задачи поиска K максимальных элементов в массиве, K кратчайших путей в графе. Расширение понятия инварианта в программировании. Задача о наибольшем произведении (выбор трёх чисел из N) в терминах инвариантов. Инвариант как инструмент доказательного программирования.
Операция XOR. Инвариант в игре ним.
Метод динамического программирования как построение инварианта. Связь между инвариантом и функцией динамики на примере задачи «Покупка билетов». Задача о выборе подмножества элементов массива с максимальной суммой, в котором никакие два элемента не являются смежными.
Метод деления пополам. Минимальная теория, детали реализации. Задача «Провода».
Лекция A: LCS & LIS: advanced algorithms
1. Нахождение lcs за O(nm).
2. Алгоритм Хиршберга для нахождения lcs в линейной памяти, O(nm).
3. Нахождение lcs длины не менее k за O((k – n)m).
4. Нахождение lis за O(n\log n).
5. Нахождение lcs за O(r\log n).
Расписание на 5 ноября (воскресенье)
10.00–15.30 Личный практический тур (с перерывом на обед)
сдача решений таблица результатов сдача решений таблица результатов 16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция С: Динамическое программирование
1. Подсчет числа сочетаний: факториалы, рекурсия, динамическое программирование.
2. Общие принципы построения динамического программирования.
3. Основные применения динамического программирования:
б. Нахождение минимального (максимального) решения (задача на минимальную стоимость проезда на сетке).
- Позиционные игры (задача «Игра с датами»).
4. Задача «Банкомат».
5. «Рюкзак».
Лекция BС: Введение в геометрию
1. Координаты и векторы.
2. Ориентированная площадь.
3. Уравнения линий.
Лекция А: Приближение функций
1. Интерполяционные многочлены Лагранжа и Ньютона.
2. Вычисление многочлена Ньютона через разделенные разности.
3. Выбор узлов интерполяции для уменьшения погрешности.
4. Кусочная интерполяция. Сплайны – кубические, параболические.
Расписание на 6 ноября (понедельник)
10.00–15.30 командная олимпиада школьников (с перерывом на обед)
Легкий тур (по Кировской системе): сдача решений таблица результатов
Сложный тур (по системе ACM): сдача решений таблица результатов
16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция С: О пользе и вреде рекурсии
1. О вреде рекурсии ;)
2. О пользе рекурсии :)
3. Backtracking (Перебор с возвратом)
Лекция B: Максимальный поток и максимальное паросочетание
1. Максимальный поток.
б) сети с несколькими источниками и стоками.
в) алгоритм Форда-Фалкерсона.
г) алгоритм Эдмонса-Карпа.
2. Максимальное паросочетание.
б) сведение задачи о максимальном паросочетании в двудольном графе к задаче о нахождении максимального потока.
3. Решение задач сведения к задаче о построении максимального потока.