Символьное моделирование / S-моделирование задач и конструирование программ

S-моделирование задач

Значительный вклад в моделирование задач принадлежит Энну Харальдовичу Тыугу (Тыугу Э. Х. Концептуальное программирование. — М., Наука, 1984. — 256 c.). Его идеи оказали существенное влияние на формирование предложенного В. Д. Ильиным подхода к s-моделированию задач в системе порождения программ (В. Д. Ильин. Система порождения программ, М.: Наука, 1989, 264 с.).

Представление связей между понятиями в виде разрешимых задач — необходимое условие построения количественных s-моделей систем понятий.

S-задача

□ S-задача — это четвёрка {Formul, Rulsys, Alg, Prog}, где Formul — постановка задачи; Rulsys — множество систем обязательных и ориентирующих правил решения задачи, поставленных в соответствие Formul; Alg — объединение множеств алгоритмов, каждое из которых соответствует одному элементу из Rulsys; Prog — объединение множеств программ, каждое из которых поставлено в соответствие одному из элементов Alg. Постановка задачи Formul — пара {Mem, Rel}, где Mem — множество понятий задачи, на котором задано разбиение Mem = Inp U Out (Inp ^ Out = 0) и совокупность Rel связей между понятиями, определяющая бинарное отношение Rel < Inp ^ Out. Множество Mem называют памятью задачи, а Inp и Out — её входом и выходом, значения которых предполагается соответственно задавать и искать. □

Для каждого элемента из Rulsys, Alg и Prog задано описание применения. Описания применения элементов Rulsys включают спецификацию типа решателя задачи (автономная s-машина, сетевая кооперация s-машин, кооперация человек-s-машина и др.); требование к информационной безопасности и др. Описания применения элементов из Alg включают данные о допустимых режимах работы решателя задачи (автоматический локальный, автоматический распределенный, интерактивный локальный и др.), о требованиях к полученному результату и др. Описания применения программ включают данные о языках программирования, операционных системах и др.

◊ Каждая программа сопровождается ссылками на наборы тестовых примеров. ◊

В общем случае множества Rulsys, Alg и Prog могут быть пустыми: числа их элементов зависят от степени изученности задачи.

S-алгоритм

□ S-алгоритм — система правил решения задачи (соответствующая одному из элементов Rulsys), позволяющая за конечное число шагов поставить в однозначное соответствие заданному набору данных, принадлежащему Inp, результирующий набор, принадлежащий Out. □

S-программа

□ S-программа — реализованный (на языке программирования высокого уровня, машинно-ориентированном языке и/или в системе машинных команд) s-алгоритм, представленный в форме сообщения, определяющего поведение s-машинного решателя задачи с заданными свойствами. Существует в символьном, кодовом и сигнальном воплощениях, связанных отношениями трансляции].□

S-данные

□ S-данные — s-сообщение, необходимое для решения некоторой задачи или совокупности задач, представленное в форме, рассчитанной на распознавание, преобразование и интерпретацию решателем (программой или человеком). Специализация s-сообщения (s-message) по параметру получатель s-сообщения (s-recipient), значением которого является решатель s-задачи (s-solver): s-data ≈ s-message [::s-recipient = s-solver]. □

Конструирование s-задач

Связи по памяти между s-задачами определяются тремя типами функций, каждая из которых является функцией двух аргументов и позволяет поставить в соответствие паре s-задач некоторую третью s-задачу, образованную из этой пары.

Связь s-задач по памяти

□ S-задача a связана с s-задачей b по памяти, если существует хотя бы одна пара элементов {elem Mem^a, elem Mem^b}, принадлежащих памяти Mem^a s-задачи a и памяти Mem^b s-задачи b, относительно которой определено общее означивание (элементы имеют одно и то же множество значений). Если S и H — множества s-задач и 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. □

Тип связи по памяти зависит от содержимого пересечения по памяти: составлена ли связь из элементов выхода одной и входа другой задачи; из элементов выходов задач или из элементов их входов; или же связь получена путём комбинации предыдущих способов.

S-задачные конструктивные объекты, задачная область и задачный граф

Элементарная задачная конструкция — задачная пара. Любая задачная конструкция, в свою очередь, может быть использована как составляющая ещё более сложной задачной конструкции.

□ Cистема pS знаний о задачных конструктивных объектах (называемых также p-объектами) — это триада <pA, lng, intr>, где pA — задачная область, lng — язык спецификации p-объектов, intr — интерпретатор спецификаций искомых p-объектов на pA. Если P — множество всех p-объектов, а A < P — его непустое подмножество, при этом в A (содержащем не менее двух элементов) не существует ни одного элемента, который не был бы связан по памяти хотя бы с одним элементом из A, то s-модель pa задачной области pA — это p-объект, который задаётся парой <память mem^A множества задач A задачной области pA>, <семейство rul (mem^A) связей, заданных на mem^A>. Непустое множество mem^A элементов памяти разбито на три подмножества: входов inp^A задач, выходов out^A задач и подмножество or^A, каждый из элементов которого является и входом, и выходом некоторых задач. Любое одно из этих подмножеств может быть пустым; могут быть одновременно пустыми inp^A и out^A. □

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

S-модель pa задачной области pA служит для интерпретации составленных на языке lng спецификаций искомых задач. Интерпретация заключается в постановке в соответствие некоторому подмножеству (или паре подмножеств) памяти mem^A некоторой подобласти задачной области pA, названной разрешающей структурой. Интерпретация спецификации искомого p-объекта на pA — конструктивное доказательство существования разрешающей структуры.

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

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

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

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

G-графы служат средством формализации знаний о p-объектах. Система знаний об s-задачах обеспечивает процессы p-(специализации, конкретизации и конструирования).

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

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

Интерпретация на 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-графа (или С-графа) в процессе поиска разрешающей структуры заключается в соотнесении означенности входа и выхода.

Правила интерпретации задачной вершины:

• если полностью означен вход, то полностью означен и выход;

• если означенным полагается хотя бы один элемент выхода, то означенным полагается полностью вход.

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

1. Для заданных подмножеств x и y (x ^ y = 0) памяти mem^t-graph, тогда существует разрешающая структура solv^xy (xy — помета) с минимальным числом задачных вершин, вход которой определён посредством x, а выход — посредством y, когда найдётся подграф G, множество вершин которого включает хотя бы одну вершину с разрешимой задачей, а объединение выходов вершин подграфа G содержит подмножество y (или совпадает с ним).

2. Для подмножества x, заданного на памяти mem^t-graph задачного графа, тогда найдётся разрешающая структура solv^x (x — помета), вход которой определён подмножеством x, а выход является непустым подмножеством памяти графа, включающим максимальное число элементов, которые могут быть определены при заданном x, когда x ^ Comput = 0 (Comput < mem^t-graph) и найдётся хотя бы одна вершина с разрешимой задачей.

3. Для подмножества y, заданного на mem^t-graph, тогда найдётся разрешающая структура solv^y с минимальным числом задачных вершин, выход которой содержит y, а вход составлен из элементов, принадлежащих Giv, когда y ^ Giv = 0.

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