План сборов

Тур на простые задачи (4.5 часа)

A.	Цветные перестановки
B.	Дороги
C.	Симпатичные таблицы

Открытие сборов (0.5 часа)

Разбор задач семинара (1 час)

Лекция по LCA (для группы "П", 2 часа)

Лекторы: Станкевич Андрей Сергеевич, Митричев Петр Игоревич

План лекции

Постановка задачи
1. Частичный порядок на вершинах дерева
2. Определение наименьшего общего предка
3. Требуемые сложности алгоритмов
Pre-order обход дерева, свойства
Полное бинарное дерево
1. Определение, основные свойства
2. Нахождение LCA в полном бинарном дереве
Отображение I
1. Определение, основные свойства
2. Построенение отображения I на этапе предобработки
3. Полосы: определение, свойства
Реализация обработки запроса
Алгоритм Шибера-Вишкина
Задача RMQ
1. Сведение задачи LCA к задачи RMQ
2. Решение задачи RMQ со сложностью <N log(N), 1>
3. Решение задачи RMQ со сложностью <N log(log(N)), 1>
4. Решение задачи RMQ со сложностью <N log*(N), log*(N)>
Алгоритм Фарака-Колтона, Бендера
1. Решение задачи RMQ для последовательностей высот вершин в pre-order обходе за <N, 1>
2. Декартово дерево: определение, основные свойства
3. Построение декартова дерева за O(N^2)
4. Сведение RMQ к LCA: построение декартова дерева за O(N)

Задания

1.	Докажите однозначность отображения I в алгоритме Шибера-Вишкина
2.	Докажите монотонность отображения I в алгоритме Шибера-Вишкина
3.	Придумайте способ реализации битовых операций на арифметической машине для алгоритма Шибера-Вишкина. Ваша реализация должна осуществлять предобработку за время и память O(n), после чего выполнять операцию XOR для log N-битных чисел за время O(1)

Рекомендуемая литература

Строки, деревья и последовательности в алгоритмах. Гасфилд Д.
The LCA Problem Revisited Michael A. Bender, Matrin Farach-Colton

Введение в алгоритмы на графах (для группы "И", 2 часа)

Лектор: Матюхин Виктор Александрович

План лекции

Оценка сложности алгоритмов
1. O символика
2. Цепочка стандартных сложностей
Виды графов
1. Ориентированный граф
2. Неориентированный граф
3. Петли
4. Кратные ребра
5. Цикл
6. Дерево
7. Связные графы
8. Взвешенный граф
Способы представления графов
1. Матрица смежности
2. Матрица инцидентности
3. Список ребер
4. Списки ребер, инцидентных вершине
5. Неявный
Стандартные алгоритмы на графах
1. Обход в ширину
2. Обход в глубину
3. Проверка на двудольность
4. Топологическая сортировка
Нахождение кратчайших путей во взвешенных графах
1. Алгоритм Дейкстры
2. Алгоритм Флойда
3. Алгоритм Форда-Беллмана
4. Функция высоты и изменение весов ребер с сохранением кратчайшего пути
5. Алгоритм Джонсона
Нахождение минимального остовного дерева
1. Алгоритм Прима
2. Связь алгоритмов Прима и Дейкстры
3. Алгоритм Краскала
Эйлеров цикл, алгоритм Флёри
NP-полные задачи на графах
1. Гамильтонов путь (HAM)
2. Задача коммивояжера
3. Максимальная клика (MAX-CLIQUE)
4. Минимальное вершинное покрытие (MIN-COVER)
5. Раскраска графа в 3 цвета (3-COL)
Планарность графа
1. Гомеоморфизм графов
2. Графы K(5) и K(3,3), критерий Куратовского
3. Формула Эйлера для планарных графов

Задания

4.	Докажите экспоненциальность модификации алгоритма Дейкстры для случая отрицательных весов

Рекомендуемая литература

Алгоритмы: построение и анализ. Кормен Т., Лейзерсон Ч., Ривест Р.
Комбинаторика для программистов. Липский В.
Лекции по теории графов. Емеличев В., Мельников О., Сарванов В., Тышкевич Р.

