Оценка характеристик структуры ПО

Лабораторные работы N1-5

«Определение свойств случайного графа структуры ПО. Оценка числа вариантов на отладку ПО по модели структуры ПО»

Версия 5

Методические указания

Цель работы:

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

Теоретические основы

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

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

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

Вспомним ряд определений и положений теории графов, необходимые нам для выполнения данной работы.

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

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

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

Оценка характеристик структуры ПО

Многие графы приложений – деревья. В каждую вершину дерева входит только одно ребро(за исключением корневого – в него не входит ни одно ребро).

Можно легко убедится, что каково бы ни было дерево в нем число ребер на единицу меньше числа вершин. Эта особенность - однозначная связь между числом узлов и числом ребер отличает деревья от других графов

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

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

Мы будем рассматривать графы ПО – деревья.

Это конечно идеализация – часто в реальных структурах ПО в узлы могут входить несколько ребер, но и эта идеализация позволяет получить оценки многих полезных характеристик ПО, для которых точность данной идеализации достаточна. Примеры графов – деревьев приведены на рис. Висячие вершины – вершины, из которых не выходят ребра у которых нет потомков, заштрихованы.

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

Рассмотрим дерево, в котором всего узлов Р, а висячих узлов В.

Имеет место теорема , где m _i – число ребер, входящих и выходящих из i-го узла. Эта теорема легко доказывается, если вспомнить, что для дерева число ребер на единицу меньше числа узлов и при приведенном суммировании каждое ребро учитывается дважды. Для “регулярного” дерева, для которого m=const (кроме корневого и висячих узлов) эта теорема имеет вид:

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

После преобразований ;

;

Для больших деревьев, В достаточно велико для того, чтобы было можно положить (В находится в знаменателе второго члена)

Формулы получены для “регулярного дерева”, где для каждого узла (кроме корневого и висячих) m = const.

В реальном ПО это не так m_i ¹ const и скорее всего величина случайная, но возможны средние оценки, которые нужно сделать для определения объема и трудозатрат при отладке даже при предположении, что m_i – случайная величина. Случайный граф, в котором число ребер, исходящих из каждого узла случайно, более адекватная модель ПО.

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

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

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

При работе программы вследствие неправильно заданных исходных данных могут получаться неправильный результат. Необходимо предусмотреть при конструировании защитные мероприятия.