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

Общая информация
ЛекторД. М. Ицыксон
Семестросень 2013
Дата начала12.09.2013
Количество пар13
Язык курсарусский
Lecture notes
Вопросы к экзамену
Аннотация

Курс призван познакомить слушателей с некоторыми классическими результатами и идеями теоретической информатики (Theoretical Computer Science), которые будут полезны как исследователям, так и программистам, желающим расширить свой кругозор. В частности:

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

Более детальная программа приведена ниже. Конкретное содержание курса будет корректироваться по ходу дела в соответствии с пожеланиями слушателей.

I. О понятии "доказательства" в информатике.

  1. Перечислимые множества и классические системы доказательств.
  2. Классы NP, coNP, сведения и полные задачи. Сложность доказательств.
  3. DPLL алгоритмы и метод резолюций. Экспоненциальная оценка для принципа Дирихле.
  4. Интерактивные доказательства, IP=PSPACE.
  5. Вероятностно проверяемые доказательства и NP-трудность приближения.
  6. Доказательства с нулевым разглашением. Пример для изоморфизма графов.

II. Линейное программирование

  1. Лемма Фаркаша. Принцип двойственности. Метод внутренней точки.
  2. MINMAX-теорема для матричных игр и нижние оценки для вероятностных алгоритмов.
  3. Приближенный алгоритм для MAXSAT с помощью вероятностного округления.

III. Вычисления с маленькой памятью

  1. Регулярные выражения, конечные автоматы и машины Тьюринга с константой памяти.
  2. Вычисления с логарифмической памятью. Вероятностный алгоритм для достижимости в графе с логарифмической памятью.
  3. Теорема Савитча (PSPACE=NPSPACE), NL=coNL.

IV. Вероятностные методы

  1. Коды Адамара и Рида-Соломона.
  2. k-независимые хеш-функции и их применения.
  3. Приближенный подсчет числа выполняющих наборов не сложнее проверки выполнимости.
  4. Перманент: определение, #P-трудность, интерактивный протокол. Вычислить перманент почти везде не легче, чем везде.
  5. Локальная лемма Ловаса и ее конструктивный вариант.
  6. Декодирование списком и построение псевдослучайного генератора из односторонней перестановки.
  7. Коды и повышение сложности функций.

V. Параллельные вычисления

  1. Параллельные алгоритмы сложения, умножения.
  2. Параллельный алгоритм достижимости в графе.
  3. Параллельное вычисление определителя.

VI. Классическая и алгоритмическая теория информации

  1. Энтропия Шеннона и однозначно-декодируемые коды. Применение энтропии в комбинаторике.
  2. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте.
  3. Сложность пары.
  4. Принцип несжимаемости: нижняя оценка на сложность копирования слова, доказательство бесконечности простых чисел.
  5. Коммуникационная сложность. Постановка задачи. Примеры: коммуникационная сложность предиката равенства.
  6. Коммуникационная сложность и схемная сложность.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1. О понятии "доказательства" в информатике
(12.09.2013 - 18:30 - 19:50)

Доказательство в математике и информатике. Примеры доказательств: интерактивное доказательство, доказательство с нулевым разглашением, вероятностно проверяемое доказательство, доказательство неразрешимости системы неравенств. Система доказательств, перечислимые языки, разрешимые языки. Задача об остановке алгоритма, ее неразрешимость.
2. Практическое занятие № 1
(12.09.2013 - 20:00 - 21:50)

Тут выложены задачи, которые обсуждались на занятии 12.09.
3. Лекция 2. Короткие доказательства, класс NP
(19.09.2013 - 18:30 - 19:50)

Машины Тьюринга, класс NP, сертификация простоты числа, сведения, полнота задачи об ограниченной остановке, полнота задач CircuitSAT и SAT.
4. Практическое занятие № 2
(19.09.2013 - 20:00 - 21:20)

Домашнее задание, которое будет разбираться на практике 19.09.
5. Лекция 3. Решение оптимизационных задач: вероятностное округление
(26.09.2013 - 18:30 - 19:50)

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

Домашнее задание, которое будет разбираться на практике 26.09.
7. Лекция 4. Линейное программирование
(03.10.2013 - 18:30 - 19:50)

Задача линейного программирования. Оптимальное значение достигается в вершине. Канонические и стандартные формы. Критерий вершины для стандартной формы. Конечность числа вершин. Метод эллипсоидов.
8. Практическое занятие № 4
(03.10.2013 - 20:00 - 21:30)

