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