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

Экспандеры и их применения
Весна 2017, посмотреть все семестры

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

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

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

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

Список литературы:

Дата и время Название Место Материалы
08 апреля
17:20–18:50
Лекция 1. Комбинаторные экспандеры: определения и теоремы о существовании, лекция ПОМИ РАН видеофайлы
08 апреля
19:10–20:40
Лекция 2. Примеры применений комбинаторных экспандеров, лекция ПОМИ РАН видеофайлы
09 апреля
11:15–12:45
Лекция 3. Вершинное и рёберное расширение графа, лекция ПОМИ РАН видеофайлы
09 апреля
13:00–14:30
Лекция 4. Спектр графа, определение спектрального экспандера, лекция ПОМИ РАН видеофайлы
09 апреля
15:30–17:00
Лекция 5. Спектр случайного графа. Случайное блуждание на экспандере, лекция ПОМИ РАН видеофайлы
15 апреля
17:20–18:50
Лекция 6. Зигзаг-произведение графов, лекция ПОМИ РАН видеофайлы
15 апреля
19:10–20:40
Лекция 7. Рекурсивные конструкции спектральных экспандеров, лекция ПОМИ РАН видеофайлы
16 апреля
11:15–12:45
Лекция 8. Экстракторы случайности, лекция ПОМИ РАН видеофайлы
16 апреля
13:00–14:30
Лекция 9. Генератор Нисана, лекция ПОМИ РАН видеофайлы
16 апреля
15:30–17:00
Лекция 10. Алгоритм Рейнголда. Надежные вычисления, лекция ПОМИ РАН видеофайлы
15 мая 2017

Конспект лекций

На сайт добавлен недостающий конспект девятой лекции.

Конспект десятой лекции обновлён.