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

Эффективные алгоритмы и коммуникационная сложность
Санкт-Петербург / весна 2019, посмотреть все семестры

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

При разработке эффективных алгоритмов, как правило, стараются уменьшить время работы алгоритма и объём используемой памяти. Это две естественные меры сложности вычислительной задачи. Однако при распределённых вычислениях оказывается важным ещё и объём данных, которым нужно обменяться агентам, участвующим в вычислении, для решении задачи. Данная мера является основным объектом изучения области коммуникационной сложности. В отличие от других мер, для количества информации удаётся доказывать очень сильные нижние оценки. Именно такие оценки позволяют доказывать невозможность построения эффективных структур данных и потоковых алгоритмов обработки больших объёмов данных. Грубо говоря, эффективный потоковый алгоритм может быть перестроен в эффективный коммуникационный протокол, где коммуникация происходит между игроком в прошлом и игроком в будущем, а сообщение — это состояние памяти. С другой стороны, построение протоколов с низкой коммуникацией может быть использовано в классических алгоритмах. Например, недавно было получено первое за полвека существенное ускорение для классической задачи нахождения всех попарных расстояний в графе. В мини-курсе будут рассмотрено несколько результатов из области коммуникационной сложности и несколько красивых и удивительных применений к различным областям Computer Science.

Математическая модель данной области такова. У Алисы и Боба есть два больших массива данных. Их целью является вычислить некоторую функцию от этих двух массивов (скажем, в качестве Алисы и Боба могут выступать два дата-центра, которые хотят проверить, совпадают ли их данные). Предполагается, что Алиса и Боб обладают неограниченными вычислительными способностями, но при этом им очень дорого платить за пересылку данных. Очевидное решение состоит в том, что один из игроков просто посылает другому все свои данные, а тот использует свои неограниченные вычислительные способности, чтобы вычислить искомую функцию. Однако во многих важных примерах такое решение оказывается неоправданно дорогим и известны более эффективные решения.

Дата и время Название Место Материалы
18 мая
17:15–18:45
Лекция 1, лекция ПОМИ РАН видео
18 мая
19:00–20:30
Лекция 2, лекция ПОМИ РАН видео
19 мая
11:15–12:45
Лекция 3, лекция ПОМИ РАН видео
19 мая
13:00–14:30
Лекция 4, лекция ПОМИ РАН видео