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

Общая информация
ЛекторД. М. Ицыксон
Семестросень 2012
Дата начала12.09.2012
Количество пар12
Язык курсарусский
Lecture notes
Вопросы к экзамену
Анонсы
Анонс habrahabr.ruhttp://habrahabr.ru/events/963/
Аннотация

Это первая часть годового курса о вычислениях.

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

Основная литература
  • Н.К. Верещагин, А. Шень, Вычислимые функции. [pdf]
  • S. Arora, B. Barak, Computational Complexity: A modern approach. Draft [pdf]
Дополнительная литература
  • M. Sipser, Introduction to the theory of computation.
  • Ch. Papadimitriou, Computational Complexity.
  • А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. [ps.zip]

Лекционный план указан для каждой лекции.

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

1. Разрешимые и перечислимые множества. Классы P и NP
(12.09.2012 - 18:30 - 19:50)

Разрешимые множества, определения перечислимого множества. Теорема Поста. Классы P и NP. m-сведение, самое трудное перечислимое множество. Неразрешимость задачи об остановке алгоритма.

http://www.lektorium.tv/lecture/?id=13899
2. Вычислимые функции
(19.09.2012 - 18:30 - 19:50)

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

http://www.lektorium.tv/lecture/?id=13938
3. Теорема о неподвижной точке. Машины Тьюринга
(03.10.2012 - 18:30 - 19:50)

Теорема о неподвижной точке. Программа, печатающая свой текст. Доказательство с помощью искусственного языка программирования. Машины Тьюринга. Неразрешимость задачи Поста. http://www.lektorium.tv/lecture/?id=13976
4. Вычислимость и выразимость в арифметике
(10.10.2012 - 18:30 - 19:50)

Формулы исчисления предикатов. Выразимость в арифметике. Арифметичность перечислимых множеств. http://www.lektorium.tv/lecture/?id=13992
5. Арифметическая иерархия. Колмогоровская сложность
(17.10.2012 - 18:30 - 19:50)

Арифметическая иерархия и ее простейшие свойства. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Системы доказательств и перечислимые множества. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте. http://www.lektorium.tv/lecture/?id=14011
6. Моделирование машин Тьюринга. Недетерминированные машины Тьюринга
(24.10.2012 - 18:30 - 19:50)

Нижняя оценка на палиндром на одноленточной машине Тьюринга. Моделирование k-ленточной машины на k-ленточной с линейным замедлением. Эффективное моделирование k-ленточной машины на 2-ленточной. Недетерминированные машины Тьюринга и класс NP. Задача Circuit-SAT, сведение Circuit-SAT к 3SAT. http://www.lektorium.tv/lecture/?id=14039
7. О классе NP
(31.10.2012 - 18:30 - 19:50)

NP-полнота задачи Circuit-SAT и задачи о независимом множестве. NP-задачи поиска. Сведения по Тьюрингу. Сведение задач поиска к задачам распознавания. Теорема Ладнера. http://www.lektorium.tv/lecture/?id=14053
8. P vs NP с оракулами. Иерархии по времени
(07.11.2012 - 18:30 - 19:50)

Оракулы при которых P=NP и P$ \neq $NP. Иерархия по времени для детерминированных и недетерминированных вычислений. http://www.lektorium.tv/lecture/?id=14069
9. Вычисления с ограничениями по памяти
(14.11.2012 - 18:30 - 19:50)

Теорма Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Теорема об иерархии по памяти. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем. http://www.lektorium.tv/lecture/?id=14084
10. Полиномиальная иерархия
(21.11.2012 - 18:30 - 19:50)

Замкнутость классов NSpace[s(n)] относительно дополнения. Полиномиальная иерархия. Простейшие свойства, полные задачи в \Sigma_i^P и в \Pi_i^P. Оракульное определение полиномиальной иерархии. http://www.lektorium.tv/lecture/?id=14095
11. Нижние оценки для SAT. Схемная сложность
(28.11.2012 - 18:30 - 19:50)

Вычисления с ограничением по времени и по памяти. Нижняя оценка для SAT. Альтернирующие машины Тьюринга и полиномиальная иерархия. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Теорема Карпа-Липтона. Существование функций большой схемной сложности. http://www.lektorium.tv/lecture/?id=14125
12. Схемы и параллельные вычисления
(05.12.2012 - 18:30 - 19:50)

Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). Равномерные схемы. Классы NC и NC$ ^i $. P-полные задачи. Соотношение между NC$ ^1 $, L, NL и NC$ ^2 $. Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел. http://www.lektorium.tv/lecture/?id=14134
Ваша оценка: Пусто Средняя: 3.4 (5 votes)
Share |