Санкт-Петербург, 199178, Россия, 14-ая линия Васильевского острова, дом 29
(812) 363-68-71, (812) 363-68-72
ru

Экспандеры и коды

2019 – 2020, VI, VIII, X семестр

Информация по курсу

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

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

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