Приглашаем всех желающих на очередной курс открытых лекций в рамках Computer Sceince клуба.

Лектор - Дмитрий Михайлович Ицыксон, к.ф.-м.н., ведущий научный сотрудник лаборатории математической логики ПОМИ РАН, доцент Академического Университета РАН.

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

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