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

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

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





 

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

Для вычисления цикломатического числа Маккейба 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. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


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


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


Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

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

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

Случайной величины Плотностью распределения вероятностей непрерывной случайной величины Х называют функцию f(x) – первую производную от функции распределения F(x): Понятие плотность распределения вероятностей случайной величины Х для дискретной величины неприменима...

Тема: Составление цепи питания Цель: расширить знания о биотических факторах среды. Оборудование:гербарные растения...

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

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

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