Оценка сложности программного комплекса на основе интегральной модели
Севастопольский национальный технический университет
Информационные расчеты, выполняемые
На этапе курсового и дипломного
Проектирования
Методические указания
для студентов специальности 7.080401 —
"Информационные управляющие системы и технологии"
всех форм обучения при выполнении лабораторных работ,
курсового и дипломного проектирования,
связанных с разработкой программного продукта
Севастополь
2006
УДК
Информационные расчеты, выполняемые на этапе курсового и дипломного проектирования для студентов специальности 7.080401 — "Информационные управляющие системы и технологии" всех форм обучения при выполнении лабораторных работ, курсового и дипломного проектирования, связанных с разработкой программного продукта /Сост. Ю.В. Доронина, В.Ю. Карлусов, Л.П. Старобинская - Севастополь: Изд-во СевНТУ, 2005.-16с.
Цель методических указаний: выработка у учащихся практических навыков по расчетам и анализу ИС.
Методические указания рассмотрены и утверждены на заседании кафедры Информационных Систем.
Протокол № от 2005 г.
Рецензент: доц. департамента кибернетики и вычислительной техники, к.т.н. Мащенко Е. Н.
Допущено учебно-методическим центром в качестве методических указаний.
| СОДЕРЖАНИЕ | |
| Введение……………………………………………………………. | ……………………….4 |
| 1.Оценка сложности алгоритмов и программ на основании степенной модели……………………………….…………………. | ………………………5 |
| 2. Оценка сложности программы на основе меры Холстеда..…. | ………………………6 |
| 3.Оценка сложности программного комплекса на основании интегральной модели……………………………………………… | ………………………7 |
| 4. Оценка надежности программных модулей и систем на основании статистических испытаний …………………………. | ……………………....12 |
| 5. Оценка показателей информационного фонда……………….. | ……………………14 |
| Библиографический список………………………………………. | ……………………...16 |
Введение
|
|
|
Общедоступность информационных технологий на интуитивном уровне породило в среде профессионалом и лиц, причисляющих себя к таковым, закономерное пренебрежение и игнорирование отдельных вопросов инженерной практики создания программных продуктов.
В первую очередь, это коснулось эскизных расчетов, выполняемых на этапе проектирования, прогнозов надежности программных модулей в ходе отладки и опытной эксплуатации, разработки баз данных, где все, de facto, сведено к нормализации отношений, реализации типовых пользовательских запросов и разработки типовых экранных форм меню.
|
|
|
Настоящее методическое указание призвано обратить внимание студентов и отдельных руководителей на указанные аспекты курсового проектирования, а также послужить глоссарием (справочником) для выполнения необходимых расчетов.
Предполагается, что указанные расчеты будут оформлены отдельной главой в пояснительной записке.
1. ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ И ПРОГРАММ НА ОСНОВАНИИ СТЕПЕННОЙ МОДЕЛИ
Формально сложности алгоритма определяется как порядок функции, выражающей время его работы [2]. Фактически это время определяется как объемом обрабатываемых данных, так и предписываемой алгоритмом последовательности действий. Если массив обрабатываемых данных неизменен по объему, то продолжительность его обработки постоянна. Последнее соображение позволяет сравнивать между собой различные алгоритмы.
Проиллюстрируем это примерами.
1. Пусть алгоритм реализован в виде программы, которая принимает некоторую последовательность данных из последовательного порта и переписывает ее на дисковый накопитель. В этом случае время работы алгоритма можно оценить формулой:
|
|
|
, (1.1)
где N – объем обрабатываемых данных,tсч – время считывания элемента данных, tзап – время его записи, t вспом – время затрачиваемое на выполнение вспомогательных функций, как-то: настройка и инициализация порта, открытие файла et.c.
Поскольку время обработки линейно возрастает с ростом объема обрабатываемых данных, то сложность такого алгоритма называют линейной.
2. Сортировка по методу пузырька [3] N элементов последовательно определяет минимум из всех элементов и ставит его на первое место, затем из оставшихся элементов определяется минимальный и ставится на второе место и т.д.
Число операций сравнения в ходе нахождения минимального элемента на каждом шаге может быть оценено суммой ряда
. (1.2)
Поправка на выполнения операций считывания и записи в данном случае не меняет порядок полинома
, (1.3)
где t ср – время затрачиваемое на сравнения двух элементов в оперативной памяти, включая адресацию.
Так как в рассмотренном случае временные издержки оцениваются полиномом второго порядка, то сложность алгоритма квадратична.
|
|
|
Можно оценить сложность алгоритма по уже написанной программе [1]
for k:= 1 to n-1 Begin {1}
min:=A[k];
loc:=k;
for i:=k+1 to n do
if min >A[i] then Begin{2}
min:=A[i];
loc:=i;
End{2}
A[loc]:=A[k];
A[k]:=min;
End{1}
Внешний цикл выполнятся n-1, внутренний цикл срабатывает (в среднем) 
раз.
Отсюда следует, что общее число обращений к телу внутреннего цикла составит
раз, что подтверждает данные примера 2.
3. Классический пример умножения двух матриц одинаковой размерности
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
c[i,j]=0;
for (k=0; k<n; k++)
c[i,j]+=A[i,k]*B[k,j] }
Из анализа программы видно, что внутренний цикл выполняется N3 раз. По этому сложность алгоритма кубической. Отметим, что изменения в размерностях матриц приведут к изменению коэффициента пропорциональности, но не к изменению полиномиальной зависимости.
В заключение раздела заметим, что предпочтительнее является логарифмическая зависимость, чем линейная, а линейная зависимость предпочтительнее полиномиальной. Для всех задач, кроме очень коротких крайне нежелательной является экспоненциальная зависимость aN или NN.
2. Оценка сложности программы на основе меры Холстеда [2,5]
Для расчета значения используются следующие параметры:
1 – число различных операторов (знаков операций);
2 – число различных операндов (идентификаторов, констант et c.);
= 1+ 2 - словарь модуля;
N1 – число появлений операторов;
N2 – число появлений операндов;
N= N1+N2 длина модуля.
Объем модуля определяется выражением
V=Nlog2 
. (2.1)
Уровень записи модуля определяется (если возможно)
, (2.2)
где V* - минимально возможный объем. Приближенно уровень записи модуля определяется по формуле
. (2.3)
Сложность программы по Холстеду характеризуется величиной
, (2.4)
которая эмпирически соответствует усилию, затраченное на кодирование и понимание модуля.
Пример 1[2]. Для вычисления значения синуса малых углов может с равным успехом использоваться два похода:
1. y=sin(x),
2. y=x-x**3/6+x**5/120-x**7/5040.
При вызове функции используется пять различных символов: операнды –{y,x}; операторы – {=, sin,( )}, словарь модуля равен 5.
При использовании суммы ряда тринадцать символов: операнды –{y,x,3,6,5,120,7,5040}; операторы - {=,-,**,/,+} при длине модуля в 21 знак.
Очевидно, что в первом случае объем модуля минимален
V*=5 log2 5 
11,6 , а во втором равен
V=21 log2 13 77,7.
Таблица 1 – характеристики модулей
| Величина | Использование функции | Использование ряда |
| 1
| 3 | 5 |
| 2
| 2 | 8 |
|
| 5 | 13 |
| N1 | 3 | 10 |
| N2 | 2 | 11 |
| N | 5 | 21 |
| V | 11,6 | 77,7 |
| L | 
| 
|
| E | 11,6(17,58) |  518(267,9)
|
В графах таблицы в скобках приведены результаты приближенной оценки L, полученные по формуле (3.3) и значения E, полученный с использованием этой приближенной оценки.
Значения мер Холстеда указывают на то, что вариант вычисления выражения с использованием встроенной функции удобен для понимания и проще для программирования и отладки.
Оценка сложности программного комплекса на основе интегральной модели
Модель сложности программного модуля строится на основании следующих факторов: логической сложности, сложности взаимосвязей, сложности вычислений, сложности ввода-вывода и удобочитаемости. Указанные факторы определяются численно следующим образом [4].
Показатель логической сложности модуля или общая логическая сложность модуля напрямую зависит от числа операторов ветвлений, циклов и условный переходов
, (3.1)
где 
- общее число логических операторов;
- число исполняемых операторов;
- число ветвлений (операторов вида Goto, If и переключателей типа Case), 0,001 – эмпирический коэффициент.
Показатель сложности циклов 
, в свою очередь есть
,где (3.2)
, (3.3)
а 
– число циклов в модуле, имеющих i-ый уровень вложения, Q – наивысший уровень вложенности, 4 и 3 нормирующие множители.
Аналогично определяется показатель сложности условных операторов
, (3.4)
где 
- число условных операторов i-го уровня вложенности, а Q и 
определяются аналогично (3.3).
Показатель сложности взаимосвязей
, (3.5)
где 
– число вызовов прикладных (пользовательских, написанных как лично, так и другими пользователями), 
– число связей (вызовов) системных программ, при этом коэффициент 0,5 определяет относительную значимость системных интерфейсов в сравнении с интерфейсами прикладных программ.
Показатель сложности вычислений
, (3.6)
где Nвыч – число операций вычислительного характера, 
- суммарная логическая сложность программного обеспечения, вычисляется суммированием значений показателя (3.1), выполняемая по всем модулям, вовлеченным в систему. Аналогично определяется 
- суммарное число вычислительных операций, определяемое по всем модулям.
Показатель сложности ввода-вывода
, (3.7)
где 
- число операций ввода-вывода, 
- суммирование, осуществляемое по всем модулям системы.
Удобочитаемость, или показатель простоты программы есть
, (3.8)
Где 
– число комментариев в программе, 
– общее число операторов, как исполняемых, так и неисполняемых, исключая комментарии.
Показатель общей сложности программного модуля
, (3.9)
Проводимые натурные исследования [4, с. 124] показывают значительную корреляцию (0,5231- 0,9058) числа ошибок в программе с величинами PСЛ , PЛС и PСЛ – PЛС для реальных программных продуктов.
Рассмотрим применение оценки к программе перевода чисел из римской системы счисления в арабскую [1, с. 60-61], текст программы которой приведен ниже.
Program roman (Input, Output)
Var n, state: integer; symbol: char; ok: boolean;
Begin {программа}
state:=1; ok:=true; n:=0;
while not eoln do
Begin
Read (symbol);
If ((symbol=’X’) or (symbol=’V’) or (symbol=’I’))
Then
Case state of
1: Case symbol of
’X’: Begin n:=10; state:=2 End;
’V’: Begin n:=5; state:=3 End;
’I’: Begin n:=1; state:=6 End;
End;
2: Case symbol of
’X’: Begin n:=10; state:=2 End;
’V’: Begin n:=n+5; state:=3 End;
’I’: Begin n:=n+1; state:=6 End;
End;
3: Case symbol of
’X’,’V’: ok:=false;
’I’: Begin n:=n+1; state:=4 End;
End;
4: Case symbol of
’X’,’V’: ok:=false;
’I’: Begin n:=n+1; state:=5 End;
End;
5: Case symbol of
’X’,’V’: ok:=false;
’I’: Begin n:=n+1; state:=7 End;
End;
6: Case symbol of
’X’: Begin n:=n+8; state:=7 End;
’V’: Begin n:=n+3; state:=7 End;
’I’: Begin n:=n+1; state:=5 End
End
7: ok:= false;
End {Case state}
else
Begin
If ok
Then Wrileln (n:2)
Else Writeln (‘Peccavisti’);
state:=1; ok:=true
End {Else}
End {While not}
End.
Из текста программы следует, что логических операторов Nло=8 (2 – If’а и 6 – Case’ов), а исполняемых операторов Nисп=47 (включая условия в операторе If, сами If’ы и Case’ы)
Показатель сложности циклов определится с учетом того, что m1=1 – 1 глобальный цикл, Q=1 – он же и на первом уровне вложенности, отчего
Для сравнения, у программы умножения матриц из предыдущего раздела:
m1=1; m2=1; m3=1; Q=3.
У программы сортировки:
m1=1; m2=1; Q=2.
То есть, на данный показатель влияет наличие сложной структуры во вложениях.
Показатель сложности условных операторов определяется тем, что один из них вложен в ветвь Else глобального. Имеем:
m1=1; m2=1; Q=2.
Подсчитаем число ветвлений: по 2 ветви – на каждый If, 7 – case state of, 15 – case symbol of. Итого Nветвл=26.
Таким образом, общая логическая сложность модуля есть
Показатель сложности взаимосвязей определим приняв во внимание, что прикладных модулей не вызывается, а команды Read/Write выполняются трехкратно
Показатель сложности вычислений, в силу того, что расчеты выполняются в пределах одной программы, а поэтому 
, будет обусловлен числом локальных операций вычислительного характера:
Nвыч = 13 (5 операций в логическом выражении глобального If’а, 8 – операций суммирования в Case’ах), поэтому
Показатель сложности ввода/вывода в силу вышеуказанных причин, тоже относится к программе, NI/O = 3
Видно, что исследуемая программа комментариями не изобилует. Комментариев в программе аж Ncom = 3. Общее число операторов, в которое вошли операторы описания данных, заготовки циклов и процедур, операторные скобки и т. д. составило Nопер = 89, откуда
На основании этих данных определим показатель общей сложности программного модуля как
Наиболее значительный вклад в этот показатель определяется общей логической сложностью модуля. Сам автор [1] указывает на «скрытый дефект» алгоритма, заключающийся в том, что вначале записи может идти сколь угодно большое число римских десяток «X», что несколько подтверждает расчеты.
Дата добавления: 2021-07-19; просмотров: 50; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!