Spot-Checkers (Никита Гаевой)
Семинар по сублинейным алгоритмам


Что: Лекция
Когда: Пятница, 16 декабря 2016, 19:00–20:20
Где: ПОМИ РАН, аудитория 106

Описание

Spot-Checkers - это разновидность тестеров, проверяющих корректность работы программы. Более формально, spot-checker для функции \(P\) - алгоритм, принимающий вход \(x\) и \(f(x)\) и тестирующий близость \(f(x)\) к \(P(x)\) за сублинейное от \(|x| + |f(x)|\) время.

На докладе мы разберем spot-checkers для некоторых из следующих задач: sorting, convex hull, element distinctness, set containment, set equality, total orders, and group and field operations.