ВУЗ:
Составители:
Рубрика:
К сожалению, количество потенциальных маршрутов графа комбинаторно растет с
ростом цикломатического числа
ν
, характеризующего сложность программного модуля.
Из таблицы 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:
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
