Граф машина

Трудно найти язык описания алгоритмов, одновременно пригодный для обучения, с одной стороны, и достаточно мощный для реализации реальных приложений (включая научные) — с другой. В качестве базового языка описания алгоритмов предлагается использовать язык визуального программирования GRAPH [2].

В системе GRAPH произвольная программа интерпретируется некоторой вычислимой функцией:

,

где - множество входных данных программного модуля f, - множество выходных (вычисляемых) данных программного модуля f.

Определим граф состояний G как ориентированный помеченный граф, вершины которого - суть состояния, а дугами отмечаются переходы системы из состояния в состояние.

Каждая вершина графа помечается соответствующей локальной вычислимой функцией . Одна из вершин графа, соответствующая начальному состоянию, объявляется начальной вершиной и, таким образом, граф оказывается инициальным. Дуги графа проще всего интерпретировать как события. С позиций данной работы событие - это изменение состояния объекта O, которое влияет на развитие вычислительного процесса.

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

Для реализации событийного управления на графе состояний G введем множество предикативных функций P. Под предикатом будем понимать логическую функцию P_i(D), которая в зависимости от значений данных D принимает значение равное 0 или 1. Дугам графа Gпоставим в соответствие предикативные функции. Событие, реализующее переход на графе состояний G,инициируется, если модель объекта Oна текущем шаге работы алгоритма находится в состоянии S_i и соответствующий предикат (помечающий данный переход) истинен.

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

Традиционное решение этой проблемы связано с использованием механизма приоритетов. В связи с чем все дуги, исходящие из одной вершины, помечаются различными натуральными числами, определяющими их приоритеты. Отметим, что принятое уточнение обусловлено ресурсными ограничениями, свойственными однопроцессорной ЭВМ.

Определение 6. Определим универсальную алгоритмическую модель языка GRAPH четверкой <D,, P, G>, где

· D - множество данных (ансамбль структур данных) некоторой предметной области O;

· - множествовычислимых функций некоторой предметной области;

· P - множество предикатов, действующих над структурами данных предметной области D;

· G - граф состояний объекта O.

Граф в данном случае заменяет текстовую (вербальную) форму описания алгоритма программы, при этом:

1). Реализуется главная цель - представление алгоритма в визуальной (графосимволической) форме.

2). Происходит декомпозиционное расслоение основных компонент описания алгоритма программного продукта. Так структура алгоритма представляется графом G,элементы управления собраны во множестве предикатов P и, как правило, значимы не только для объекта O, но и для всей предметной области. Спецификация структур данных, а также установка межмодульного информационного интерфейса по данным “пространственно” отделена от описания структуры алгоритма и элементов управления.