Приглашаем всех желающих на очередной курс открытых лекций в рамках Computer Sceince клуба.
Лектор - Дмитрий Михайлович Ицыксон, к.ф.-м.н., ведущий научный сотрудник лаборатории математической логики ПОМИ РАН, доцент Академического Университета РАН.
Лекции будут посвящены основным способам представлений булевых функций и моделях вычислений, основам теории информации, теории кодирования, коммуникационной сложности и матричных играх. Будут приведены примеры, показывающие, что эти области связаны друг с другом.
Примерная программа курса:
1. Представление булевых функций: КНФ, ДНФ, деревья решений, формулы, ветвящиеся программы, схемы. Нижние оценки для деревьев решений.
2. Схемы и машины Тьюринга. Сведение задачи выполнимости к КНФ. NP-полнота задачи SAT.
3. Деревья решений как доказательства невыполнимости формул в КНФ. Игры доказывающего и откладывающего. Древовидная резолюция.
4. Энтропия и однозначно-декодируемые коды. Коды Хаффмена.
5. Лемма Фаркаша. Теорема фон-Неймана о матричных играх.
6. Принцип Яо. Нижние оценки для вероятностных алгоритмов сортировки и вероятностных деревьев решений.
7. Коммуникационная сложность, прямоугольники. Time vs Space tradeoff для машин Тьюринга, вычисляющих палиндром.
8. Коды, исправляющие ошибки. Коды Хаффмена, коды Адамара и Рида-Соломона. Вероятностная проверка произведения булевых матриц.
9. Вероятностная коммуникационная сложность предиката равенства.
10. Теорема Карчмара-Вигдерсона о связи коммуникационной сложности и формульной сложности. Оценка на формульную сложность Parity.