Основы современных компьютерных технологий
Вычислительные модели и задачи, синтез программ - часть 4
Замена уравнений в ВМ их функциями разрешения позволяет избавиться от слабосвязанных переменных и тем самым получить описание вычислительной модели в виде двудольного ориентированного графа (орграфа). На рис. 25.3 приведено графическое представление ВМ КВАДРАТ, в которой такая замена выполнена, т.е. вместо отношений типа уравнение используются представляющие их функции разрешения в виде однооператорных отношении.
Рис. 25.3. ВМ КВАДРАТ с однооператорными отношениями
Однако ВМ с использованием однооператорных отношений еще не является алгоритмическим описанием - в модели не зафиксирован порядок выполнения
332
операторов. Поэтому такое описание по сути задает потенциальное множество алгоритмов, которые могут быть сконструированы с использованием отношений вычислительной модели. Конкретный алгоритм может быть получен, если к ВМ присоединить формулировку задачи в виде:
ЗНАЯ ВЫЧИСЛИТЕЛЬНУЮ МОДЕЛЬ >
ВЫЧИСЛИТЬ < ВЫХОДЫ ЗАДАЧИ > ПО < ВХОДАМ ЗАДАЧИ >.
Вычислительная модель и присоединенная к ней формулировка задачи образуют модель задачи. Формулировка задачи разбивает множество входящих в вычислительную модель переменных на два подмножества: входные переменные, значения которых известны до решения задачи, и выходные переменные, значения которых необходимо вычислить.
Если входных переменных достаточно для нахождения выходных с использованием разрешающих функций, которые содержит вычислительная модель, то задача является разрешимой, и для ее решения может быть сконструирована программа.
Обычно поиск решения задачи (т.е. программы) сводится к отысканию пути в орграфе модели задачи, ведущего от исходных данных задачи к ее результатам. Нахождение такого пути в ИППП осуществляет планировщик. Планирование при этом называют планированием от данных, возможен и другой подход: планирование от цели, в этом варианте планировщик ищет путь от выходных переменных задачи к входным. Возможна и комбинация этих вариантов (например, в системе ПРИЗ используется метод прямой и обратной волны).
