Page 149 - 4495

0 залежить від кількості обмежень в C). Прикладом множини W
C
може бути множина дійсних додатних чисел R з мінімальним елеме-
+
нтом 0.

Означення 14 (степінь задоволення, розв’язок). У системі об-
межень з ієрархічними анотаціями P  ( , , ,V D C A , )a . Та відповідній
A 
АІО C C  C   C , помилкою АІО на присвоєнні  називається
0 1 n
)]
кортеж [ (E C ), , (E C  . Цей кортеж позначається як E (C ).
1 n
Розв’язком системи обмежень з ієрархічними анотаціями P є
A H
таке присвоєння  , для якого справедлива рівність (E C  ) 0 , а по-
0 C 0
милка E (C ) є мінімальною відповідно до лексикографічного впоря-
дкування, тобто:

)
   k  таке, що i k  :[ (E C  E (C )] [ (E C  )  E (C  )].
V i W i k W k
Вимога найкращого можливого задоволення рівня C має на меті
0
виразити вимогу повного задоволення всіх обмежень на рівні

C ( c C  : | c  . Із цього визначення видно, що помилки присвоєнь
)
0 0
порівнюються шляхом співставлення помилок їх рівнів, від найбільш
до найменш важливих. Менша помилка на будь-якому більш важли-
вому рівнів виражає вибір кращого присвоєння, не зважаючи на по-
милки нижчих рівнів.
Було означено помилку множини обмежень як загальну функцію

C
E :2   W . Розглянемо можливі часткові випадки цієї помилки
V
для W=R зі стандартним впорядкуванням на дійсних числах, де мі-
+
німальним елементом є 0:
)
помилки за сумарною вагою: (E C  )   acv ( ) (c e c ;
c C
)
помилка в найгіршому випадку: (E C  ) maxacv ( ) (c e c ;

c C
2
)
помилка за найменшими квадратами: (E C  )   acv ( ) (c e c ,
c C
де справедливо C  , та   .
C
V
Приклад 4. Нехай систему обмежень із ієрархічними анотаціями
та середнім арифметичним як об’єднувальною функцією, із заданими
обмеженнями, такими ж, як і у прикладі 3. Покажемо як задати для
такої системи ієрархію обмежень з анотаціями і розв’язати її, викори-

стовуючи тривіальну функцію помилки та помилку по сумарній вазі.
Анотації обмежень:

( a c L ) a (c P )
ac ( )c  1 1  0.75,
1
2

149