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

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

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

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

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

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

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

27 апреля 2017

Экзамен

Задачи к экзамену и инструкции доступны на страничке курса.