Введение (Николай Карпов)
Семинар по сублинейным алгоритмам


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

Описание

Мотивация и направления исследований в области сублинейных алгоритмов. Определение задачи приближенного решения и модели в которой мы будем работать. Классификация тестеров. Примеры задач и метрик между объектами. Примеры алгоритмов для задачи проверки монотонности функции, подсчета числа единиц в строке. Примеры нижних оценок на алгоритмы. Базовые вероятностные факты.