Основы современных компьютерных технологий
Вычислительные модели и задачи, синтез программ
В общем случае ИППП включает в свой состав следующие компоненты: подсистему общения пользователя с пакетом, подсистему планирования решений задач (планировщик) и базу знаний о программных модулях, составляющих функциональное наполнение пакета.
Планировщик является ядром ИППП, основная цель его - получение плана решения задачи пользователя, формулировка которой поступает на вход подсистемы планирования. План решения задачи в ИППП трактуется как поиск программы, решающей эту задачу. При этом программа решения задачи может конструироваться либо явно на каком-либо из алгоритмических языков программирования, либо существует в виде шагов работы планировщика. В первом случае ИППП является транслятором с декларативного языка описания задач на алгоритмический язык программирования. Во втором варианте, когда программа решения задачи не конструируется явно, а существует в виде шагов работы планировщика, планировщик работает в режиме интерпретации и является по сути интерпретатором с языка описания задач.
Как в первом, так и во втором вариантах работа планировщика отличается от функционирования обычного транслятора с алгоритмического языка программирования. Если функцией обычного транслятора является преобразование входной программы с входного алгоритмического языка программирования в язык машинных команд ЭВМ, то основная задача планировщика - синтез алгоритма программы решения задачи по декларативному описанию формулировки задачи. Синтез осуществляется с использованием базы знаний (БЗ). Типовая структура системы синтеза программ на основе представления знаний приведена на рис. 25.1.
База знаний в ИППП описывается на языке спецификаций, задачи формулируются на языке формулировок задач. В общем случае это может быть один и тот же язык. Пользователь, применяющий ИППП для решения прикладных задач, выступает обычно в двух ролях:
329
Рис. 25.1. Структура системы синтеза программ
Знания в БЗ могут быть представлены с использованием различных моделей. В наиболее развитых ИППП в качестве модели предметной области используются так называемые вычислительные модели. На основе вычислительных моделей формулируются вычислительные задачи.
Вычислительная задача формулируется в рамках некоторой предметной области, рассматриваемой как совокупность объектов и отношений между ними. При этом рассматриваются только такие объекты, на основе которых можно осуществлять вычисления. Между объектами существуют отношения вычислимости, задаваемые в виде функциональных отображений. Объекты могут быть простыми или составными. В составном объекте между его компонентами имеют место структурные отношения.
Объекты и отношения между ними описываются на некотором языке. Объектам в этом языке соответствуют переменные, а отношениям - функции. Значениями переменных являются данные.
Вычислительная задача имеет следующую форму:
ЗНАЯ М ВЫЧИСЛИТЬ Y1,Y2...YN ПO X1,X2...XM.
Здесь М, Y1 ,Y2... YN, X1 ,Х2.. .ХМ - переменные, которые имеют смысл, определяемый их вхождением в задачу. Идентификаторы ЗНАЯ, ВЫЧИСЛИТЬ и ПО имеют фиксированный смысл и служат для разделения переменных. Переменные Х1,Х2...ХМ являются входными для задачи, значения их задаются в постановке задачи. Переменные Y1,Y2...YN - выходные, значения их требуется вычислить. М - переменная, значение которой выражает условия задачи. Данные, являющиеся значением М, выражают знания в виде вычислительных моделей, включающих в свой состав переменные и отношения между ними.
Вычислительную модель (ВМ) можно представлять графически, с помощью языка спецификации и с помощью формул некоторого логического языка.
330
Графическое представление вычислительной модели - это семантическая сеть специального вида, узлам которой соответствуют переменные и отношения. Переменные обозначаются точками, отношения кружочками, овалами или прямоугольниками, внутри которых помещается описание реализации отношения.
Связи между переменными и отношениями могут быть следующих типов:
На рис. 25.2 приведен пример вычислительной модели КВАДРАТ, где в качестве отношений используются отношения типа уравнение. Все переменные, входящие в уравнения, являются слабосвязанными, т.е. любая из переменных может быть либо входной, либо выходной для уравнения.
Рис. 25.2. ВМ КВАДРАТ с отношениями типа уравнение
На одной вычислительной модели может быть решено множество вычислительных задач. Так, на приведенной на рис. 25.2 ВМ можно решить следующие задачи:
вычислить ПЕРИМЕТР по СТОРОНА;
вычислить СТОРОНА по ПЕРИМЕТР;
вычислить ПЛОЩАДЬ по СТОРОНА;
вычислить СТОРОНА по ПЛОЩАДЬ;
вычислить ПЕРИМЕТР по ПЛОЩАДЬ;
вычислить ПЛОЩАДЬ по ПЕРИМЕТР.
Проводить такие вычисления возможно при условии, что для уравнения всегда можно построить его разрешение относительно любой из входящих в него переменных. Если, например, в уравнение входит n переменных, то будем иметь п функций разрешения. Записывается это обычно в виде:
xj=fij(x1, x2,...xj-1, xj+1... xn)
331
Здесь хj - переменная, входящая в уравнение, f11 - реализация функции, вычисляющей значение j-й переменной в уравнении с номером i (i=1 ,...,k; k - число уравнений в ВМ). Уравнения считаются независимыми друг оу друга и являются компактным описанием множества разрешающих функций.
Входной язык ИППП обычно допускает использование уравнений при описании вычислительных моделей. После преобразования такого описания во внутреннее представление базы знаний уравнения заменяются функциями разрешения и в базе знаний уравнения хранятся в форме однооператорных отношений, т.е. без использования слабосвязанных переменных. Для уравнений из примера на рис. 25.2 такими разрешениями являются следующие:
Периметр = f11(Сторона);
Сторона = f21(Периметр);
Площадь = f21 (Сторона);
Сторона = f22 (Площадь).
В однооператорном отношении имеется одна выходная переменная, остальные являются входными для отношения, и однооператорное отношение показывает, значения каких переменных должны быть известны, для того чтобы можно было вычислить значение выходной переменной.
Замена уравнений в ВМ их функциями разрешения позволяет избавиться от слабосвязанных переменных и тем самым получить описание вычислительной модели в виде двудольного ориентированного графа (орграфа). На рис. 25.3 приведено графическое представление ВМ КВАДРАТ, в которой такая замена выполнена, т.е. вместо отношений типа уравнение используются представляющие их функции разрешения в виде однооператорных отношении.
Рис. 25.3. ВМ КВАДРАТ с однооператорными отношениями
Однако ВМ с использованием однооператорных отношений еще не является алгоритмическим описанием - в модели не зафиксирован порядок выполнения
332
операторов. Поэтому такое описание по сути задает потенциальное множество алгоритмов, которые могут быть сконструированы с использованием отношений вычислительной модели. Конкретный алгоритм может быть получен, если к ВМ присоединить формулировку задачи в виде:
ЗНАЯ ВЫЧИСЛИТЕЛЬНУЮ МОДЕЛЬ >
ВЫЧИСЛИТЬ < ВЫХОДЫ ЗАДАЧИ > ПО < ВХОДАМ ЗАДАЧИ >.
Вычислительная модель и присоединенная к ней формулировка задачи образуют модель задачи. Формулировка задачи разбивает множество входящих в вычислительную модель переменных на два подмножества: входные переменные, значения которых известны до решения задачи, и выходные переменные, значения которых необходимо вычислить.
Если входных переменных достаточно для нахождения выходных с использованием разрешающих функций, которые содержит вычислительная модель, то задача является разрешимой, и для ее решения может быть сконструирована программа.
Обычно поиск решения задачи (т.е. программы) сводится к отысканию пути в орграфе модели задачи, ведущего от исходных данных задачи к ее результатам. Нахождение такого пути в ИППП осуществляет планировщик. Планирование при этом называют планированием от данных, возможен и другой подход: планирование от цели, в этом варианте планировщик ищет путь от выходных переменных задачи к входным. Возможна и комбинация этих вариантов (например, в системе ПРИЗ используется метод прямой и обратной волны).
Выписывание встречающихся на этом пути функций разрешения в форме, например, операторов присваивания, дает описание плана (алгоритма) решения задачи. Так, например, если на ВМ КВАДРАТ сформулировать задачу:
ЗНАЯ КВАДРАТ ВЫЧИСЛИТЬ ПЛОЩАДЬ ПО ПЕРИМЕТР,
будет получен следующий план вычислений в форме присваиваний:
Сторона: = f21(Периметр).
Площадь: = f12(Сторона);
В функциональной форме это записывается в следующем виде:
Площадь =f12(f21 (Периметр)).
Графическое представление вычислительной модели данной задачи приведено на рис. 25.4. И если теперь для каждой из входящих в план вычислений функций имеется реализация в виде, например, программного модуля, то выполнение (интерпретация) модулей приведет к получению результата задачи.
Графическое представление ВМ достаточно полно описывает существо вычислительных задач. Однако в этом представлении отсутствует информация о типах объектов модели задачи не с позиций проведения вычислений в принципе, а с использованием ЭВМ. Для реализации вычислений на ЭВМ с каждым объектом необходимо связать тип его данного с точки зрения множества принимаемых этим объектом значений (целое, вещественное, символьное и т.д.). Такой информацией ВМ доопределяется с использованием языка спецификации вычислительных задач и построением поддерживающей этот язык программной системы синтеза программ.
333
Рис. 25.4. ВМ задачи нахождения площади квадрата по периметру
В настоящее время разработан и используется на практике ряд языков спецификаций вычислительных задач, программы решения которых находятся с применением рассмотренных и более сложных вычислительных моделей (УТОПИСТ, ДЕКАРТ, Язык решения задач системы МИКРОПРИЗ и др.). Устройство языка спецификаций и его применение для описания и решения вычислительных моделей и задач рассмотрим на примере системы ТК Solve r.
334
329 :: 330 :: 331 :: 332 :: 333 :: 334 :: Содержание
