Материал, мимо которого мы прошли
-3.01.16 День 1.
- Поиск гамильтнова пути/цикла в графе за O(2nn2), O(2nn)
- Теоремы Оре и Дирака. Нахождение гамильтонова пути/цикла в графе в условиях этих теорем.
- Теорема Хватала. Нахождение гамильтонова пути/цикла в графе в условиях теоремы.
- Теорема Редеи-Камеона. Нахождение гамильтонова пути/цикла в турнире.
- Задача о коммивояжере. 2 и 1.5 приближения
-2.01.16 День 2.
- Решето Эратосфена, линейная реализация, вычисление функции Эйлера и подобного с ее помощью.
- Расширенный алгоритм Евклида. Решение диафантовых уравнений, обращение по модулю.
- Китайская теоерма об остатках
- Тест на простоту Миллера-Рабина
- Метод Полларда факторизации чисел
0.01.16 День 4.
- Теория расписаний, нотация.
- Задачи с одним станком. 1||Cmax, 1||SumC, 1||SumU, 1||SumWU, 1|ri|SumU, 1|prec|Fmax. Алгоритм Лоулера.
- Задачи с параллельными станками. Задачи P2||Cmax, R2||Cmax, Q||SumC
- Задача о двух станках. F2||Cmax
- Задача о двух станках. O2||Cmax
1.01.16 День 5.
- Игры на графах. Игры на ациклических графах. Игры на графах с циклами. Ретроанализ.
- Теория Шпрага-Гранди. Прямая сумма ациклических игр. Эквивалетность по Гранди. Эквивалетность ниму. Теорема про mex. Теорема про xor.
- Прямая сумма игр на графах с циклами. Неопределенные игры. Теория Смита.
2.01.16 День 6.
- Подсчет перестановок с заданным числом подъемов, максимумов, и т.п..
- Разбиения. Числа Стирлинга 1 и 2 рода. Числа Белла. Базисы убывающих и возрастающих степеней полиномов, переход между ними.
- Подсчет деревьев. Подсчет помеченных деревьев. Подсчет непомеченных деревьев. Подсчет неподвешенных деревьев. Формула Кэли. Код Прюфера.
- Лемма Бернсайда. Подсчет ожерелий.
3.01.16 День 7.
- Вероятностные пространства. События. Независимые события. Условная вероятность. Формула полной вероятности. Формула Байеса.
- Случайная величина. Математическое ожидание. Линейность математического ожидания.
- Марковские цепи. Поглощающие Марковские цепи. Фундаментальная матрица. Расчет времени поглощения. Расчет вероятности поглощения в состоянии.
4.01.16 День 8.
- Криптография с открытым ключом. Протокол Диффи-Хеллмана.
- Алгоритм RSA. Алгоритм шифрования. Алгоритм электронной цифровой подписи. Алгоритм слепой цифровой подписи.
- Интерактивные доказательства. Доказательства с нулевым разглашением.