Обзорный курс по теоретической информатике

Санкт-Петербург, осень 2016

Описание

Это содержательный курс, который даст слушателям представление не только о различных областях теоретической информатики, а также и об основных методах и идеях. Мы поговорим про такие области: алгоритмическая неразрешимость, сложность вычислений, понятие доказательств в информатике (классические, интерактивные, вероятностно проверяемые, доказательства с нулевым разглашением), линейное программирование и принцип двойственности, вычисления с малой памятью, параллельные вычисления, вероятностные алгоритмы, теория информации (классическая и алгоритмическая), коммуникационная сложность, тестирование свойств и пр.

Курс не требует никаких предварительных знаний, выходящих за программу первых двух курсов ВУЗов, но существенно проще будет тем, кто уже прослушал курсы по дискретной математике, алгоритмам и структурам данных и теории вероятностей.

Похожий курс читался в 2013 году: http://compsciclub.ru/courses/cs-intro/2013-autumn/

Преподаватели

Список лекций

Лекция 1. О понятии "доказательства" в теоретической информатике

Лекция начнется с неформального рассказа про взгляд теоретической информатики на понятие доказательства по мотивам статьи на хабре: https://habrahabr.ru/company/spbau/blog/217215/.

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

Лекция 2. Короткие доказательства и класс NP

Определение класса NP, примеры. Доказательство простоты числа (критерий Пратта). Сведения и полнота. NP-полнота задачи об ограниченной остановке. Сведение Circuit-SAT к 3SAT.

Лекция 3. Машины Тьюринга. Элементы сложности доказательств.

Машины Тьюринга. Моделирование машин Тьюринга схемами. NP-полнота задачи Circuit-SAT. Деревья поиска противоречия. Нижняя оценка на принцип Дирихле с помощью игр. Резолюционные доказательства и их связь с деревьями поиска противоречия.

Лекция 4. Решение оптимизационных задач: вероятностное округление

Приближенные алгоритмы для MaxSAT: 1/2-приближенный, задача линейного программирования, (1-1/e)-приближенный алгоритм с помощью вероятностного округления. Комбинированный 3/4-приближенный алгоритм.

Лекция 5. Линейное программирование

Задача линейного программирования. Оптимальное значение достигается в вершине. Канонические и стандартные формы. Критерий вершины для стандартной формы. Конечность числа вершин. Метод эллипсоидов.

Лекция 6. Двойственность задач линейного программирования, матричные игры

Лемма Фаркаша. Двойственные задачи линейного программирования. Матричные игры, цена игры, теорема фон Неймана.

Лекция 7. Принцип Яо. PCP-теорема.

Принцип Яо (применение матричных игр для оценки сложности вероятностных алгоритмов), нижняя оценка средней сложности вероятностных алгоритмов сортировки. Две формулировки PCP-теоремы: NP-трудность GAP-3SAT и NP=PCP(log n, 1). Трудность приближения MAX3SAT и задачи о клике.

Лекция 8. Конечные автоматы и вычисления с константной памятью.

Детерминированные и недетерминированные конечные автоматы. Автоматы и регулярные выражения. Лемма о накачке. Автоматные языки и классы эквивалентности. DSpace[1] совпадает с множеством автоматных языков. Пример языка, который не является автоматным, но решается с использованием O(loglogn) памяти. DSpace[o(loglogn)]=DSpace[1].

Лекция 9. Вычисления с (поли)логарифмической памятью

Теорема Савича: достижимость в неориентированном графе решается с использованием O(log^2n) памяти. Вероятностный алгоритм достижимости в неориентированном графе, использующий O(log n) памяти.

Лекция 10. Параллельные вычисления. Коды, исправляющие ошибки

Параллельный алгоритм для языков из DSPACE[log n]. Параллельное сложение и умножение. Код Хемминга.

Лекция 11. Коды, исправляющие ошибки. Коммуникационная сложность.

Код Уолша-Адамара и его вероятностное декодирование. Коммуникационная сложность. Коммуникационная сложность функции равенства. Компромисс между памятью и временем работы для машин Тьюринга, распознающих палиндромы.

Лекция 12. Энтропия и однозначно-декодируемые коды

Вероятностный коммуникационный протокол для функции равенства. Энтропия и однозначно-декодируемые коды. Неравенство Крафта. Коды Хаффмена и их построение.

Лекция 13. Колмогоровская сложность.

Сложность относительно декомпрессора. Оптимальный декомпрессор. Свойства колмогоровской сложности. Вычислимые функции и перечислимые множества. Невычислимость нетривиальной нижней оценки на колмогоровскую сложность. Доказательство Чайтина первой теоремы Геделя о неполноте. Доказательство бесконечности простых чисел. Нижняя оценка на время работы одноленточной машины Тьюринга, распознающей палиндромы.