Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Цикломатическое число Маккейба





 

Впервые графическое представление программ было предложено Маккейбом. Основной метрикой сложности он предлагает читать цикломатическую сложность графа программы, или, как ее еще называют цикломатическое число Маккейба, характеризующее трудоемкость тестирования программы.

Для вычисления цикломатического числа Маккейба Z(G) применяется формула

Z(G) = e-v+2p (1)

где e – число дуг ориентированного графа G; v – число вершин; 2p – число компонентов связности графа.

Число компонентов связности графа можно рассматривать как количество дуг, которые необходимо добавить для преобразования графа в сильносвязнный. Сильносвязным называется граф, любые две вершины которого взаимно достижимы. Для графов корректных программ, т.е. графов, не имеющих недостижимых от точки входа участков и «висячих» точек входа и выхода, сильносвязанный граф получается путём замыкания дугой вершины, обозначающей конец программы на вершину, обозначающую точку входа в эту программу. Как правило, р = 1

По сути Z(G) определяет число линейно независимых контуров в сильносвязном графе. Иначе говоря, цикломатическое число Маккейба показывает требуемое количество проходов для покрытия всех контуров сильносвязного графа или количество тестовых прогонов программы, необходимых для исчерпывающего тестирования по критерию " работает каждая ветвь"

Для программы, граф которой

изображен на рисунке 1,

цикломатическое число при e = 10, v = 8, p = 1,

определится как Z(G) = 10-8+2=4. Таким образом, имеется сильносвязный граф с четырьмя линейно независимыми контурами: a-b-c-g-e-h-a; a-b-c--e-h-a; a-b-d-f-e-h-a; a-b-d-e-h-a.

Цикломатическое число зависит только от количества предикатов, сложность которых при этом не учитывается.

Например, имеется два оператора условия:

IF X> 0

THEN X=A;

ELSE;

и

IF (X> 0 & FLAG = '1'B)!

(X=0 & FLAG = '0'B)

THEN X=A;

ELSE;

Оба оператора предполагают единственное ветвление и могут быть представлены одним и тем же графом (рис. 2). Очевидно, цикломатическое число будет для обоих операторов одинаковым, не отражающим сложности предикатов, что весьма существенно при оценке программ.

 

 

Исходя из этого Г.Майерс предложил расширение этой метрики. Суть подхода Г.Майерса состоит в представлении метрики сложности программ в виде интервала [Z(G), Z(G)+h]. Для простого предиката h ≠ 0, а для n-местных предикатов h=n-1. Таким образом, первому оператору соответствует интервал [2, 2], а второму [2, 6].

Такая метрика позволяет различать программы, представленные одинаковыми графами.

 







Дата добавления: 2014-11-10; просмотров: 5387. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Философские школы эпохи эллинизма (неоплатонизм, эпикуреизм, стоицизм, скептицизм). Эпоха эллинизма со времени походов Александра Македонского, в результате которых была образована гигантская империя от Индии на востоке до Греции и Македонии на западе...

Демографияда "Демографиялық жарылыс" дегеніміз не? Демография (грекше демос — халық) — халықтың құрылымын...

Субъективные признаки контрабанды огнестрельного оружия или его основных частей   Переходя к рассмотрению субъективной стороны контрабанды, остановимся на теоретическом понятии субъективной стороны состава преступления...

ТЕОРИЯ ЗАЩИТНЫХ МЕХАНИЗМОВ ЛИЧНОСТИ В современной психологической литературе встречаются различные термины, касающиеся феноменов защиты...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Studopedia.info - Студопедия - 2014-2025 год . (0.01 сек.) русская версия | украинская версия