МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО–МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи

УДК 519.71

Пивоваров Александр Павлович

НЕПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ

ИНФОРМАЦИОННОГО ПОИСКА

01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2012

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель доктор физико-математических наук, профессор Гасанов Эльяр Эльдарович

Официальные оппоненты:

Ложкин Сергей Андреевич доктор физико-математических наук, профессор факультет Вычислительной Математики и Кибернетики, МГУ имени М. В. Ломоносова Майлыбаева Гульнара Абаевна кандидат физико-математических наук Каргилл Энтерпрайзис Инк.

аналитик по инфраструктурной безопасности

Ведущая организация Московский энергетический институт (Национальный исследовательский университет)

Защита диссертации состоится 8 июня 2012 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механикоматематического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 25 апреля 2012 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, А.О. Иванов профессор

Общая характеристика работы

Актуальность темы. Диссертация посвящена исследованию задач информационного поиска и принадлежит важнейшему разделу дискретной математики и математической кибернетики теории управляющих систем. Задачи информационного поиска (ЗИП) один из наиболее часто встречающихся на практике видов задач. При написании практически любой программы для ЭВМ требуется решать те или иные задачи поиска. Постоянная необходимость решения таких задач привела к появлению множества специализированных структур данных и алгоритмов поиска. В книге Дональда Кнута “Искусство программирования для ЭВМ” 1, рассчитанной, в том числе, на инженеров, собраны некоторые из наиболее часто используемых на практике алгоритмов поиска и структур данных.

ЗИП могут иметь самую разную природу. Распространённый вид ЗИП геометрические задачи информационного поиска. В таких задачах в качестве объектов, хранящихся в базах данных, а также в качестве запросов выступают геометрические фигуры. В качестве примера таких задач можно привести задачу о метрической близости2, задачу о доминировании3, задачу интервального поиска4,5, задачу двумерного интервального поиска с фиксированной стороной6. В работе Шеймоса и Препараты7 собрано воедино множество разнообразных геометрических задач информационного поиска и подходов к их решению. Для задач информационного поиска, в которых возникает потребность в последовательном поиске одного и того же ключа в нескольких линейно упорядоченных множествах, оказывается полезным использование техники частичного каскадирования8, позволяющей снизить время поиска за счёт увеличения объёма требуемой памяти.

Важным параметром задач информационного поиска является возможность добавлять и удалять элементы из базы данных. По этому параметру задачи можно разделить на статические и динамические. Динамическим Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. – М.: Мир, 1978, 846 с.

Gasanov E. E. On Functional Complexity of Two-dimensional Manhattan Metrics Closeness Problem, Emerging Database Research In East Europe. Proceedings of the pre-conference workshop of VLDB 2003, 51-56.

JaJa J., Mortensen C. W., Shi Q. Space-Ecient and Fast Algorithms for Multi-dimensional Dominance Reporting and Counting, Proc. ISAAC (2004), 558-568.

Chazelle B. Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model. Journal of the ACM (1990), 200-212.

Willard D. E. Applications of the fusion tree method to computational geometry and searching. In Proceedings of the 3rd Annual ACM - SIAM Symposium on Discrete Algorithms (1992), 286-295.

McCreight E. M. Priority search trees. SIAM Journal of Computing (1985), 14(2), 257-276.

Препарата Ф., Шеймос М. Вычислительная Геометрия: Введение, Москва Мир, 1989, 478 с.

Chazelle B., Guibas L. J. Fractional cascading: I. A Data Structuring Technique, Algorithmica 1 (1986), 133-162.

задачам информационного поиска посвящены работы Овермарса9, Мортенсена10 и других авторов.

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

В диссертации автором исследуются другие варианты ЗИП, а именно ЗИП в смысле поиска представителя и вычислительные ЗИП (ВЗИП). Поиск представителя отличается от перечислительной ЗИП тем, что в такой задаче не требуется перечислять все записи базы данных, удовлетворяющие запросу, а требуется найти хотя бы одну такую запись, которая и называется представителем. Решение ВЗИП подразумевает вычисление некоторой интегральной характеристики множества записей БД, удовлетворяющих запросу. Это может быть, например, количество таких записей. Также возможен вариант, когда каждой записи БД приписан некоторый ранг и требуется вычислить, к примеру, максимальный ранг записей, удовлетворяющих запросу.

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

