Заключение

Конструирование разрешающих структур на задачных графах позволяет путем интерпретации интерактивно формируемой спецификации искомой за­дачи получить структуру задач с известными алгоритмами.

Построение множества задачных конструктивных объектов в составе системы знаний о задачах основано на исчислении p‑объектов.

Важными нововведениями по сравнению с [2-3] является то, что задачные сети заменены задачными графами и в s‑модель p‑объекта введена гиперссылка на набор тестовых примеров.

Примером применения метода построения разрешающих структур на задачных графах может служить интерактивный преобразователь ресурсов с изменяемыми правилами поведения [5].

5. О наборах тестовых примеров в системе знаний о задачах

Применительно к конструированию разрешающих структур на задачных графах существование набора тестовых примеров для каждого p‑объекта – необходимое условие реализации предложенной технологии. Заметим, что тестирование полученной разрешающей структуры входит в конструктивное доказательство ее существования.

◊ Нынешние библиотеки программ различного назначения (в том числе – динамически присоединяемые dll) не удовлетворяют требованиям, предъявляемым к s‑модели задачного конструктивного объекта. В частности, они не содержат ссылок на наборы тестовых примеров. Нет возможности протестировать составляющие нынешних операционных систем и работающих под их управлением приложений.

Правило – продавать программные продукты с заранее оговоренной возможностью доступа к наборам тестовых примеров (выложенных на сайте производителя) – заметно уменьшит число ошибок и уязвимостей на этапе разработки и увеличит вероятность их выявления после начала эксплуатации.

Известно, что составление наборов тестовых примеров требует понимания не только сути задачи, выполняемой тестируемой программой, но и допустимых условий ее применения. Если правило – предъявлять потребителю наборы тестовых примеров – станет обязательным, изменится отношение разработчиков и к изготовлению таких наборов, и к производству программных продуктов ◊.

4. Разрешающие структуры на задачных графах

Рассмотрим принцип действия механизма конструирования на задачном графе. Искомая конструкция задается спецификацией задачи, содержащей описа­ние ее памяти, ограничений на число задачных узлов (и, если необходимо – ограничений, связанных с размером задачи, точностью результата и др.). Заданное описание интерпретируется на задачном графе, который служит представлением интересующей конструктора задачной области. Средством интерпретации спецификаций задач служит механизм конструирования на задачном графе.

Интерпретация на U-графе в процессе задачного конструиро­вания заключается в постановке в соответствие подмноже­ству (или паре подмножеств) элементов его памяти такого подграфа, память которого находилась бы в заданном от­ношении к введенному подмножеству (или паре подмно­жеств). Интерпретации на C-графе и G-графе аналогичны интерпрета­ции на U-графе.

□ Задача t представима на задачном графе graph, если вход inp[t] задачи содержится в подмножестве Giv[graph] U Or[graph], а вы­ход out[t] – в подмножестве Comput[graph] U Or[graph] памяти задачного графа; при этом существует не менее одной задачи из базиса этого графа, вход которой содержится в inp[t] или совпа­дает с ним □.

□ Разрешающей структурой solv[t] на графе graph, поставленной в соответствие некоторой задаче t, называется подграф c минимальным числом задачных вершин, на котором задача t представима □.

 Интерпретация задачного узла U-графа (или С-графа) в про­цессе поиска разрешающей структуры заключается в соотне­сении означенности входа и выхода. Смысл этого определения поясняют правила интерпретации задачного узла: если полностью означен вход, то полностью означен и выход; если означенным полагается хотя бы один элемент вы­хода, то означенным полагается полностью вход.

Механизм построения разрешающих структур ставит в соответствие спецификации исходной задачи подграф на задачном графе путем реализации трех типов поведения в соответствии с тремя типами запросов на конструирова­ние. Для каждого из трех типов запросов в [2] было получено конструктивное доказательство существования разрешающей структуры соответствующего типа. Там эти доказательства были получены применительно к задачным сетям. Схемы доказательств существования разрешающих структур на задачных графах аналогичны. После того как найдена разрешающая структура, начина­ется процесс ее конкретизации в соответствии со специфика­цией условий применения исходной задачи.

3.3. Исчисление p‑объектов

