Кафедра математической логики и теории алгоритмов

Коммуникационная сложность

Полугодовой спецкурс для студентов и аспирантов мехмата МГУ

2022 год, осенний семестр

Лектор: Н.К. Верещагин

 

Лекции проходят по четвергам 18:30 — 20:05 онлайн. Первая лекция — 6 октября. Ссылка на Zoom: https://us06web.zoom.us/j/84630363941?pwd=VGVxUGMzUXBzUUJxZTdpWkFHQ0taZz09


Программа курса

Посещавшие лекции и желающие сдать экзамен должны решить вот эти задачи в указанные сроки (скопируйте эту ссылку на Dropbox, поскольку сайт кафедры часто падает). Сдача задач после срока возможна, но в этом случае баллы за решение учитываются с коэффициентом 0.5.

Оценки за решения домашних задач

Оценки за курс (при условии посещения не менее 7 лекций):
отлично — 80% от максимального количества баллов,
хорошо — 62%, удовлетворительно — 45%. Зачет — 50%.

 

Дневник лекций

Конспект теоремы о верхней оценке вероятностной безошибочной сложности предиката DISJnk

Конспект теоремы о нижней оценке вероятностной сложности предиката DISJ