— сохранить поведение алгоритма неизменным с точки зрения его функ-
ционирования. Таким образом, необходим аппарат, ограничивающий число
ненаблюдаемых операторов; в качестве такого аппарата предлагается исполь-
зовать механизм зависимостей [5].
Для алгоритмов можно использовать известные зависимости по данным
и управлению, определения которых даны в работе [5]. Отношение зави-
симости между операторами алгоритма может быть выявлено по описанию
алгоритма и используется для предсказания возможного хода его выполне-
ния. Существует два основных типа зависимостей в последовательной про-
грамме: зависимости по управлению, которые определяются управляющими
конструкциями программы, и зависимости по данным, которые определяют-
ся переменными, используемыми в алгоритме.
Под алгоритмом понимается кортеж
(
G, V ar
)
, где
G
= (
N, E, n
0
)
—
управляющий граф алгоритма;
N
— множество вершин, каждая из которых
соответствует оператору алгоритма;
E
— множество дуг, соответствующих
переходу управления в алгоритме;
n
0
2
N
— начальная вершина алгоритма;
V ar
— множество переменных алгоритма.
Оператор
s
2
N
зависит по управлению: от предиката
c
, который со-
держится в операторе условного ветвления; от выбора пути выполнения, на
который потенциально влияет предикат
c
; от того, будет ли выполнен опера-
тор
s
. Оператор
s
2
N
зависит по данным от оператора
s
0
2
N
, если данные,
определяемые в
s
0
, используются в
s
, потенциально могут достичь оператора
s
через последовательность присваиваний переменных.
Если событие, отмечающее факт выполнения оператора
s
, входит в на-
блюдаемое поведение алгоритма, то множество операторов
S
c
, от которых
зависит оператор
s
по управлению, также войдет в остаточный алгоритм.
Также туда войдут все операторы, от которых операторы из множества
S
c
зависят синтаксически.
Функциональная модель процесса масштабирования алгоритма показана
на рис. 1. На первом шаге строятся зависимости, ограничивающие редукцию
операторов в алгоритме, после чего определяются наблюдаемые операторы.
Построение остаточного алгоритма выполняется до тех пор, пока результат,
полученный на очередной итерации, не совпадет с предыдущим результатом.
Операторы, не вошедшие в остаточный алгоритм, не соответствуют выбран-
ному уровню абстракции, поэтому они либо удаляются, либо заменяются на
эквивалентные по потреблению вычислительных ресурсов операторы, если
в цели тестирования входит оценка времени выполнения алгоритма.
Формально уровень абстракции [6]
α
определяется как отображение мно-
жества операторов алгоритма
G.N
во множество всех подмножеств перемен-
ных алгоритма
2
V ar
, объединенных со специальным элементом
ϕ
:
α
:
G.N
→
2
V ar
∪ {
ϕ
}
.
Если
α
(
x
) =
ϕ
, то на данном уровне абстракции для оператора
x
никакие пе-
ременные не контролируются. Уровень абстракции описывает, какую часть
алгоритма требуется протестировать, однако в реальности должны быть про-
тестированы операторы, составляющие заданный уровень абстракции, а так-
же операторы, от выполнения которых зависят существенные операторы и
значения существенных переменных в точках наблюдения.
Основной проблемой составления тестов является экспоненциальный
взрыв, возникающий при ветвлениях алгоритма. Поэтому понятие уровня аб-
стракции необходимо дополнить свойством глубины анализа (которое легко
120 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 4
