Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ІКФОРМАЦІОНИО-ГРАФОВАЯ МОДЕЛЬ ДАНИХ

Якщо розглянута в попередньому розділі реляційна модель даних є моделлю логічного організації даних, що описує базу даних з точки зору користувача, то пропонована в цьому розділі модель даних, призначена для дослідження фізичної організації даних, тобто представлення даних на фізичних носіях. Ця модель даних називається інформаційно-графовой і була розроблена другим з авторів.

Критерії, що визначають вибір фізичної організації, відрізняються від тих, які визначають вибір логічної організації даних. При виборі фізичної організації вирішальним фактором є ефективність, причому відповідно до Дж. Мартіна [40] на першому місці стоїть забезпечення ефективності пошуку, далі йдуть ефективність операцій занесення і видалення і потім забезпечення компактності даних.

На першому кроці нам необхідно ввести поняття завдання інформаційного пошуку.

У поняття завдання пошуку дослідники вкладають по крайней міряю 3 різних сенсу.

Фахівці в теорії дослідження операцій розуміють завдання пошуку як завдання управління зближенням однієї системи (пошукової) з іншого (шуканим об'єктом) за неповною апріорної інформації. Розуміється, що мета пошуку - це виявлення шуканого об'єкта, яке визначається як виконання певних термінальних умов. Інтенсивно проблемою пошуку рухомих об'єктів почали займатися в період Другої світової війни. Інтерес до цієї проблеми в той період був викликаний необхідністю розробки тактики боротьби проти підводних човнів. Серед робіт, присвячених цій тематиці, можна виділити, наприклад, роботи О. Хеллмана [61] і Д. П. Кіма [21].

Інше розуміння завдань пошуку можна знайти в книзі Р.Аль- сведе, І.Вегенера "Завдання пошуку" [2]. Наведемо пояснює приклад з цієї книги.

Під час Другої світової війни все призиваються в армію США піддавалися перевірці на реакцію Вассермана. При цьому перевірялося, чи є в крові обстежуваного певні антитіла, наявні тільки у хворих. Під час цього масового обстеження було помічено, що розумніше аналізувати пробу крові цілої групи людей. Якщо така об'єднана проба крові не містить антитіл, то, значить, жоден із обстежених не хворий. В іншому випадку серед них є хоча б один хворий. Хороший алгоритм пошуку для цього завдання - це той, який для типової вибірки людей дозволяє 11 найшвидшим образом "виявляти безліч всіх хворих.

Інший приклад ми знаходимо в статті Д.Лі, Ф.Препарати "Обчислювальна геометрія" [36]. Дано безліч горизонтальних і вертикальних відрізків. Треба знайти всі точки перетину відрізків.

Ці два приклади об'єднує те, що в обох випадках пошук проводиться одноразово. Це породжує свої особливості таких завдань пошуку. Як правило, дані в цих завданнях не мають складної організації. Фіксація безлічі, в якому проводиться пошук, однозначно визначає безліч знайдених об'єктів. "Гарності" алгоритму пошуку визначається при варіюванні безлічі, в якому проводиться пошук.

У третьому розумінні завдання пошуку передбачається багаторазове звернення до одних і тих же даних, але можливо кожен раз з різними вимогами до шуканим об'єктам, тобто з різними запитами на пошук. Такі завдання пошуку зазвичай виникають в системах, що використовують бази даних. Багаторазове використання породжує особливу проблему - проблему спеціальної організації даних, спрямованої на подальше прискорення пошуку. Процес такої спеціальної організації даних, що проводиться до того, як здійснюється пошук, називається передобробці і часто може займати дуже великий час, яке потім окупається сторицею в результаті многократности пошуку. Найпростішим прикладом предобработки є сортування. Побудова "хорошого" алгоритму пошуку в цьому випадку зводиться до знаходження хороших структур даних, тобто до здійснення такої гарної предобработки даних, яка забезпечила б хорошу швидкість пошуку. "Гарності" алгоритму пошуку в цьому випадку визначається варіюванням запиту на пошук, наприклад, як середній час пошуку на запит.

Залежно від того, чи є база даних фіксованої або змінюється протягом часу роботи з нею, ми маємо два типи організації баз даних: статичну і динамічну відповідно.

Завдання пошуку, що виникають в статичних базах даних і передбачають багаторазове звернення до одних і тих же даних, і є об'єктом дослідження даного розділу.

Наведемо приклади таких завдань пошуку.

Найпростішим і найпоширенішим прикладом завдання пошуку, зустрічається в будь-якій базі даних, є завдання пошуку по ключу. Суть її полягає в тому, що будь-який об'єкт в базі даних має свій унікальний ключ. Це може бути порядковий номер, унікальне ім'я, або унікальне значення деякого поля, наприклад, номер паспорта. Завдання полягає в тому, щоб по заданому в запиті ключа знайти в базі даних об'єкт з цим ключем (якщо такий об'єкт в базі є). Більш формально це завдання можна поставити в такий спосіб. Є деяке кінцеве безліч ключів. Є деяка більш широке безліч запитів. Потрібно за довільним запитом з безлічі запитів знайти в безлічі ключів ключ ідентичний (рівний) ключу-замовлення. У такій постановці ця задача називається задачею пошуку ідентичних об'єктів.

