Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».

Коммуникационная сложность

Лектор:
Николай Константинович Верещагин, профессор МГУ, член Европейской Академии.

Аннотация
Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений. Результаты из коммуникационной сложности имеют очень широкое применение в других областях теоретической информатики.

Материалы и видео курса.

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

Лектор:
Андрей Евгеньевич Ромащенко, научный сотрудник Института проблем передачи информации РАН в Москве и Лаборатории информатики, робототехники и микроэлектроники (LIRMM) в Монпелье.

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

Материалы и видео курса.

Машинный перевод

Лектор:
Дэвид Талбот, ведущий научный сотрудник Google в Великобритании, преподаватель Школы анализа данных.

Аннотация
Первый день курса знакомит слушателей с проблемой машинного обучения с параллельных данных для автоматического перевода. Слушателям будет предложено реализовать простые алгоритмы для выравнивания слов. Второй день курса будет посвящён основам нейронного машинного перевода. Слушатели смогут получить практический опыт работы с простой моделью кодер-декодер. Будут полезны начальные навыки Python и умение компилировать и запускать код с github. Курс читается на английском языке.

Материалы и видео курса.

Избранные главы теории потоков

Лектор:
Максим Александрович Бабенко, доцент Высшей школы экономики, преподаватель Школы анализа данных, сотрудник Яндекс.

Аннотация
Теория потоков, без сомнения, представляет собой один из наиболее хорошо изученных разделов комбинаторной оптимизации, имеющий разнообразные приложения, как теоретические, так и практические. Курс начнется с краткого введения в предмет, в котором мы разберем базовые алгоритмы для задачи о максимальном потоке, а затем быстро перейдем к более современным темам: проталкиванию предпотока и параметрическим потоковым задачам. В заключительной части курса коснемся обобщений понятия потока: изучим простейшие виды мультипотоковых задач, а также поговорим о потоках в кососиметрических и двунаправленных графах. От слушателей предполагается знакомство с базовыми понятиями алгоритмической теории графов.

Материалы и видео курса.