ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
1997, ТОМ 3, ВЫПУСК 3, СТР. 759-773

Об одной математической модели фоновых алгоритмов поиска и быстрый фоновый алгоритм двумерной задачи о доминировании

Э. Э. Гасанов
Т. В. Мхитарова

Аннотация

Посмотреть как HTML    Посмотреть как рисунок    Посмотреть в формате LaTeX

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

Постскрипт статьи (60 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/97/973/97308h.htm
Изменения вносились 20 января 2000