Расписание на 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. Временные оценки для различных реализаций
Расписание на 11 ноября (суббота)
10.00–15.30 Командный практический тур (с перерывом на обед)
сдача решений таблица результатов сдача решений таблица результатов 16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция C: Структуры данных – 1
1. Списки: представление в массиве, списки в динамической памяти; добавление, удаление, поиск элемента; двусвязные и кольцевые списки.
2. Стеки: реализация на массивах, реализация на списках.
3. Очереди: реализация на массиве (циклический буфер), на списках.
4. Деки
5. Бинарный поиск в отсортированном массиве
6. Поиск k-го по величине элемента в массиве
Лекция C++: Использование библиотеки STL
1. Основные контейнеры: vector, stack, queue, map, set, multiset, priority_queue, back(), front() и top()
2. Работа с map/set: count, find, operator [] для map, удаление элементов, использование итераторов, *begin() и *rbegin()
3. Строка и строковый поток: string::substr, istringstream, ostringstream
4. Основные алгоритмы: min/max/swap, sort, stable_sort, next_permutation / prev_permutation, min_element, max_element, reverse, copy, generate, generate_n, find, count, find_first_of, count_if, accumulate, inner_product, binary_search, lower_bound, equal_range
5. Хитрости: vector::reserve, container.swap
6. Полезные мелочи: копирование объектов и const references, #include-файлы, “>>", typedef, make_pair, typeof в GNU
Лекция A: Дерево Фенвика. RMQ, LCA
1. Дерево Фенвика
2. Двумерное дерево Фенвика
3. Метод сжатия координат
4. задача о Парковке
5. FIND_LESS_THAN на отрезке
6. RMQ <O(n*log n), O(1)>
7. LCA <O(n*log n), O(log n)>