Оценка структурной сложности трех критериев и метрики Маккейба
Исходный управляющий граф, построенный по алгоритму программы:
Рис. 2 Управляющий граф разработанной программы
Найдем цикломатическое число:
Z = m – n +2 = 28 – 22 + 2 = 8,
Где m – количество дуг, а n – количество вершин.
Модифицированный граф
Как видно, некоторые из вершин можно убрать, так как они образуют линейную последовательность операторов:
Рис. 3 Модифицированный управляющий граф разработанной программы
Цикломатическое число осталось таким же:
Z = m – n +2 = 22 – 16 + 2 = 8,
Первый критерий
Определяем минимальный набор маршрутов, проходящих через каждый оператор ветвления и по каждой дуге:
Вычислим уровень сложности:
Второй критерий
Определяем число проверок каждого линейно независимого цикла и линейно независимого циклического участка программы:
Общее число проверок = Z = 8 Таким образом, общее число циклических и ациклических участков в графе равно 8.
Первый навык управленца четырехактная структура управляющего текста
Циклические участки:
Ациклические маршруты:
Метрика структурной сложности:
Третий критерий
Так как циклы, идущие от вершин 4 и 14 независимы друг от друга (2 подзадачи в программе), то в третьем критерии можно рассматривать комбинации всех маршрутов внутри этих независимых циклов:
Посчитаем третий критерий:
Таблица 16 Матрица смежности управляющего графа
Таблица 17 Матрица достижимости управляющего графа
Алгоритмическая сложность на основе метрики Маккейба
На основе цикломатического числа полученного графа (Z = m –n + 2 =8) можно утверждать, что в данном графе управления можно выделить 8 независимых контуров, ведущих из начальной вершины в конечную.
Согласно полученным результатам оценки структурной сложности программы по трем критериям выделения маршрутов, можно сделать вывод о том, что программа, описываемая полученным графом управления, имеет среднюю алгоритмическую сложность – в программе используется 8 операторов условий, для их проверки необходимо проверить от 8 до 111 тестовых вариантов исходных данных.
Оценка характеристик программы на основе модели функциональных указателей
Источник: infopedia.su
Структурное тестирование
базируется наанализелогики ПО (ПО рассматривается как «белый ящик») тестированием по «маршрутам» Структурный подход к тестированию имеет ряд недостатков • не обнаруживают пропущенных маршрутов; • не обнаруживают ошибок, зависящих от обрабатываемых данных, например, в операторе if (a — b) < eps — пропуск функции абсолютного значения abs проявится только, если а < b; • не дают гарантии, что программа правильна, например, если вместо сортировки по убыванию реализована сортировка по возрастанию.
Управляющий граф программы
УГП — отображает поток управления программы. Это граф G(V, A), где V(V1,… Vm) – множеств вершин (операторов), A(A1,… An) – множество дуг (управлений), соединяющих вершины.
06 — Введение в алгоритмы. Графы
Путь – последовательность вершин и дуг УГП, в которой любая дуга выходит из вершины Vi и приходит в вершину Vj Ветвь – путь (V1, V2, … Vk), где V1 — либо первый, либо условный оператор, Vk — либо условный оператор, либо оператор выхода из программы, а все остальные операторы – безусловные. Ветви — линейные участки программы, их конечноe число. Число путей в программе может быть не ограничено (пути, различающиеся хотя бы числом прохождений цикла – разные). Существуют реализуемые и нереализуемые пути в программе, в нереализуемые пути в обычных условиях попасть нельзя.
Преобразование схемы алгоритма в УГП
Управляющий граф /* Функциявычисляетнеотрицательную степень n числа x */ 1 double Power(doublex, int n) < 2 doublez=1; int i ; 3 for ( i = 1; 4 i <= n; 5 i++ ) 6 < z= z* x ; >/* Возвратв п.4 */ 7 return z; > примеры путей: (3,4,7), (3,4,5,6,4,5,6), (3,4), (3,4,5,6) примеры ветвей: (3,4) (4,5,6,4) (4,7)
Источник: studfile.net
Управляющий граф алгоритма
А. А. Тюгашев полагает, что «теоретической основой графического языка блок-схем служит управляющий граф программы» [83]. Это верно лишь отчасти:
- • язык блок-схем не удовлетворяет требованиям, предъявляемым к формальному языку, их нельзя подать на вход компилятора. Как отмечает А. Н. Степанов, для конечного исполнителя-компьютера блок-схемы не обеспечивают свойство понятности: «процессорами компьютеров не воспринимаются алгоритмы, заданные в виде блок-схемы» [15, с. 190];
- • принцип ограничения топологии блок-схем Дейкстры накладывает принципиальные ограничения на управляющий граф алгоритма (control flow graph) и является частью теоретического фундамента блок-схем. В стандартах ГОСТ 19.701—90 и ISO 5807:1985 эти ограничения никак не учтены, что делает указанные стандарты уязвимыми для критики, недостоверными и нелигитимными.
Теоретические основы языка ДРАКОН
В отличие от блок-схем, теоретической основой языка ДРАКОН служит визуальное логическое исчисление, благодаря чему графический синтаксис ДРАКОНа является не только формальным и безопасным, но и эргономичным, облегчающим выявление слабых мест [39, с. 393—448].
Кроме того, в языке ДРАКОН — на основе четырех принципов структуризации блок-схем Дейкстры — разработан двумерный структурный подход к алгоритмам и программам (шампур-метод) [39, с. 449—472]. Метод содержит большое число правил, которые хранит в своей памяти программа ДРАКОН-конструктор. Последняя, выполняя черчение дракон-схем, автоматически обеспечивает выполнение правил и не допускает ошибок.
Метод Эдварда Ашкрофта и Зохара Манны
Известно, что пересечения соединительных линий в блок- схемах затрудняют их понимание, поэтому ГОСТ 19.701—90 предписывает: «В схемах следует избегать пересечения линий», что свидетельствует о неумении теоретически решить проблему пересечений.
В отличие от блок-схем, в языке ДРАКОН эта проблема решена; разработан теоретический метод, исключающий пересечения и разрывы линий, а также внутренние соединители. Метод использует введение переменной состояния по Ашкрофту — Манне [84] и Йо- дану [10, с. 192—196]. Затем переменная состояния удаляется, превращаясь в идентификаторы икон Имя ветки и Адрес [39, с. 436— 448]. Метод реализован на практике во внутренних алгоритмах программы ДРАКОН-конструктор.
Рис. 193. Структурные блок-схемы Дейкстры (в центре) и эквивалентные им дракон-схемы (справа) выводы
- 1. Стандарт на блок-схемы алгоритмов ГОСТ 19.701—90 прямо противоречит принципам структуризации блок-схем, которые предложил Э. Дейкстра в классической работе «Заметки по структурному программированию».
- 2. Принцип ограничения топологии блок-схем Дейкстры накладывает жесткие ограничения на управляющий граф алгоритма (control flow graph) и является частью теоретического фундамента схем алгоритмов.
- 3. В стандарте ГОСТ 19.701—90 эти ограничения никак не учтены, что делает указанный стандарт уязвимым для критики и не- лигитимным.
- 4. В языке ДРАКОН — на основе четырех принципов структуризации блок-схем Дейкстры — разработан двумерный структурный подход к алгоритмам (шампур-метод).
- 5. В отличие от блок-схем в языке ДРАКОН решена проблема пересечений соединительных линий: разработан теоретический метод, исключающий пересечения и разрывы линий. Метод использует введение переменной состояния по Ашкрофту — Манне и Йода- ну с последующей модификацией.
- 6. Правила разработки блок-схем алгоритмов по ГОСТ 19.701— 90 не формализованы, не эргономичны и разрешают совершать небезопасные действия.
- 7. В отличие от блок-схем в дракон-схемах предусмотрены специальные средства предотвращения ошибок:
- • формализация построения графики с помощью исчисления икон;
- • формальные средства алгоритмической логики;
- • формализация отростков;
- • формализация валентных точек;
- • формализация макроикон;
- • формализация и минимизация стрелок;
- • использование ДРАКОН-конструктора.
Тема 37
Источник: studme.org
Основные понятия тестирования
Основная проблема тестирования — определение достаточности множества тестов для истинности вывода о правильности реализации программы, а также нахождения множества тестов, обладающего этим свойством.
Простой пример
Рассмотрим вопросы тестирования на примере простой программы (Пример 2.6) на языке С#. Текст этой программы и некоторых других несколько видоизменен с целью сделать иллюстрацию описываемых фактов более прозрачной.
/* Функция вычисляет неотрицательную степень n числа x */ 1 double Power(double x, int n)< 2 double z=1; int i; 3 for (i=1; 4 n>=i; 5 i++) 6 /* Возврат в п.4 */ 7 return z;>
2.6. Пример простой программы на языке С#
/* Функция вычисляет неотрицательную степень n числа x */ 1 double Power(double x, int n)< 2 double z=1; int i; 3 for (i=1; 4 n>=i; 5 i++) 6 /* Возврат в п.4 */ 7 return z;>
2.6.1. Пример простой программы на языке С
Рис. 2.2. Управляющий граф программы
Управляющий граф программы (УГП) на Рис. 2.2 отображает поток управления программы. Нумерация узлов графа совпадает с нумерацией строк программы. Узлы 1 и 2 не включаются в УГП , поскольку отображают строки описаний, т.е. не содержат управляющих операторов.
Управляющий граф программы
Управляющий граф программы (УГП) – граф G(V,A) , где V(V1,… Vm) – множество вершин (операторов), A(A1,… An) – множество дуг (управлений), соединяющих операторы-вершины.
Путь – последовательность вершин и дуг УГП, в которой любая дуга выходит из вершины Vi и приходит в вершину Vj, например: (3,4,7) , (3,4,5,6,4,5,6) , (3,4) , (3,4,5,6)
Ветвь – путь (V1, V2, … Vk) , где V1 — либо первый, либо условный оператор программы, Vk — либо условный оператор, либо оператор выхода из программы, а все остальные операторы – безусловные, например: (3,4) (4,5,6,4) (4,7) . Пути , различающиеся хотя бы числом прохождений цикла – разные пути , поэтому число путей в программе может быть не ограничено. Ветви — линейные участки программы, их конечноe число.
Существуют реализуемые и нереализуемые пути в программе, в нереализуемые пути в обычных условиях попасть нельзя.
float H(float x,float y)
2.7. Пример описания функции с реализуемыми и нереализуемыми путями
float H(float x,float y)
2.7.1. Пример описания функции с реализуемыми и нереализуемыми путями
Например, для функции Пример 2.7 путь (1,3,4) реализуем, путь (1,2,4) нереализуем в условиях нормальной работы. Но при сбоях даже нереализуемый путь может реализоваться.
Основные проблемы тестирования
Рассмотрим два примера тестирования :
- Пусть программа H(x:int, y:int) реализована в машине с 64 разрядными словами, тогда мощность множества тестов ||(X,Y)||=2**128 Это означает, что компьютеру, работающему на частоте 1Ггц, для прогона этого набора тестов (при условии, что один тест выполняется за 100 команд) потребуется ~ 3K лет.
// Прочитать значения датчика static public bool ReadSensor(bool Sensor) < //. чтение значения датчика Console.WriteLine(«. reading sensor value»); return Sensor; >// Открыть схват static public void OpenHand() < //. открываем схват Console.WriteLine(«. opening hand»); >// Закрыть схват static public void CloseHand() < //. закрываем схват Console.WriteLine(«. closing hand»); >[STAThread] static void Main(string[] args) < while (true) < Console.WriteLine(«Enter Sensor value (true/false)»); if (ReadSensor(Convert.ToBoolean(Console.ReadLine()))) < OpenHand(); CloseHand(); >> >
2.8. Фрагмент программы срабатывания схвата
#include /* Прочитать значения датчика */ int ReadSensor(int Sensor) < /* . чтение значения датчика */ printf(«. reading sensor valuen»); return Sensor; >/* Открыть схват */ void OpenHand() < /* . открываем схват */ printf(«. opening handn»); >/* Закрыть схват */ void CloseHand() < /* . закрываем схват */ printf(«. closing handn»); >void main(void) < int s; while (1) < printf(«Enter Sensor value (0/1)»); scanf(«%d», if (ReadSensor(s)) < OpenHand(); CloseHand(); >> >
2.8.1. Фрагмент программы срабатывания схвата
Рис. 2.3. Тестовая последовательность сигналов датчика схвата
- Тестирование программы на всех входных значениях невозможно.
- Невозможно тестирование и на всех путях .
- Следовательно, надо отбирать конечный набор тестов , позволяющий проверить программу на основе наших интуитивных представленийТребование к тестам — программа на любом из них должна останавливаться, т.е. не зацикливаться. Можно ли заранее гарантировать останов на любом тесте?
Задача о выборе конечного набора тестов (X,Y) для проверки программы в общем случае неразрешима.
Поэтому для решения практических задач остается искать частные случаи решения этой задачи.
Источник: intuit.ru
Анализ характеристик программных модулей с помощью управляющего графа
Для количественной оценки сложности программных модулей используется графовая модель, представляющая собой направленный граф с циклами, вершинами которого являются линейные участки программы, а дугами — управляющие связи между линейными участками. Анализируя такой граф, можно обнаружить неисполняемые участки программы, получить все циклы (явные, заданные операторами цикла, и неявные, построенные с помощью условных операторов), обнаружить входы «сбоку» в структурированные конструкции (например, вход в тело цикла, минуя заголовок), наличие нескольких входов и выходов из процедур, отступления от стандартов программирования и т.д., что существенно важно при анализе технологической безопасности программ и, в частности, при определении критичных путей их выполнения.
Количественная оценка сложности программы при помощи управляющего графа вычисляется [Лип0] как сумма V=e-n+2p, где e – число дуг, n — число вершин, p — число связных компонент графа. Оценкой сложности можно пользоваться и при проектировании программ: если сложность превосходит некоторое критическое значение, то программу целесообразно разбить на более мелкие модули для упрощения ее понимания и отладки. В качестве критической сложности обычно принимают значение 10 единиц.
Основные алгоритмы, используемые на данном этапе, связаны с преобразованием управляющего графа, его анализом и построением возможных путей реализации программы. При этом преобразование графа основывается на понятии структурного дерева программы, вершинам которого соответствуют структурированные конструкции программы (условные операторы, циклы и последовательные операторы), вершины управляющего графа и неструктурируемые конструкции.
Неструктурируемой конструкцией графа называется его компонент, не содержащий других конструкций с одним входом и одним выходом и не принадлежащий множеству структурированных конструкций.
Вычисление управляющего графа обычно осуществляется при трансляции программы, но, к сожалению, большинство компиляторов не выдает его программисту в качестве результата своей работы.
При использовании ассемблеров управляющий граф легко может быть восстановлен по машинному коду [Лип0],а для языков высокого уровня необходимо создавать нетривиальные программы, сканирующие исходный текст и выделяющие управляющие конструкции языка.
Однако при разработке методики определения критических путей управляющих программ с позиции обеспечения технологической безопасности можно сделать допущение, что управляющий граф программы известен.
Алгоритм построения структурного дерева программы (алгоритм А) сводится к реализации следующей конструкции. Построение структурного дерева программы осуществляется параллельно со сверткой управляющего графа, когда выделенная конструкция заменяется одной вершиной. Для краткости управляющий граф на очередном этапе свертки будем называть графом программы. Таким образом, граф программы будет последовательно преобразовываться в G0,G1. где G0 — исходный управляющий граф последовательности — граф, состоящий из одной вершины.
Алгоритм А
А1. В структурном дереве образуются вершины простейшего типа, которым соответствуют вершины исходного управляющего графа.
А2. В графе программы ищется структурированная конструкция. Если такой нет, то выполняется переход к шагу А4.
А3. В дереве образуется вершина структурированной конструкции. Эта конструкция сворачивается в вершину, тип которой указывается. Выполняется переход к шагу А2.
А4. Если в графе осталась только одна вершина, то работа алгоритма заканчивается.
А5. В графе выделяется неструктурируемая конструкция и в структурном дереве образуется вершина соответствующего типа. Конструкция в графе сворачивается, после чего выполняется переход к шагу А2.
Построение структурного дерева выполняется от элементов, представляющих вершины управляющего графа, к элементу, представляющему всю программу целиком. Используя понятие структурного дерева программы, можно рассчитать существенную сложность программы EV: S(V(i)-1), где NS — множество вершин неструктурируемого типа в структурном дереве; V(i) — топологическая сложность конструкции, соответствующей i-й вершине дерева.
Вычисление V(i) производится на шаге А5 алгоритма по формуле V(i)=e(i)-n(i)+2, где e(i) — количество дуг, а n(i) — количество вершин рассматриваемой конструкции.
Таким образом, построение структурного дерева программы при реализации алгоритма А позволяет получить численные оценки сложности, которые в дальнейшем используются при определении критических путей, требующих наиболее тщательного обследования с позиций технологической безопасности программ.
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы.
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние.
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою.
Почему 1285321 студент выбрали МегаОбучалку.
Система поиска информации
Источник: megaobuchalka.ru