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

Курс «Коммуникационная сложность». Полугодовой спецкурс по выбору кафедры

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


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

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

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

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

Лекции состоятся по понедельникам 18:30-20:05, ауд. 16-04. Первая лекция 11 сентября.

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

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

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

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


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

Посещавшие лекции и желающие сдать экзамен должны решить вот эти задачи.

Лекции состоятся по понедельникам 18:30-20:05, ауд. 16-04.

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

2009 год

Осенью 2009 года лекции состоялись по понедельникам 18:30-20:05, ауд. 14-14.

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

Программа экзамена

Доказательство верхней оценки вероятностной сложности предиката DISJ PDF