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


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


Замена уравнений в ВМ их функциями разрешения позволяет избавиться от слабосвязанных переменных и тем самым получить описание вычислительной модели в виде двудольного ориентированного графа (орграфа). На рис. 25.3 приведено графическое представление ВМ КВАДРАТ, в которой такая замена выполнена, т.е. вместо отношений типа уравнение используются представляющие их функции разрешения в виде однооператорных отношении.


Рис. 25.3. ВМ КВАДРАТ с однооператорными отношениями

Однако ВМ с использованием однооператорных отношений еще не является алгоритмическим описанием - в модели не зафиксирован порядок выполнения

332

операторов. Поэтому такое описание по сути задает потенциальное множество алгоритмов, которые могут быть сконструированы с использованием отношений вычислительной модели. Конкретный алгоритм может быть получен, если к ВМ присоединить формулировку задачи в виде:

ЗНАЯ ВЫЧИСЛИТЕЛЬНУЮ МОДЕЛЬ >
ВЫЧИСЛИТЬ < ВЫХОДЫ ЗАДАЧИ > ПО < ВХОДАМ ЗАДАЧИ >.

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

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

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


Начало  Назад  Вперед