Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Экспандеры и их применения весна 2017


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

Экспандеры (расширяющие графы) являются мощным и весьма изощрённым инструментом теоретической информатики и дискретной математики. По-видимому, эффективность экспандеров отчасти объясняется тем, что они (по самому своему определению) позволяют естественно сочетать комбинаторно-геометрические, алгебраические и вероятностные рассуждения.

Экспандеры были определены в 1970-х годах. За прошедшие 30 лет они нашли множество красивых применений. Экспандеры используются в различных конструкциях дерандомизации. С помощью экспандеров строятся коды, исправляющие ошибки, и надёжные вычислительные схемы. Техника экспандеров применяется в различных доказательствах теории сложности вычислений (например, в доказательстве знаменитой PCP-теоремы).

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

Занятия

Дата Время Название Место Материалы
08.04.2017 17:20–18:50 Лекция 1 ПОМИ РАН Лекция Нет
08.04.2017 19:10–20:40 Лекция 2 ПОМИ РАН Лекция Нет
09.04.2017 11:15–12:45 Лекция 3 ПОМИ РАН Лекция Нет
09.04.2017 13:00–14:30 Лекция 4 ПОМИ РАН Лекция Нет
09.04.2017 15:30–17:00 Лекция 5 ПОМИ РАН Лекция Нет
15.04.2017 17:20–18:50 Лекция 6 ПОМИ РАН Лекция Нет
15.04.2017 19:10–20:40 Лекция 7 ПОМИ РАН Лекция Нет
16.04.2017 11:15–12:45 Лекция 8 ПОМИ РАН Лекция Нет
16.04.2017 13:00–14:30 Лекция 9 ПОМИ РАН Лекция Нет
16.04.2017 15:30–17:00 Лекция 10 ПОМИ РАН Лекция Нет