Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский 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
Деревья принятия решений, семинар ПОМИ РАН Нет