Построение моделей алгоритмов в системе GRAPH

Построение моделей алгоритмов в системе GRAPH

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве конструктивного объекта данных в системе GRAPH используются любые возможные структуры данных, доступные базовому языку программирования C++, на котором компилируются программы с визуальных образов GRAPH.

В системе GRAPH вводится стандарт на организацию межмодульного информационного интерфейса. Стандарт обеспечивается выполнением пяти основных правил:

1). Вводится единое для всей предметной области хранилище данных, актуальных для предметной области программирования (ПОП). Полное описание данных размещено в словаре данных ПОП. Любые переменные, не описанные в словаре данных, считаются локальными данными тех объектов ГСП, где они используются.

2). В пределах ГСП описание типов данных размещается централизовано в архиве типов данных.

3). В базовых модулях в качестве механизма доступа к данным допускается только передача параметров по адресам данных.

4). Привязка данных объектов ПОП реализована в паспортах объектов ПОП.

5). В технологии ГСП не рекомендуется использовать иные способы организации межпрограммных связей по данным.

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

Здесь под предметной областью программирования понимается следующее.

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

Словарь данных представляет собой таблицу, в которой каждому данному присвоено уникальное имя, задан тип, начальное значение данного и краткий комментарий его назначения в ПОП.

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

Кроме словаря данных и каталога типов данных информационную среду определяют объекты ГСП. Под объектом понимается специальным образом построенный в рамках технологии ГСП программный модуль, выполняющий определенные действия над данными ПОП.

С информационной точки зрения каждый объект ГСП f_i представляет собой функциональное отображение области определения объекта на область значений :

.

В общем случае (в объекте могут быть модифицируемые данные) и , где D - полная область данных ПОП. Для двух произвольных объектов ПОП f_i и f_j в общем случае справедливо: .

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

Рис. 2

В качестве примера использования системы GRAPH для описания алгоритмов рассмотрим известный алгоритм сортировки «вставками».

Пусть нам задан массив натуральных чисел . Для простоты введем фиктивный наименьший элемент (для ЭВМ ).

Создадим словарь данных ПОП. В первую очередь в качестве конструктивного объекта для множества данных массив A (в языке C++ тип массива определяется описанием: typedef int MASSIV[200];). Переменные n, i, j, w описаны в таблице 1.

Таблица 1.

Алгоритм сортировки вставками представлен на рисунке 3.

Здесь

· образом обозначена вычислимая функция (объект) вывода на печать содержимого массива A (int k;printf("массив А: \n"); for (k=1;k<=n;k++) printf(" %d",A[k]); printf("\n"); getch(););

· образом обозначен объект «j++»;

· образом обозначен объект «i--»;

· образом обозначена пустая функция «// Конец».

Нулевому элементу массива (A[0]) присвоено значение -32000.

Работа алгоритма начинается с вызова корневой вершины (на рисунке 5 обведена «жирно»). В данном случае - печать исходного массива данных. Далее, последовательно, начиная с элемента A[j] (первоначально j=2) на участке массива A от j до 1 производится упорядочивание элементов в порядке возрастания их значений.

Для этого индексу «i» присваивается значение на 1 меньше j (вершина 1). В объекте 2 запоминается «старшее» (улучшаемое значение элемента) A[j]. При этом в цикле вершина 3 - вершина 4 производится перемещение элементов в направлении A[j], до тех пор, пока не выполнится логическая функция 2 (w<A[i]). В этом случае на «освободившееся» место вставляется элемент A[j] (объект 5). Очевидно, что на данный момент все элементы на участке от 1 до j оказываются упорядоченными.

В блоке 8 производится печать текущего состояния массива, в вершине 6 - увеличение индекса j на 1.

Алгоритм работает, пока не исчерпаются все числа массива A (предикат 3).

Список литературы

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений. 2008

2. Коварцев А.Н. Автоматизация разработки и тестирования программных средств. - Самара, СГАУ. 2009 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - м.: Энергоатомиздат, 2005 г.

4. Немировский А.С., Юдин Д.Б. Сложность и эффективность методов оптимизации. М.: Наука, 2000.