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

Тестирование на монотонность 2 (Александр Логунов)
Семинар по сублинейным алгоритмам

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

Описание

На этом докладе будут обобщаться результаты предыдущего доклада.

А именно, мы выясним, что задачу тестирования на монотонность функций из множества $[m]^l$ (оно же множество одномерных кубиков в $l$-мерном гиперкубе со стороной $m$) можно запросто свести к той же задаче при $m=2$. Кроме того, окажется (при некоторых предположениях), что алгоритм, с хорошей вероятностью находящий немонотонные булевы функции, неплохо работает и на функциях с произвольным множеством значений.