Аннотация:В работе исследуются алгоритмы поиска, используемые в фоновом
режиме, и предлагается математическая модель этих алгоритмов,
опирающаяся на понятие информационного графа. В работе также
предлагается фоновый алгоритм решения двумерной задачи о
доминировании с линейными затратами по памяти и константным в
среднем временем поиска. Для сравнения отметим, что нефоновый
алгоритм, среднее время поиска которого равно константе плюс
среднее время перечисления ответа, требует квадратичных затрат по
памяти.