Результаты и условия задач

Программы лекций

4 ноября (суббота)

Лекция С: Как эффективно и без ошибок решать олимпиадные задачи по информатике

1. Порядок решения олимпиадной задачи во время тура
2. Оптимальное использование типов данных
3. Программистские ошибки и способы их контроля
4. Эффективное управление директивами компилятора

Лекция B: Инварианты. Введение в нимберсы. Динамическое программирование и метод деления пополам.

Понятие инварианта. Инвариант в математике. Математическая задача о вещественных числах.

Понятие инварианта а программировании на примере задачи поиска 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 ноября (воскресенье)

Лекция С: Динамическое программирование

1. Подсчет числа сочетаний: факториалы, рекурсия, динамическое программирование.
2. Общие принципы построения динамического программирования.
3. Основные применения динамического программирования:

4. Задача "Банкомат".
5. "Рюкзак".

Лекция BС: Введение в геометрию

1. Координаты и векторы.
2. Ориентированная площадь.
3. Уравнения линий.

Лекция А: Приближение функций

1. Интерполяционные многочлены Лагранжа и Ньютона.
2. Вычисление многочлена Ньютона через разделенные разности.
3. Выбор узлов интерполяции для уменьшения погрешности.
4. Кусочная интерполяция. Сплайны – кубические, параболические.

6 ноября (понедельник)

Лекция С: О пользе и вреде рекурсии

1. О вреде рекурсии ;)
2. О пользе рекурсии :)
3. Backtracking (Перебор с возвратом)

Лекция B: Максимальный поток и максимальное паросочетание

1. Максимальный поток.

2. Максимальное паросочетание.

3. Решение задач сведения к задаче о построении максимального потока.

Лекция A: Динамика по профилю. Динамика по изломанному профилю. Трудные задачи на графы

7 ноября (вторник)

10.00-15.30 Личный практический тур (с перерывом на обед) сдача решений ("одно окно") таблица результатов

16.00-17.30 Лекции (все лекции читаются параллельно)

Лекция С: Рекурсия и динамическое программирование

1. Разбор задач прошедшего тура.

Лекция B: Дерево интервалов. (Система непересекающихся множеств)

1. Дерево интервалов.
2. Дерево максимумов.
3. Дерево отрезков.
4. Быстрый подсчет площади объединения прямоугольников.
5. Другие примеры использования.
(Система непересекающихся множеств)

Лекция A: Производящие функции

1. Что такое производящие функции.
2. Степенные производящие функции.
3. Экспоненциальные производящие функции.
4. Примеры задач.

8 ноября (среда)

Лекция С: Поиск кратчайших путей в графах

1. Поиск кратчайших путей во взвешенных графах.
2. Алгоритм Дейкстры
3. Восстановление пути
4. Примеры
5. Дополнение: использование кучи в Алгоритме дейкстры.

Лекция B: Декартово дерево. Бор

1. Декартово дерево

2. Бор

Лекция A: Алгоритмы проверки чисел на простоту и факторизации

1. Тест Соловея-Штрассена.
2. Тест Рабина-Миллера

9 ноября (четверг)

Лекция C: Метод рекурсивного спуска

1. Задача о вычислении значения арифметического выражения
2. Формулы Бэкуса-Науэра для арифметического выражения
3. Написание программы методом рекурсивного спуска.
4. Обощения (отслеживание ошибок, вычисление логических выражений, вычисление переменных, функций, возведение в степень).
5. Пара слов о синтаксическом разборе. Формализация понятия "число".

Лекция B: Геометрия

Вычислительная планиметрия. Векторы. Площадь. Полярный угол. Построение выпуклой оболочки – алгоритмы Грэхема, Джарвиса.

Лекция A: Минимальный разрез в графе

1. Минимальный s-t разрез в графе, связь с максимальным потоком
2. Постановка задачи, наивный алгоритм
3. Решение за O(n) поисков минимальных s-t разрезов
4. Алгоритм проталкивания предпотока, его выгодная модификация
5. Алгоритм поиска минимального разреза в графе
6. Временные оценки для различных реализаций

11 ноября (суббота)

Лекция 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)>

12 ноября (воскресенье)

Лекция C: Структуры данных – 2

1. Heap, Heap-sort и очередь с приоритетами
2. Хеш-таблицы: хеш-функции, методы разрешения коллизий, хеширование с открытой адресацией, двойное хеширование
(3. Двоичные деревья поиска: поиск, добавление и удаление, сбалансированные деревья.)

Лекция B: Методы решения геометрических задач

1. Теорема Хелли
2. Метод границ
3. Метод деления на 2^dimension

Будут рассмотрены классические задачи
1. Разместить круглый бассейн максимального размера среди колонн.
2. В данном наборе линейных неравенств найти максимальное количество совместных.

Лекция A: Криптография

1. Постановка задачи. Криптография и стеганография.
2. Классические криптографические алгоритмы: шифры замены и перестановки.
3. Абсолютно стойкий шифр и почему им не пользуются.
4. Современная симметричная криптография: потоковые и блочные шифраторы (ГОСТ 28147-89).
5. Хэш-функция SHA1.
6. Современная криптография с открытым ключом: RSA, электронная подпись, открытое распределение ключей.