Кафедра математической логики и теории алгоритмов

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

5 сентября

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

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

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

12 сентября

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

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

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

19 сентября

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

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

Теорема Кука—Левина
об NP полноте задачи выолнимости схем из функциональных элементов.

NP полнота задачи 3-CNF.

26 сентября

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

Класс n.u.P и включение класса P в этот класс.

3 октября

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

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

10 октября

Включение BPP в n.u.P.

Сильно односторонние функции (противник — вероятностный
полиномиальный алгоритм). Кандидаты.

Если P=NP, то сильно односторонние функции не существуют.

17 октября

Определение необратимости с противником в виде схемы из функциональных
элементов

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

24 октября

Частичные односторонние функции.
Примеры предположительно односторонних перестановок

31 октября

Вычислительно неотличимые случайные величины.
Определение генератора ПСЧ

7 ноября

Свойства вычислительно неотличимых случайных величин.

Трудный бит для данной перестановки. Общая схема
построения генератора, исходя из односторонней перестановки
и трудного бита.

14 ноября

Лемма о трудном бите. Построение генератора из перестановки
и трудного бита

21 ноября

Теорема Левина-Голдрайха о декодировании кода Адамара
и построении трудного бита для данной односторонней перестановки.

28 ноября

Генераторы, выдающие бесконечно много случайных битов.

Надехность генераторов по Яо и эквивалентность
этого определения обычному.

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

5 декабря

Псевдослучайный функции. Два вида надежности. Построение ПСФ
на основе генератора.

12 декабря

Схемы шифрования с закрытым ключом (симметричные схемы).

Построение одноразовой схемы на основе генератора

Построение многоразовой схемы на основе ПСФ

19 декабря

Односторонние перестановки с секретом

Схемы шифрования с открытым ключом (асимметричные схемы).

13 февраля

Неинтерактивные протоколы привязки.

20 февраля

Интерактивные протоколы привязки.

27 февраля

Протоколы электронной монеты.

6 марта

Протоколы идентификации с закрытым и открытым ключом.

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

13 марта

Определение неразглашения информации в общем случае. Сведение
стойкости протоколов с идентификации и при многократном
использовании к неразглашению информации и стойкости для однократного
применения.

Лемма о последовательном повторении неразглашающего алгоритма.

Построение протокола идентификации с открытым ключом на основе
функции Рабина.

20 марта

Доказательство стойкости протокола идентификации
с открытым ключом на основе функции Рабина.

Протокол идентификации
с открытым ключом на основе любой односторонней функции
(с помощью 3-раскраски графа и привязки к биту).

27 марта

Семейства хэш-функций с трудно обнаружимими коллизиями (СТОК).

Семейства пар функций с трудно обнаружимыми зацеплениями.
Их использование для построения СТОК.

3 апреля

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

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

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

10 апреля

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

17 апреля

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

Решение задач.

24 апреля, 8 и 15 мая

Решение задач.