День 3 (23.06.03)

Тур на стандартные алгоритмы на графах (3 часа)

A.	Странная игра
B.	Центры в дереве
C.	Строим граф
D.	Почтальон

Структуры данных (1.5 часа)

Лектор: Станкевич Андрей Сергеевич

План лекции

Решение задачи RMQ со сложностью <N log(N), 1>
Решение задач RMQ и RSQ с изменением ключей с помощью дерева отрезков, сложность <N, log(N)>
Решение задачи RSQ с изменением ключей с помощью дерева Фенвика, сложность <N log(N), log(N)>
Система непересекающихся множеств

Задания

5.	Приведите реализацию процедур изменения ключа и подсчета частичных сумм для дерева Фенвика. Докажите корректность построения.

Рекомендуемая литература

Алгоритмы: построение и анализ. Кормен Т., Лейзерсон Ч., Ривест Р.

Тур на разные темы (4 часа)

E.	Matrix Unloaded 2
F.	Выпуклая оболочка
G.	Покраска забора

День 4 (24.06.03)

Теория потоков, паросочетаний и назначений (часть I) (4 часа)

Лекторы: Станкевич Андрей Сергеевич, Бабенко Максим Александрович

План лекции

Построение максимального потока
1. Постановка задачи: определения сети, потока, максимального потока
2. Остаточная сеть, дополняющие пути
3. Разрезы, их свойства
4. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе, разрез, порожденный максимальным потоком
5. Алгоритм Форда-Фалксерсона
6. Градиентная модификация алгоритма Форда-Фалкерсона
7. Алгоритм Эдмондса-Карпа
Паросочетания в двудольных графах
1. Постановка задачи: определения двудольного графа, паросочетания, максимального паросочетания
2. Эквивалентность задачи о максимальном паросочетании и задачи о максимальном потоке в сети специального вида
3. Использование алгоритма Форда-Фалкерсона для нахождения максимального паросочетания
4. Вершинное покрытие: определение, нижняя оценка мощности
5. Теорема о равенстве мощности наибольшего паросочетания и минимального вершинного покрытия, построение минимального вершинного покрытия
6. Теорема Холла
7. Лемма об оценке числа дополняющих путей
8. Алгоритм Хопкрофта-Карпа
9. Алгоритм Куна
Задача о назначениях
1. Матричная и графовая формулировка задачи о назначениях
2. Элементарные преобразования матрицы весов
3. Общая структура венгерского алгоритма: фазы, итерации
4. Преобразование Эгервари
5. Оценка числа фаз и итераций в фазе
6. Оценка сложности одной итерации
7. Потенциалы, ускорение итерации в венгерском алгоритме
8. Оценка O(N^3) сложности венгерского алгоритма

Задания

6.	Постройте пример сети и последовательности дополняющих путей для алгоритма Форда-Фалкерсона, при использовании которых поток не сходится к максимальному
7.	Докажите леммы об неубывании расстояния до источника в алгоритме Эдмондса-Карпа и о строгом возрастании расстояния в алгоритме Хопкрофта-Карпа
8.	Докажите теорему Холла
9.	Докажите корректность алгоритма Куна

Рекомендуемая литература

Лекции по теории графов. Емеличев В., Мельников О., Сарванов В., Тышкевич Р.
Дискретный анализ. Романовский И.
Комбинаторика для программистов. Липский В.
Алгебраические основы теории дискретных систем. Богомолов А., Салий В.
Notes for the course advanced algorithms Johad Hastad
Combinatorial Optimization Lecture Notes Andrew V. Goldberg
Notes for the course advanced algorithms Johad Hastad
A New Approach to the Maximum-Flow Problem Andrew V. Goldberg, Robert E. Tarjan

Тур на теорию потоков и паросочетаний (4.5 часа)

A.	Предприятие переезжает
B.	День пограничника
C.	Равномерный поток

День 5 (25.06.03)

Семинар по теме "Графы" (3 часа)

Тур на структуры данных (4.5 часа)

A.	Парковка
B.	Мэры
C.	Ломаная

