Город: Санкт-Петербург Казань Язык: Русский English

Тестирующие и потоковые алгоритмы для слов, деревьев и графов
Санкт-Петербург / весна 2019, посмотреть все семестры

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

Проверяющим алгоритмом называется вероятностный алгоритм, который может отличить объект, удовлетворяющий некоторому свойству, от объекта, который далек от любой другого объекта с таким свойством, и при этом делает лишь небольшое (константное или сублинейное) число запросов к объекту. Примеры: проверка линейности функции, проверка соответствия строки регулярному выражению, проверка 3-раскрашиваемости графа. Потоковые алгоритмы читают входные данные и определяют их свойства, не храня сами данные в памяти. Мы рассмотрим классические примеры — в частности, задачу обнаружения кластеров в графе, заданном как поток рёбер. Мы также построим проверяющие потоковые алгоритмы.

Дата и время Название Место Материалы
24 мая
18:00–19:30
Лекция, лекция ПОМИ РАН Нет
24 мая
19:30–21:00
Лекция, лекция ПОМИ РАН Нет