Домашнее задание, которое будет разбираться на практике 03.10.
9. Лекция 5. Двойственность задач линейного программирования, матричные игры
(10.10.2013 - 18:30 - 19:50)

Лемма Фаркаша. Двойственные задачи линейного программирования. Матричные игры, цена игры, теорема фон Неймана. Применение теоремы о матричных играх для оценки сложности вероятностных алгоритмов.
10. Практическое занятие №5
(10.10.2013 - 20:00 - 21:20)

Задачи, которые буду разбираться 10.10
11. Лекция 6. PCP-теорема и трудность приближения. Конечные автоматы.
(17.10.2013 - 18:30 - 19:50)

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

Задания, которые будут разбираться 17.10
13. Лекция 7. Вычисления с маленькой памятью
(24.10.2013 - 18:30 - 20:00)

Автоматные языки и классы эквивалентности. DSpace[1] совпадает с множеством автоматных языков. Лемма о накачке. Пример языка, который не является автоматным, но решается с использованием $ O(\log \log n) $ памяти. DSpace[$ o(\log \log n) $]=DSpace[1]. Теорема Савича: достижимость в неориентированном графе решается с использованием $ O(\log^2 n) $ памяти.
14. Практика 7
(24.10.2013 - 20:00 - 21:20)

Задачи, которые будут разбираться 24.10
15. Лекция 8. Вычисления с маленькой памятью и парраллельные вычисления.
(31.10.2013 - 18:30 - 20:00)

Следствие теоремы Савича: NPSPACE=PSPACE. Вероятностный алгоритм достижимости в неориентированном графе, использующий $ O(\log n) $ памяти. Вычисление достижимости в графе схемой полиномиального размера и глубины $ O(\log^2 n) $. Параллельное вычисление функций, вычислимых с использованием $ O(\log n) $ памяти.
16. Практика 8
(31.10.2013 - 20:00 - 21:20)

Внимание. Исправлена задача 46.
17. Лекция 9. Параллельные вычисления. Коды, исправляющие ошибки.
(07.11.2013 - 18:30 - 20:00)

Параллельное сложение и умножение. Линейные коды, код Хемминга.
18. Практика 9
(07.11.2013 - 20:00 - 21:20)

Задания, которые будут разбираться 07.11
19. Лекция 10. Коды Адамара и Рида-Соломона. Коммуникационная сложность.
(14.11.2013 - 18:30 - 20:00)

Коды Адамара, расстояние кода. Вероятностная проверка произведения 0/1 матриц. Вероятностное декодирования кодов Адамара. Коды Рида-Соломона, алгоритм Берлекампа-Велша. Каскадные коды. Коммуникационный протокол, коммуникационная сложность функции равенства.
20. Практика 10
(14.11.2013 - 20:00 - 21:20)

21. Лекция 11. Маленькие k-независимые множества. Энтропия.
(21.11.2013 - 18:30 - 20:00)

Вероятностный коммуникационный протокол для предиката равенства. Маленькие k-независимые множества. Дерандомизация приближенного алгоритма для MAX3SAT. Энтропия и однозначно декодируемые коды.
22. Практика 11
(21.11.2013 - 20:00 - 21:20)

23. Лекция 12. Колмогоровская сложность
(28.11.2013 - 18:30 - 20:00)

Нижняя оценка на произведение времени и памяти для многоленточной машины Тьюринга, которая распознает язык палиндромов. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте. Бесконечность простых чисел. Нижняя оценка на сложность распознавания палиндромов на одноленточной машине Тьюринга.
24. Практика 12
(28.11.2013 - 20:00 - 21:20)

25. Лекция 13. Конструктивный вариант локальной леммы Ловаса. Условная колмогоровская сложность.
(05.12.2013 - 18:30 - 20:00)

Локальная лемма Ловаса, следствие о выполнимости формулы в КНФ. Вероятностный алгоритм поиска выполняющего набора для формулы в m-КНФ, у которой каждый дизъюнкт пересекается по переменным не более, чем с $ 2^m/8 $ другими. Условная колмогоровская сложность. Теорема Колмогорова-Левина. Неравенство $ 2KS(x,y,z)\le KS(x,y)+KS(y,z)+KS(x,z)+O(\log n) $, неравенство о связи объема и площадей проекций трехмерного тела.
26. Практика. Зачет.
(05.12.2013 - 20:00 - 21:20)

Задание на контрольную. Правила внутри.
Ваша оценка: Пусто Средняя: 5 (8 votes)
Share |