Город: Санкт-Петербург Казань Язык: Русский English

Основы вычислимости и теории сложности
Санкт-Петербург / осень 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Какие задачи можно решать на компьютере, а с какими компьютер не справится? Какие задачи можно решать эффективно, а какие нельзя? Из первой части курса, которая посвящена вычислимости, можно будет узнать: как доказывается алгоритмическая неразрешимость задач, доказательство и применения теоремы о неподвижной точке, арифметическую иерархию и доказательство первой теоремы Геделя о неполноте. Вторая часть курса будет посвящена сложности вычислений, кроме классических вещей (классы P,NP, сводимость, NP-полнота) мы изучим полиномиальную иерархию, булевы схемы, вероятностные алгоритмы, интерактивные протоколы и вероятностно проверяемые доказательства.

Основная литература:

  • Н.К. Верещагин, А. Шень, Вычислимые функции.
  • S. Arora, B. Barak, Computational Complexity: A modern approach.

Дополнительная литература:

  • M. Sipser, Introduction to the theory of computation.
  • Ch. Papadimitriou, Computational Complexity.
  • А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления.

Примерный план курса:

  1. Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества.

  2. \( m \)-сведения, другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса. Теорема Клини о неподвижной точке. Программа, печатающая свой текст. Доказательство теоремы Клини для искусственного языка программирования. Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини.

  3. Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Предикатные формулы (формулы I-го порядка). Интерпретации.

  4. Выразимость в арифметике. Арифметичность графика вычислимой функции. Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя.

  5. Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.

  6. NP-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для NP-задач поиска. Класс PSPACE и полная задача в ней. Теорема Ладнера о не NP-полном языке в классе NP.

  7. Теоремы об иерархии по времени. Полиномиальная иерархия. Простейшие свойства, полные задачи в \( \Sigma_i^P \) и в \( \Pi_i^P \). Оракульное определение полиномиальной иерархии.

  8. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Существование функций большой схемной сложности. Теорема Карпа-Липтона. Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана).

  9. Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в \( \Sigma_2 \).

  10. Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов и для квадратичных невычетов. Теорема Шамира (IP = PSPACE) и ее следствия.

  11. Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки.

  12. Попарно-независимые хеш-функции. Лемма Вэлианта-Вазирани. Вычисления с ограничениями и по времени, и по памяти. Нижняя оценка для SAT.

Дата и время Название Место Материалы
10 сентября
18:30–19:50
Лекция 1, лекция ПОМИ РАН Нет
10 сентября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
17 сентября
18:30–19:50
Лекция 2, лекция ПОМИ РАН Нет
17 сентября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
24 сентября
18:30–19:50
Лекция 3, лекция ПОМИ РАН Нет
24 сентября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
01 октября
18:30–19:50
Лекция 4, лекция ПОМИ РАН Нет
01 октября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
08 октября
18:30–19:50
Лекция 5, лекция ПОМИ РАН Нет
08 октября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
22 октября
18:30–20:00
Лекция 6, лекция ПОМИ РАН Нет
22 октября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
29 октября
18:30–20:00
Лекция 7, лекция ПОМИ РАН Нет
29 октября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
05 ноября
18:30–19:50
Лекция 8, лекция ПОМИ РАН Нет
05 ноября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
12 ноября
18:30–19:50
Лекция 9, лекция ПОМИ РАН Нет
12 ноября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
19 ноября
18:30–19:50
Лекция 10, лекция ПОМИ РАН Нет
19 ноября
20:00–21:20
Практика, семинар ПОМИ РАН Нет
26 ноября
18:30–20:00
Лекция 11, лекция ПОМИ РАН Нет
26 ноября
20:00–21:30
Практика, семинар ПОМИ РАН Нет
03 декабря
18:30–20:00
Лекция 12, лекция ПОМИ РАН Нет
03 декабря
20:00–21:20
Зачет, семинар ПОМИ РАН Нет
10 декабря
18:30–19:50
Экзамен, лекция ПОМИ РАН файлы
11 декабря 2014

Опрос по курсу

Добрый день, ребята!

Предлагаю вам одностраничную короткую анкету, чтобы вы поделились своими впечатлениями от курса. Опрос находится по ссылке. Заполните его, пожалуйста, – это может быть полезно для этого курса и для других, которые вам ещё предстоит прослушать.

Опрос анонимный. Ждём ответов до выходных.

Катя

29 ноября 2014

Вопросы к экзамену.

Выложены вопросы к экзамену. Смотрите в списке занятий.

11 октября 2014

Отмена занятий 15 октября

Добрый вечер!

Обратите внимание, что 15 октября занятий по основам вычислимости и теории сложности не будет. Изменения расписания отражены на соответствующей странице.

Катя Лебедева