Математическая логика и сложность вычислений

Бакалавриат 2019/2020

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 3-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Верещагин Николай Константинович, Милованов Алексей Сергеевич

Язык: русский

Кредиты: 6

Контактные часы: 80

Полная версия программы учебной дисциплины

Аннотация

Теория вычислений и логика в их современном виде появились одновременно (и даже в работах одних и тех же людей - Гёделя, Чёрча, Тьюринга и других), и это не случайно: процесс формального вывода (применение разрешённых правил) и процесс вычисления (детерминированное применение разрешённых правил) по природе близки. Знаменитая теорема Гёделя (не все истинные утверждения формально доказуемы) означает на языке теории вычислений, что множество истинных утверждений неперечислимо - и в такой форме легко следует из классических результатов теории вычислений. Впоследствии появились и другие связи: логические теории можно использовать для доказательства свойств программ, классы сложности можно описывать в логических терминах, поэтому знакомство с основными понятиями и результатами логики входит в базовое образование программистов.

Цель освоения дисциплины

Целями освоения дисциплины «Сложность вычислений и логика в теоретической информатике» являются овладение студентами основными концепциями и результатами сложности вычислений и математической логики, применяемыми в теоретической информатике.

Планируемые результаты обучения

В результате освоения дисциплины студент должен знать: • основные понятия и теоремы сложности вычислений; • основные понятия и теоремы математической логики; • методы доказательства разрешимости логических теорий; • основные понятия дискретной математики, линейной алгебры и математического анализа. • способы построения графов-экспандеров и их применения в сложности вычислений.
В результате освоения дисциплины студент должен уметь: • пользоваться основными методами построения экспандеров; • пользоваться методами элиминации кванторов и игр Эренфойхта; • пользоваться понятиями чуствительности и блочной чуствительности; владеть: • навыками доказательства нижних оценок в сложности вычислений; • навыками доказательства верхних оценок в сложности вычислений; • методом дерандомизации вероятностных алгоритмов с попощью графов-экспандеров.

Содержание учебной дисциплины

Тема 1. Разрешимость логических теорий.
Язык логики предикатов: сигнатуры, термы, формулы. Семантика логики предикатов: модели данной сигнатуры (алгебраические системы, интерпретации). Формальные теории. Модели теорий, семантическое следование (истинность во всех моделях теории), нормальные модели. Метод элиминации кванторов на примере элементарной теории упорядоченного множества действительных чисел. Элементарная теория поля комплексных чисел, ее аксиоматизация и доказательство ее полноты. Элементарная теория упорядоченного поля действительных чисел, ее аксиоматизация и доказательство ее полноты.
Тема 2. Графы-экспандеры и их применения.
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа. Expander mixing lemma. Связь второго собственного числа и рёберного расширения. L_2-расстояние до равномерного распределения при одном шаге случайного блуждания. Лапласиан графа. Нижние оценки \sqrt d и 2\sqrt{d-1}-o(1) на второе собственное числа d-регулярного графа. Вероятностное доказательство существования спектрального экспандера. Тензорное произведение графов и возведение графа в степень. Собственные числа получающихся графов. Зигзаг-произведение графов, первая спектральная оценка для зигзаг-произведения. Зигзаг-произведение графов: вторая спектральная оценка для зигзаг-произведения. Построение спектрального экспандера с использованием первой спектральной оценки для зигзаг-произведения. Уменьшение вероятности ошибки рандомизованного алгоритма с помощью экспандеров без использования дополнительной случайности. Уменьшение вероятности ошибки рандомизованного алгоритма с помощью экспандеров с использованием дополнительных случайных битов. Алгоритм Рейнголда. Экспандер Маргулиса. Двудольные экспандеры: необходимое и достаточное условие существования. Экспандер Варди-Парвареша. Экспандерные коды: последовательный алгоритм декодирования. Экспандерные коды: параллельный алгоритм декодирования.
Тема 3. Сложность разрешающих деревьев
Детерминированные деревья разрешения. Метод противника для доказательства нижних оценок детерминированной сложности. Сертификаты, чувствительность и блочная чувствительность булевых функций. Связь сертификатной сложности c представлением функции в виде ДНФ и КНФ. Верхняя оценка детерминированной сложности в терминах сертификатной сложности (квадрат сертификатной сложности) и в терминах сертификатной сложности и блочной чувствительности (их произведение). Верхняя оценка сертификатной сложности через блочную чувствительность и обычную чувствительность.
Тема 4. Нижние оценки схемной сложности
Случайные ограничения и Hastad Switching Lemma. Теорема Разборова о нижней оценки схемной сложноси функции клики для монотонных схем. Теорема Разборова---Смоленского о нижней оценке cхемной сложности функции MOD_2 для схем глубины d из элементов MOD_3, \lor, \land, \lnot.

Элементы контроля

Домашнее задание
Коллоквиум
Экзамен
Экзамен проводится в письменной форме. Экзамен проходит с прокторингом. Студенты загружают задание с сайта по ссылке, решают на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена. Экзамен длится 90 минут. Во время экзамена разрешено смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач.

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.2 * Домашнее задание + 0.4 * Коллоквиум + 0.4 * Экзамен

Программа дисциплины