Объединение множеств базовых задачных объектов и сконструированных объектов обозначается через P и называется множеством p-объектов. Совокупность пространств, построенных на подмножествах множества P, называется миром p-объектов (или миром за­дач). Процесс работы с задачными объектами реализуется по принципу «от общего к частному». В системе задачного кон­струирования существуют пространства задачных конструк­тивных объектов, одни из которых содержат представлен­ные в самом общем виде объекты, другие – объекты, полу­ченные путем специализации объектов-прообразов. Множество пространств p-объектов (мир p-объектов) не имеет логических ограничений на расширение.

□ Исчисление задачных конструктивных объектов Igen — это построение некоторого множества T конструктивных объектов (t-объектов, обозначаемых через t) на основе множества B базовых конструктив­ных объектов (b‑объектов, обозначаемых через b) по прави­лам R построе­ния t‑объектов из b-объектов и ранее постро­енных t-объек­тов. Формально Igen — это четверка (lng, B, T, R), включающая язык lng опи­сания объектов и конструкций из объектов, не­пустое множе­ство B базовых объектов, порождаемое множе­ство T (B ^ T = 0; до начала процесса задачного конструиро­вания T = 0) и множество R правил построения объектов □.

Символы conn[x], conn[yx], conn[y] обо­значают функции трех типов, применение которых позволяет построить t-объект из пары уже существующих объектов или конструкций из объ­ектов. Символ pre –обозначение прооб­раза некоторого непус­того множества объектов. Этот сим­вол используется в объ­явлениях и в функциях. Символ im – обозначение образа некоторого объекта (рассматриваемого как прообраз). Этот символ употребля­ется (так же, как и символ pre) в объявлениях и функциях. Множество B состоит из базовых объектов (b-объектов), являющихся объектами первого поколения. Иначе говоря, лю­бой b‑объект не имеет прообраза, но может иметь образы. Лю­бому b-объекту может быть поставлено в соответствие неко­торое непустое множество объектов-образов set(t[im; p(b)]) = im(b) (в левой части символ im является верхней пометой, а p(b) — нижней, обозначающей указатель на объект-про­образ b). Каждый объект-образ t[im; p(b)] имеет единственный объ­ект-прообраз. Любой объект-образ может, в свою очередь, иметь образы. В этом случае он является прообразом своих образов и образом некоторого прообраза. Объект, множество образов которого пусто, будем называть конечным объектом. Объекты, имеющие прообраз и непустое множество обра­зов, будем называть промежуточными объектами. Множество T строится на базисе B по правилам R. В T мо­гут существовать конструкции, построенные из объектов, принадлежащих B, конструкции из b-объектов и ранее по­строенных t-объектов, а также конструкции из t-объектов.

Определены правила построения t-объектов, в соответствии с которыми работает механизм задачного кон­струирования при создании конструкций из b-объектов, b- и t-объектов, а также из t‑объектов.

rul[1]: t| p(b) = b. Правило устанавливает, что объект t| p(b) множества T может быть построен из одного объекта b, принадлежащего множеству B. Слева от вертикальной черты «|» стоит буква t, обозначающая некоторое имя объекта из T; после верти­кальной черты размещен указатель на объект, из которого по­строена конструкция; буква p – символ указателя, а в скобках – имя объекта.

rul[2]: t| p(im(t)) = im(t). Объект t| p(im(t)) множества T, являющийся образом объекта t, может быть получен p‑специали­за­цией t.

rul[3]: t| p(pre(t)) = pre(t). Объект t| p(pre(t)) множе­ства T, являющийся прообразом объекта t, может быть полу­чен p‑обобщением t.

rul[4]: t| p(conc(t)) = conc(t). Лю­бой объект, полученный путем p‑конкретизации, мо­жет быть t-объектом.

