62. Приближенный метод оценки числа вариантов для отладки ПО для «широкого графа» программы. Графы деревья, как модели структуры ПО

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

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

Связный граф без циклов называется деревом. Узлы дерева , в которые входит ребро, но ребра не выходят называются концевыми или висячими. Для дерева в каждый узел (кроме корневого) входит только одно ребро.

Для дерева число ребер на единицу меньше числа вершин .

Граф-дерево хорошо моделирует структуру программы, но дерево это идеализированная модель. Реальные структуры ПО имеют циклы. В рассмотренном ранее примере «узкий» граф ПО не является деревом. Однако, представление структуры ПО в виде дерева допустимо и позволяет получить хотя и приближенные, но полезные результаты.

«Широкий» граф ПО - структурная модель программного обеспечения (ПО) либо отдельно взятой программы представляется нами в виде дерева, Часть программных модулей – узлов графа ПО не имеет связей с другими модулями, так как они связаны с аппаратурой, либо в них заканчивается вычислительный процесс для данного варианта работы ПО. Такие узлы являются концевыми или висячими.

Число вариантов исполнений программы (программного комплекса) для ПО, имеющего структуру деревьев определяется числом маршрутов т.е. числом висячих узлов. Последнее справедливо только для деревьев. Для графов ,имеющих циклы, такая однозначная связь между числом маршрутов и числом висячих узлов отсутствует.

Рассмотрим дерево, в котором всего узлов P, а висячих узлов B. Если m i– число ребёр входящих и исходящих из каждого i го узла, то

имеет место теорема для деревьев общего вида:

P

mi 2 P 1 (1)

i1

Для дерева данное выражение легко доказывается, если учесть, что при суммировании по всем узлам числа входящих и исходящих в/из узел ребер, каждое ребро будет учитываться дважды.

[Введите текст]

63. Регулярное дерево и устойчивость его структурного параметра

Регулярным деревом будем называть дерево, где m для всех узлов, кроме корневого и висячих, постоянно. Для регулярного дерева сумма в выражении (1) легко подсчитывается и имеет вид:

m-1 +B*1+(P-B-1)*m=2*(P-1) (2)

Проделав необходимые преобразования, получим:

Найдем отношение P к B:

m 1 m 2

Вданной модели ПО с регулярной структурой считается что m постоянно по всему дереву (кроме висячих

и корневого узлов), но в реальных структурах ПО это не так и , обобщая, можно полагать ,что m изменяется от узла к узлу ограниченным случайным образом.

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

Благодаря экспериментально доказанной асимптотической устойчивости параметра возможно его использование для оценки числа B висячих узлов структуры ПО т.е. вариантов на отладку ПО. Эти оценки справедливы для более реальных моделей ПО в виде графов-деревьев со случайным числом ребёр ≤m, выходящих из каждого узла.

В = Р/α

94

Выделив маршруты на управляющем графе нужно дополнить их другими «ненакрытыми» вариантами работы ПО.

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

64. Контроль отлаженности ПО в процессе отладки.

65.Гипотеза Джелинского – Моранды и математическая модель надежности ПО

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

На пути создания такой универсальной модели казалось бы имеются два препятствия:

Во первых ПО чрезвычайно разнообразно по назначению и сложности,

Во вторых ПО разрабатывается различными людьми, частота ошибок у них отличается во много раз.

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

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

Метод наименьших квадратов (МНК), которым мы будем пользоваться, не только фильтрует случайные ошибки экспериментальных данных, но и позволяет получать решение переопределенной в алгебраическом смысле системы уравнений.

Математическая модель проявления ошибок в ПО Джелинского – Моранды имеет понятный физический смысл: чем больше ошибок в ПО, тем чаще они проявляются при работе.

Математическая формулировка: интенсивность проявления ошибок в ПО пропорциональна числу

оставшихся ошибок.

dn/dt =K×(N0 – n) или обозначая среднюю интенсивность проявления ошибок = К (No-n).

Здесь N0 – начальное число ошибок , n –число обнаруженных ошибок, К – коэффициент пропорциональности [Введите текст]

Рассмотренная модель изменения надежности ПО Джелинского - Моранды позволяет, основываясь на наблюдениях за процессом проявления ошибок в ПО, определить характеристику надежности ПО – интенсивность проявления ошибок .

Решение упомянутого выше дифференциального уравнения первого порядка

n = N0 ( 1 – е-кt ) и К N0 е-кt К>0

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

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

66. Приращение количества обнаруженных ошибок на интервале t

Здесь ni - приращение количества обнаруженных ошибок на интервале t.

ni N0 (1 e Кti ) N0 (1 e Кti 1 )

N0e Кti N0e К (ti t ) N0e Кti ( 1 e К t )

Пусть шаг t можно выбрать так, чтобы произведение К t 1. Тогда, разлагая exp функцию в ряд и пренебрегая членами выше 1-ой степени К t, как малыми, имеем: еxp(x)=1+х/1!+х^2/2!+…..

интервала t - будет два уравнения с двумя неизвестными.

Однако, возникает вопрос какую пару интервалов из r имеющихся интервалов наблюдений выбрать для определения N0 и К, так как каждой паре интервалов соответствует в общем случае свое решение относительно N0 и К.

Полученное по каждой паре случайно «пляшущих» данных решение не соответствует всей совокупности