Інший приклад взятий з систем машинної графіки, обробки зображень і систем автоматизованого проектування Дано кінцеве безліч точок з відрізка [0,1) речової прямої. Безліч запитів є безліч всіх відрізків, що містяться в [0,1]. Треба для довільного запиту [u, t>] з безлічі запитів перерахувати всі крапки з нашого безлічі точок, які потрапляють в відрізок [u, v]. Це завдання має назву одновимірної задачі інтервального пошуку.

Якщо ми хочемо вивчати складність алгоритмів пошуку, то без введення математичної моделі об'єкта вивчення нам не обійтися.

Тому почнемо з формалізації поняття завдання інформаційного пошуку (ЗІП). У роботах [7, 53, 56, 69] вводилися різні формалізації ЗІП. Так в [69] вводилася формалізація найбільш близька до тієї, яку ми будемо використовувати в цій роботі. Формалізація ЗІП в [69) вводилася в такий спосіб: питання до бази даних представляє певний запит, який має тип Т 1, сама база даних складається з елементів типу Т 2, а відповідь на питання - значення типу ТЗ, наприклад, ТЗ може мати логічний тип, якщо передбачається, що відповідь на запит має бути "так" або "ні", ТЗ може збігатися з Т2, якщо відповіддю на запит є елемент бази даних, і нарешті ТЗ може бути безліччю елементів типу Т2, якщо у відповідь на запит треба перераховувати деякі елементи з бази даних. Питання Q розглядається як відображення з Т1 і безлічі підмножин Т2 в ТЗ, тобто Q: Т 1 х 2 Т2 -> ТЗ.

Ми будемо розглядати тільки такі завдання пошуку, в яких у відповідь на запит треба перерахувати елементи бази даних, що задовольняють запиту. ЗІП такого типу називаються завданнями на перерахування. З урахуванням цього факту ми і дамо власну формалізацію ЗІП, більш зручну для використання в подальшому.

З наведених прикладів видно, що в задачах пошуку є якийсь універсум, з якого беруться об'єкти пошуку (елементи бази даних). У першому прикладі таким універсумом є безліч всіляких ключів, а в другому - відрізок [0,1] речової прямої. Цей універсум позначимо через Y і будемо називати множиною об'єктів пошуку або безліччю записів , а елементи множини Y, будемо називати, записами.

Далі в задачах пошуку завжди є безліч запитів. У першому прикладі безліч запитів збігається з безліччю об'єктів пошуку і є безліччю всіляких ключів, а в другому прикладі безліч запитів є безліч всіх відрізків, що містяться в [0,1], тобто безліч {(tt, v): 0 < і <v < 1}. Безліч запитів будемо позначати через X.

На декартовом творі X х Y є бінарне відношення, яке дозволяє встановлювати, коли запис з Y задовольняє запиту з X. Це відношення будемо називати ставленням пошуку. У першому прикладі ставлення пошуку є ставлення ідентичності (рівності), тобто запис задовольняє запиту, якщо вони ідентичні. У другому прикладі ставлення пошуку, яке позначимо через pint , визначається співвідношенням

де (u, v) і Х } у eY.

Трійку S = (Х, У, р), де X - безліч запитів, Y - безліч записів, р - відношення пошуку, заданий на X х У, будемо називати типом , або іноді більш розгорнуто типом завдань інформаційного пошуку.

Трійку I = } Vy р) у де X - безліч запитів; V - деякий кінцеве підмножина безлічі Y, надалі зване бібліотекою ; р - відношення пошуку, заданий на X х Y у називатимемо завданням інформаційного пошуку (ЗІП) типу S = (XyYyp). Змістовно будемо вважати, що завдання / = (Ху Vy р) складається в перерахуванні для довільно взятого запиту хX всіх тих і тільки тих записів з V , які перебувають у відношенні р із запитом х, тобто відповідають запиту х.

