Конечный ориентированный граф

Cтраница 2

Удобным средством задания автомата является его задание посредством диаграммы, представляющей собой конечный ориентированный граф, вершинам и ребрам которого приписаны некоторые символы. Диаграмма автомата 11 строится следующим образом. [16]

Граф организационной структуры сводного статистического. [17]

Перечень различных наименований объектов образует некоторое информационное множество, которое удобно изображать в виде конечного ориентированного графа G ( рис. 2.1) без контуров. Вершинам этого графа соответствуют объекты, а дугам - отношения между ними. [18]

Схема программы с памятью, называемая также а л г о л о п о д о б н о и, или о п е-р а т о р н о и, схемой, задается в виде конечного ориентированного графа переходов, имеющего обычно одну входную и одну выходную вершины, вершины с одной ( преобразователи) и двумя ( распознаватели) исходящими дугами. С помощью символов сигнатуры и счетного множества символов переменных и констант обычным образом строится множество функциональных и предикатных термов. Каждому распознавателю сопоставляется нек-рый предикатный терм, а преобразователю - оператор присваивания, имеющий вид г /: т, где у - символ переменной, а т - функциональный терм. Конечная совокупность всех переменных в схеме образует ее память. Интерпретация в дополнение к конкретизации базовых операций предписывает каждой переменной область ее изменения, а каждой константе - ее значение. Для программ с памятью наиболее обычна т.н. операционная семантика, состоящая из алгоритма выполнения программы на заданном состоянии памяти. Программа выполняется при движении по графу переходов. При попадании на распознаватель вычисляется предикатный терм и происходит переход по дуге, соответствующей значению предиката. При попадании на преобразователь с оператором у: т: вычисляется значение т и присваивается переменной у. [19]

Программа с процедурами строится над базисом S. Она представляет собой конечный ориентированный граф с размеченными вершинами и дугами. Граф распадается на подграфы с непересекающимися множествами вершин. Один из подграфов называется главным; в нем выделены две вершины: вход - вершина без заходящих в нее дуг и с одной исходящей, и выход - вершина без исходящих из нее дуг. В любом неглавном подграфе тоже выделены две вершины - инициальная и финальная. Всякая вершина, кроме входа, выхода и финальных, принадлежит одному из четырех типов - преобразователь, распознаватель, вызов, возврат. Из распознавателя исходят две дуги, помеченные числами 0 и 1 соответственно, другие дуги пометок не имеют. Из преобразователя, вызова и возврата исходит по одной дуге. Вызовы и возвраты находятся во взаимно однозначном соответствии. Вызов и соответствующий ему возврат составляют пару, принадлежащую одному и тому же подграфу. Такая пара связана с некоторым неглавным подграфом следующим образом. Дуга из вызова ведет в инициальную вершину этого подграфа, а из его финальной вершины исходит дуга, ведущая в соответствующий вызову возврат, и это - единственная заходящая в него дуга. Пара вершин вызов-возврат и связанный с ним подграф называются инцидентными друг другу. Всякой паре вершин вызов-возврат присвоен номер, отличный от номеров других пар. [20]

Алгебраические схемы определяются над символьным базисом Bs, представляющим собой объединение четырех непересекающихся конечных алфавитов: Y P C Rt. Элементы Р называются логическими переменными; элементы остальных алфавитов - символами. Алгебраические схемы задаются конечным ориентированным графом такой же структуры, как и для стандартных схем. Разметка вершин такого графа осуществляется следующим образом. [21]

Страницы: 1 2