Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.
Дополнительные материалы
Содержание лекций: PDF
Конспект лекций: PDF
Вопросы к экзамену: PDF
Доказательство верхней оценки безошибочной сложности предиката дизъюнктности: PDF
| 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 |
