Обозначим все множество переменных алгоритма как
V
,
и мно-
жество функций, изменяющих значения переменных как
F
:2
D
→
D
,
где
D
—
домены переменных
V
.
На определенном графе удобно ввести следующие функции раз-
метки:
func
:
N
×
V
→ {
F
∪;}
:
каждой паре вершин управляющего графа
и изменяемых в них переменных соотвествует набор функций, изме-
няющих значение переменных. Если паре
(
n, v
)
соответствует пустое
множество, то значение переменной
v
в вершине
n
не меняется. Без
ограничения общности можно полагать, что отображение биективно,
положив, что значение любой переменной может изменяться только
один раз;
use
:
N
→
2
V
:
каждой вершине управляющего графа соотвествует
набор переменных, используемых в операторе;
def func
:
N
→
2
V
:
каждой вершине управляющего графа со-
ответствует набор переменных, определенном в данном операторе. Без
ограничения общности можно положить, что
func
:
def
→ {
F
∪ ;}
,
т.е. определение переменной совпадает с ее первым и единственным
изменением.
При выполнении оператора алгоритма изменяется состояние по-
следнего. Фактически изменение наблюдаемого состояния при выпол-
нении оператора описывает то, как алгоритм порождает наблюдаемое
поведение в терминах описанной выше модели.
Уровнем абстракции наблюдаемого поведения алгоритма [7] будет
называться отношение:
σ
:
N
→
2
V
∪ {
φ
}
.
Если
σ
(
n
)
=
φ
,
то это означает, что оператор
n
является ненаблю-
даемым. На множестве уровней абстракции можно ввести отношение
частичного порядка и говорить, что
σ
1
≤
σ
2
,
если для всех операторов
алгоритма
n
верно, что
σ
2
(
n
)
=
φ
)
σ
1
(
n
)
=
φ
∨
σ
1
(
n
)
σ
2
(
n
)
.
Для описания измения состояния алгоритма используется струк-
тура
s
= (
n, val
)
,
где
n
2
N
,
val
:
V
→
D
—
значение переменной
v
,
т.е. состояние
описывается текущим выполняемым оператором и значениями пере-
менных.
Деревом поведения алгоритма называется ациклический ориенти-
рованный граф
behaviour
= (
S, R, s
0
)
,
где
S
—
множество состояний алгоритма;
R
—
отношение достижимо-
сти на множестве
S
;
s
0
—
выделенная корневая вершина (начальное
состояние алгоритма).
68
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
