Построение генераторов псевдослучайных чисел (мехмат, весна 2022)
Полугодовой спецкурс по выбору кафедры (весна 2022)
Лектор: Н.К. Верещагин
Курс читается по вторникам 18:30–20:05 он-лайн (Zoom).
Первая лекция – 8 февраля.
Ссылка на записи на доске во время лекций. | Группа в Телеграм https://t.me/+2Xitr2DF0VphZjhi | Записи лекций на канале Youtube
Краткое описание курса:
Генератором псевдослучайных чисел (ПСЧ) называется полиномиально вычислимая функция G, отображающая слова какой-то длины n в слова длины n со следующим свойством. Любой полиномиально вычислимый тест не может отличить случайную величину G(x) (где x имеет равномерное распределение на словах длины n) от случайной величины, равномерно распределенной среди всех слов длины m. Нетрудно доказать, что если P=NP, то генераторов ПСЧ не существует. Поэтому для доказательства существования генератора ПСЧ нужна гипотеза о различии классов P и NP или более сильная гипотеза. В спецкурсе будет рассказано о конструкции Хостада — Импальяццо — Левина — Люби генератора ПСЧ, исходя из любой односторонней функции. Кроме того, будет рассказано о конструкции Нисана — Вигдерсона генератора ПСЧ, исходя из функции с большой схемной сложностью.
Необходимы предварительные знания: начала сложности вычислений (машины Тьюринга, схемы из функциональных элементов, взаимоотношения между ними, вероятностные алгоритмы, классы P, BPP, NP), односторонние функции.
Программа курса
Домашние задания
После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF лектору по адресу nikolay.vereshchagin@math.msu.ru) не позже начала следующей лекции. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).
Итоговая оценка
Итоговая оценка выставляется только при условии посещения не менее 8 лекций, исходя из общей оценки за домашние задания по следующему правилу:
отлично — 65% от максимального количества баллов,
хорошо — 50%,
удовлетворительно — 25%.
Зачет — 25%.
Для студентов ФКН ВШЭ:
85% — 10 баллов,
75% — 9 баллов,
65% — 8 баллов,
55% — 7 баллов,
45% — 6 баллов,
35% — 5 баллов,
25% — 4 балла,
менее 25% — 3 балла.