Тим самим ми формалізували поняття ЗІП.

Для повної визначеності відзначимо, що оскільки бібліотека V є безліч, то в ній всі елементи різні, тобто в ній немає повторюваних елементів.

Следующій.шаг, який ми зобов'язані зробити - це вибрати математичну модель для алгоритмів пошуку.

Відзначимо, що тут і скрізь далі, використовуючи термін "алгоритм", ми часто будемо підміняти ним поняття "умовного алгоритму" (або "відносного алгоритму", див. [39, с. 44-45]), тобто будемо розглядати алгоритми, які виконуються за умови, що ми вміємо виконувати деякі операції з описаного заздалегідь безлічі. В якості таких операцій можуть виступати, наприклад, деякі операції над числами, але так чи інакше ми завжди будемо явно обумовлювати операції, щодо яких розглядається кожен описуваний умовний алгоритм.

Перш ніж запропонувати модель алгоритмів пошуку поглянемо на алгоритм, що вирішує завдання пошуку з функціональної точки зору.

Розглянемо довільну ЗІП I = (X, V, р ). Алгоритм пошуку вирішує ЗІП, якщо на будь-який запит з безлічі запитів X він видає всі ті і тільки ті записи з V , що відповідають запиту. Візьмемо довільну запис у 6 Y. Для неї можна ввести характеристическую функцію

тобто вона дорівнює 1 на тих запитах, яким задовольняє запис у. Тоді можна сказати, що алгоритм, вирішальний ЗІП I = (X, V, p), де V = {j / i, -. -, 2 / jfc}, - ні що інше як алгоритм, який реалізує систему функцій {х У1 , р , • • •, Xy fc , p} - Отже, керуюча система, що моделює алгоритм, вирішальний ЗІП / = ( X , V, p), повинна являти собою багатополюсника, який реалізує безліч характеристичних функ- Д ий

Розглянемо випадок коли безліч запитів X = У п - 71- мірний одиничний куб. Тоді кожна з функцій Xy t , p буде функцією алгебри логіки і, отже, в класі контактних схем [37] можна побудувати багатополюсника, який реалізує безліч функцій {Xyi.p »• • • > Ху до , р} як Функцій провідності.

Якщо безліч запитів не є n-мірним одиничним кубом, то можна замість множини {xi, ..., х п , Х > ..., х п } використовувати для навантаження ребер деякий безліч F предикатів, визначених на безлічі запитів X. Тоді при вдалому виборі безлічі F і правильної навантаженні ребер багатополюсника предикатами з F ми можемо в якості функцій провідності між полюсами отримати характеристичні функції Xy it p (} - !> &) • Але якщо вводити складність отриманої багатополюсною мережі так само як в контактних схемах (то є як кількість ребер мережі), то ця з хибність швидше буде характеризувати обсяг пам'яті, відповідного алгоритму, але не час пошуку. Щоб складність мережі характеризувала час пошуку, її інакше. А саме, будемо вважати, що мережа у нас орієнтована, що в мережі є такий полюс, який називається коренем , і кожна з характеристичних функцій записів Xy it p (* = 1, Л) реалізується як функція провідності між коренем і своїм полюсом, який відзначимо приписуванням йому записи тд. Тепер якщо взяти довільний запит

хX, то алгоритм функціонування мережі на запиті х можна описати аналогічно алгоритму розмітки графа [18, 32): вважаємо, що в початковий момент всі вершини мережі, крім кореня, невідмічені, а деякий впорядкована множина вершин мережі, яке назвемо безліччю активних вершин , містить тільки корінь мережі. На кожному черговому кроці робимо наступне. Якщо безліч активних вершин не порожньо, то вибираємо першу активну вершину і видаляємо її з безлічі активних вершин. Якщо обрана вершина є полюсом, то відповідну їй запис включаємо у відповідь на запит х. Переглядаємо в деякому порядку всі ребра, що виходять з обраної вершини, і якщо предикат, приписаний переглядати ребру, на запиті х приймає значення 1 і кінець проглядається ребра невідзначеними вершина, то відзначаємо кінець проглядається ребра і включаємо його в безліч активних вершин (якщо ми включимо його в початок безлічі активних вершин, то отримаємо алгоритм обходу "спочатку вглиб", а якщо в кінець - то "спочатку вшир"). Алгоритм завершує роботу в той момент, коли безліч активних вершин виявиться порожнім.

