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

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

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

Непротиворечивымежду собой присвоения первого и пятого процессоров (12 шагов). Согласно п.3.5 получаем такие четыре F-набора (жирным выделена рабочая формулапроцессора):105первый процессор V a1 , a 2 , a 3   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 a3 ,a1 , x3   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 V a3 , x3 ,a5   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 V a5 ,a3 , 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( a3 ,a1 ,a5 )  L( a4 ,a2 ,a6 )на замену всех вхождений переменных на их значения уходит 6 шагов;второй процессор V a1 , x1 , a2   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 a 2 , a1 , a4   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 V a2 , a4 , x6   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 V  x6 , a2 , 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a2 , a1 , x6   L( a3 , a1 , a5 )  L( a4 , a2 , a6 )на замену всех вхождений переменных на их значения уходит 7 шагов;третий процессор V  x2 , x1 , a3   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 a3 , x2 , a1   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 V a 3 , a1 , a4   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 V a4 , a3 , 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 , x2 ,a4   L( a3 ,a1 ,a5 )  L( a4 ,a2 ,a6 )106на замену всех вхождений переменных на их значения уходит 7 шагов;четвертый процессор V  x2 , x1 , a4   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 V a4 , x2 , x3   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 V a4 , x3 , a3   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 a 3 , 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a4 , x2 ,a3   L( a3 ,a1 , a5 )  L( a4 ,a2 ,a6 )на замену всех вхождений переменных на их значения уходит 6 шагов;пятый процессор V a1,a2 ,a3   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 V a3 , a1 , x3   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 V a3 , x3 , 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 ) V a5 , a3 , 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a 3 , a1 , a5   L( a3 , a1 , a5 )  L( a4 , a2 , a6 )на замену всех вхождений переменных на их значения уходит 6 шагов.Всего число шагов выполнения п.

3.5 равно наибольшему из этих пятичисел, то есть 7 шагов.На пп. 3.6, 3.7 и 3.8 потребовалось 15 шагов (по пять на каждый пункталгоритма для каждого процессора). Согласно п. 3.9 переходим к выполнению п.3.1. Берем новые рабочие формулы. На их выбор ушел 1 шаг.Согласно п. 3.2 второй и третий процессоры отменяют свои действия.

Наотмену действий обоих процессоров ушло по 7 шагов. После чего этипроцессоры обрабатывают исходный F-набор D, но для второго процессораотрицание V a2 , a1, a4  получило нулевой приоритет (1 шаг), для третьего –107отрицание V a3 , a1, a4  получило нулевой приоритет (1 шаг). Итого 8 шагов длякаждого процессора.Согласно п.

3.1 первый и пятый процессоры меняют рабочую формулу наV a3 , a1, x3 , четвертый процессор меняет рабочую формулу на V  x2 , x1 ,a4  (1шаг). Согласно п. 3.3 (3 шага на поиск подходящей системы уравнения дляпервого и пятого процессоров, 9 шагов на «усыпление» пятого процессора, 2шага на поиск подходящей системы уравнения для четвертого процессора) этипроцессоры решают следующие системы переменных:ПРОЦЕССОРПЕРВЫЙЧЕТВЕРТЫЙx3  a4x1  a1x2  a2Присвоения первого и пятого процессора противоречивы с присвоениемчетвертого, так как для первого и пятого процессоров уже получено значениепеременной x1 (2 шага).Выполнив п.

3.5 для этих процессоров имеем:первый процессор V a1,a2 ,a3   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 a 3 , 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 (a6 , a4 , a5 ) V a3 , 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 ) V a5 , a3 , 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a3 , a1, a5   L(a3 , a1, a5 )  L(a4 , a2 , a6 ) на замену всех вхождений переменных на их значения уходит 1 шаг;108четвертый процессор V a 2 , 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 (a6 , a4 , a5 ) V a4 , a2 , 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 a4 , x3 , a3   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 V a3,a4 ,a5   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a4 , a2 , a3   L(a3 , a1, a5 )  L(a4 , a2 , a6 ) на замену всех вхождений переменных на их значения уходит 2 шага.Всего на пп.

3.1-3.6 ушло 8 шагов.На пп. 3.6, 3.7 и 3.8 потребовалось 15 шагов (по пять на каждый пункталгоритма для каждого процессора). Согласно п. 3.9 переходим к выполнению п.3.1. Берем новые рабочие формулы. На их выбор ушел 1 шаг.Согласно п. 3.1 первый процессор меняет рабочую формулу на V a5 ,a3 , x5 (2 шага), четвертый – на V a4 ,a2 , x3  (1 шаг).Согласно п. 3.2 берем для первого процессора отрицание V ( a5 ,a3 ,a6 ) (7шагов), для второго и третьего процессоров V ( a1 ,a2 ,a3 ) (по 1 шагу на каждыйпроцессор) и для четвертого процессора V ( a4 ,a2 ,a3 ) (5 шагов). Итого на пп 3.1и 3.2 9 шагов.Согласно п. 3.3 решаем следующие системы уравнений:ПРОЦЕССОРПЕРВЫЙВТОРОЙТРЕТИЙЧЕТВЕРТЫЙx2  a 2x3  a3x4  a1x3  a2x4  a1x5  a6x6  a3x3  a3109В случае четвертого процессора уравнение x3  a3 решения не имеет, таккак значение a3 уже присвоено переменной x6 .

Все присвоения противоречивы (6шагов) между собой. F-наборы приобретают следующий вид:первый процессор V a1,a2 ,a3   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 a3,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 (a6 , a4 , a5 )   V a3 , a4 , a5   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 V a5 , a 3 , a6   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a3 , a1, a5   L(a3 , a1, a5 )  L(a4 , a2 , a6 ) на замену всех вхождений переменных на их значения уходит 2 шага;второй процессор V a2 , x1, a1   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 a1 , a 2 , a 3   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 a1, a3 , 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 , a1, 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a1, a2 , x6   L(a3 , a1, a5 )  L(a4 , a2 , a6 ) на замену всех вхождений переменных на их значения уходит 7 шагов;третий процессор110 V  x2 , x1, a1   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 a1, x2 , a2   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 a1 , a 2 , a 3   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 V  x6 , a1, 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a1, x2 , a3   L(a3 , a1, a5 )  L(a4 , a2 , a6 ) на замену всех вхождений переменных на их значения уходит 6 шагов;Итого на п.

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

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