rul[5]: t| p(t[*]| p(f,s)) = t[*]| p(f,s). Правило уста­навливает, что t‑объектом может быть любая допустимая конструкция t[*]| p(f,s). Конструкцию t[*]| p(f, s) получаем, применяя функцию связи по памяти conn[*] (f, s), т. е. t[*]| p(f,s) = conn[*] (f, s). Помета * принимает одно из трех значений (x, yx, y), каждое из которых обозначает определенный тип функции conn[*] (имена объ­ектов-аргументов указываются в круглых скобках сразу после символа функции conn[*]). Конструкция t[*]| p(f, s) получена путем применения функ­ции conn[*], аргумен­тами которой служит пара (f, s), для которой допустимы следующие значения: (f: elem(B), s: elem(B)); (f: elem(B), s: elem(T)); (f: elem(T), s: elem(B)); (f: elem(T), s: elem(T)).

3.1. Задачные графы

Задачный граф служит формальным представлением задачной области, рассчитанным на реализацию процесса p‑конструирования и формализацию задачных знаний. Множество вершин графа составлено из задачных объектов. Оно называется задачным базисом графа и обозначается p-basis. Ребро задачного графа — это пара вершин с непустым пересечением по памяти. Нагрузка ребра определяется множеством всех пар элементов памяти, входящих в это пересе­чение. Каждая вершина графа имеет память. Память вершины — это память задачи (или задачной области), которую представляет вершина.

□ Составная задача comp – это подобласть задачной области pA, которая содержит не менее двух элементов из множества задач A и на памяти которой задано разбиение: mem[comp] = inp[comp] U out[comp]; inp[comp] ^ out[comp] = 0, определяющее вход inp[comp] и выход out[comp] составной задачи. Составной задаче поставлен в соответствие ориентирован­ный граф, вершинами которого являются задачи. Каждая вершина помечена именем задачи. Ребра графа — это пары задач с непустыми пересечениями по памяти □. Cоставная задача может быть построена путем последовательного применения функций связи по памяти.

Типы задачных графов. В зависимости от состава вершин определим следующие типы задачных графов: U-граф имеет множество вершин только из простых за­дач; в C-графе хотя бы одна вершина представлена составной задачей и нет вершин, представляющих собой задач­ную область; в G‑графе — не менее одной вершины представлено задач­ной областью (остальные могут быть простыми и состав­ными задачами).

□ Связный граф U‑graph с непустым множеством ребер и задачным ба­зисом p-basis, все элементы которого являются простыми задачами, называется U-графом: U-graph = (p-basis, set[ver]), где set[ver] – множество ребер задачного графа. Объединение памяти задачных вершин, составляющих базис, называется памятью U-графа и обозначается mem[U‑graph]. На памяти U‑графа задано разбиение: подмножеством Giv[U‑graph] зада­ваемых элементов памяти называ­ется подмножество входных элементов; подмножеством Comput[U‑graph] вычисляемых элементов памяти называется подмножество выходных элементов; подмножеством Or обратимых элементов памяти называ­ется разность (mem[U‑graph]) \ (Giv[U‑graph] U Comput[U‑graph]) □.

□ Связный граф с непустым множеством ребер и задачным базисом, в составе которого есть хотя бы одна составная за­дача и нет задачных областей, называется C‑графом и обо­значается C‑graph □.

 □ Связный граф с непустым множеством ребер и задачным базисом, в составе которого есть хотя бы одна задачная об­ласть, называется G-графом и обозначается G‑graph. Память C‑графа и память G‑графа обозначаются и опреде­ляются аналогично памяти U‑графа □.

3.2. G‑графы как средство формализации знаний о p‑объектах

Система знаний о p‑объектах обеспечивает процессы p-(специализации, конкретизации и конструирования)[1]. Возможность существования в задачном графе одного или нескольких уз­лов, являющихся задачными областями, имеет принципи­альное значение для формализации задачных знаний. Кон­кретным воплощением задачной области может быть граф любого типа (U-, C- или G-граф). Тот факт, что G-граф мо­жет замещать задачный узел, открывает логически неограниченные возможности для усложнения задачной области. Она может быть представлена, в частности, посредством G-графа, базис которого состоит только из вершин, пред­став­ленных G­-графами.

3. Система знаний о задачных конструктивных объектах

□ Cистема pS знаний о задачных конструктивных объектах (p‑объектах) – это триада < pA, lng, intr >, где pA – задачная область, lng – язык спецификации p‑объектов, intr – интерпретатор спецификаций искомых p‑объектов на pA □.

