City: Санкт-Петербург Новосибирск Казань Language: Русский English

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

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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