Г.И. КАЙГОРОДЦЕВ
ВВЕДЕНИЕ В КУРС МЕТРИЧЕСКОЙ ТЕОРИИ
И МЕТРОЛОГИИ ПРОГРАММ
НОВОСИБИРСК
2009
УДК 004.412(075.8)
К 15
Рецензенты: <...> Введение в курс метрической теории и метрологии прог-рамм : учебник / Г.И. Кайгородцев. <...> Холстедом около трех десятков лет назад, в данном учебнике изложена концептуально и математически
как одно из приложений алгоритмической теории сложности. <...> . Эта дисциплина (в отечественной литературе именуемая также программометрикой) в ее современном состоянии позволяет разработчикам программного обеспечения информационных систем с удовлетворительной для практики
точностью решать следующие задачи:
– количественного анализа возможности и целесообразности создания программного обеспечения (ПО) задач информационных систем (ИС) в заданной постановке (на основе оценок критических значений величин их программной, вычислительной и информационной
сложности);
– оптимизации и численной оценки основных конструктивных
параметров (метрик) будущего ПО ИС (длина, объем в битах, количество модулей и иерархических уровней, надежность в начальный
период эксплуатации) на основе постановок задач;
– оценки трудоемкости и календарного планирования разработки
ПО, а также технико-экономического обоснования проекта системы. <...> Первая глава посвящена изложению основных сведений из алгоритмической теории сложности (логической основы дисциплины в
принятом автором подходе ее построения), а также некоторых фактов
6
ПРЕДИСЛОВИЕ
инженерной психологии, необходимых для расчета ряда параметров,
особенно характеристик надежности программ. <...> Во второй главе на основе трактовки объемных метрик программ
как мер алгоритмической сложности решения задач дан вывод соотношений Холстеда. <...> Доказано основное свойство вероятностной модели текста программы, т. е. быстрое уменьшение коэффициента вариации ее длины с ростом словаря. <...> Третья глава посвящена изложению основных результатов теории
вычислительной и информационной <...>
Введение_в_курс_метрической_теории_и_метрологии_программ.pdf
Министерство образования и науки Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
__________________________________________________________________________
Г.И. КАЙГОРОДЦЕВ
ВВЕДЕНИЕ В КУРС МЕТРИЧЕСКОЙ ТЕОРИИ
И МЕТРОЛОГИИ ПРОГРАММ
НОВОСИБИРСК
2009
Стр.1
УДК 004.412(075.8)
К 15
Рецензенты:
Ю.А. Щеглов, д-р техн. наук, проф.,
директор Ин-та прикладной информатики НГУЭиУ;
М.Г. Максимов, канд. техн. наук, гл. конструктор автоматизированных
систем технологической подготовки производства ОАО НИИсистем;
М.Г. Зайцев, канд. физ.-мат. наук, доц. кафедры ПСиБД НГТУ
Кайгородцев Г.И.
Введение в курс метрической теории и метрологии прог-рамм : учебник
/ Г.И. Кайгородцев. – Новосибирск : Изд-во НГТУ, 2009. –
192 с. (Серия «Учебники НГТУ»).
ISBN 978-5-7782-1080-6
Метрическая теория программ, созданная М. Холстедом около трех десятков
лет назад, в данном учебнике изложена концептуально и математически
как одно из приложений алгоритмической теории сложности. Это позволило
придать ей не только логическую последовательность, но и уточнить смысл
базовых понятий; кроме того, впервые дать строгую оценку точности основных
соотношений, составляющих ядро расчетных методов программной инженерии.
Предложенный в учебнике алгоритм расчета характеристик и трудоемкости
программного обеспечения является, по существу, аналогом метода
функциональных точек, параметры и количество которых определяются на
основе этой теории.
Учебник предназначен для студентов вузов, специализирующихся в области
прикладной информатики (по областям применения), а также для специалистов,
занятых проектированием и разработкой как прикладного, так и
системного программного обеспечения больших информационных систем.
УДК 004.412(075.8)
ISBN 978-5-7782-1080-6
Кайгородцев Г.И., 2009
Новосибирский государственный
технический университет, 2009
Стр.2
ОГЛАВЛЕНИЕ
Предисловие ............................................................................................................ 5
Введение .................................................................................................................. 8
Г л а в а 1. Необходимые сведения из алгоритмической теории сложности
и инженерной психологии .......................................................... 13
1.1. Определение алгоритмической сложности ........................................... 13
1.2. Свойства алгоритмической сложности ................................................. 14
1.3. Сложность и случайность ....................................................................... 18
1.4. Законы преобразования информации в кратковременной памяти
человека .................................................................................................... 19
Г л а в а 2. Программная сложность задач (объемные характеристики
программ) ............................................................................................ 23
2.1. Длина программы (алгоритмическая сложность решаемой
задачи) ...................................................................................................... 23
2.2. Вероятностная модель программы. Математическое ожидание
длины ее текста ........................................................................................ 25
2.3. Дисперсия длины программы. Точность соотношения Холстеда ..... 27
2.4. Метрические характеристики программ. Словарь программы ........... 30
2.5. Оптимизация характеристик модульно-иерархической структуры
программ ............................................................................................. 34
2.6. Количественная оценка работы программирования. Квалификационное
время программирования ........................................................ 42
2.7. Количественная оценка уровня универсальных алгоритмических
языков программирования ...................................................................... 44
2.8. Принцип системности в метрической теории программ ..................... 51
Г л а в а 3. Вычислительная и информационная сложность задач
(временные характеристики программ) ........................................... 55
3.1. Вычислительная сложность решения задач .......................................... 55
3.2. Информационная сложность решения задач ........................................ 70
Стр.187
190
Г л а в а 4. Надежность и корректность программного обеспечения ............... 77
4.1. Ошибки и последствия: принципиальный вопрос разработки ПО ..... 77
4.2. Основные понятия надежности программ. Экспоненциальная
модель распределения ошибок ............................................................... 81
4.3. Защитное программирование и использование различных видов
избыточности для повышения надежности ПО .................................... 87
4.4. Отладка программ ................................................................................... 93
4.5. Тестирование (испытание) программ .................................................... 97
4.6. Формальная корректность программ .................................................. 101
4.7. Детерминированная, стохастическая и динамическая корректность
программ ...................................................................................... 102
Г л а в а 5. Применение метрической теории программ .................................. 105
5.1. Измерение производительности труда в программировании ........... 105
5.2. Расчет метрических характеристик ПО и трудоемкости его разработки
(на основе постановок задач) ................................................. 113
5.3. Трансляторы и операционные системы .............................................. 119
5.4. Программометрический расчет некоторых статистических характеристик
ПО ..................................................................................... 127
5.5. Оценка эффективности специализированных языков программирования
................................................................................................... 130
5.6. Проблема языка программирования, близкого к естественному ...... 131
5.7. Конструкторская компоновка логических схем ................................. 132
5.8. Оценка эффективности экономических ИС на стадии их проектирования
............................................................................................... 133
Г л а в а 6. Метрология качества программ (методологический аспект) ....... 139
6.1. Основные сведения из теории шкал и измерений качества ............. 140
6.2. Номинальные шкалы ............................................................................ 144
6.3. Порядковые шкалы ............................................................................... 145
6.4. Интервальные шкалы ............................................................................ 146
6.5. Преобразование шкал ........................................................................... 147
6.6. Фасетная классификация мер качества программ.............................. 149
6.7. Интенсивность использования мер качества программ по категориям
..................................................................................................... 156
Заключение .......................................................................................................... 157
Приложения ......................................................................................................... 159
Приложение 1 ...................................................................................................... 159
Приложение 2 ...................................................................................................... 160
Стр.188
191
Приложение 3 ...................................................................................................... 161
Приложение 4 ...................................................................................................... 162
Приложение 5 ...................................................................................................... 163
Приложение 6 ...................................................................................................... 164
Приложение 7 ...................................................................................................... 165
Приложение 8 ...................................................................................................... 169
Приложение 9 ...................................................................................................... 179
Библиографический список ............................................................................... 186
Стр.189