Повна версія

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

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


<<   ЗМІСТ   >>

КРИТЕРІЙ ДОПУСТИМОСТІ ІГ

Нехай нам дана ЗІП I = (X , V, р).

Скажімо, що ІГ U вирішує ЗІП I = ( X , V, />), якщо для будь-якого запиту х 6 X відповідь на цей запит містить всі ті і тільки ті записи з V , які відповідають запиту х , тобто

ІГ U , вирішальний ЗІП /, будемо також називати допустимим для завдання I.

Нехай U - деякий ІГ, у -.запісь з Y. Через Ьц (у) позначимо безліч листів ІГ U, яким відповідає запис У

Справедлива наступна теорема.

Теорема 9. ІГ U вирішує ЗІП I = ( X , V, p) тоді і тільки тоді, коли для будь-якого запису у 6 V , такий, що 0 } р) ф 0, справедливо ьі (у) Ф 0 і у а = Ху.р > а будь-якого запису

у 6 V, такий, що 0 (у, р) = 0, справедливо або Ьц {у) = 0, або ^ = 0.

<* € Lu (у)

Доведення. Достатність.

Візьмемо довільний запит х € X.

Візьмемо довільну запис у 6 V.

Якщо 0 (у, р) = 0 і, отже, х ф 0 (у, р ), то за припущенням або ьі (у) - 0, або J <р а = 0. Звідки випливає,

e €? i / (y)

ЩО УФ Л (х).

Тепер розглянемо випадок, коли 0 (у, р) ф 0.

Якщо хру , то Ху, р ( х ) = 1, і згідно з припущенням

Звідки випливає, що існує лист а €? (? /) Такий, що ра (х) = 1. Отже, у € * 7с / (#).

Якщо х? 0 (у, р), то Ху, р ( х ) = 0, і згідно з припущенням VV? A (s) = 0. Звідки випливає, що у ф Ju ( x ) - <* € Lu (y)

Таким чином, ми показали, що

і тим самим довели достатність.

Необхідність.

Візьмемо довільну запис у € V.

Якщо 0 (у , р) = 0 і, отже, для будь-якого запиту хX х ф 0 (г /, р), значить, для будь-якого х € X у & Ju (x). Звідки випливає, що або Ьц (у) = 0, або Jа = 0.

лбЬ (/ (у)

Тепер розглянемо випадок, коли 0 (у, р) ф 0.

Припустимо, що для цього запису у не виконуються припущення теореми, тобто існує такий запит х у що

Але це означає, що у належить в точності одному з множин Ju (x) або {г / € V : хру).

Отже, при цьому х

і, отже, ІГ U не вирішує ЗІП /.

Тим самим теорема доведена. ?

По суті теорема 9 говорить, що якщо нам дана ЗІП I = (X, V, р), і ми хочемо побудувати ІГ, вирішальний цю ЗІП, ми повинні побудувати багатополюсника, який між коренем і іншими полюсами реалізує як функції провідності всі функції Xy, pi г де УV.

вправи

  • 2.16. Нехай S = } Х } =) - тип пошуку ідентичних об'єктів, безліч предикатів F задається співвідношенням (2.7), базове безліч має вигляд Т - (F, 0), V = {yi, 3/2, •. •, У *} З X. Наведіть приклад інформаційного графа над базовим безліччю F, вирішального ЗІП I = (X, V, =).
  • 2.17. Нехай S = (X, X, =) - тип пошуку ідентичних об'єктів, безліч перемикачів має вигляд

Мал. 2.3 :

базове безліч має вигляд Т = (0, G), V = {уь У2, • • •, 3 / *} Я X. Наведіть приклад інформаційного графа над базовим безліччю Т, вирішального ЗІП I = ( X , V, =).

2.18. Нехай X = {1,2, ..., Nj, S = (Х, Х, =) - тип пошуку ідентичних об'єктів, безліч перемикачів має вигляд

базове безліч має вигляд Т = (0,6?), V = {3,5,7,11,13,17,19}. Побудуйте інформаційний граф над базовим безліччю Т ', вирішальний ЗІП / = ( X , V, =).

2.19. Нехай X = {1,2, ..., N), S = (X, X, =) - тип пошуку ідентичних об'єктів, V = {yi, у2, ..., Ук] Я X. Припустимо, що У <у 2 < • • * < Ук- Метод блочного пошуку з розміром блоку т, що вирішує завдання / = (X , V t =), полягає в наступному. Якщо на вхід алгоритму пошуку подається запит х 6 X, то, починаючи з i = 1 до: = fc / m, переглядаємо записи у *. т - Якщо х > у *. т , то збільшуємо г на 1, інакше по черзі переглядаємо записи y (ii) m + i, У (* - 1) т + 2> •> У »т

і порівнюємо їх із запитом х. У разі рівного розподілу ми знайшли потрібний запис, якщо ж ні для якої записи рівності не спостерігається, то відповідь на запит х порожній. Опишіть базове безліч і побудуйте інформаційний граф над цим базовим безліччю, який би вирішував ЗІП / = ( X , V, =) методом блочного пошуку.

Мал. 2.4 :

2.20. Нехай X = {1,2, ..., TV}, V З X, р з - відношення пошуку, що задається на X х V і визначається співвідношенням

тобто хр з у у якщо у ? V, найближчим справа до х. При виконанні цих умов ЗІП / = ( X , V y р з ) називається завданням про близькість. Нехай базове безліч має вигляд Т - (0, G), де безліч перемикачів З задається співвідношенням (2.8). Побудуйте інформаційний граф над базовим безліччю Ту вирішальний ЗІП I = (X, V, р з ), якщо V = {3,5,7,11,13,17,19}.

2.21. Одновимірна задача про домінування задається типом

Sdomi = ([0,1), [0,1],>). Нехай V = з [0,1]. Опишіть

деякий базове безліч і побудуйте будь-якої інформаційний граф над цим базовим безліччю, який би вирішував ЗІП

/ = ([0,1], К>).

2.22. Нехай Sint = (Xmt, Yi n tу Pint) - тип одновимірного інтервального пошуку, де ставлення pint визначається співвідношенням (2.1),

V = {У1,2 / 2, ..., г / б}, де у = 1/6, уг = 1/4, у 3 = 3/8, у 4 = 2/5, ys = 3/4 , ye = 7/8. Чи вирішує інформаційний граф, зображений на малюнку 2.3, де функції визначаються співвідношеннями (2.2) - (2.6), завдання інформаційного пошуку I = (Xi n t y V y pint) 7 Обгрунтуйте відповідь.

  • 2.23. Доведіть, що інформаційний граф, зображений на малюнку 2.1, вирішує одновимірну задачу інтервального пошуку / = (Xinty Vy Pint) у де V = {yi, У2, уз, У4, У5, Уб} - бібліотека, зображена на малюнку 2.4.
  • 2.24. Нехай Sint = (Xinty Yint у Pint) - тип одновимірного інтервального пошуку, де ставлення pint визначається співвідношенням (2.1),

V = {1 / 8,1 / 7,1 / 5,3 / 7, 3 / 5,4 / 5,7 / 8}. Опишіть деякий базове безліч і побудуйте будь-якої інформаційний граф над цим базовим безліччю, який би вирішував ЗІП I = (Xinty V, pint).

: Інформаційний граф переборного алгоритму

Мал. 2.5 : Інформаційний граф переборного алгоритму

 
<<   ЗМІСТ   >>