Структурная теория сложности

Общая информация
ЛекторЭ. А. Гирш
Семестросень 2008
Дата начала28.09.2008
Количество пар12
Язык курсарусский
Видеоhttp://lektorium.tv/course/?id=22750
Аннотация Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область информатики содержит как "великие" нерешенные задачи (например, P vs NP — одна из семи задач, за решение которых Clay Mathematical Institute объявил призы по $1,000,000), так и красивые теоремы (теорема Шамира об интерактивных доказательствах, теорема Разборова о монотонных логических схемах…). Без знания теории сложности невозможно глубокого понимания криптографии и многих других областей теоретической информатики. Конспекты лекций, читавшихся ранее: http://logic.pdmi.ras.ru/~hirsch/students/complexity1/
Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекции 1-2
(28.09.2008 - 14:15)

Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NP\P. http://lektorium.tv/lecture/?id=12788
2. Лекции 3-4
(12.10.2008 - 14:15)

Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени. http://lektorium.tv/lecture/?id=12790
3. Лекции 5-6
(26.10.2008 - 14:15)

Теорема Карпа–Липтона. Схемы фиксированного полиномиального размера. P–полнота. NSPACE. Полиномиальные вычисления и логарифмическая память. http://lektorium.tv/lecture/?id=12792
4. Лекции 7-8
(09.11.2008 - 14:25)

Классы RP, BPP, PP. 2–раундовые интерактивные доказательства. Многораундовые интерактивные доказательства. http://lektorium.tv/lecture/?id=12794
5. Лекции 9-10
(16.11.2008 - 14:30)

IP=PSPACE. Лемма Вэлиэнта–Вазирани. PCP–theorem. Неаппроксимируемость. http://video.google.com/videoplay?docid=2279332992556994476
6. Лекции 11-12
(23.11.2008 - 14:30)

Доказательство PCP–theorem.
Ваша оценка: Пусто Средняя: 5 (2 голосов)
Share |
Лекция Эдуарда Алексеевича Гирша