Цель работы. В диссертации ставится задача разработки моделей для неперечислительных задач информационного поиска, таких как задачи поиска представителя и вычислительные задачи информационного поиска.

Целью работы является исследование неперечислительных модификаций некоторых известных задач информационного поиска в рамках предOvermars M. H. The design of dynamic data structures, Ph. D. thesis, University of Utrecht, The Netherlands, 1983.

Mortensen C. W. Fully Dynamic Orthogonal Range Reporting on RAM. SIAM Journal of Computing (2006), 35(6), 1494-1525.

Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. ФИЗМАТЛИТ, Москва, 2002, 288 с.

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

Ставится задача оценить явно объём структур, получаемых с помощью техники частичного каскадирования в зависимости от различных параметров.

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

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

В работе получены следующие основные результаты.

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

2. Для задачи поиска представителя в задаче о метрической близости предложен алгоритм поиска с линейным от размера базы данных объемом памяти, логарифмическим временем поиска в худшем случае и константным временем поиска в среднем.

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

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

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

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

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

Апробация работы. Результаты настоящей работы докладывались • на научно-исследовательском семинаре кафедры Математической теории интеллектуальных систем механико-математического факультета МГУ Теория автоматов под руководством академика В. Б. Кудрявцева, 2009–2011 гг. (неоднократно);

• на семинаре механико-математического факультета МГУ Вопросы сложности алгоритмов поиска под руководством профессора Э. Э. Гасанова, 2008–2011 гг. (неоднократно);

• на семинаре механико-математического факультета МГУ Кибернетика и информатика под руководством академика В. Б. Кудрявцева, • на семинаре факультета ВМиК МГУ Дискретная математика и математическая кибернетика под руководством проф., д.ф-м.н.

В.Б.Алексеева, проф., д.ф-м.н. А.А.Сапоженко, проф., д.ф-м.н.

С.А.Ложкина, 2012 г.;

• на конференции Ломоносовские чтения (2008, 2011, 2012 гг.);

• на Международной конференции Современные проблемы математики, механики и их приложений, посвященной 70-летию ректора МГУ академика В.А.Садовничего (2009 г.);

• на Х Международном семинаре Дискретная математика и ее приложения (2010 г.);

• на X Международной конференции Интеллектуальные системы и компьютерные науки (2011 г.);

• на Международной конференции студентов, аспирантов и молодых ученых Ломоносов-2009, Ломоносов-2010 (2009, 2010 гг.).

Публикации по теме диссертации. Основные результаты диссертации опубликованы в пяти статьях [1][5] и материалах конференций [6][10], список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения и трех глав. Объем диссертации 103 стр. Список литературы содержит наименования.

Краткое содержание работы Первая глава диссертации посвящена модификации и исследованию информационно-графовой модели данных.

В разделе 1.1 даётся определение информационного графа общего вида (ИГОВ), используемого далее как основа для определения информационных графов (ИГ), вычислительных информационных графов (ВИГ) и упрощённых вычислительных информационных графов (УВИГ). Для ИГОВ доказывается теорема 1, предоставляющая один способ получения мощностных нижних оценок для ИГОВ.

Определение информационного графа общего вида Определим понятие информационного графа общего вида (ИГОВ). Для этого нам потребуются следующие множества: множество запросов X, множество F одноместных предикатов, заданных на множестве X, множество G одноместных переключателей, заданных на множестве X (переключатели это функции, область значений которых является начальным отрезком натурального ряда).

Пару F = F, G будем называть базовым множеством.

Определение ИГОВ с точки зрения его структуры.

Пусть нам дан ориентированный граф с выделенной вершиной, которую мы назовём корнем.