Модель задачной области. Пусть P – множество всех p‑объектов, а A < P – его непустое подмножество. При этом в A (содержащем не менее двух элементов) не существует ни одного элемента, который не был бы связан по памяти хотя бы с одним элементом из A.

□ Символьная модель (s‑модель [4]) pa задачной области pA – это p‑объект, который задается парой <память mem[A] множества задач A задачной области pA>, <семейство rul(mem[A]) связей, заданных на mem[A]>. Непустое множество mem[A] элементов памяти разбито на три подмножества: входов inp[A] задач, выходов out[A] задач и подмножества or[A], каждый из элементов которого является и входом и выходом некоторых задач. Любое одно из этих подмножеств может быть пустым; могут быть одновременно пустыми inp[A] и out[A] □.

☼ В s‑модели tr задачной области Tr произвольного треугольника элементами mem[tr] являются стороны (a, b, c), углы (α, β, γ), площадь q, периметр p и др. Семейство rel(mem[tr]) связей включает (α+β+γ=π), (p=a+b+c) и др. ☼.

В отличие от памяти задачи, состоящей из входа и выхода, память задачной области содержит подмножество or эле­мен­тов памяти, каждый из которых может быть или задан (как входной), или вычислен (как выходной). Будем назы­вать такие элементы памяти обратимыми, а or –подмножеством обратимых элементов. Подмножество inp будем называть подмножеством задавае­мых, а подмножество out подмножеством вычисляемых элементов.

Задачная область pA служит s‑моделью [4], на которой интерпретируются спецификации искомых задач, составленные на языке lng. Интерпретация заключается в постановке в соответствие некоторому подмножеству (или паре подмножеств) памяти mem[A] некоторой подобласти задачной области pA, названной разрешающей структурой. Формально интерпретация спецификации искомого p‑объекта на pA – это конструктивное доказательство существования разрешающей структуры.

2.1. Связь между p‑объектами

Функции связи по памяти. Отношения связи по памяти между p‑объектами определяются тремя типами функций, каждая из ко­торых является функцией двух аргументов и позволяет по­ставить в соответствие паре p‑объектов некоторый третий p‑объект, образованный из этой пары.

□ Задача a связана с задачей b по памяти, если существует хотя бы одна пара элементов {elem Mem[a], elem Mem[b]}, принадлежащих памяти Mem[a] задачи a и памяти Mem[b] задачи b, от­носительно которой определено общее означивание (эле­менты имеют одно и то же множество значений). Пусть S и H – множества p‑объектов и D ≤ S * S. Если каждой паре (s[i], s[j]) элементов из D ста­вится в соответствие определенный элемент из H, то будем говорить, что задана функция связи по памяти h = conn (s[i], s[j]). При этом D будем называть областью определения функции conn и обозначать D [conn]. Множество R = {h: elem H; h = conn (s[i], s[j]); s[i]: elem D[conn], s[j]: elem D[conn]} будем называть областью значений функции conn □.

Тип связи зависит от содержимого пересечения по памяти: составлена ли связь из элементов выхода одной и входа дру­гой задачи; из элементов выходов задач или из элементов их входов; или же связь получена путем комбинации предыду­щих способов. Будем обозначать функцию связи по памяти типа вход-вход через conn[x], выход-вход – через conn[yx] и выход-выход – через conn[y].

Родовые связи. Задачный объект может быть прообразом некоторого непус­того множества p‑объектов или образом некоторого прооб­раза; или быть одновре­менно и образом какого-то одного p‑объекта, и про­образом некоторого множества других p‑объектов. Предусмотрены следующие типы родовых связей между p‑объектами: указание на задачу, частную по отношению к исходной (p‑специализация); указание на задачу, которая служит обобщением исход­ной (p‑обобщение).

Конструирование. Реализуется посредст­вом связи по памяти при образова­нии задачных конструкций (p‑конструирование). Элементарная задачная конструкция — это задачная пара. Из задачных пар можно построить более сложную задачную конструкцию, если рассматривать их как элементы, подоб­ные задачам. Любая конст­рукция, в свою очередь, может быть использована как со­ставляющая еще более сложной конструкции.

Конкретизация задачного объекта. Переход формулировка → алгоритм → программа представляет собой конкретизацию задачного объекта (p‑конкретизацию), которая служит фор­мальным отражением процесса автоматизированного конструирования программы.

