City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Communication Complexity
Saint Petersburg / spring 2009, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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

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

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

Видео лекций: https://www.lektorium.tv/course/22755
Date and time Class|Name Venue|short Materials
28 February
10:25–11:55
Лекция 1, Lecture ПОМИ РАН video
28 February
12:00–13:30
Лекция 2, Lecture ПОМИ РАН video
01 March
10:25–11:55
Лекция 3, Lecture ПОМИ РАН video
01 March
12:00–13:30
Лекция 4, Lecture ПОМИ РАН video
01 March
14:00–15:30
Лекция 5, Lecture ПОМИ РАН No
07 March
10:25–11:55
Лекция 6, Lecture ПОМИ РАН video
07 March
12:25–13:55
Лекция 7, Lecture ПОМИ РАН video
08 March
10:25–11:55
Лекция 8, Lecture ПОМИ РАН video
08 March
12:25–13:55
Лекция 9, Lecture ПОМИ РАН video
08 March
14:00–15:30
Лекция 10, Lecture ПОМИ РАН video