Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

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


Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

Занятия

Дата Время Название Место Материалы
25.03.2017 17:20–18:50 Лекция 1 ПОМИ РАН Лекция Нет
25.03.2017 19:10–20:40 Лекция 2 ПОМИ РАН Лекция Нет
26.03.2017 11:15–12:45 Лекция 3 ПОМИ РАН Лекция Нет
26.03.2017 13:00–14:30 Лекция 4 ПОМИ РАН Лекция Нет
26.03.2017 15:30–17:00 Лекция 5 ПОМИ РАН Лекция Нет
01.04.2017 17:20–18:50 Лекция 6 ПОМИ РАН Лекция Нет
01.04.2017 19:10–20:40 Лекция 7 ПОМИ РАН Лекция Нет
02.04.2017 11:15–12:45 Лекция 8 ПОМИ РАН Лекция Нет
02.04.2017 13:00–14:30 Лекция 9 ПОМИ РАН Лекция Нет
02.04.2017 15:30–17:00 Лекция 10 ПОМИ РАН Лекция Нет