Основы современных компьютерных технологий

         

Вычислительные модели и задачи, синтез программ


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

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

Как в первом, так и во втором вариантах работа планировщика отличается от функционирования обычного транслятора с алгоритмического языка программирования. Если функцией обычного транслятора является преобразование входной программы с входного алгоритмического языка программирования в язык машинных команд ЭВМ, то основная задача планировщика - синтез алгоритма программы решения задачи по декларативному описанию формулировки задачи. Синтез осуществляется с использованием базы знаний (БЗ). Типовая структура системы синтеза программ на основе представления знаний приведена на рис. 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 :: Содержание


    Содержание раздела