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

Параллельное вычисление совершенного паросочетания, лемма изоляции
Рандомизированные алгоритмы

Что: Лекция
Когда: Среда, 28 апреля 2021, 18:10–19:45
Где: НГУ, ауд. 5210, НГУ, новый корпус

Описание

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

Мы также увидим последствие леммы изоляции для теории сложности вычислений. А именно, что предположение, что существует только одно решение задачи, как правило не упрощает её.