Решатель вычислительных задач для TK Solver.
1. Решатель вычислительных задач.
2. Планировщик.
3. База знаний.
4. Вычислительная задача.
5. Вычислительная модель.
6. Графическое представление вычислительной модели.
(1). Решатели вычислительных задач принадлежат к классу ИППП. Они позволяют пользователю решать задачи с помощью ЭВМ по исходным данным, по описанию задачи, без программирования алгоритма решения. Программирование осуществляется автоматически программой-планировщиком из набора готовых программных модулей, относящихся к данной предметной области.
(2). Планировщик является ядром ИППП. Его цель – получение плана решения задачи пользователя, формулировка которой поступает на вход подсистемы планирования. План решения задачи в ИППП трактуется, как поиск программы, решающей эту задачу. При этом программа решения задачи может конструироваться либо явно, на каком-либо из алгоритмических языков программирования, либо существует в виде шагов работы планировщика. В первом случае ИППП является транслятором; во втором варианте, когда программа решения задачи не конструируется явно, а существует в виде шагов работы планировщика, планировщик работает в режиме интерпретации и является, по сути, интерпретатором с языка описания задач.
Как в первом, так и во втором вариантах, работа планировщика отличается от функционирования общего транслятора с алгоритмического языка программирования.
Если функцией обычного транслятора является преобразование входной программы входного алгоритмического языка программирования в язык машинных команд ЭВМ, то основная задача планировщика – синтез алгоритма программы решения задачи по декларативному описанию формулировки задачи. Синтез осуществляется с использованием БЗ.
(3). БЗ в ИППП описывается на языке спецификаций, задачи формулируются на языке формулировок задач. В общем случае это может быть один и тот же язык. Пользователь, применяющий ИППП для решения прикладных задач, выступает обычно в двух ролях:
1. Как инженер по знаниям, т.е. специалист предметной области, – когда описывает содержимое БЗ.
2. Как кодировщик задач, – когда формулирует задачи с использованием накопленных в ИППП знаний.
Знания БЗ могут быть представлены с использованием различных моделей. В наиболее развитых ИППП в каестве модели предметной области используются так называемые вычислительные модели. На основе вычислительных моделей формулируются вычислительные задачи.
(4). Вычислительная задача формулируется в рамках некотрой предметной области, рассматриваемой, как совокупность обхектов и отношений между ними. При этом рассматриваются только такие объекты, на основе которых можно осуществлять вычисления. Между объектами существуют отношения вычислимости, задаваемые в виде функциональных отображений. Объекты могут быть простыми или составными. В составном объекте между его компонентами имеют место структурные отношения. Объекты и отношения между ними описываеются на некотором языке. Объектам в этом языке соответствуют переменные, а отношениям – функции. Значения переменных – данные.
Вычислительная задача имеет следующую форму:
ЗНАЯ М ВЫЧИСЛИТЬ У1, У2… Уn ПО Х1, Х2…Хm.
Здесь М, У1, У2…Уn, Х1, Х2…Хm – это переменные, которые имеют смысл, определяемый их вхождением в задачу. Идентификаторы ЗНАЯ, ВЫЧИСЛИТЬ, ПО имеют фиксированный смысл и служат для разделения переменных. Переменные Х1, Х2…Хm являются входными для задачи, значения их задаются в постановке задачи. Переменные У1, У2…Уn – выходные, их значение требуется вычислить. М – переменная, значения которй выражают условие задачи. Данные, являющиеся значением М выражают значения в виде вычислительных моделей, включающих в свой состав переменные и отношения между ними.
(5, 6)Вычислительную модель можно представить графически, с помощью языка спецификации и с помощью функции некоторого логического языка.
Графическое представление вычислительной модели – семантическая сеть специального вида, узлам которой соответствуют переменные и отношения. Переменные обозначаются точками, отношения – кружочками, овалами или прямоугольниками, внутри которых помещается описание реализации отношений.
Связи между переменными и отношениями могут быть следующих типов:
входные (переменная является входной для отношений).
выходные (переменная является выходной для отношений).
слабая связь (переменная может быть как входной, так и выходной).
сильная связь (значение переменной меняется отношением).
определяющая связь (значение переменной определяет возможность применения отношения).
На рисунке приведён пример вычислительной модели КВАДРАТ, где в качестве отношений используются отношения типа уравнение. Все переменные, входящие в уравнения, являются слабосвязанными, т.е. любая из переменных может быть либо входной, либо выходной для уравнения.
На одной вычислительной модели может быть решено много вычислительных задач. Например, при ВМ КВАДРАТ можно решать следующие задачи:
1. вычислить ПЕРИМЕТР по СТОРОНА.
2. вычислить СТОРОНА по ПЕРИМЕТР.
3. вычислить ПЛОЩАДЬ по СТОРОНА.
4. вычислить СТОРОНА по ПЛОЩАДЬ.
5. вычислить ПЕРИМЕТР по ПЛОЩАДЬ.
6. вычислить ПЛОЩАДЬ по ПЕРИМЕТР.
Проводить такие вычисления можно при условии, что для уравнения всегда можно построить его разрешение относительно любой из входящих в него переменных. Если, например, у уравнение входит n переменных, то будем иметь n функций разрешений. Записывается это обычно в виде:
x = f (x, x,.., x, x…x)
Здесь х – переменная, входящая в уравнение, f – реализация функции, вычисляющей значение j – переменной в уравнении с номером i (i=1…k, k – число уравнений в ВМ). Уравнения считаются независимыми друг от друга и являются компактным отношением множества разрешающих функций.
Входной язык ИППП обычно допускает использование уравнений при описании ВМ. После преобразования такого описания во внутреннее представление БЗ, уравнения заменяются функциями разрешения и в БЗ уравнения хранятся в форме однооператорных отношений, т.е. без использования слабосвязанных переменных. Для уравнения из примера, такими разрешениями являются:
Периметр = 111(сторона)
Сторона = 121(периметр)
Площадь = 112(сторона)
Сторона = 122(площадь)
В однооператорном отношении имеется одна выходная переменная, остальные являются входными для отношения, и однооператорное отношение показывает, значения каких переменных должны быть известны для того, чтобы можно было вычислить значения выходных переменных. Замена уравнений в вычислительной модели их функциями разрешения позволяет избавиться от слабо связанных переменных и тем самым получить описание вычислительной модели в виде двудольного ориентированного графа (орграфа).
Однако ВМ с использованием однооператорных отношений ещё не является алгоритмическим описанием – в модели не зафиксирован порядок выполнения операторов. Поэтому такое описание, по сути, задаёт потенциальное множество алгоритмов, которые могут быть сконструированы с использованием отношений ВМ. Конкретный алгоритм может быть получен, если к ВМ присоединить формулировку задачи в виде:
ЗНАЯ <ВМ>ВЫЧИСЛИТЬ <ВЫХОДЫ ЗАДАЧИ>ПО<ВХОДАМ ЗАДАЧИ>
ВМ и присоединённая к ней формулировка задачи образуют модель задачи. Формулировка задачи разбивает множество входящих в ВМ переменных на 2 подмножества: входные переменные, значения которых известны до решения задачи, и выходные переменные, значения которых необходимо вычислить.
Если входных переменных достаточно для нахождения выходных с использованием решающих функций, которые содержит ВМ, то задача является разрешимой, и для её решения может быть сконструирована программа.
Обычно поиск решения задачи (т.е. программы) сводится к отысканию пути в орграфе модели задачи, ведущего от исходных данных задачи к её результатам. Нахождение такого пути в ИППП осуществляет планировщик. Планирование при этом называют планированием от данных, возможен и другой подход: планирование от цели, в этом варианте планировщик ищет путь от выходных переменных к входным. Возможна и комбинация этих вариантов. Например, в системе ПРИЗ используется метод прямой и обратной связи. Выписывание встречающихся на этом пути функций разрешения в форме, например, операторов присваивания, даёт описание плана (алгоритма) решения задачи. Так, например, если на ВМ КВАДРАТ сформулировать задачу:
ЗНАЯ КВАДРАТ ВЫЧИСЛИТЬ ПЛОЩАДЬ ПО ПЕРИМЕТР,
будет получен следующий план вычислений в форме присваиваний:
Сторона: = 121 (периметр
Площадь: = 112 (сторона)
В функциональной форме это записывается в следующем виде:
Площадь: = 112 (121 периметр)
Графическое представление ВМ достаточно полно описывает суть вычислительных задач. Однако в этом представлении отсутствует информация о типах объектов модели задач не с позиций приведения вычислений в принципе, а с использованием ЭВМ.
Для реализации вычислений на ЭВМ с каждым объектом, необходимо указать тип его данного с точки зрения множества принимаемых этим объектом значений (целое, вещественное, символьное и т.д.). Такой информацией ВМ определяется с использованием языковых спецификаций вычислительных задач и построением поддерживающей этот язык программной системы синтеза программ, такого как УТОПИСТ, ДЕКАРТ или МИКРОПРИЗ.