Повна версія

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

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


<<   ЗМІСТ   >>

ПОТУЖНОСТНОГО НИЖНЯ ОЦІНКА

В роботі [52, стр. 92] бездоказово, просто як очевидний факт стверджується, що час пошуку принаймні не менше ніж час, необхідний на перерахування відповіді. У нашій моделі цей факт знаходить своє підтвердження і носить назву мощностной нижньої оцінки. У зв'язку повсюдно застосовності мощностной нижньої оцінки часто при оцінці часу алгоритму пошуку оцінюють лише різницю між часом пошуку і часом перерахування відповіді (див., Наприклад, [52]).

Нехай нам дано довільну безліч запитів X, записів Y і ставлення пошуку р на X х Y. Причому на безлічі запитів задано ймовірнісний простір ( X , а, Р).

Скажімо, що базове безліч Т допустимо для ЗІП /, якщо існує ІГ над базовим безліччю J r1 який вирішує ЗІП /.

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

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

Теорема 12 (показники потужності нижня оцінка). Нехай I = ( X , V , р) - довільна ЗІП, така, що існує такий запис у G V, що 0 (у, р) ф 0, Т - вимірне базове безліч, допустимий для I, тоді

Доведення. Візьмемо довільний ІГ U , що вирішує завдання I. Такий граф існує, так як 1Л (1, Т) Ф 9.

Візьмемо довільний запит х 6 X. Так як ІГ U вирішує ЗІП /, то відповідь на запит х

Візьмемо довільну запис у 6 Зі (х). Оскільки запис у потрапила у відповідь, то, значить, в ІГ U існує якийсь лист а, якому приписана запис у і такий, що у? а (: г) = 1. А так як ip Q (т) = 1 і ніякої лист не збігається з коренем, то існує ланцюг, що веде з кореня в лист а, провідність якої дорівнює 1, і в цьому ланцюзі є ребро, що веде в а, з провідністю 1. Це ребро назвемо проводять ребром записи у. Зрозуміло, що різним записів з Зі (х) відповідають різні провідні ребра, так як ці ребра ведуть в різні листя. Якщо проводить ребро записи предикатное, предикат, приписаний проводить ребру, обов'язково був обчислений перед тим, як ми потрапили в лист. Якщо проводить ребро записи комутаційне, то обов'язково був обчислений перемикач, приписаний вершині, з якої виходить проводить ребро. Причому такі перемикачі для різних записів з ЗЦ (х) будуть різними, так як тільки одне з перемикачів ребер, що виходять з однієї вершини, може мати провідність, рівну 1. Таким чином, кожного запису з Ju (x) можна зіставити перемикач або предикат, який вираховується безпосередньо перед попаданням в відповідний запис лист. Причому різних записів будуть співставлені різні перемикачі або предикати. Звідси слідує що

отже,

А так як це нерівність виконується для будь-якого графа і то

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

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

У пражненія

  • 2.31. Нехай X = {1,2, ..., ЛГ}, 5 = у X, =, Р, <т) - тип пошуку ідентичних об'єктів, де а = 2 *, Р - рівномірна імовірнісна міра, тобто для будь-якого х 6 X виконується Р (х) = 1 / 7V, V = {3,5,7,11,13,17,19}. Наведіть мощностную нижню оцінку для ЗІП I = (X, V, =).
  • 2.32. Нехай Sdom 1 = ([0,1], [0,1],>, Р, <т) - тип одновимірної задачі про домінування, де Р - рівномірна імовірнісна міра на [0,1], V = {yi, y2 , ... | Ук} Я [ОЛЬ Наведіть мощностную нижню оцінку для ЗІП / = ([0,1], V,>).
  • 2.33. Нехай Sint = (X int , Yint> Pint) - тип одновимірного інтервального пошуку і на безлічі запитів Xi n t = {(u, v): 0 <і V = {у'Уг, • • •, 2 / fc} Q [0,1]. Наведіть мощностную нижню оцінку для ЗІП / = ( Xi n t , V, p% nt) - оточили зверху отриману величину.
 
<<   ЗМІСТ   >>