Современные технологии разработки и тестирования программного обеспечения (ПО). Часть 1. Коварцев А.Н. - 34 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

Из таблицы 3.3 видно, что, начиная с
ν
=6, число потенциальных маршрутов
полносвязного графа исчисляется десятками, а далее - сотнями тысяч. В этих условиях
сравнительно простая процедура проверки принадлежности маршрута
ориентированному графу становится невыполнимой, не говоря уже о классификации
типов данных агрегата, когда число данных в каждом из модулей агрегата может
исчисляться сотнями или тысячами.
Для сокращения числа операций над
данными в процессе их классификации
предлагается использовать метод, основанный на аксиомах трехзначной логики.
Таблица 3.3
порядок
графа
max число
дуг
цикломат.
Число
прогнозируемое
число циклов
2 1 0 0
3 3 1 1
4 6 3 7
5 10 6 63
6 15 10 1023
7 21 15 32767
8 28 21 2097151
9 36 28 2.68E+08
10 45 36 6.87E+10
Для реализации алгоритма сжатия количества операций предлагается использовать
аксиомы 4, 5 и 6, которые сформулируем как правила вывода в форме метаформул:
П1:
α
β
α
αβ
ΔΔ
Δ
,
П2:
()()
α
β
γ
α
β
αβγ
ΔΔ Δ
ΔΔ
∇
правило поглощения,
П3:
()()
()()
α
β
γ
α
γ
αβ αγ
ΔΔ Δ
ΔΔ
∇
∇
поглощение общего окончания.
Последовательность вершин, лежащих на маршруте и связанных операцией
следования, назовем условно "дизъюнктами”. Для простоты записи и восприятия вместо
оператора следования Δ в записи формулы будем употреблять “запятую”.
Алгоритм упрощения формулы классификации данных состоит из следующих
шагов:
1. Все дизъюнкты упорядочиваются, в первую очередь, по длине и
лексикографически, в случае одинаковой длины. Более длинные дизъюнкты ставятся на
первое место.
2. К
каждому дизъюнкту применяется правило П1 до тех пор, пока это возможно.
3. К каждому дизъюнкту, начиная с первого, применяется правило П3. Причем,
контактный “партнер” ищется на множестве дизъюнктов меньшей длины. Если правило
П3 реализуется, то множество дизъюнктов переупорядочивается.
4. После выполнения пункта 3 алгоритма для каждого дизъюнкта меньшей длины
ищется дизъюнкт, его поглощающий
, т.е. применяется правило П2. Поглощаемый
дизъюнкт вычеркивается из списка дизъюнктов.
Работу предложенного алгоритма рассмотрим на примере упрощения формулы
классификации данных агрегата
G1:

Страницы