Выделим в графе некоторые вершины и назовём их точками переключения (корень может быть точкой переключения).

Если вершина графа, то через обозначим полустепень исхода вершины.

Каждой точке переключения сопоставим некий символ из G. Это соответствие назовём нагрузкой точек переключения.

Для каждой точки переключения рёбрам, из неё исходящим, поставим во взаимно однозначное соответствие числа из множества {1, }. Эти ребра назовём переключательными, а это соответствие нагрузкой переключательных рёбер.

Ребра, не являющиеся переключательными, назовем предикатными.

Каждому предикатному ребру сети сопоставим некоторый символ из множества F. Это соответствие назовем нагрузкой предикатных ребер.

Полученный нагруженный граф назовем информационным графом общего вида над базовым множеством F = F, G.

Определение функционирования ИГОВ.

Скажем, что предикатное ребро проводит запрос x X, если предикат, приписанный этому ребру, принимает значение 1 на запросе x; переключательное ребро, которому приписан номер n, проводит запрос x X, если переключатель, приписанный началу этого ребра, принимает значение n на запросе x; ориентированная цепочка ребер проводит запрос x X, если каждое ребро цепочки проводит запрос x; запрос x X проходит в вершину, если существует ориентированная цепочка, ведущая из корня в вершину, которая проводит запрос x.

Результатом функционирования ИГОВ на запросе x X считается набор вершин, в которые проходит запрос x.

Понятие ИГОВ определено.

Пусть – некоторая вершина ИГОВ. Тогда обозначим (x) предикат на X, такой что (x) = 1 для тех и только тех запросов x, которые проходят в вершину. Предикат (x) называется функцией фильтра вершины.

Переключатель g, приписанный переключательной вершине считаем вычисленным на запросе x, если запрос x проходит в вершину. Аналогично предикат f, приписанный некоторому ребру, выходящему из предикатной вершины, считаем вычисленным на запросе x, если запрос x проходит в вершину.

Сложностью ИГОВ U на запросе x назовем число T (U, x), равное сумме числа переключателей и предикатов, вычисленных в процессе обработки запроса x. Эту величину также называют временем работы U на запросе x. Верхней сложностью (или временем работы в худшем случае) называют величину T (U ) = maxxX T (U, x). В случае, когда на X введено вероятностное пространство, а переключатели и предикаты являются измеримыми функциями, с помощью действий, дословно совпадающих с описанными в монографии Гасанова и Кудрявцева, можно показать, что T (U, x) является случайной величиной относительно x и можно рассматривать T (U ) = Mx T (U, x) сложность ИГОВ U в среднем (или время работы U в среднем).

Объёмом Q(U ) ИГОВ U назовем число ребер в ИГОВ U.

Пусть X – некоторое множество запросов, Z – множество, которое мы будем называть множеством ответов и задана функция A : X Z. Нас будет интересовать случай, когда область значений функции A конечна.

Пусть дан ИГОВ U. Обозначим множество его вершин как W. Для любого запроса x X обозначим множество достижимых вершин U на этом запросе как W (x) = { W : (x) = 1}. Будем говорить, что U является допустимым для функции A : X Z, если существует такая функция B : 2W Z, что для любого x X выполнено B(W (x)) = A(x).

Теорема 1. Пусть X – множество запросов, Z – множество ответов и задана функция A : X Z. Пусть также задано некоторое базовое множество F = F, G и U – некоторый ИГОВ над F, допустимый для функции A.

1. Тогда для любого непустого множества X0 X выполнено:

пень исхода среди переключательных вершин U (но не менее 2), либо 2, если таких вершин нет.

2. Пусть относительно X задано вероятностное пространство и функция A и F измеримы относительно этого пространства, случае имеют место следующие оценки на сложность в среднем:

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

С точки зрения определения, задача поиска представителя не отличается от определения задачи информационного поиска в перечислительном смысле, вводимого в монографии Гасанова и Кудрявцева. Для полноты описания, мы повторим здесь это определение.

