Завершаем забытое и не успетое, в оставшееся время Машина тьюринга, возможно RAM

Рандом
----------

1. Кратко повторить Полларда (если будет нужно)
1.1 Избавляемся от логарифма в Полларде

2. Многочлены
2.1 Лемма Шварца-Зиппеля: P(x) над F_p Prob_x [P(x) = 0] <= deg(P) / |F_p|.
2.2 Применение: матрица Татта

3. Random Shuffle
3.1 Алгоритм
3.2 Зачем он нужен. Пример про QuickSort, возможно про BST и случайный порядок добавления.

4. Другие применения случайных чисел.
4.1 Идеальное шифрование x -> (x + secret) % M, secret = rand
4.2 Вычисление средней зарплаты без разглашения
4.3 Доказательства без разглашения, общая идея.
4.4 Пример? Гамильтонов путь в графе [внимание, в практике есть GI]

Перерыв!

Вычислимость
----------------

1. Turing Machine
1.1 Определение
1.2 Non-deterministic Turing Machine
1.3 А что с рандомом? Вероятностная лента.
1.4 Как альтернативное определение классов NP, RP, etc.

2. Ram Machine
2.1 ADD, SUB, MULT, DIV, mov, jump, jumpif, halt
2.2 Одна операция == O(1)
2.2 Не борзеем: числа в регистре <= c * t(n)^k, где t(n) время работы

3. Strong Polynomial Time
3.1 Примеры: QSort, алгоритм Евклида

4. Вовращаем долги: теорема о временной иерархии
4.1 Универсальная машина тьюринга.
4.2 Диагонализация!


Bibliography:
-----------
Aho,Hopcroft,Ullman -- Design of Computer algorithms
Arora, Barak -- Computation Complexity [https://theory.cs.princeton.edu/complexity/book.pdf]