Избранные темы Computer Science

Общая информация
ЛекторА. Х. Шень
Семестросень 2012
Дата начала22.09.2012
Количество пар10
Язык курсарусский
Вопросы к экзамену
Анонсы
Анонс habrahabr.ruhttp://habrahabr.ru/events/1009/
Аннотация

Целью этого курса является изложить некоторые классические результаты теоретической информатики, которые сочетают в себе (по возможности) разные качества

  • формулировку и доказательство можно понять за ограниченное время, у нас имеющееся
  • результат достаточно фундаментальный для того, чтобы практическим программистам стоило про него знать
  • результат не общеизвестный (последнее можно будет скорректировать по ходу дела)

Примерный перечень возможных тем:

  • понятие универсальной функции (хранимой программы) и диагональная конструкция алгоритмически неразрешимых проблем (перечислимого неразрешимого множества)
  • конкретные модели и доказательство неразрешимости конкретных задач (подстановки в словах = проблема тождества слов в полугруппах)
  • теорема Клини о неподвижной точке и self-referential конструкции
  • понятие сводимости как средство доказательства неразрешимости и полиномиальной сводимости как средства сравнения сложности
  • case study: потоки в сетях, сведение к ним (двудольного) паросочетания, вероятностный и детерминированный полиномиальные алгоритмы
  • правила доказательства свойств программ: примеры
  • вероятностные алгоритмы: пример анализа времени работы (быстрая сортировка)
  • пример результата из теории сложности: что значит и почему BPP содержится в $ \Sigma_2 $
  • теория смыкается с практикой: регулярные выражения и конечные автоматы
  • алгебра и computer science: разделение секрета, коды Рида–Соломона
  • алгебра и computer science: IP=PSPACE
  • пример из теории кодирования: границы Гилберта и Шеннона
  • пример из теории информации: шенноновская энтропия как граница для средней длины префиксного (или даже однозначного) кода
  • колмогоровская сложность (пример результата: теорема о сложности пары)
  • PCP: эквивалентность проверки доказательства и gap reduction
  • доказательства с двумя пруверами: пример, когда квантовая механика позволяет перейти границу для классической
  • псевдослучайные генераторы: почему тестирование равносильно предсказанию
Материалы:

Результаты Кари

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

1. Лекция
(22.09.2012 - 17:20 - 18:55)

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

Неразрешимость проблемы остановки.

http://www.lektorium.tv/lecture/?id=13949
2. Лекция
(22.09.2012 - 19:05 - 20:40)

Сводимость. Доказательство неразрешимости с помощью сведения. Задача FRAKTRAN Конвея: есть набор положительных рациональных чисел $ r_1,\ldots,r_n $ и целое число $ m>0 $. На каждом шаге выбирается минимальное $ i, $ при котором $ mr_i $ целое, и $ m $ заменяется на $ mr_i $; далее процесс повторяется. Надо выяснить, произойдёт ли остановка (это бывает, если ни одно из чисел $ mr_i $ не целое)

Ассоциативные исчисления. Пример исчисления $ RRR\leftrightarrow
\Lambda $, $ SS\leftrightarrow \Lambda $, $ SRS\Leftrightarrow RR $ и его полнота и корректность для утверждений о поворотах и симметриях. Неразрешимость проблемы равенства для ассоциативного исчисления (сведение проблемы остановки для машин Тьюринга)

Схемы из функциональных элементов. Размер и глубина схемы. Пример: сумматор $ n $-битовых чисел размера $ O(n) $ и глубины $ O(\log n) $.

http://www.lektorium.tv/lecture/?id=13943
3. Лекция
(23.09.2012 - 11:15 - 12:50)

Исчисление резолюций. Полнота и корректность.

Линейные уравнения: если из равенств $ \xi_1=0, \ldots, \xi_k=0 $ вытекает равенство $ \eta=0 $ (для некоторых линейных функционалов $ \xi_k $ и $ \eta $), то $ \eta $ является линейной комбинацией $ \xi_i $. (Доказательство исключением переменных.)

Совместность системы аффинных неравенств: если система несовместна, то некоторая неотрицательная линейная комбинация этих неравенств даёт противоречивое неравенство $ 0\ge 1 $.

http://www.lektorium.tv/lecture/?id=13944
4. Лекция
(23.09.2012 - 13:00 - 14:35)

Цена игры двух лиц с нулевой суммой. Доказательство существования цены с помощью системы аффинных неравенств (теорема фон Неймана)

Игры и сложность: теорема Яо о совпадении двух вариантов сложности для вероятностных алгоритмов (существование вероятностного алгоритма, имеющего малое ожидание сложности для любого входа, и существование для любого распределения на входах детерминированного алгоритма малой ожидаемой сложности по этому распределению эквивалентны).

http://www.lektorium.tv/lecture/?id=13945
5. Лекция
(23.09.2012 - 15:35 - 17:10)

Нерешённые задачи: улучшение оценок в теореме Гача--Дея (о разрыве между априорной и монотонной сложностью) в терминах игры; дискретный вариант 13 проблемы Гильберта.

Апериодические наборы плиток: конструкция Кари.

http://www.lektorium.tv/lecture/?id=13946
6. Лекция
(29.09.2012 - 17:20 - 18:55)

Разрешимые множества. Перечислимые множества как проекции разрешимых. Арифметическая иерархия. Выразимость с помощью формул первого порядка. Выразимые множества в натуральных числах с отношением порядка; элиминация кванторов.

Выразимость в языке формальной арифметики. Кодирование кортежей с помощью бета-трюка Гёделя.

http://www.lektorium.tv/lecture/?id=13964
7. Лекция
(29.09.2012 - 19:05 - 20:40)

Выразимость перечислимых множеств (с помощью сведения к FRACTRAN). Множества из класса $ \Sigma_2 $ как перечислимые с помощью оракула для проблемы остановки.

Теорема Гёделя о неполноте как следствие. Полиномиальный вариант иерархии, класс PSPACE.

http://www.lektorium.tv/lecture/?id=13965
8. Лекция
(30.09.2012 - 11:15 - 12:50)

Теория вероятностей: использование неравенства Чебышёва и метода сравнения двух распределений (мартингалов) для оценок больших уклонений.

Вероятностные алгоритмы: уменьшение вероятности ошибки. Класс BPP содержится в \Sigma_2. Класс BPP содержится в P/poly. Интерпретация P как класса языков, задаваемых полиномиально вычислимой последовательностью схем.

http://www.lektorium.tv/lecture/?id=13966
9. Лекция
(30.09.2012 - 13:00 - 14:35)

Коммуникационная сложность. Детерминированная коммуникационная сложность равенства максимальна.

Вероятностная коммуникационная сложность равенства: использование кодов, простых чисел или многочленов над конечным полем.

http://www.lektorium.tv/lecture/?id=13967
10. Лекция
(30.09.2012 - 15:35 - 17:10)

Последовательное и параллельное повторения для диалогов с одним и двумя доказывающими (формулировки вопросов).

В игре проверяющего с двумя доказывающими использование сцепленных состояний позволяет повысить вероятность выигрыша.

http://www.lektorium.tv/lecture/?id=13968
Ваша оценка: Пусто Средняя: 4.7 (16 votes)
Share |
Александр Шень
Александр Шень
Слушатели курса "Избранные темы Computer Science"
Вопросы студентов