Атомарный p‑объект. Задачный конструктивный объект называется атомарным, если его формулировка не представлена в виде структуры, заданной на некотором множестве формулировок других p‑объектов. Будем также говорить об атомарном p‑объекте как о простой задаче. Простая задача (с точки зрения построи­теля задачных конструкций) не наделена внутренней струк­турой и потому не подлежит декомпозиции. Простые задачи используются для создания конструкций. Каждая созданная конструкция может быть объявлена некоторым новым p‑объектом. В свою очередь, эти новые объекты вместе с атомар­ными могут быть применены при p‑конструировании.

2. Задачный конструктивный объект (p‑объект)

Исходим из того, что одной формулировке могут соответствовать несколько алгоритмов, а каждому алгоритму – несколько программ.

□ Будем называть задачным конструктивным объектом (задачей, задачным объектом или p‑объектом) триаду {Formul, Alg, Prog}, где Formul – постановка задачи, Alg – множество алгоритмов, поставленных в соответствие постановке задачи, Prog – объединение множеств программ, каждое из которых поставлено в соответствие алгоритму из Alg. Постановка задачи Formul – это пара {Mem, rul}, где Mem – множество символьных представлений понятий задачи, на котором задано разбиение

Mem = Inp U Out (Inp ^ Out = 0), а rul – правило [5], задающее на Mem бинарное отношение Rel [rul (Mem)] < Inp * Out. Назовем множество Mem памятью задачи, а Inp и Out – входом и выходом задачи, значения которых предполагается соответственно задавать и искать □.

☼ Формулировка задачи линейного программирования. Вход задачи Inp = {матрица a [i = 1…m, j = 1…n] коэффициентов ограничений, вектор b [i = 1…m] правых частей ограничений, вектор c [j = 1…n] коэффициентов целевой функции}. Выход Out = {искомый вектор x [max; j = 1…n]}. Правило rul максимизации по x [j = 1…n] целевой функции c [j = 1…n] * x [j = 1…n]) при ограничениях a [i = 1…m, j = 1…n] * x [j = 1…n] ≤ b [i = 1…m] и x [j = 1…n] ≥ 0 имеет следующий вид: max [x [j = 1…n]: a [i = 1…m, j = 1…n] * x [j = 1…n] ≤ b [i = 1…m], x [j = 1…n] ≥ 0] (c [j = 1…n] * x [j = 1…n]) ☼.

Различия между алгоритмами из множества Alg определяются задаваемым описанием применения (ограничениями на предельный размер задачи, точность полученного результата и др.), а различия между программами – выбранными языками программирования и операционными системами. ◊ Каждая программа сопровождается обязательной ссылкой на набор тестовых примеров, что необходимо для проверки ее работоспособности ◊.

Задачный объект наделен структурой в виде конечного дерева, кор­нем которого является вершина, помеченная формули­ровкой, а листьями — вершины, помеченные программами.

Спецификация p‑объекта. 
□ Спецификация spec задачи – это пара (Formul, as), где as – описание применения □.

1. О языке спецификации задачных конструктивных объектов

Применяемая в статье система формальной записи соответствует языку спецификации задачных конструктивных объектов, предложенному в [2]. С тех пор язык был усовершенствован (добавлены графические средства описания блок-схем и др.). Поясним используемые в статье средства этого языка.

Запись теоретико-множественных утверждений. a: elem A ≈ a – элемент множества A; A: set a ≈ A – множество, содержащее элемент a; A < B (когда оговорено, что A и B рассматриваются как множества) ≈ A –подмножество B; B = D ≈ множества D и B совпадают; C ≤ B ≈ C является подмножеством B или совпадает с ним; B > A ≈ B содержит A; A ≥ E ≈ A содержит E или совпадает с E; A ^ B ≈ пересечение множеств A и B; A \ B ≈ разность множеств A и B; A * B ≈ декартово произведение множеств A и B; R ≤ A * B ≈ бинарное отношение, заданное на множествах A и B. Символ 0 обозначает пустое множество или нуль (в зависимости от контекста); символ # обозначает «не равно». ☼ Если x: elem X, y: elem Y и x = y, то x: elem(X ^ Y); если X: set x, Y: set y и пара (x, y): elem R, где R < A * B, то (X * Y) ^ (A * B) # 0 ☼.
 

