Содержание к диссертации
Введение
Глава I. Состояние вопроса и постановка задач 12
1.1. Модель поведения субъекта в управлении... 14
1.2. Троичные векторы дискретного щ-мерного пространства 15
1.3. Троичные векторы как прообразы принимаемых решение 17
1.4. Субаксиоматическое моделирование и таблицы решении 19
1.5. Задача субаксиоматического программирования 23
Глава 2. Методология субаксиоматического моделирования 25
2.1. Условия существования субаксиоматической модели 25
2.2. Алгоритм моделирования 32
2.3. Язык моделирования 34
2.4. Пример субаксиоматического моделирования... 40
Глава 3. Методика субаксиоматического программирования 51
3.1. Критерий оптимальности 51
3.2. Метод последовательного обхода и построения дерева перебора на множестве условий 54
3.3. Лес решений 59
3.4. Теорема об однородных строках троичной матрицы 6
3.5. Алгоритм оптимизации исходного описания... 62
3.6. О параметрах стратегии выбора условий ветвления при формировании дерева решений 63
3.7. О предпочтительности сбалансированной схемы.. 68
3.8. Алгоритм выбора ветвящейся вершины 70
3.9. Ретранслированиывтаблицы решений 73
3.10. Исследование зависимости средней длины ветвей дерева от числа висячих вершин 77
Глава 4. Практическая реализация задач субаксиоматического моделирования и программирования в системах, автоматизированного проектирования программного обеспечения АСУ '... 83
4.1. Язык кодирования логических и арифметических операторов 83
4.2. Средства трансляции языка кодирования 84
4.3. Пример проектирования программного модуля... 89
4.4. Основные характеристики препроцессора 95
Анализ результатов и выводы 104
Литература
- Модель поведения субъекта в управлении...
- Условия существования субаксиоматической модели
- Метод последовательного обхода и построения дерева перебора на множестве условий
- Язык кодирования логических и арифметических операторов
Модель поведения субъекта в управлении...
При рассмотрении поведения субъекта в процессе управления некоторой сложной системой (объектом) следует выделить: &e{.ft,i,...,fgJ - конечное множество принимаемых субъектом решений, определяющее все Доступные ему возможности воздействия на объект; С = {С С , ..., (т)} - конечное множество условий, в зависимости от которых в каждом конкретном случае принимается решение rK еД, (K US ) Будем считать, что проверка каждого из условий Ct , Сг э » » Ст может иметь только два возможных исхода (либо С/. (Цг7?)выполнено, либо нет). Поэтому элементы множества (D С ... С} будут булевыми переменными с областью значений
Тогда точки тп- мерного пространства с осями координат , С , Са э , . . f Сгр будут являться вершинами единичного и - мерного гиперкуба, число которых равно 2 .
Если В- множество вершин этого гиперкуба, то поведение субъекта может быть определено однозначным отображением ; В — {r р ...г}» которое может быть определено следующим выражением: t - однозначное отображение = 4=»(VieB)(3iK u,.,,s Ц(Ьугк1 -истинно /.;.:; (і.І) На множестве Ш выделим подмножества Bt , 3 ... g в соответствии с правилами
Утверждение I. Множество і Бі 964,..1, 3si подмно жеств множества В , определенных в соответствии с (1.2), является раабиением этого множества тогда и только тогда, когда f - однозначное отображение.
Полученные множества троичных векторов Dj) каждого из подмножеств Ьк (к - its ) можно объединить в одно множе-ство 6 — і 6t , &z , ... ч 5 } а модель поведения субъекта представить однозначным отображением : В " «& ($=//7,/2,..., }) J которое обеспечивает определение элементов разбиения { 6 , . .., 6s } множества 1В согласно выражением
Данная модель удобнее не только тем, что в большинстве, случаев к 6 , но еще и тем, что элементарная конъюнкция Ж , определяющая обобщенную точку 8- , в ттг-мэрном дискретном пространстве, может быть только компактнее конъюнкции, определяющей точку 6 ев . Если элементы множества В определяют состояние объекта управления, то обобщенные точки определяют только некоторые обобщенные понятия, характеризующие эти состояния. Эти обобщенные понятия более наглядны и более удобны для оценки субъектом, чем сами состояния. Так, например, шахматист оценивает позицию не состоянием, которое определяет размещение всех фигур на доске, а наличием скрытых шахов, вилок, связок, матовых ситуаций. Однако данная модель имеет один существенный недостаток. В ней элементы множества { С1, Са Ст } рассматриваются как независимые переменные, хотя на практике возможны случаи их взаимозависимости. Например, если координатными осями трехмерного-дискретного пространства Ct 9 С2 , С3 являются условия ct & ft уд ; Q2 =e z. {jh \ С5 = уз J , то одна из вершин единичного куба, а именно вершина і =. 6(1,1,1"), определяется условием которое не выполняется при любых значениях переменных Цх , uz , Цъ , и, следовательно, объект управления никогда не будет находиться в состоянии Ь - 6(1,1,1) , так как свойство транзитивности бинарного отношения накладывает ограничение откуда следуют зависимости
Аналогично в абстрактном случае, если на множестве {Cj , С2 . . ., т ... ,Ст) имеются зависимости, то некоторые вершины т -мерного единичного гиперкуба не являются возможными состоя А ниями объекта управления. Пусть В - множество таких вершин, тогда B=B\ о есть множество состояний объекта. Поэтому модель поведения субъекта, допускающая зависимости между элементами множества { i» С , ..., Ст } должна быть V V представлена отображением f : S " (rt f , ...,r } » где Л {$,Д, .... Ец} . а 6у =В/йЙ.
Однако формирование множества В как формальными, так и неформальными средствами имеет определенные трудности. Поэтому предлагается остановиться на модели, определяемой отображением f множества J5ss{B1, -BSL,... Bn}, которое составлено из элементов множества D , обозначающих обобщенные точки, содержание по крайней мере одну точку дискретного лг-мерного пространства, определяющую состояние объекта управления, в { j lj,..., j} (Ji& t7iJ$?i) . Поскольку отброшенные обобщенные точки определяются тождественно ложными предикатами, которые легко распознаются субъектом, хотя имеются трудности для общего случая их формального распознавания, поэтому задачу определения тождественной ложности логического выражения $} очевидно, следует возложить на человека, осуществляющего моделирование .
Условия существования субаксиоматической модели
ТР, являющаяся формой отображения субаксиоматической модели, определяется совокупностью четырех множеств t6?] где С - ICi,Ъ.1 -» С,, - t Єщ}- определенное ранее множество условий; $ t i Дг,. мВу,..., 6П} -множество вектор - столбцов троичной матрицы 4у11 » определяющих ситуации согласно выражения (1.9) ; & = { A t f А;,,..., Л tt ,... » Ас ) - множество дейст вий (арифметических и управляющих операторов) ; «F = { F,, F2 ,... t fj , -.. , fn } - множество столбцов, каждый из которых обеспечивает задание на множестве кортежа гк є .
Пара С, Ъ инициирует множество 1 ,2 ,...,- } согласно (1.9), а пара Jtf F инициирует множество принимаемых решений - Д согласно следующего правила. Принимаемое решение ze инициируется столбцом fj = \у , iy , ..., hj (далее / —I(F/) будет означать, что Я инициирует / ), элементы которого удовлетворяют условиям Здесь условие fM? = Л означает, что в ситуации , J v/ оператор Аи не используется. Следовательно, правило решения )о/ t в ТР инициируется парой столбцов В.-, R .
Определение б. Пару В-, R будем называть сбойным соответствием, если Б- и R- удовлетворяют условиям J J (W) [ h,. = ЛІ ; ( t= ї й ; « = ,;/ = 17). Определение V. Будем говорить, что условие ( избыточ но, если Ьц = 3/2 — ... = 6/ т"1 Л (заметим, что в том случае, если bi t - bijL =. . . . = 6,- = X » условие С; не может быть элементом множества & ).
Определение 8. Столбцы »j и &j/ будем считать ортогональ ными [2І] ( В. JL &/ ), если выполнено условие
Определение 9. Вектор-столбец а = 5(4-1,d , ...,im ) ортогонален троичной матрице Цйл-Ц (а 1 Jfi.. ) если он ортогонален всем столбцам этой матрицы. Определение Ю. Будем говорить, что пара правил решения, инициируемых парами столбцов (б- , Г; и By , Fj» , образует двусмысленность, если столбцы uj и 6г» неортогональны, а столбцы Fy и Гу неэквивалентны ( fy Ф F» ). Определение II. Булеву функцию " , инициированную вектор-столбцом 5 (6f— Kjp) , который ортогона лен троичной матрице II // II , будем называть неописанной ситуацией, если она удовлетворяет Определению I. Следовательно, каждой ТР в общем случае соответствует некоторое множество неописанных ситуаций { 1(9Д, Г( г),.,. ,Kj )j. Определение 12. Будем называть ТР абсолютно полной, если ей соответствует пустое множество троичных векторов, ор тогональных троичной матрице 11% 1 , и логически пол ной, если любой из вектор-столбцов Jz ( "С = if "6 ), ор тогональных матрице ИБ,у , инициирует тождественно ложный предикат (НФГ)НО). Ошибками описания рассматриваемых ТР будем считать сбойные соответствия, избыточные условия, двусмысленности и неописанные ситуации.
Теперь предположим, что W 1( »ЙЛ ... п) 0, где о - булева функция, определяемая ДНФ логического выражения, которая не является тождественно ложным предикатом. Поэтому в этой ДНФ найдется такая элементарная конъюнкция, которая определяет булеву функцию УФЪ . Тогда имеет место условие (2.5), равносильное инверсии условия (1.7). Лемма доказана.
Теорема I. Отсутствие сбойных соответствий в описании ТР есть необходимое условие отсутствия в нем двусмысленностей.
Доказательство. Предположим противное. Пусть (2.1) не выполняется, т.е. найдется такая пара столбцов 8« F- » Для которых выполнены утверждения не ортогональны. Следовательно, условие (2.3) также не выполнено. Это противоречие доказывает данную теорему. Теорема 2. Отсутствие избыточных условий в описании ТР есть необходимое условие его логической полноты.
Доказательство. Предположим противное. Пусть П. - избы?-.- точное условие, т.е. ЬСі - Ь1г = ... = Ьіп і С І -Ц-Я 0). Тогда существует троичный вектор ty , ортогональный троичной матрице II 6- , с координатами и 9/ - 0 (4/=1) ,который инициирует булеву функцию 1(5) = 1С,. ( Ку) = С4- ) . Но, так как Q. -условие, влияюшее на выбор альтернативы (т.е. С не может быть тождественно ложным либо тождественно истинным предикатом), то К а) - неописанная ситуация, что противоречит условию (2.4) и доказывает данную теорему.
Метод последовательного обхода и построения дерева перебора на множестве условий
Предлагаемый алгоритм трансляции основан на методе последовательного обхода и построения дерева перебора на множестве {Сі,Сг,..., Ст } или методе деревьев [121 . Суть его в следующем.
Пусть Т= С, ,Л,$Г - исходное описание ТР. Поставим его в соответствие корню их искомого дерева решений. Из вершины ut проводятся две дуги, левая из которых метится символом С« а правая - символом 1С- , где С - произвольно выбранный элемент из множества С . Дуга С; (1С ) входит в вершину иг (и$) которой соответствует описание ТР Tz (Т3) полученное из Т вычеркиванием из нее правил решения, для которых 6..=0 (6,у =D» пустых строк и I -й строки, т.е. Тг = С? Я , Л, Fz , где где Здесь матрица 1 в . (ІІв /К) составлена из столбцов множества $ Ш. (i,c = l,rn , J= i,n ). uip ч,І%
Вершина аЛ , которой соответствует ТЛ ( с=2,3,...) объявляется висячей, если 0 0 \ в противном случае и ос объявляется ветвящейся вершиной, и для нее осуществляются пост роения, аналогичные описанным выше построениям для вершины и± Процесс построения дерева решений завершается, когда не останется ни одной ветвящейся вершины. Определение 17. Описанный выше алгоритм далее будем называть Н - алгоритмом. Определение I&. Будем говорить, что дерево решений d рациональнее d" ( d t oL" є & ; 3 - лес решений для некоторой ТР), если (kU ) (X(d") .
Определение 19. ТР Т " , соответствующую вершине UOL формируемого дерева решений, будем называть к- вырожденной, если каждый из ее столбцов поля IV иницирует решение rK (I(f)= ку= ...=НР„;) = Ъ ).
Каждой из вершин и дерева решений соответствует две булевы функции, одна из которых определяется элементарной конъюнкцией из меток дуг участка ветви между вершинами и± и ик - далее эту булеву функцию будем обозначать S" —, а другая г$г иницируется троичной матрицей II6?. , представленной в поле II таблицы Т0 ".
Очевидно, для корня ut дерева решений S" SI, а лГ1 иницируется троичной матрицей II Ь \\ , представленной полем II исходного описания ТР (см.рис.2.1), т.е. = #, У % v ... v »n . (3.5) Если из и, выходят дуги С/ и "ТС;, входящие в вершины г и иь соответственно, то вершине 1 2. (из ) соответствуют булевые функции $-г С- ( #3 = ТС» )и &г4=ьф-1лС1 ( оРэ = лр1 л і С/), что вытекает непосредственно из Н-алгоритма. Поэтому для любой вершины ( ос = 1,2, ...) справедливо соотношение KF1 Ф= F\ (З.б) 5?
Теорема 6. Для каждой вершины дерева решений, полученного по Н - алгоритму из логически полной ТР, справедливо соотношение ф= ФЛ.
Доказательсво. Для логически полных ТР с учетом (3.5), Леммы 2 и Теоремы 3 с 1- тождественно истинная булева функция. Следовательно, откуда с учетом (З.б) имеем что и требовалось доказать.
Теорема 7. Каждая висячая вершина и дерева решений, полученного по Н - алгоритму из ТР, удовлетворяющей условию (2.3) отсутствия двусмысленностей, соответствует некоторой к - вырожденной ТР ( к ЇІ? ).
Доказательство. Предположим противное. Пусть для некоторой произвольной висячей вершины и ( Т" - 0 Л & fc =0 ) Т в поле ІУ содержит по крайней мере два отличных друг от друга столбца и Fjr , инициирующих альтернативные решения ( HF/4) Ф ГСF -) ). Этим решениям соответствуют правила 6у , F/ и By/, Fjv , где с учетом Н-алгоритма R = F ; ff - Fjr , & =Ф- - ; Іо= "-S/
Язык кодирования логических и арифметических операторов
Для того, чтобы рассматриваемые выше программные средства обеспечили возможность получения готовых программных модулей необходимы дополнительные усилия для разработки: 1) языка кодирования логических и арифметических выражений в ТР; 2) средств трансляции для этого языка.
Ниже предлагается один из вариантов такого языка и средства, его трансляции, работа которого иллюстрируется приведенным примером, и приводится оценка эффективности предлагаемого программного комплекса автоматизированного проектирования алгоритмического и программного обеспечения АСУ на базе ТР.
Язык кодирования логических и арифметических выражений
Предлагаемый для кодирования логических и арифметических выражений язык представляет собой общепринятую форму записи формул и соотношений. Синтаксис языка определяется следующей совокупностью правил: 1) целочисленные и вещественные константы кодируются в соответствии с общепринятыми правилами их записи (в десятичных дробях целая часть от дробной отделяется запятой); 2) для обозначения переменных используются прописные буквы латинского алфавита. При этом идентификаторы переменных, принимающих целочисленные значения начинаются с букв I , J , К L М , N . Идентификатор переменной не может содержать более 6 знаков ; 3) в кодировании логических и арифметических операторов допускается использование только круглых скобок ; 4) для обозначения арифметических и логических операций используются знаки +, -, ,/, , и т.д., которые имеются в наличии у перфорирующих устройств в среде ОС ЕС, и прописные буквы русского алфавита, не совпадающие по начертанию с буквами латинского алфавита; 5) идентификатор функции должен заключаться в квадратные скобки ; 6) логические и арифметические выражения должны заканчиваться знаком ";и (здесь точка с запятой есть признак конца выражения).
В языке отсутствуют понятия массива и операций над массивами. Исходные и выходные данные проектируемых подпрограмм представлены перечнем простых переменных.
Средства трансляции языка кодирования Данные средства трансляции разработаны на базе транслятора языка Фортран-1У. Проектируемый программный продукт представляется подпрограммой в кодах языка Фортран-1У, которая затем транслируется, редактируется и загружается в библиотеку объектных модулей средствами ОС ЕС.
Перед формированием текста подпрограммы на языке Фортран-1У каждое из выражений (логическое или арифметическое), представленное в исходной ТР, преобразуется в обратную польскую (постфиксную) запись с целью определения последовательности вычислительных операций в данном выражении. Затем идентификаторы этих операций и функций замещаются соответствующими им идентификаторами языка Фортран-ІУ. Таблица , соответствий идентификаторов операций и функций исходного описания операциям и функциям языка Фортран-ІУ (ТСИОФ) долина присутствовать в исходном описании задачи.
Структура исходного массива представлена на рис.4.I. Каждая строка изображенной здесь матричной формы соответствует одной перфокарте и имеет 80 элементов. Этот массив состоит из 7 частей (см.рис.4.1): 1) нулевая карта массива ТСИОФ; 2) карты массива ТСИОФ ; 3) нулевая карта массива ТР ; 4) карты описания логических операторов массива ТР; 5) карты описания арифметических, операторов массива ТР; 6) карты описания ограничителей действия арифметических операторов ТР; 7) карта идентификатора проектируемой подпрограммы. 4.2.1. С 1-й позиции нулевой перфокарты массива ТСИОФ набивается двузначное число L , определяющее длину этого массива. 3-я, 4-я и все последующие позиции этой карты не используются.
4.2.2. С 1-й по 13-ю позиции L -й карты массива ТСИОФ ( і і L. ) набивается ее идентификатор, которым определяется одна из версий таблицы соответствия (ТСИОФ) и номер карты - і . В 14-й позиции набивается разделитель, отделяющий поле идентификатора карты от ее основного поля. С 1-й по 16-ю карты массива ТСИОФ в 15-й позиции набивается знак операции, а в последующих картах этого массива набивается идентификатор функции на языке кодирования длиной LF С LF«14), С 30-й позиции первых 16 (последующих 17-й, 18-й ,...., L-й) карт набивается знак операции (идентификатор функции) в кодах языка Фортран-ІУ. В 45-й позиции набивается приоритет
