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

Сложность булевых функций
Санкт-Петербург / весна 2017, посмотреть все семестры

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

Булевы функции — это одни из наиболее важных и наиболее изученных объектов в теоретической информатике. Множество важнейших теоретических и прикладных вопросов можно переформулировать на языке булевых функций. На данном семинаре мы будем изучать сложность булевых функций — будем доказывать нижние оценки на размеры описания булевых функций в виде формул, схем и некоторых других представлений. Основные материалы, обсуждаемые на семинаре, будут из книги Boolean Function Complexity: Advances and Frontiers, Stasys Jukna, 2012.

Семинар входит в магистерскую программу теоретическая информатика Академического университета.

Дата и время Название Место Материалы
15 февраля
18:30–19:50
Введение в сложность булевых функций, Семинар ПОМИ РАН Нет
22 февраля
18:30–19:50
Первые оценки на формульную сложность., Семинар ПОМИ РАН Нет
01 марта
18:30–19:50
Квадратичные оценки на размер формул, Семинар ПОМИ РАН Нет
15 марта
18:30–19:50
Метод случайных подстановок, Семинар ПОМИ РАН Нет
22 марта
18:30–19:50
Формулы и прямоугольники, Семинар ПОМИ РАН Нет
29 марта
18:30–19:50
Выпуклые меры и препятствия для доказательства нижних оценок, Семинар ПОМИ РАН Нет
05 апреля
18:30–19:50
Графовая сложность, Семинар ПОМИ РАН Нет
12 апреля
18:30–19:50
Деревья принятия решений, начало, Семинар ПОМИ РАН Нет
19 апреля
18:30–19:50
Деревья принятия решений, Семинар ПОМИ РАН Нет
26 апреля
18:30–19:50
Деревья принятия решений для задачи поиска, Семинар ПОМИ РАН Нет
03 мая
18:30–19:50
Деревья принятия решений и многочлены, Семинар ПОМИ РАН Нет
10 мая
18:30–19:50
Линейные деревья принятия решений, Семинар ПОМИ РАН Нет