Тестирующие и потоковые алгоритмы для слов, деревьев и графов. Лекция 1

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