Диссертация (1150569), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

2.6 и 2.7 затрачено 10 шагов. На выполнение п. 2.8 ушло5 шагов. Согласно п. 2.9 (5 шагов) возвращаемся к п. 2.2 и 2.3. Берем формулуV a4 , a3 , x6  и отрицание V (a4 , a3 , a6 ) (7 шагов). Согласно п. 2.4 решаемсистему уравнений, отождествляющую эти две формулыx6  a6(1 шаг)Согласно п. 2.5 рассматриваемый F-набор D приобрел вид98  V a2 , a1, a4   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )   V(a,a,a)L(a,a,a)L(a,a,a)6 4 53 1 54 2 6  V a4 , a2 , a3   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V ( a , a , a )  V ( a , a , a )  V ( a , a , a )  V ( a , a , a )   3 4 54 2 34 3 65 3 6V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  V a4 , a3 , a6   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )   D :   V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )    V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  V a6 , a4 , x5   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )    V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  La4 , a2 , a6   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V ( a , a , a )  V ( a , a , a )  V ( a , a , a )  V ( a , a , a )   3 4 54 2 34 3 65 3 6V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )на замену всех вхождений переменных на их значения уходит 6 шагов.На выполнение пп.

2.6 и 2.7 затрачено 10 шагов. На выполнение п. 2.8 ушло5 шагов. Согласно п. 2.9 (5 шагов) возвращаемся к пп. 2.2 и 2.3. Берем формулуV a6 ,a4 , x5  и отрицание V ( a6 ,a4 ,a5 ) (8 шагов). Согласно п. 2.4 решаемсистему уравнений, отождествляющую эти две формулыx5  a 5(1 шаг)Согласно п. 2.5 рассматриваемый F-набор D приобрел вид99  V a2 , a1, a4   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )   V(a,a,a)L(a,a,a)L(a,a,a)6 4 53 1 54 2 6  V a4 , a2 , a3   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V ( a , a , a )  V ( a , a , a )  V ( a , a , a )  V ( a , a , a )   3 4 54 2 34 3 65 3 6V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  V a4 , a3 , a6   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )   D :   V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )    V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  V a6 , a4 , a5   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )    V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  La4 , a2 , a6   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V ( a , a , a )  V ( a , a , a )  V ( a , a , a )  V ( a , a , a )   3 4 54 2 34 3 65 3 6V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )на замену всех вхождений переменных на их значения уходит 5 шагов.Согласно п.

2.6 получился пустой F-набор (5 шагов), объект «тройка»выделен.Рис. 2.2.5. Выделенный на заданном контурном изображении объект «тройка».На выделение объекта ушло 209 шагов.100ПРИЛОЖЕНИЕ B. Пример решения задачи с помощью алгоритма IAPTAПусть имеется множество контурных изображений, составленных изотрезков прямых, задаваемых своими концами. Заданы два предиката V и L,определяемых так, как представлено на рис. 1.Рис. 1. Предикаты V и L.Задан класс объектов Ω1 – класс контурных изображений «троек».Схематическое изображение эталонного объекта имеет вид (см.

рис. 2):Рис. 2. Контурное изображение «тройка».Описание класса задается следующей формулой:A x1,..., x6   V  x2 , x1, x4  & V  x4 , x2 , x3  & V  x4 , x3 , x6  & V  x6 , x4 , x5  & L x4 , x2 , x6 .Пусть задано контурное изображение, представленное на рис. 3, в которомтребуется найти хотя бы один объект, принадлежащий классу «троек».101Рис. 3. Контурное изображение.Это изображение имеет описание:S a1,, a6   {V a1, a2 , a3  & V a2 , a1, a4  & V a3 , a1, a4  & V a3 , a4 , a5  & La3 , a1, a5 & V a4 , a2 , a3  & V a4 , a3 , a6  & La4 , a2 , a6  & V a5 , a3 , a6  & V a6 , a4 , a5 }Для того чтобы выделить объект, принадлежащий классу «троек»,необходимо доказать справедливость логического следованияS a1,, a6   x1,..., x6 Ax1,..., x6 Общезначимость этой формулы равносильна общезначимости формулы102a1,..., a6x1,..., x6  V  x2 , x1, x4   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )      V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )   &  V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )   V  x4 , x2 , x3   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V ( a , a , a )   V ( a , a , a )   V ( a , a , a )  V ( a , a , a )   &  3 4 54 2 34 3 65 3 6 V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )   V  x , x , x   V ( a , a , a )  V ( a , a , a )  V ( a , a , a )   4 3 61 2 32 1 43 1 4   V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )   &  (1) V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )   V  x6 , x4 , x5   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V ( a , a , a )   V ( a , a , a )   V ( a , a , a )  V ( a , a , a )   &  3 4 54 2 34 3 65 3 6  V (a6 , a4 , a5 )  L(a3 , a1, a5 )  L(a4 , a2 , a6 )  L x4 , x2 , x6   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )     V (a3 , a4 , a5 )  V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )     V(a,a,a)L(a,a,a)L(a,a,a)645315426 Для рассматриваемого примера количество формул в F-наборе δ=5,количество атомарных формул в S a1, , a6  с одним и тем же предикатнымсимволом s1  8 и s2  2 для предикатов V и L соответственно ( s1  8 ),наибольшее количество аргументов в атомарной формуле l  3 .