Разбор задач семинара по теме "Графы" (1 час)

Задания

10.	Доказать теорему о фундаментальном множестве циклов

День 6 (26.06.03)

Лекция по теории автоматов, грамматик и синтаксическому разбору (2 часа)

Лектор: Матюхин Виктор Александрович

План лекции

Конечные автоматы
1. Определение детерминированного конечного автомата (DFA)
2. Автомат, распознающий язык
3. Определение и примеры регулярных языков
4. Недетерминированный конечный автомат (NFA)
5. Детерминизация NFA
Операции над автоматами
1. Регулярность дополнения к регулярному языку
2. Регулярность конкатенации двух регулярных языков
3. Регулярность итерации регулярного языка
4. Регулярность объединения двух регулярных языков
5. Регулярность пересечения двух регулярных языков
6. Распознавание эквивалентности автоматов
Минимизация автомата
1. Удаление недоcтижимых вершин
2. Создание одного стока
3. Определение остаточного языка
4. Эквивалентность состояний
5. Склейка эквивалентных состояний
6. Невозможность дальнейшего уменьшения минимизированного автомата
7. Различимость состояний экспериментом длины не более N
8. Лемма о разрастании
9. Нерегулярность языка O^n 1^n
10. Незамкнутость класса регулярных языков относительно взятия подмножества
Грамматики
1. Определение грамматики, продукции, язык, задаваемый грамматикой, примеры
2. Контекстно-свободные грамматики
3. Правосторонние грамматики
4. Регулярность правосторонних грамматик
5. Эквивалентность правосторонних грамматик и автоматов
Регулярные выражения
1. Определение регулярных выражений
2. Регулярность регулярных языков
3. Эквивалентность регулярных выражений и автоматов (без доказательства)
Разбор арифметических выражений
1. Разбор регулярных языков
2. Выделение лексем
3. Формулы Бэкуса-Наура для арифметических выражений
4. Написание программы методом рекурсивного спуска

Задания

11.

Докажите или опровергните утверждение о регулярности языка правильных скобочных последовательностей

12.

Докажите лемму о разрастании для КС-грамматик: для любой грамматки существует постоянная N, такая что любую строку длины больше N соответствующего языка можно представить в виде uvxyz, где |vxy| < N, |vy| > 0, и при этом всякая строка вида u v^k x y^k z также принадлежит языку

Рекомендуемая литература

Введение в теорию автоматов, языков и вычислений Хопкрофт Дж., Мотвани Р., Ульман Дж.
Программирование: теоремы и задачи. Шень А.
Алгебраические основы теории дискретных систем. Богомолов А., Салий В.

Тур на теорию конечных автоматов и другие темы (5.5 часов)

A.	Левая грамматика
B.	Синхрограф
C.	Дороги в королевстве

День 7 (27.06.03)

Тур на разные темы (4.5 часа)

A.	Игра "О'Макс!"
B.	Склейка
C.	Гора

Теория потоков, паросочетаний и назначений (часть II) (1 час)

Лектор: Станкевич Андрей Сергеевич

План лекции

Сведение задачи о назначениях к задаче о кратчайшем пути
1. Лемма о паросочетаниях наименьшей стоимости
2. Решение задачи о назначениях с помощью обращения ребер вдоль цепи наименьшего веса
3. Метод потенциалов Джонсона
4. Решение задачи о назначениях с помощью алгоритма Дейкстры

Рекомендуемая литература

Notes for the course advanced algorithms Johad Hastad

Разбор задач прошедших туров (2 часа)

Задания

13.

Докажите, что наименьшее число отождествелений пар вершин, которое необходимо сделать, чтобы орграф стал сильно связанным равно максимуму из мощностей базы и антибазы минус 1 тогда и только тогда, когда каждая компонента связности графа представляет собой сильно связанный граф

14.

Приведите способ за O(M) превратить граф в лес последовательным исключением циклов

День 8 (28.06.03)

Тур по задачам IOI'2001 (4 часа)

A.	Склад
B.	Double Crypt
C.	Twofive

Точное решение игровых задач (1 час)

