ВУЗ:
Составители:
Рубрика:
этого типа наиболее известны канонические системы Поста, нормальные алгорифмы
Маркова и т.д.
Для технологии графосимволического программирования наиболее подходит
первый тип формализации понятия алгоритма, когда произвольная программа
интерпретируется некоторой вычислимой функцией
A
: in
D
ou
t
D
() ()→
,
где
in
D
() - множество входных данных программного модуля
A
, ou
t
D
( ) - -
множество выходных (вычисляемых) данных программного модуля
A
.
Определим граф состояний
G как ориентированный помеченный граф, вершины
которого - суть состояния, а дугами отмечаются переходы системы из состояния в
состояние. Каждая вершина графа помечается соответствующей локальной вычислимой
функцией
f
k
. Одна из вершин графа, соответствующая начальному состоянию,
объявляется начальной вершиной и, таким образом, граф оказывается инициальным.
Дуги графа проще всего интерпретировать как
события. С позиций данной работы
событие - это изменение состояния объекта O , которое влияет на развитие
вычислительного процесса.
На каждом конкретном шаге работы алгоритма в случае возникновения коллизии,
когда из одной вершины исходят несколько дуг, соответствующее
событие определяет
дальнейшей ход развития вычислительного процесса алгоритма. Активизация того или
иного события так или иначе зависит от состояния объекта, которое в свою очередь
определяется достигнутой конкретизацией структур данных D объекта
O.
Для реализации
событийного управления на графе состояний G введем множество
предикативных функций P
{}
= PP P
l12
, ,..., . Под предикатом будем понимать
логическую функцию P
i
(D), которая в зависимости от значений данных D принимает
значение равное 0 или 1. Дугам графа
G поставим в соответствие предикативные
функции. Событие, реализующее переход SS
ij
→ на графе состояний G, инициируется,
если модель объекта O на текущем шаге работы алгоритма находится в состоянии S
i
и
соответствующий предикат PD
ij
() (помечающий данный переход) истинен.
В общем случае предложенная концепция (без принятия дополнительных
соглашений) допускает одновременное наступление нескольких событий, в том случае
когда несколько предикатов, помечающих дуги (исходящих из одной вершины), приняли
значение истинности. Возникает вопрос: на какое из наступивших событий объект
программирования должен отреагировать в первую очередь?
Традиционное решение этой
проблемы связано с использованием механизма
приоритетов. В связи с чем все дуги, исходящие из одной вершины, помечаются
различными натуральными числами, определяющие их приоритеты. Отметим, что
принятое уточнение обусловлено ресурсными ограничениями, свойственными
однопроцессорной ЭВМ.
Определим универсальную алгоритмическую модель технологии
графосимволического программирования четверкой <D,
ℑ
, P, G>, где D - множество
данных (ансамбль структур данных) некоторой предметной области (для конкретного
объекта программирования O структуры его данных
D
∈
D);
ℑ
- множество
вычислимых функций некоторой предметной области; P - множество предикатов,
действующих над структурами данных предметной области D;
G - граф состояний
объекта O.
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