Легко бачити, що якщо між коренем мережі і деякою вершиною на запиті х є провідність, тобто з кореня в цю вершину веде деяка ланцюжок ребер, кожному з яких приписаний предикат, що приймає значення 1 на запиті х , то обов'язково в результаті описаного алгоритму обходу мережі дана вершина виявиться зазначеної, тобто алгоритм обходу відвідає її.

Описаний алгоритм обходу мережі можна вважати відповідним мережі алгоритмом пошуку на запит х } а складність мережі на запиті х можна вважати рівною, кількістю переглянутих ребер, або, що те ж саме числу обчислених алгоритмом обходу предикатів. Така складність буде характеризувати час роботи відповідного алгоритму пошуку на запит х.

Описана мережу з описаним функціонуванням є окремим випадком інформаційного графа (ІГ).

Перш ніж дати суворе формальне визначення ІГ, введемо деякі допоміжні поняття і позначення.

Нехай М - деякий кінцеве безліч. Через М позначимо число елементів у множині М, зване потужністю безлічі М.

Через {1, т} домовимося позначати безліч

{1,2

Деякі оцінки ми будемо приводити з точністю до головного члена, тому введемо позначення, зазвичай прийняті при описі асимптотических оцінок.

Будемо писати а (н) = о (1), якщо lim а (п) = 0; А (п) =

г »-» оо

про (Б (і)), якщо А {п) = В (п) • про (1). Скажімо, що А (п) асимптотично не перевищує В (п) при п -? оо і позначимо А ~ В у якщо існує а (і) = д (1) таке, що починаючи з деякого номера n 0 , Л (і) < (1 -f- а (н)) • В (п). Якщо А ~ В і В ~ Л, то будемо говорити, що А і В асимптотично рівні при п -> оо і позначати А ~ В. Будемо писати А & В, якщо існує така позитивна константа с, що, починаючи з деякого номера по , Л (п) В (п). Якщо А ^ В і В ^ А, то будемо говорити, що А і В рівні по порядку при і - * оо і позначати А ж У або А = 0 (B).

Через (?) Будемо позначати число поєднань з п елементів по к. Якщо г - дійсне число, то через [г] будемо позначати максимальне ціле, що не перевищує г, а через] г [- мінімальне ціле, одна з, ніж р Значок = f будемо розуміти як "за визначенням одно". Математичне сподівання будемо позначати значком М, а значок М х будемо розуміти як середнє значення при варіації змінної х.

Домовимося також про теоретико-графовой термінології.

Нехай нам дано орієнтований граф. В орієнтованому ребрі (а, /?) Вершину а будемо називати початком ребра , а / 3 - кінцем. Скажімо, що орієнтоване ребро графа виходить з вершини 0 ( входить в вершину 0 ), якщо 0 - початок (кінець) даного ребра. Скажімо, що ребро інцидентне вершині, якщо ця вершина є одним з кінців даного ребра. Полустепе- нью результату ( заходу ) вершини графа назвемо число ребер, що виходять з даної вершини (що входять в дану вершину). Ступенем инцидентности вершини назвемо число інцидентних їй ребер. Вершину графа назвемо кінцевий , якщо полустепені її результату дорівнює 0. Решта вершини графа назвемо внутрішніми.

Послідовність орієнтованих ребер графа

назвемо орієнтованої ланцюгом від вершини а до вершини а т .

Якщо / - одномісний предикат, визначений на X , тобто /: X -> {0,1}, то безліч N / = {хX : f (x) = 1} назвемо характеристичним безліччю предиката /.

Безліч 0 (у, р) = 6 X : хру } назвемо тінню записи yeY.

Функцію Ху.р : х - »{0,1} таку, що N Xv p = 0 (у, р), назо вем характеристичної функцією запису у.

У формальному визначенні поняття ІГ використовуються 4 безлічі:

  • • безліч запитів X ;
  • • безліч записів Y ;
  • безліч F одномісних предикатів , заданих на множині Х
  • безліч G одномісних перемикачів , заданих на множині X ( перемикачі - це функції, область значень яких є початковим відрізком натурального ряду).

Пару Т = (F y G) будемо називати базовим безліччю.

Визначення поняття ІГ розбивається на два кроки. На першому кроці розкривається структурна (схемна) частина цього поняття, на другому - функціональна.