Пусть X множество запросов, Y множество записей, бинарное отношение на X Y называемое отношением поиска. Тройку S = X, Y, будем называть типом задач информационного поиска. Тройка I = X, V,, где V – конечное подмножество Y (называемое в дальнейшем библиотекой) называется задачей информационного поиска (ЗИП) типа S (пишем I S). Пусть задана некоторая ЗИП I = X, V,. Введём функцию JI (x) : X 2V, заданную соотношением JI (x) = {y V | x y}.

Эту функцию будем называть функцией ответа на запрос для задачи I.

Описывать алгоритмы решения задач поиска представителя предлагается также с помощью обычных информационных графов (ИГ). Здесь мы приведём определение понятия ИГ, однако сделаем это с использованием информационных графов общего вида.

Пусть F некоторое множество предикатов, определённых на X, а G некоторое множество переключателей, определённых на X. Будем называть пару F = F, G базовым множеством для ИГ.

Определим ИГ над базовым множеством F = F, G следующим образом. Будем называть информационным графом (ИГ) такие графы U, что U, во-первых, является ИГОВ над базовым множеством F, G, во-вторых, выделено некоторое множество вершин U, называемых листьями и каждому листу приписана некоторая запись из Y. Объём и сложность в среднем и худшем случаях для ИГ считаются так же, как и для ИГОВ.

Определим функционирование ИГ. Будем считать ответом графа U на запрос x множество записей JU (x), состоящее из тех и только тех записей y Y, что в U есть лист, которому приписана запись y и при этом запрос x проходит в этот лист.

При этом для перечислительных задач требовалось равенство JI (x) = JU (x) для всех x X. Если же рассматривать задачу I как задачу поиска представителя, то определение графа решающего задачу меняется: граф U решает задачу поиска представителя для I, если выполнены следующие условия: JU (x) JI (x) и JI (x) = JU (x) =.

Раздел 1.3 содержит определение вычислительной задачи информационного поиска (ВЗИП), определение УВИГ и ВИГ. Для модельной задачи одномерного интервального поиска в смысле подсчёта доказываются теоремы 2 и 3, с помощью которых обосновывается необходимость введения ВИГ.

Формализация вычислительных задач информационного поиска Дадим строго определение вычислительной задаче информационного поиска (ВЗИП). Пусть X множество запросов, Y множество записей, бинарное отношение на X Y называемое отношением поиска.

Пусть также задано множество Z, которое мы будем называть множеством ответов. Наконец, задана функция : 2Y Z функция отвеY та, определённая на 2 – множестве подмножеств Y (достаточно, чтобы была определена для всех конечных подмножеств Y ). Будем называть пятерку S = X, Y, Z,, типом вычислительных задач информационного поиска. Пятерка I = X, V, Z,,, где V – конечное подмножество Y (называемое в дальнейшем библиотекой) называется вычислительной задачей информационного поиска (ВЗИП) типа S (пишем I S). Фактически задача I = X, V, Z,, состоит в том, чтобы для заданного запроса x X найти такой ответ z Z, что z = ({y V : x y}). Будем обозначать этот ответ как zI (x) = ({y V : x y}) и называть правильным ответом для ВЗИП I на запрос x.

Определение упрощённого вычислительного информационного графа (УВИГ).

Пусть F некоторое множество предикатов, определённых на X, а G некоторое множество переключателей, определённых на X. Пусть Z некоторое множество. Будем называть тройку F = F, G, Z базовым множеством для УВИГ.

Определим УВИГ над базовым множеством F = F, G, Z следующим образом. Будем называть упрощённым вычислительным информационным графом (УВИГ) такие графы U, что U, во-первых, является ИГОВ над базовым множеством F, G, во-вторых, выделено некоторое множество вершин U, называемых листьями и каждому листу приписан некоторый элемент множества Z. Объём и сложность в среднем и худшем случаях для УВИГ считаются так же, как и для ИГОВ.