Индексы и пометы. Не накладывается никаких ограничений на максимальное число индексов и помечающих символов (помет). Все индексы и пометы записываются в строчку внутри квадратных скобок, следующих сразу за индексируемой (или / и помеченной) переменной. Индексы, определяющие элемент массива, отделяются запятыми. Верхний индекс от нижнего отделяется точкой с запятой «;». Если в описании индекса точка с запятой не встречается, то индекс считается нижним. ☼ x [out; j = 1…n] ≈ вектор из n компонент, имеющий помету out; a [inp; i = 1...m, j =1...n] ≈ матрица размера m * n, имеющая помету inp ☼.

Запись функций. Аргументы функции размещаем в круглых скобках, стоящих сразу за идентификатором, обозначающим функцию: f (x) ≈ f от x; f [max;] (x[i = 1…n]) ≈ f с верхней пометой max от x[i = 1…n]. Для записи суммы вместо заглавной «сигмы» используется sum; при этом индекс суммирования, его начальное и конечное значения записываются в квадратных скобках справа от sum: sum [i=1...n] ≈ сумма по i от 1 до n.

Конструирование разрешающих структур на задачных графах системы знаний о программируемых задачах

А.В. Ильин

Аннотация. Изложен метод конструирования разрешающих структур на задачных графах системы знаний о программируемых задачах. По спецификации исходной задачи ищется подграф задачного графа, все вершины которого представлены задачами с известными алгоритмами.

Литература

1. Библиотека Численного Анализа. НИВЦ МГУ.

http://num-anal.srcc.msu.su/lib_na/libnal.htm

2. Ильин В.Д. Система порождения программ. М.: Наука, 1989, с. 264

3. Vladimir D. Ilyin. A Methodology for Knowledge Based Engineering of Parallel Program Systems // Proc. of the Eight Int. Conf. «Industrial and Engineering Applications of Artificial Intelligence and Expert Systems», Melbourne, Australia, 1995, p. 805-809

4. Ильин В.Д., Соколов И.А. Информация как результат интерпретации сообщений на символьных моделях систем понятий. – Информационные технологии и вычислительные системы, №4, 2006, с. 74-82

5. Ильин А.В., Ильин В.Д. Интерактивный преобразователь ресурсов с изменяемыми правилами поведения. – Информационные технологии и вычислительные системы, №2, 2004, с. 67-77

Введение

Существует огромное число задач, запрограммированных на различных языках и реализованных в составе системных и прикладных комплексов. Какие это задачи, к каким классам отнесены? Где можно найти сведения об их формулировках, методах, алгоритмах и тестовых примерах? Как использовать этот арсенал при разработке программ?

Идея автоматизации программирования заключается в том, чтобы использовать ранее полученные результаты в последующих разработках. Как должны быть представлены эти ранее полученные результаты, чтобы служить основой автоматизированной разработки?

Уже на начальных этапах автоматизации программирования вместе с языками и трансляторами стали создавать и различные библиотеки программ. Примером одной из таких библиотек может служить БЧА НИВЦ МГУ [1]. Что требуется для объединения подобных библиотек и тех программ, которые успешно работают, но не входят ни в какие библиотеки? Какой должна быть система знаний о программируемых задачах, чтобы служить основанием для конструирования программных систем?

Один из возможных ответов на этот вопрос был предложен в [2] применительно к порождению программ. В [3] этот подход был применен в методологии конструирования параллельных программ.

В данной статье предложены усовершенствованные (по сравнению с изложенными в [2-3]) подходы к представлению знаний о программируемых задачах и конструированию разрешающих структур на задачных графах. Работа выполнена в рамках создания методологии построения и применения символьной модели системы знаний информатики [4].

Обозначения. Для записи определений, примеров и замечаний применяются обозначения, используемые при создании символьной модели системы знаний информатики:

□ <текст> □ - определение;

☼ <текст> ☼ - пример;

◊ <текст> ◊ - замечание;

      ≈ - символ заменяет слово «означает».