- •Ответы на экзаменационные вопросы
- •1. Функциональность программного средства (functionality)
- •Оценивание качества разработки программ на основе метрик Холстеда. Измеримые свойства алгоритмов
- •Длина программы
- •Объем программы
- •Потенциальный объем V*
- •Значение уровня языка
- •{Ri (ej)} e -event.
- •Модель Джелинского-Моранды.
- •Модель Шика-Уолвертона.
- •Модель Нельсона. Применение последовательного анализа Вальда для снижения количества прогонов программы.
Длина программы
С использованием рассмотренных программных параметров можно получить уравнение для оценки количественного соотношения между длиной программы N и словарем Это уравнение на первый взгляд может показаться несколько неожиданным Однако тщательный анализ доказывает его правомерность кроме этого его правильность подтверждается экспериментально
Строка длины N образуемая символами входящими в словарь из символов должна подчиняться ряду ограничений Требование согласно которому каждый символ словаря должен появиться по меньшей мере хотя бы один раз гарантирует выполнение условия
N
что определяет нижнюю границу для N выраженную через
Найдем верхнюю границу для N Разобьем строку длины N на подстроки длины Разделенная таким образом программа для ЭВМ оказывается состоящей из N/ операторов длины каждый Теперь если мы потребуем чтобы строка не содержала двух одинаковых подстрок длины то появится искомая верхняя граница
Требование отсутствия дубликатов подстрок длины является весьма обоснованным в программах для ЭВМ в которых экономия выражений приводит к тому что общему подвыражению дается отдельное имя поэтому его надо вычислять только один раз Следовательно если общее подвыражение длины необходимо программе более одного раза присваивание его отдельному операнду увеличит (число типов операторов) на единицу
Число возможных комбинаций из элементов взятых по за раз хорошо известно из школьного курса математики и составляет
N +1
Если учесть что операторы и операнды как правило, чередуются, то можно получить другое соотношение
N 1122
Верхняя граница для этого неравенства должна включать не только упорядоченное множество из N элементов представляющих исследуемую программу но и его всевозможные подмножества Семейство всевозможных подмножеств из N элементов содержит 2N элементов. Следовательно мы можем приравнять число возможных комбинаций из операторов и операндов (равное числу подстрок N/) числу подмножеств из N элементов и выразить длину реализации алгоритма через его словарь Из уравнения
2N = 1122
получаем
N = log2 (1122)
или
N = log2 11 + log2 22
Это дает нам уравнение оценки длины
1 log21 + 2 log22 (2.1)
В этом выражении символ N снабдили для того чтобы отличать вычисленную (теоретическую) оценку длины от значения N полученного в результате непосредственного измерения (опытной длины) Эта оценка соответствует основным концепциям теории информации, по которым частота использования операторов и операндов в программе пропорциональна двоичному логарифму количества их типов. Выражение (2.1) представляет собой идеализированную аппроксимацию измеренной длины N=N1+N2 , справедливую для программ, не содержащих несовершенств (стилистических ошибок) [1]. Экспериментальные исследования ряда авторов на представительной группе программ показали, что для стилистически корректных программ отклонения в оценке их теоретической длины от опытной не превышают (10-15)% .