Определим функционирование УВИГ. Элемент z Z, приписанный листу некоторого УВИГ U будем считать ответом U на запрос x X, если запрос x проходит в лист. Этот ответ z обозначим как zU (x) и будем называть функцией ответа УВИГ U. В случае, если запрос x проходит в два листа 1 и 2, которым приписаны ответы z1 и z2 соответственно и при этом z1 = z2, то считаем, что zU (x) не определено. Также zU (x) не определено в случае, если x не проходит ни в один лист УВИГ U.

Будем говорить, что некоторый УВИГ U над базовым множеством F = F, G, Z решает ВЗИП I = X, V, Z,,, если для любого запроса x X функция ответа УВИГ zU (x) определена и равна значению zI (x).

Определение вычислительного информационного графа (ВИГ).

Пусть, как и ранее, F некоторое множество предикатов, определённых на X, а G некоторое множество переключателей, определённых на X.

Пусть M некоторое множество, которое мы будем называть множеством состояний ВИГ и m0 некоторый выделенный элемент M, который мы будем называть начальным состоянием. Пусть дополнительно определено множество H функций изменения состояния вида h : M M, такое, что любые две функции из H коммутируют относительно операции суперпозиции. Пусть, наконец, определено множество ответов Z и функцию вычисления ответа по состоянию : M Z. Будем называть шестерку F = F, G, H, M, m0, базовым множеством для ВИГ.

Определим ВИГ над базовым множеством F = F, G, H, M, m0, следующим образом. Будем называть вычислительным информационным графом (ВИГ) такие графы U, что U, во-первых, является ИГОВ над базовым множеством F, G, во-вторых, выделено некоторое множество вершин U, называемых листьями и каждому листу приписан некоторый элемент множества H. Объём и сложность в среднем и худшем случаях для УВИГ считаются так же, как и для ИГОВ.

Определим функционирование ВИГ. Пусть есть некоторый ВИГ U над базовым множеством F = F, G, H, M, m0,. Рассмотрим запрос x X.

Пусть 1,..., p – это все листья, в которые проходит запрос x и этим листьям приписаны функции h1,..., hp H соответственно. Назовем состояние mU (x) = h1 · · · hp (m0 ) финальным состоянием ВИГ U на запросе x.

Если запрос x не проходит ни в один лист, положим mU (x) = m0. Будем называть zU (x) = (mU (x)) функцией ответа ВИГ U.

Как и для УВИГ, будем говорить, что некоторый ВИГ U над базовым множеством F = F, G, H, M, m0, решает ВЗИП I = X, V, Z,,, если для любого запроса x X функция ответа ВИГ zU (x) равна значению zI (x).

Объёмная сложность вычислительных задач поиска Пусть задана некоторая ВЗИП I = X, V, Z,,. Пусть задано некоторое базовое множество для УВИГ F = F, G, Z. Обозначим U uvig (I, F) множество всех УВИГ над базовым множеством F, которые решают задачу I.

Обозначим UD (I, F) множество всех древовидных УВИГ над базовым множеством F, которые решают задачу I. Объёмной сложностью задачи I при базовом множестве F назовем число Число назовем древовидной объёмной сложностью задачи I при базовом множестве F.

Если k натуральное число, S тип вычислительных задач информационного поиска, то обозначим Будем исследовать функцию Шеннона, характеризующую объёмную сложность (либо древовидную объёмную сложность) класса ВЗИП I(k, S):

Аналогичные функции Qvig (k, S, F) и Qvig (k, S, F) введем и для ВИГ – с той лишь разницей, что использоваться должны базовые множества для ВИГ F = F, G, H, M, m0,.

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

Рассмотрим множество предикатов Fint1 и переключателей Gint1, заданные следующим образом: Fint1 = f id (x) 1, Gint1 = G1 G2, Теорема 5. Пусть дана задача I = [0, 1]2, V, R S R. Если вероятностная мера на X задаётся ограниченной функцией плотности вероятности c, то для любого m N : 1/m < R/2 существует ИГ U над баp(x) зовым множеством F R, решающий задачу поиска представителя для I, удовлетворяющий условиям:

