Основы вычислимости и теории сложности

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

Какие задачи можно решать на компьютере, а с какими компьютер не справится? Какие задачи можно решать эффективно, а какие нельзя? Из первой части курса, которая посвящена вычислимости, можно будет узнать: как доказывается алгоритмическая неразрешимость задач, доказательство и применения теоремы о неподвижной точке, арифметическую иерархию и доказательство первой теоремы Геделя о неполноте. Вторая часть курса будет посвящена сложности вычислений, кроме классических вещей (классы 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-теоремы. Эквивалентные формулировки.

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

1. Лекция
(10.09.2014 - 18:30 - 20:00)

Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества.
2. Практика 1
(10.09.2014 - 20:00 - 21:30)

Задания выложены в занятии "Практика 2".
3. Лекция
(17.09.2014 - 18:30 - 20:00)

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

Задание на практику.
5. Лекция
(24.09.2014 - 18:30 - 20:00)

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

Задание на практику.
7. Лекция
(01.10.2014 - 18:30 - 20:00)

Выразимость в арифметике. Арифметичность графика вычислимой функции. Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя.
8. Практика 4
(01.10.2014 - 20:00 - 21:30)

Задание на практику.
9. Лекция
(08.10.2014 - 18:30 - 20:00)

Системы доказательств и перечислимые языки. Нижняя оценка на палиндром на одноленточной машине. Моделирование машин Тьюринга. Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.
10. Практика 5
(08.10.2014 - 20:00 - 21:30)

Задание на практику. В файле 100.pdf содержатся бонусные задания.
11. Лекция
(22.10.2014 - 18:30 - 20:00)

NP-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для NP-задач поиска. Класс PSPACE и полная задача в ней.
12. Практика 6
(22.10.2014 - 20:00 - 21:30)

Задание на практику.
13. Лекция
(29.10.2014 - 17:30 - 19:00)

Теоремы об иерархии по времени для детерминированных и недетерминированных вычислений. Полиномиальная иерархия. Простейшие свойства, полные задачи в $  \Sigma_i^P  $ и в $  \Pi_i^P  $.
14. Практика 7
(29.10.2014 - 20:00 - 21:30)

Задание на практику.
15. Лекция
(05.11.2014 - 18:30 - 20:00)

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

Задание на практику.
17. Лекция
(12.11.2014 - 18:30 - 20:00)

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

Задание на практику.
19. Лекция
(19.11.2014 - 18:30 - 20:00)

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

Задание на 19.11. В файле 100.pdf содержатся обновленные бонусные задания.
21. Лекция
(26.11.2014 - 18:30 - 20:00)

Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки.
22. Практика 11
(26.11.2014 - 20:00 - 21:30)

Задание на 19.11.
23. Лекция
(03.12.2014 - 18:30 - 20:00)

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

Домашняя контрольная работа. 999.pdf --- условие. Res.pdf --- баллы за семестр. res.pdf --- результат контрольной.
Ваша оценка: Пусто Средняя: 3.3 (4 голосов)
Share |