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

Рассказы о теоретической информатике
Казань / осень 2017, посмотреть все семестры

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

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

Примерная программа курса:

  1. Представление булевых функций: КНФ, ДНФ, деревья решений, формулы, ветвящиеся программы, схемы. Нижние оценки для деревьев решений.
  2. Схемы и машины Тьюринга. Сведение задачи выполнимости к КНФ. NP-полнота задачи SAT.
  3. Деревья решений как доказательства невыполнимости формул в КНФ. Игры доказывающего и откладывающего. Древовидная резолюция.
  4. Энтропия и однозначно-декодируемые коды. Коды Хаффмена.
  5. Лемма Фаркаша. Теорема фон-Неймана о матричных играх.
  6. Принцип Яо. Нижние оценки для вероятностных алгоритмов сортировки и вероятностных деревьев решений.
  7. Коммуникационная сложность, прямоугольники. Time vs Space tradeoff для машин Тьюринга, вычисляющих палиндром.
  8. Коды, исправляющие ошибки. Коды Хемминга, коды Адамара и Рида-Соломона. Вероятностная проверка произведения булевых матриц.
  9. Вероятностная коммуникационная сложность предиката равенства.
  10. Теорема Карчмара-Вигдерсона о связи коммуникационной сложности и формульной сложности. Оценка на формульную сложность Parity.
Дата и время Название Место Материалы
26 октября
17:00–20:10
Лекции 1-2, лекция Физический корпус КФУ, ауд. 305 Нет
27 октября
17:00–20:10
Лекции 3-4, лекция 2-й учебный корпус К(П)ФУ, ауд. 109 Нет
28 октября
15:20–18:30
Лекции 5-6, лекция 2-й учебный корпус К(П)ФУ, ауд. 109 Нет