Следствие 5.1. Если последовательность Rk удовлетворяет условию = o log kk, то для последовательности задач Ik = [0, 1]2, V, k, где |V | = k, существует последовательность ИГ Uk, решающих соответствующие задачи поиска представителя, такие, что выполнено:

Третья глава диссертации посвящена вычислительным задачам информационного поиска.

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

Под расширенными действительными числами будем понимать элементы множества R = R{, +}. Каталогами будем называть неубывающие последовательности расширенных действительных чисел. Например, последовательность, 5, 0, 0, 7, +, + – каталог из семи элементов. Один каталог будем называть подкаталогом другого, если он как последовательность является подпоследовательностью второго. Каталог 5, 7, +, + – подкаталог указанного выше каталога. Пусть C – каталог. Тогда каталог, получающийся из него удалением дубликатов будем обозначать U (C). Например, если C =, 5, 0, 0, 7, +, +, то U (C) =, 5, 0, 7, +.

сов p = (i, j), такую что 1 i n, 1 j m будем называть переходом между каталогами C и D, если ci = dj. Про элементы ci и dj будем говорить, что они принадлежат переходу p. Для удобства будем называть некоторый переход x-переходом, если значение соединяемых этим переходом элементов равно x. Последовательность переходов B = {pk = (ik, jk )}s где s 2 будем называть мостом если номера элементов и в первом и во втором каталоге строго возрастают.

Будем говорить, что элемент ci каталога C принадлежит k-му ярусу моста B (1 k s1) в том случае, если ik < i < ik+1. Очевидно, каждый элемент каталога C принадлежит не более чем одному ярусу моста B, но может не принадлежать ни одному ярусу если для него выполнено одно из условий: элемент принадлежит одному из переходов моста, либо элемент лежит выше верхнего перехода моста, либо элемент лежит ниже нижнего перехода моста. Аналогично, будем говорить, что элемент dj каталога D принадлежит k-му ярусу моста B, если jk < j < jk+1.

Шириной k-го яруса моста B будем называть суммарное количество элементов в каталогах C и D, принадлежащих k-му ярусу моста B. Шириной моста B будем называть максимальную ширину некоторого яруса данного моста. Отрезок [ci1, cis ] (= [dj1, djs ]) будем называть отрезком покрытия моста B.

Графом каталогов будем называть тройку L = (G, C, R), где G = (V, E) – граф без петель и кратных ребер (V – множество вершин графа G, а E множество рёбер G), C = {Cv }vV – набор каталогов, поставленных в соответствие вершинам G, R = {Re }eE – набор отрезков Re = [ae, be ] (ae, be R и ae < be ), поставленных в соответствие рёбрам G. Локальной степенью вершины v графа каталогов L = (G, C, R) будем называть величину d(v) = maxxR |{e E : v e, x [ae, be ]}|. Локальной степенью графа каталогов L = (G, C, R) будем называть величину d(L) = maxvV d(v).

Как видно из определения, локальная степень графа каталогов зависит только от G и R, но не зависит от C.

Системой мостов будем называть четвёрку S = (G, A, R, B), где (G, A, R) образуют граф каталогов (A = {Av }vV – некоторый набор каталогов), а B = {Be }eE – набор мостов, такой что выполнены условия:

для любого ребра {v, w} = e E мост Be является мостом между каталогами Av и Aw, либо между каталогами Aw и Av ; для любого ребра e E отрезок покрытия моста Be равен отрезку Re ; для любого x R каждый мост из B содержит не более одного x-перехода.

Систему мостов S = (G, A, R, B) будем называть строгой, если каждый элемент любого каталога Av, приписанного любой вершине v V, либо не принадлежит ни одному переходу ни одного моста из B, либо принадлежит только одному переходу одного моста из B; Некоторый элемент каталога Av будем называть свободным в том случае, если он не принадлежит ни одному переходу ни одного моста из B. Шириной системы мостов S = (G, A, R, B) будем называть максимальную ширину моста среди B. Система мостов S = (G, A, R, B) называется согласованной с графом каталогов L = (G, C, R) если для любого v V каталог U (Cv ) является подкаталогом Av.

