City: Saint-Petersburg Kazan Language: Русский English

Testing and Streaming algorithms for words, trees and graphs
Saint-Petersburg / spring 2019, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

Date and time Class|Name Venue|short Materials
24 May
18:00–19:30
Лекция, lecture ПОМИ РАН No
24 May
19:30–21:00
Лекция, lecture ПОМИ РАН No