Дневник лекций (осень 2012 года, весна 2013 года)

Среда, 5 сентября

Равнодоступные адресные машины, меры сложности: количество операций,
длина машинного слова, количество использованных регистров.
Полиномиальные РАМ (по всем трем мерам сложности).

Полиномиальные алгоритмы нахождения НОД и быстрого возведения в
степень по данному модулю.

Одноленточные и многоленточные машины Тьюринга. Время работы и память
как меры сложности. Оценка количества шагов для копирования слова.

Оценка сложности выполнения арифметических операций на
машинах Тьюринга.

Среда, 12 сентября

Моделирование машин Тьюринга на РАМ.

Моделирование многолентночных машин Тьюринга на одноленточных.

Моделирование РАМ на многоленточных машинах Тьюринга.

Классы полиномиально вычислимых
функций и полиномиально разрешимых предикатов.
Независимость этих классов от вычислительной модели.

Среда, 19 сентября

Вероятностные алгоритмы.
Полиномальные по времени вероятностные алгоритмы (время ограничено
полиномом от длины входа при любых исходах бросаний).
Определение вычисления с ограниченной ошибкой.
Уменьшение вероятности ошибки с помощью повторения.
Классы BPP и FBPP.

Вероятностный полиномиальный алгоритм проверки полиномиального
тождества.

Понедельник, 24 сентября

Класс P/poly.
Включение BPP в P/poly.

Схемы из функциональных элементов.
Верхняя оценка O(n2^n) схемной сложности
любой булевой функции.
Нижняя оценка
2^n/3n схемной сложности некоторой булевой функции.

Понедельник, 1 октября

Характеризация класса
P/poly в терминах схемой сложности.

Класс NP. Примеры.

Среда, 3 октября

Определение сводимости. NP трудные и полные задачи.

Теорема Кука—Левина.

Понедельник, 8 октября

NP полнота задачи 3-CNF, CLIQUE, 3-COLORING, SUBSET-SUM,

Понедельник, 22 октября

Необратимые и односторонние функции (слабый и сильный
вариант поределениия). Кандидаты.
Несуществование односторонних функций в предположении
P=NP.

Понедельник, 29 октября

Преобразование слабо односторонних
функций в сильно односторонние функции.

Понедельник, 12 ноября

Полиномиально моделируемые и доступные распределения вероятностей.
Односторонние частичные функции. Примеры.
Односторонние перестановки.

Понедельник, 19 ноября

Вычислительно неотличимые последовательности случайных величин.
Их свойства.
Генераторы псевдослучайных чисел.

Понедельник, 26 ноября

Трудный бит h(x) к данной функции f(x). Лемма о вычислительной неотличимости
значения f(x)h(x) от h(x)(случайный бит).

Понедельник, 3 декабря

Построение генераторов ПСЧ с любой степенью расширения,
исходя из односторонней перестановки и трудного бита для нее.

Построение генераторов ПСЧ с любой степенью расширения,
исходя из генераторов ПСЧ с минимальной степенью расширения.

Понедельник, 10 декабря

Построение трудного бита, для данной односторонней частичной перестановки
(начало доказательства).

Понедельник, 17 декабря

Построение трудного бита, для данной односторонней частичной перестановки
(конец доказательства).

Псевдослучайные функции. Построение семейства ПСФ исходя из генераторов
ПСЧ.

Среда, 13 февраля

Повторение содержания осеннего семестра: детерминированные и вероятностные полиномиальные алгоритмы,
схемы из функциональных элементов, классы P, BPP и nuP. Класс NP и NP полные проблемы. Слабо и сильно односторонние функции,
преобразование слов односторонней функции в сильно односторонннюю функцию . Частичные односторонние функции.
Генераторы ПСЧ. Трудный бит. Построение генераторов ПСЧ, исходя из
односторонней перестановки и трудного бита.

Среда, 20 февраля

Повторение ПСФ.

Односторонние функции с секретом. Трудный бит для односторонних функций с секретом.

Среда, 27 февраля

Одноразовые СШЗК. Построение СШЗК на основе генератора ПСЧ

Многоразовые СШЗК.
Построение многоразовой СШЗК
на основе семейства ПСФ и одноразовой СШЗК.

Среда, 6 марта

Схемы шифрования с открытым ключом (асимметричные схемы).
Построение СШОК на основе необратимой перестановки с секретом (экономная схема).

Среда, 13 марта

Построение СШОК на основе необратимой перестановки с секретом (неэкономная
схема с побитовым шифрованием).

Неинтерактивные схемы привязки. Построение такой схемы на основе
односторонней перестановки.

Интерактивные схемы привязки (определение).

Среда, 20 марта

Построение интерактивного протокола привязки на основе генератора ПСЧ.

Протоколы бросания монетки (определение).

Среда, 27 марта

Построение протокола бросания монетки на основе интерактивного протокола
привязки. Игра в орлянку по телефону.

Среда, 3 апреля

Неразглашение информации (общее определение).
Теорема о последовательном повторении неразглашающего алгоритма.

Среда, 10 апреля

Неразглашение информации при наличии общедоступной информации.

Протоколы идентификации с секретным ключом. Построение такого
протокола исходя из семейства ПСФ

Протоколы идентификации с открытым ключом. Построение такого
протокола исходя из схемы шифрования с открытым ключом.

Среда, 17 апреля

Другая конструкция протокола идентификации, которая годится для любой
из трех односторонних перестановок (RSA, функции Рабина, дискретной экспоненты).

Среда, 24 апреля

СТОК, СТОЗ, построение СТОЗ и СТОК исходя из СТОЗ.

Среда, 1 мая лекции не было

Среда, 8 мая

Схемы цифровой подписи с закрытым ключом (симметричные).
Построение такой
схемы на основе семейства ПСФ.

Схемы цифровой подписи с открытым ключом (асимметричные).
Построение схемы цифровой подписи одного бита.

Среда, 15 мая

Схема одноразовой цифровой подписи фиксированного количества битов.

Схема одноразовой цифровой подписи слова
нефиксированной длины.

Общая схема несиметричной цифровой подписи.