Визначення ІГ з точки зору його структури.

Нехай нам дана орієнтована багатополюсна мережу.

Виділимо в ній один полюс і назвемо його коріння а решта полюса назвемо листям.

Виділимо в мережі деякі вершини і назвемо їх точками перемикання (полюса можуть бути точками перемикання).

Якщо р - вершина мережі, то через фр позначимо полустепені результату вершини / ?.

Кожній точці перемикання р порівняти якийсь символ з G. Це відповідність назвемо навантаженням точок перемикання.

Для кожної точки перемикання Р ребер, з неї виходить, поставимо у взаємно однозначна відповідність числа з безлічі {1, ^ /?}. Ці ребра назвемо перемикачів , а це відповідність - навантаженням переключательних ребер.

Ребра, які не є перемикачів, назвемо предикативними.

Кожному предикатні ребру мережі можна порівняти деякий символ з безлічі F. Це відповідність назвемо навантаженням предикатних ребер.

Порівняємо кожному листу мережі деякий запис з безлічі Y. Це відповідність назвемо навантаженням листя.

Отриману навантажену мережу назвемо інформаційним графом над базовим безліччю Т - (F } G).

Визначення функціонування ІГ.

Скажімо, що предикатное ребро проводить запит хX, якщо предикат, приписаний цьому ребру, приймає значення 1 на запиті рр; комутаційне ребро, якого приписаний номер п, проводить запит х € X, якщо перемикач, приписаний початку цього ребра, приймає значення п на запиті х; орієнтована ланцюжок ребер проводить запит х 6 X } якщо кожне ребро ланцюжка проводить запит х; запит х G X проходить в вершину Р ІГ, якщо існує орієнтована ланцюжок, що веде з кореня в вершину / ?, яка проводить запит х; запис t /, приписана листу а, потрапляє у відповідь ІГ на запит х € X, якщо запит х проходить в лист а. Відповіддю ІГ U на запит х назвемо безліч записів, які потрапили у відповідь ІГ на запит х, і позначимо його Jv (x). Цю функцію Зі (х): X -> 2 У вважатимемо результатом функціонування ІГ U і називати функцією відповіді ІГ U.

Поняття ІГ повністю визначено.

Проілюструємо наведене визначення на прикладі одновимірної задачі інтервального пошуку. В цьому випадку 4 безлічі, що визначають ІГ, мають вигляд: [1]

: Рішення одновимірної задачі інтервального пошуку

Мал. 2.1 : Рішення одновимірної задачі інтервального пошуку

  • • безліч записів = [0,1];
  • • безліч предикатів

• безліч перемикачів

В інформаційному графі, наведеному на малюнку 2.1, корінь зображений порожнистим гуртком. Листя зображені жирними точками, а записи, приписані листю, - це символи у з індексами. На малюнку є 8 переключательних вершин (їм приписані символи д з індексами) і 17 предикатних ребра (їм приписані символи / с індексами).

Якщо п - натуральне число, а д (х ) - якийсь перемикач, то через ?? (ж) позначимо предикат, визначений на X , такий, що

позначимо

де N - безліч натуральних чисел.

Якщо з - ребро ІГ, то через [з] позначимо його навантаження.

Згідно з наведеними вище визначеннями введемо функції провідності.

Провідність ребра (а, Р) назвемо предикат, рівний [(or, /?)], Якщо ребро предикатное, і якщо ребро комутаційне, де g - перемикач, що відповідає вершині а.

Провідність орієнтованої ланцюга назвемо кон'юнкцію проводимостей ребер ланцюга.

Якщо зафіксувати запит ДГ, то ланцюг, провідність якої на запиті х дорівнює 1, назвемо проводить ланцюгом на запиті х.

В ІГ по аналогії з контактними схемами введемо для кожної пари вершин аїр функцію провідності f a p від вершини а до вершини р наступним чином:

  • • якщо а = Р , то f a p (x) = 1 6 Х)
  • • якщо а ф Р верб ІГ не існує орієнтованих ланцюгів від а до Р то f Q p (x) = 0; [2]

Функцію провідності від кореня ІГ до деякої вершини Р ІГ назвемо функцією фільтра вершини / 3 і позначимо у? Р (х).

Через 7Z (U) yV (U) t C (U) (або просто 7Z y V, C) позначимо безлічі вершин, точок перемикання і листя ІГ U відповідно.

