Название спецкурса на русском языке
Коммуникационная сложность
Перевод названия курса на английский язык
Communication complexity
Авторы курса
Верещагин Николай Константинович
Целевая аудитория
3 курс
4 курс
5 курс
6 курс
Магистранты
Аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору студента
Учебный год
2022/23
День недели
четверг
Время
18:30-20:05
Формат проведения
Дистанционно
Аудитория
[Дистанционно]
Аннотация
Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может, поскольку у каждого из них недостаточно данных. Например, у одного из них имеется файл x, у другого файл y и нужно узнать, совпадают ли x и y. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание - в этом принципиальное отличие
от теории сложности вычислений.
Предварительные знания: знакомство с линейной алгеброй в объеме одного семестра и с началами теории вероятностей.