#матлог #учёба #спецкурс

Полугодовой спецкурс для 3-6 курсов, магистрантов и аспирантов
"Коммуникационная сложность" будет читаться проф. Н.К. Верещагиным по вторникам в 18:30-20:05 в ауд. 407 второго уч. корпуса.

Первая лекция — 17 февраля.

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

Предварительные знания: знакомство с линейной алгеброй в объеме одного семестра и с началами теории вероятностей.

Телеграмм канал: https://t.me/+9G993a4ym640ZTVi (там есть ссылка на подробную программу)

➰ ВК