В соответствии стеоремой 3.2.1 число шагов выделения «тройки» с помощью алгоритма IAPTA взаданном изображении не может быть меньше, чем  s  4  2  5 14  2  72 . По теореме 3.2.2 верхняя оценка числа шагов составляет O l   max sk   , то есть  k имеет порядокl   max sk   3  85  98 304 k103По формуле (1) строим 5-членный F-набор, состоящий из ее элементарныхдизъюнкций (то есть удаляем квантор существования вместе с переменными ивхождения знака &).Так как в алгоритме пары формул с нулевыми приоритетами (на первомшаге вторая формула пары – это постоянная формула с предикатным символом,отличным от предикатного символа в атомарной формуле с переменными) неучаствуют в переборе, в примере для простоты не будем писать их в F-наборах.Тогда после расстановки приоритетов F-набор D принимает вид V  x2 , x1, x4   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )  V (a3 , a4 , a5 )     V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )  V (a6 , a4 , a5 ) V  x4 , x2 , x3   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )  V (a3 , a4 , a5 )     V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )  V (a6 , a4 , a5 ) V  x4 , x3 , x6   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )  V (a3 , a4 , a5 )     V (a4 , a2 , a3 )  V (a4 , a3 , a6 )  V (a5 , a3 , a6 )  V (a6 , a4 , a5 ) V  x6 , x4 , x5   V (a1, a2 , a3 )  V (a2 , a1, a4 )  V (a3 , a1, a4 )  V (a3 , a4 , a5 )    V(a,a,a)V(a,a,a)V(a,a,a)V(a,a,a)4 2 34 3 65 3 66 4 5Lx4 , x2 , x6   L(a3 , a1, a5 )  L(a4 , a2 , a6 ) D: На выполнение п.

1 алгоритма потребовался 21 шаг9.Мы имеем пять процессоров. Первый из них начинает работу с формулыV  x2 , x1 , x4 , второй – с V  x4 , x2 , x3  , третий – с V  x4 , x3 , x6  , четвертый – сV  x6 , x4 , x5  , а пятый – с L x4 , x2 , x6 . У всех процессоров F-наборы одинаковые, ноимеют разные рабочие формулы.На выполнение п. 2 алгоритма потребовалось:1 шаг на создание популяции процессоров;4 шага на копирование F-набора на каждый процессор;5 шагов на назначение рабочей атомарной формулы с переменными для каждогопроцессора;9Здесь и далее, жирным выделено итоговое количество шагов, затраченное всеми процессорами, а курсивом –промежуточное количество шагов, затраченное каждым из процессоров.1041 шаг на назначение первого «унификатора» первому процессору (то естьотождествление списков  x2 , x1 , x4  и a1 , a2 , a3  );1 шаг на сравнение имен рабочих предикатов и 2 шага на назначение первого«унификатора» второму процессору, отличного от уже назначенного первомупроцессору (то есть отождествление списков  x4 , x2 , x3  и a2 , a1 , a4  );1 шаг на сравнение имен рабочих предикатов и 3 шага на назначение первого«унификатора» третьему процессору, отличного от уже назначенных первому ивторому процессорам (то есть отождествление списков  x4 , x3 , x6  и a3 , a1 , a4  );1 шаг на сравнение имен рабочих предикатов и 4 шага на назначение первого«унификатора» третьему процессору, отличного от уже назначенных первому,второму и третьему процессорам (то есть отождествление списков  x6 , x4 , x5  иa3 ,a4 ,a5  );1 шаг на сравнение имен рабочих предикатов и 1 шаг на назначение первого«унификатора» пятому процессору (то есть отождествление списков  x4 , x2 , x6  иa3 , a1 , a5  ).Итого 15 шагов.

Согласно п. 3.3 процессоры решают системыследующих уравнений (3 шага):ПРОЦЕССОРПЕРВЫЙВТОРОЙx1  a2x2  a1x2  a1x4  a3x3  a4x4  a2ТРЕТИЙЧЕТВЕРТЫЙПЯТЫЙx2  a1x3  a1x4  a3x6  a4x4  a 4x5  a5x6  a3x4  a3x6  a5Выполнив п. 3.4 алгоритма имеем следующий результат.

Характеристики

Список файлов диссертации