Теорема 6. Пусть имеется граф каталогов L = (G, C, R), где G = (V, E) и |V | = n, |E| = m. Пусть d = d(L) – локальная степень графа каталогов L. Пусть зафиксирован нечётный натуральный параметр g0 4d+1.

Тогда существует строгая система мостов S = (G, A, R, B), согласованная с графом каталогов L и при этом выполнены следующие условия:

(а) ширина системы мостов S не превосходит параметра g0 ;

(б) имеет место неравенство vV |Av | (1 + c)( vV |U (Cv )| + 4m), (в) для любого v V значение каждого из элементов Av либо равно значению некоторого элемента из Cw для некоторого w V, либо равно нижнему или верхнему концу некоторого отрезка R R;

(г) суммарное количество свободных элементов во всех каталогах A в точности равно vV |U (Cv )|.

Следствие 6.1. Пусть выполнены условия теоремы 6. Тогда существует система мостов S = (G, A, R, B) (уже не обязательно строгая), согласованная с графом каталогов L и при этом выполнены следующие условия:

(а) ширина системы мостов S не превосходит параметра g0 ;

(б) имеет место неравенство vV |Av | (1 + c)( vV |U (Cv )| + 4m), (в) для любого v V значение каждого из элементов Av либо равно значению некоторого элемента из Cw для некоторого w V, либо равно нижнему или верхнему концу некоторого отрезка R R;

(г) любой каталог Av содержит не более одной записи с некоторым Если к тому же все отрезки Re R равны между собой, то имеет место слегка изменённое ограничение на суммарное количество записей во всех каталогах: vV |Av | (1 + c) vV |U (Cv )| + 2n + 4mc.

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

Пусть I некоторая вычислительная задача информационного поиска, F некоторое базовое множество для ВИГ. Будем обозначать как U(I, F) множество ВИГ над базовым множеством F, решающих задачу I. Сложностью задачи I при базовом множестве F и объёме q назовём число T (I, F, q) = min{T (U ) : U U(I, F) и Q(U ) q}, где T (U ) – сложность U в худшем случае, а Q(U ) – объём U. Если нет таких ВИГ U U(I, F), у которых Q(U ) число, S = X, Y, Z,, – тип вычислительных задач информационного поиска. Введём следующее обозначение: I(k, S) = {I = X, V, Z,, S : |V | = k}. Таким образом, I(k, S) – множество всех ВЗИП типа S, база данных которых содержит ровно k элементов.

Наконец, введём величину T (k, S, F, q) = maxII(k,S) T (I, F, q), характеризующую максимальную сложность задач типа S с базой данных из k элементов при решении её вычислительными информационными графами над F и объём которых не превышает q.

Пусть Z = (Z, ) – коммутативная полугруппа с нулём. Операцию ных задач информационного поиска Sdom2 = Xdom2, Ydom2, Z, dom2, dom2, где Xdom2 = [0, 1]2, Ydom2 = [0, 1]2 Z, отношение поиска dom2 определено таким образом, что для любых x = (x1, x2 ) Xdom2 и y = (y1, y2, y ) Ydom соотношение x dom2 y справедливо тогда и только тогда, когда одновременно выполнены условия x1 y1 и x2 y2. Элементы множества записей Y можно рассматривать как точки на плоскости, которым дополниZ тельно приписаны веса из Z. Функция ответа dom2 : 2Y Z определена на конечных подмножествах множества Y следующим образом (значение на бесконечных подмножествах Y определять не требуется): пусть V = дельно определим dom2 () равным нейтральному элементу Z.

шения задач типа Sdom2 будем строить над базовым множеFdom2 = Fdom2, Gdom2, HZ, MZ, mZ, id.

f a : a [0, 1], i {1, 2}, где для любого x = (x1, x2 ) X значение f i a (x) равно 1 тогда и только тогда, когда xi a. Предикат f 0, значение которого равно 1 на любом запросе x, будем называть тождественно единичным предикатом. Множество пе-