logo
Конспект лекций Дискретная математика

1.3. Граф машина

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

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

,

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

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

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

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

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

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

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

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

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

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

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

Рис.3. Алгоритмическая модель языка GRAPH

Предложенная алгоритмическая модель <D, , P, G>, в конечном счете, описывает некоторую вычислимую функцию и в этом смысле может служить “исходным материалом” для построения алгоритмических моделей других программ. Последнее означает, что технология ГСП допускает построение иерархических алгоритмических моделей. Уровень вложенности граф-моделей в ГСП не ограничен.