Расписание на 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. Решение задач сведения к задаче о построении максимального потока.
Лекция A: Динамика по профилю. Динамика по изломанному профилю. Трудные задачи на графы
Расписание на 7 ноября (вторник)
10.00–15.30 Личный практический тур (с перерывом на обед) сдача решений («одно окно») таблица результатов
16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция С: Рекурсия и динамическое программирование: разбор задач
Лекция B: Дерево интервалов. (Система непересекающихся множеств)
1) Дерево интервалов.
2) Дерево максимумов.
3) Дерево отрезков.
4) Быстрый подсчет площади объединения прямоугольников.
5) Другие примеры использования.
(Система непересекающихся множеств)
Лекция A: Производящие функции
1. Что такое производящие функции.
2. Степенные производящие функции.
3. Экспоненциальные производящие функции.
4. Примеры задач.
Расписание на 8 ноября (среда)
10.00–15.30 Командный практический тур (с перерывом на обед)
Легкий тур: сдача решений таблица результатов
Сложный тур: сдача решений таблица результатов
16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция С: Поиск кратчайших путей в графах
1. Поиск кратчайших путей во взвешенных графах.
2. Алгоритм Дейкстры
3. Восстановление пути
4. Примеры
5. Дополнение: использование кучи в Алгоритме дейкстры.
Лекция B: Декартово дерево. Бор
1. Декартово дерево
b. Описание свойств
c. Конкретная реализация операций
d. Напоследок: когда не хватает set, map STL
2. Бор
b. Простейшая реализация
c. Оптимизация предыдущего метода
d. Сжатый бор
e. Разбор задачи «Файловый менеджер» с Всероссийской олимпиады 2006
f. Применение не для строк
g. Построение суффиксного дерева с линейной памятью (?)
h. Вкратце о применении суффиксного дерева (?)
Лекция A: Алгоритмы проверки чисел на простоту и факторизации
1. Тест Соловея-Штрассена.
2. Тест Рабина-Миллера
Расписание на 9 ноября (четверг)
10.00–15.30 Личный практический тур (с перерывом на обед)
Легкий тур: сдача решений таблица результатов
Сложный тур: сдача решений таблица результатов
16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция C: Метод рекурсивного спуска
1. Задача о вычислении значения арифметического выражения
2. Формулы Бэкуса-Науэра для арифметического выражения
3. Написание программы методом рекурсивного спуска.
4. Обощения (отслеживание ошибок, вычисление логических выражений,
вычисление переменных, функций, возведение в степень).
5. Пара слов о синтаксическом разборе. Формализация понятия «число».
Лекция B: Геометрия
Вычислительная планиметрия. Векторы. Площадь. Полярный угол. Построение выпуклой оболочки – алгоритмы Грэхема, Джарвиса.
Лекция A: Минимальный разрез в графе
1. Минимальный s-t разрез в графе, связь с максимальным потоком
2. Постановка задачи, наивный алгоритм
3. Решение за O(n) поисков минимальных s-t разрезов
4. Алгоритм проталкивания предпотока, его выгодная модификация
5. Алгоритм поиска минимального разреза в графе
6. Временные оценки для различных реализаций