Лектор: Станкевич Андрей Сергеевич

План лекции

Разбор задачи 'Игра "О'Макс"
1. Общий способ решения игровых задач на ациклических графах
2. Нумерация состояний игры
Алгоритм для случая графов с циклами

Практика по игровым задачам (1.5 часа)

D.	Игра "ё-Макс"

День 9 (29.06.03)

Тур по комбинаторике и другим темам (3.5 часа)

A.	Матрицы
B.	C из N по K
C.	Скобочки

О нормах поведения российской сборной за рубежом (1 час)

Лектор: Цветкова Марина Серафимовна

Свободное время (3.5 часа)

День 10 (30.06.03)

Тур на сложные задачи (5 часов)

A.	Раздолбанная клавиатура
B.	Квадрирование
C.	Игра на заборе

Введение в комбинаторику

Лектор: Мирзаянов Михаил Расихович

План лекции

Перестановки
1. Определение перестановки, их количество
2. Формула Стирлинга
3. Степень, с которой заданное простое число P входит в разложение N!
4. Определение инверсии, таблица инверсий, взаимно-однозначное соответствие между перестановками и таблицами инверсий
5. Граф перестановки, разложение перестановки в циклы за линейное время, порядок перестановки
6. Четность перестановки
7. Транспозиции, их нечетность
8. Определение четности перестановки за линейное время
9. Неразрешимость половины начальных перестановок в игре "пятнашки"
10. Генерирование всех перестановок, генерирование с минимальным количеством транспозиций
11. Произведение перестановок, обратная перестановка
12. Симметрическая группа перестановок, решение "линейных" уравнений вида AX = Y в перестановках
Сочетания, числа сочетаний
1. Сочетание, число сочетаний. Симметрия биномиальных коэффициентов. Факториальная формула. Треугольник Паскаля, обоснование.
2. Бином Ньютона, его следствия
3. Свертка биномиальных коэффициентов (формула Коши-Вандермонда)
4. Быстрое вычисление биномиального коэффициента
5. Задача разбиения множества на подмножества заданной мощности
6. Сочетания с повторениями, выражение через биномиальный коэффициент
7. Порядок роста среднего биномиального коэффициента
Числа Каталана
1. Формулировка задачи, рекуррентное соотношение
2. Другие задачи на числа Каталана
3. Замкнутое выражение для чисел Каталана
Комбинаторная лемма Бернсайда
1. Группа, теорема Лагранжа
2. Группа преобразований на множестве. Примеры
3. Действие группы на множестве, орбиты, число орбит
4. Лемма Бернсайда, доказательство. Пример

Задания

15.	Выведите замкнутое выражение для чисел Фусса-Каталана порядка 3
16.	Выведите замкнутое выражение для чисел Фусса-Каталана порядка M

День 11 (01.07.03)

Тур на сложные задачи (5 часов)

A.	Орлы и дятлы
B.	Хитрый министр
C.	Ромбы

О целях участия в сборах и олимпиадах по информатике (0.5 часа)

Лектор: Матюхин Виктор Александрович

Суффиксные массивы (1.5 часа)

Лектор: Бабенко Максим Александрович

План лекции

Постановка задачи, ожидаемые сложности алгоритмов
Поиск подстроки: наивная реализация, оценка времени работы
Первое ускорение: функция "наибольший общий префикс" (lcp), основные свойства
Окончательный алгоритм поиска, оценка количества требуемых пар lcp
Общая схема алгоритма: фазы построения суффиксного массива
Цифровая сортировка (radix sort), применение
Модификации основного алгоритма построения суффиксного массива, метод вычисления lcp для пар "несоседних" строк

Рекомендуемая литература

Строки, деревья и последовательности в алгоритмах. Гасфилд Д.
Suffix arrays: a new method for on-line string searches Udi Manber, Gene Myers

День 12 (02.07.03)

Тур на сложные задачи (5 часов)

A.	Палиндромы
B.	Коровы
C.	Инволюции

Консультация и подготовка к экзамену (4 часа)

День 13 (03.07.03)

Экзамен (3 часа)