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

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

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

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

Дополнительные материалы

Содержание лекций: PDF

Конспект лекций: PDF

Вопросы к экзамену: PDF

Доказательство верхней оценки безошибочной сложности предиката дизъюнктности: PDF

Видео лекций: https://www.lektorium.tv/course/22755
Дата и время Занятие Место Материалы
28 февраля
10:25–11:55
Лекция 1, Лекция ПОМИ РАН видео
28 февраля
12:00–13:30
Лекция 2, Лекция ПОМИ РАН видео
01 марта
10:25–11:55
Лекция 3, Лекция ПОМИ РАН видео
01 марта
12:00–13:30
Лекция 4, Лекция ПОМИ РАН видео
01 марта
14:00–15:30
Лекция 5, Лекция ПОМИ РАН Нет
07 марта
10:25–11:55
Лекция 6, Лекция ПОМИ РАН видео
07 марта
12:25–13:55
Лекция 7, Лекция ПОМИ РАН видео
08 марта
10:25–11:55
Лекция 8, Лекция ПОМИ РАН видео
08 марта
12:25–13:55
Лекция 9, Лекция ПОМИ РАН видео
08 марта
14:00–15:30
Лекция 10, Лекция ПОМИ РАН видео