О сложности интервального поиска на булевом кубе

• Автор: Блайвас, Татьяна Дмитриевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 102 с.

1. Общая характеристика работы
2. Содержание работы
3. Публикации по теме дисертации
1 Класс сбалансированных деревьев
1.1 Оптимальное решение над базисом элементарных конъюнкций
1.1.1 Построение оптимальных деревьев
1.1.2 Порядок сложности сбалансированных деревьев
1.1.3 Асимптотики в классе сбалансированных схем
1.2 Оптимальное решение над базисом переменных
1.2.1 Построение оптимальных сбалансированных деревьев
1.2.2 Порядок сложности в классе сбалансированных деревьев
1.2.3 Асимптотики в классе сбалансированных деревьев
1.2.4 Случай произвольного отношения поиска
1.3 Случай взвешенных базисов
1.3.1 Критерий допустимости системы весов
1.3.2 Построение оптимального сбалансированного дерева
1.3.3 Порядок сложности оптимальных деревьев
2 Функция Шеннона сложности в классе древовидных схем
2.1 Нижняя оценка
2.2 Верхняя оценка
2.3 Оценки функции Шеннона
3 Алгоритмы построения решающих деревьев
3.1 Описание алгоритмов
3.1.1 Алгоритм с жестким порядком проверок (А1)
3.1.2 Алгоритм первого пересечения (А2{у>о))
3.1.3 Жадный алгоритм (АЗ(У,<т))
3.1.4 Сравнительный анализ алгоритмов
3.2 Средняя сложность алгоритма с жестким порядком проверок
(А1)
3.2.1 Вспомогательные утверждения
3.2.2 Доказательство теоремы

3.3 Средняя сложность алгоритма первого пересечения (А2)
3.3.1 Вспомогательные утверждения
3.3.2 Доказательство теоремы
Список литературы
1. Общая характеристика работы
Актуальность темы. В связи с постоянным расширением области компьютерных технологий, одним из актуальных направлений дискретной математики и математической кибернетики являются проблемы оптимизации, хранения и поиска информации.
Все возрастающий поток информационновычислительных работ требует дальнейшего совершенствования методов проектирования и разработки баз данных и поисковых систем. Решение этих задач невозможно без тщательного анализа накопленного опыта, построения математической модели баз данных и информационных систем. Исследование математической модели помогает решать задачи, позволяющие повысить эффективность поиска в базах данных. В работах [5, 22, 29, 30, 39, 53, 13] вводились различные формализации информационно-поисковых систем. В данной работе используется информационно-графовая модель, предложенная в [13]. Такая модель данных может найти применение при проектировании физической организации баз данных, а также при разработке интегральных схем, обеспечивающих аппаратную реализацию быстрых алгоритмов поиска.
В данной работе используется такое понимание задачи поиска, при котором предполагается многократное обращение к одним и тем же данным, но, возможно, каждый раз с новыми требованиями к искомым объектам, то есть с разными запросами на поиск. Такие задачи обычно возникают в системах, использующих базы данных. Многократное использование порождает особую проблему — проблему специальной организации данных, направленной на последующее ускорение поиска. Процесс такой специальной организации данных может занимать много времени, что потом окупается в результате многократности поиска. Ценность алгоритма поиска в таком случае определяется варьированием запроса на поиск, например, показателем может служить среднее время поиска на запросе. Классификацию задач поиска на однократные и многократные можно найти в работах [51, 27, 13].
Пусть задано некоторое упорядоченное множество X. На множестве Хп определим отношение частичного порядка следующим образом: если а, Ь Є Хпу а = (аі ап), Ь = (&і 6п), то будем писать а ^ Ь ("а предшествует Ь"), если а* < Ь{ для любого і = 1 п. Если V С Хп,
Сбалансированные дереъя в случае взвешенных базисов
Значит
Т(а', Л + 1) — Т(а,h) = +
h 2skr + 2k
2 + зк
h Is кт k(

= Q) *r^ + 2e-3-3(e-l)(|) j
= ^ (!) Л ((2Л - 1} + (е - 15 (2 - 3 (|)”“Л_1) ) ,
и Т(а h +1) — Т{а, К) -* 0 при є -> 1.
Лемма 24 доказана. □
Лемма 25. Для любых фиксированных п, к, (*2 < $, I G Т{п, к), функция T(a,h(a)) = T(I,Fg), где h(a) — характеристика оптимального дерева, решающего ЗИП I, является непрерывной возрастающей функцией от а на множестве W(n, 1, |).
Доказательство. Пусть а = (вц,. ..,<*») и а1 = (c*i aJJ допустимые системы весов, такие, что а* < aj, щ — аг (§)* 2 + Зт ^1 — (|)* 2j, а
а2 (§)* 2 -Ь Зт*' (l — (§)* 2)> Для всех і = 1,... ,п. По лемме 23 Т* = а< и Т* = qJ ДЛЯ любого І. Пусть т' = Т • Є, X;f — * Є2> где Є -* 1 + , Є2 -> 1 +
Возьмем номер h такой, что выполнено h = Jtog2 * {^g-h+i ~~ з-^п-л))] * Возможны два случая.
1) Интервал
(tag, (Щг (Т«1Л - |Г“1л_г)) - l;log2 (g% (Г“1Л+1 - !Г“1Й)))
содержит номер Л. Тогда
T(a',h)-T(a,h) = Ц. (|) *(зу'_ З?)+(|)*. *.(3^,-3»*)-= f (^ет'-Г2“) + з(і-(|)"") (т'-т)
= y(J) ^-l) + 3r (l-(f) )(в-1)-Ю + .
To есть в окрестности точки а функция непрерывно возрастает.
2) Интервал
[bg2 (# (г„“1л - !Т“1Л_Х)) - 1; log2 (g% (г“1д+1 - |Т“1Л))] не содержит номер h. Заметим, что
l°g2 (тХ-і, ~ - 1 = log2 - 1,