Нехай N - деяка підмережа (тобто довільна підмножина вершин і ребер) ІГ U. Через {N) позначимо безліч записів, які відповідають листю цієї підмережі (якщо а - деякий лист ІГ U , то під (а) будемо розуміти запис, що відповідає листу а ).

Легко бачити, що функція відповіді ІГ U визначається співвідношенням

З визначення функціонування ІГ видно, що ІГ як керуюча система може розглядатися в якості моделі алгоритму пошуку, працює над даними, організованими в структуру, яка визначається структурою ІГ.

У разі, коли базове безліч перемикачів G порожньо, тобто в графах немає перемикачів, то ІГ називаються предикативними інформаційними графами (ПИГ).

ПИГ, різним листю якого відповідають різні записи, називається однозначухим інформаційним графом (ОІГ).

ОІГ, що має вигляд дерева, листя якого збігаються з кінцевими вершинами дерева, назвемо інформаційним деревом (ВД).

ВД зручні і цікаві тим, що структури даних, їм відповідні, практичні і їх набагато простіше реалізувати на ЕОМ.

Наведемо приклад ще одного ІГ. Нехай / = ( X , К, =) - завдання пошуку ідентичних об'єктів, де на безлічі V = {двох, .. -, 2/7} заданий лінійний порядок і записи впорядковані в порядку зростання, тобто у <у <• • • < у 7 . Нехай безліч предикатів має вигляд

: Інформаційний граф бінарного пошуку а безліч перемикачів - вид

Мал. 2.2 : Інформаційний граф бінарного пошуку а безліч перемикачів - вид

Бінарним пошуком або шляхом розподілу навпіл (див., Наприклад, [7, 23, 40]) називається алгоритм пошуку в упорядкованому масиві, при якому масив ділиться навпіл, запит порівнюється із середньою точкою і в залежності від результату порівняння пошук рекурсивно повторюється в одній з половин.

На малюнку 2.2 наведено ІГ над базовим безліччю Т - (F, G), вирішальний ЗІП /, відповідний бінарним пошуку в версії Боттенбрука [71, с. 214], в якій питання про рівність записи і запиту відкладається до самого останнього моменту.

Введення керуючої системи, тобто схеми з функціонуванням, для моделювання алгоритмів пошуку дозволяє використовувати апарат теорії складності керуючих систем для дослідження складності алгоритмів пошуку.

вправи

  • 2.11. За аналогією з одновимірної завданням інтервального пошуку приведіть тип, що описує л-мірні завдання інтервального пошуку.
  • 2.12. Опишіть тип, що задає завдання інтервального пошуку на n-вимірному булевом кубі, які складаються в пошуку в кінцевому підмножині л-меріого булевого куба всіх тих точок, які потрапляють в подкуб, що задається запитом. Яка потужність безлічі запитів у даного типу?
  • 2.13. Завдання про метричної близькості полягає в тому, щоб по довільно взятої точці-замовлення одиничного л-меріого куба л- мірного евклідового простору знайти в кінцевому підмножині цього куба (бібліотеці) всі крапки, що знаходяться на відстані не більше, ніж R від точки запиту. Опишіть тип, що задає завдання про метричної близькості.
  • 2.14. Опишіть тип, що задає завдання включає пошуку. Нагадаємо, що в задачі включає пошуку є деяка кінцеве безліч властивостей, і кожен елемент бібліотеки (безлічі даних) володіє або не володіє кожним з цих властивостей. Запит задає деякий підмножина безлічі властивостей, і необхідно знайти всі елементи бібліотеки, які мають всі властивості з запиту.
  • 2.15. Розглянемо наступну задачу пошуку, яка може виникнути, наприклад, при розгадуванні кросвордів. Елементи бібліотеки (записи) є слова фіксованої довжини л в алфавіті {0,1}. Запит задає певний набір позицій і значення букв в цих позиціях. Необхідно знайти в бібліотеці всі записи, у яких в позиціях, що задаються запитом, стоять літери, що збігаються з відповідними значеннями позицій запиту. Опишіть тип, що задає ці завдання пошуку. Порівняйте отриманий тип з типом завдань інтервального пошуку на булевом кубі (див. Вправу 2.12).

  • [1] безліч запитів X {nt = {(w, v): 0
  • [2] якщо а ф Р і безліч орієнтованих ланцюгів від а до рне порожньо, то fap (x) дорівнює диз'юнкції проводимостей всехоріентірованних ланцюгів від а до р.
 
<<   ЗМІСТ   >>