Введение в курс метрической теории и метрологии программ


Министерство образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ




Г.И. КАЙГОРОДЦЕВ






    ВВЕДЕНИЕ В КУРС МЕТРИЧЕСКОЙ ТЕОРИИ И МЕТРОЛОГИИ ПРОГРАММ



Рекомендовано Учебно-методическим объединением по образованию в области прикладной информатики в качестве учебника для студентов высших учебных заведений, обучающихся по специальности 080801 «Прикладная информатика (по областям)» и другим экономическим специальностям











НОВОСИБИРСК
2011

УДК 004.412(075.8)
     К 15

Рецензенты:
Ю.А. Щеглов, д-р техн. наук, проф., директор Ин-та прикладной информатики НГУЭиУ;
М.Г. Максимов, канд. техн. наук, гл. конструктор автоматизированных систем технологической подготовки производства ОАО НИИсистем;
М.Г. Зайцев, канд. физ.-мат. наук, доц. кафедры ПСиБД НГТУ






      Кайгородцев Г.И.
К 15 Введение в курс метрической теории и метрологии программ : учебник / Г.И. Кайгородцев. - 2-е изд., испр. - Новосибирск : Изд-во НГТУ, 2011.- 192 с. (Серия «Учебники НГТУ»).


         ISBN978-5-7782-1648-8


           Метрическая теория программ, созданная М. Холстедом около трех десятков лет назад, в данном учебнике изложена концептуально и математически как одно из приложений алгоритмической теории сложности. Это позволило придать ей не только логическую последовательность, но и уточнить смысл базовых понятий; кроме того, впервые дать строгую оценку точности основных соотношений, составляющих ядро расчетных методов программной инженерии. Предложенный в учебнике алгоритм расчета характеристик и трудоемкости программного обеспечения является, по существу, аналогом метода функциональных точек, параметры и количество которых определяются на основе этой теории.
           Учебник предназначен для студентов вузов, специализирующихся в области прикладной информатики (по областям применения), а также для специалистов, занятых проектированием и разработкой как прикладного, так и системного программного обеспечения больших информационных систем.




УДК 004.412(075.8)


ISBN 978-5-7782-1648-8

                  © Кайгородцев Г.И., 2009, 2011
© Новосибирский государственный

технический университет, 2009, 2011

   ПРЕДИСЛОВИЕ

   Цель данного учебника - введение в метрическую теорию программ, ставшую основой метрологии их качества (сложности, надежности, трудоемкости создания и т. п.). Эта дисциплина (в отечественной литературе именуемая также программометрикой) в ее современном состоянии позволяет разработчикам программного обеспечения информационных систем с удовлетворительной для практики точностью решать следующие задачи:
   -    количественного анализа возможности и целесообразности создания программного обеспечения (ПО) задач информационных систем (ИС) в заданной постановке (на основе оценок критических значений величин их программной, вычислительной и информационной сложности);
   -    оптимизации и численной оценки основных конструктивных параметров (метрик) будущего ПО ИС (длина, объем в битах, количество модулей и иерархических уровней, надежность в начальный период эксплуатации) на основе постановок задач;
   -    оценки трудоемкости и календарного планирования разработки ПО, а также технико-экономического обоснования проекта системы.
   Содержание учебника соответствует требованиям раздела ДС.08 ГОСа высшего профессионального образования «Метрология и качество программного обеспечения» (специальность 351500 «Математическое обеспечение и администрирование информационных систем»).
   Учебник состоит из шести глав и Приложения.
   Первая глава посвящена изложению основных сведений из алгоритмической теории сложности (логической основы дисциплины в принятом автором подходе ее построения), а также некоторых фактов

ПРЕДИСЛОВИЕ

инженерной психологии, необходимых для расчета ряда параметров, особенно характеристик надежности программ.
   Во второй главе на основе трактовки объемных метрик программ как мер алгоритмической сложности решения задач дан вывод соотношений Холстеда. Доказано основное свойство вероятностной модели текста программы, т. е. быстрое уменьшение коэффициента вариации ее длины с ростом словаря. Решена задача оптимизации модульно-иерархической структуры программ. Приведено понятие «работы программирования» (с точки зрения инженерной психологии), а также определение на его основе численной характеристики уровня универсальных алгоритмических языков.
   Третья глава посвящена изложению основных результатов теории вычислительной и информационной сложности задач, иначе говоря, временных характеристик алгоритмов их решения, особенно актуальных при разработке ПО методов оптимизации.
   В четвертой главе по аналогии с надежностью технических систем вводится характеристика надежности ПО ИС как «наработки на ошибку», весьма важной в начальный период его эксплуатации. На основе результатов предшествующих глав дан способ проектной оценки среднего значения этой величины.
   В пятой главе подробно изложены примеры использования программометрических методов в прикладной информатике. Приведен полный алгоритм оценки проектных параметров ПО ИС на основе постановок задач (точнее, их словарей).
   Шестая глава посвящена методологическим вопросам метрологии и качества ПО.
   В конце глав приведены вопросы и задачи, решение которых при изучении дисциплины весьма желательно.
   В конце учебника даны Приложения и библиографический список.
   В Приложения 1-7 вынесены некоторые подробности математических выкладок, не существенные с идейной точки зрения.
   Приложения 8-9, напротив, важны по принципиальным соображениям. Изложенные в них энтропийные принципы сложных систем (использованы в главах 1, 2, 5) будут полезны при изучении других дисциплин (например, экономических), где находят все большее применение.

Данный учебник подготовлен на базе курса лекций «Программо-метрика», читаемого автором в НГТУ с 1997 г. (под тем же названием в 2004 г. вышло второе издание конспекта лекций объемом 5 п. л.). В настоящее время этот курс содержит практические занятия, лабораторные и расчетно-графические работы.
   Автор, пользуясь случаем, выражает глубокую признательность доценту НГТУ М.Г. Зайцеву за конструктивное обсуждение всех аспектов преподавания этой дисциплины.

  ВВЕДЕНИЕ


   Фундаментальный характер проблем системного программирования впервые проявился при создании операционной системы OS/360. В 1975 г. руководитель разработки Ф. Брукс, осмысливая опыт управления проектом такого масштаба, писал: «Программирование больших систем последние десять лет было той асфальтовой топью, в которой увязли многие огромные и сильные "звери". Почти все работающие системы не соответствовали своим спецификациям, своему назначению, не укладывались в графики и бюджет. Большие и маленькие, громоздкие и гибкие коллективы разработчиков неизбежно попадали в ловушку асфальтовой топи. Ничто, казалось, не вызывает затруднений - можно вытащить любую лапу. Однако накопление одновременных и взаимодействующих факторов приводило к затруднению движения.
   Неподатливость проблемы вызывает всеобщее удивление, и разобраться в ее природе непросто» [1].
   Суть этой проблемы на обычном языке можно выразить очень кратко: возможно ли быстро создать большое и сложное по замыслу литературное произведение (скажем, что-либо подобное «Войне и миру» Л.Н. Толстого), используя одновременный труд большого коллектива людей.
   Операционная система OS/360, представлявшая собой текст в машинном коде, по объему на порядок превосходила упомянутое творение Л.Н. Толстого. Что касается остальных деталей, например, количества «действующих лиц» - функциональных модулей, событий вычислительного процесса, требующих синхронизации по месту и времени и тому подобное, то это сопоставление просто теряло всякий смысл. В пиковые периоды над OS/360 работали около 1000 человек.

По оценке Ф. Брукса, если бы вся работа выполнялась первоначальной группой численностью 200 человек, то для исполнения заказа потребовалось бы 25 лет (при договорном сроке около 3 лет). Таким образом, имела место жесткая дилемма. Концептуальное единство архитектуры ПО (т. е. целостное по смыслу произведение, если продолжить наше сравнение, вместо сборника плохо связанных рассказов) могло быть обеспечено только минимальным количеством исполнителей (в идеале - одним человеком), в то время как сильные ограничения по срокам разработки требовали привлечения многочисленной рабочей силы.
   Архитектура ПО ИС - это полная и подробная спецификация его сопряжения с пользователем. (Для компьютера - это руководство по программированию, а не техническое описание и блок-схемы устройств; для транслятора - руководство по входному языку. Для наручных часов, как писал Ф. Брукс, архитектура «это циферблат, стрелки и головка завода»).
   При всей кажущейся простоте задача разработки архитектуры ПО ИС в большинстве случаев трудноформализуема. Дж. фон Нейман утверждал, что в «сложных системах формальной логики на порядок труднее рассказать, что объект может сделать, чем сделать сам объект» [2].
   Последнее обстоятельство резко увеличивает вероятность семантических ошибок, делая процесс разработки ПО неизбежно итеративным. Поскольку в работе занято большое количество людей, то при декомпозиции системы на п фрагментов возникает необходимость тестирования п(п - 1)/2 сопряжений. При п ® 10³ задача становится невыполнимой, а время завершения отладки - непредсказуемым. Так возникает проблема надежности и корректности ПО.
   Другой круг проблем практически не зависит от архитектурных решений: это метризация ПО, т. е. разработка системы численных характеристик (метрик) его свойств и качеств, допускающих объективное измерение и теоретический расчет. Последнее особенно важно, так как планирование и управление проектом невозможно без численных оценок ожидаемых значений параметров программ.
   Как видим, решение этих и ряда других вопросов было невозможно без адекватного представления о природе объекта, создаваемого в процессе программирования.

ВВЕДЕНИЕ

   Реакцией практики на создавшееся положение стала разработка инженерных методов и средств создания ПО, объединенных общим названием «Soft engeering», - программная инженерия. В 1975 г. состоялась первая международная конференция, посвященная состоянию и проблемам этой дисциплины. В ее основу было положено методологическое допущение: процесс проектирования ПО ИС может быть формализован, как это имеет место в других областях техники.
   Но, как показал последующий опыт, прямое заимствование идей и методов из других областей инженерной деятельности оказалось малопродуктивным. Так, в 1995 г. компания Standich Group опубликовала статистические данные по исследованию софтверного сектора американской экономики [3]. Оказалось, что только около 16 % проектов завершены по плану, их разработчики уложились в бюджет и удовлетворили все архитектурные требования к системам (речь идет об анализе работы 364 корпораций по 23 тыс. проектов ПО ИС). Разработчики почти 53 % проектов превысили срок и бюджет примерно в два раза, а 31 % проектов были аннулированы до своего завершения.
   В последующие годы имело место лишь незначительное улучшение этих показателей. Более того, по данным Института программной инженерии (SEI) до 80 % работающего ПО создавалось вообще без использования какой-либо технологии и дисциплины проектирования (речь идет, конечно, о малых и средних проектах) [3].
   Это положение, сложившееся в проектировании и разработке ПО ИС почти полвека назад, получило странное название «кризис программирования». О нем говорят и сегодня, имея в виду приведенную выше статистику.
   Проектно-конструкторская деятельность в других областях техники основана на точных законах современной физики, обеспечивающих не только высокую точность расчетов, но и определяющих границы возможного и невозможного. Так, средний коэффициент полезного действия тепловых двигателей составляет 30...35 %, но любой проект, ставящий цель улучшить этот показатель до 60.70 %, не будет даже рассматриваться, так как он заведомо нереализуем. Таковы законы термодинамики, о кризисе теплоэнергетики в этом смысле, естественно, не может быть и речи.

Современная программная инженерия накопила огромный практический опыт и эмпирические знания, однако, изначально не выдвигала фундаментальных проблем о природе объектов, над созданием которых работают системные программисты. Конечно, этот факт имеет веские основания, хотя и субъективного характера. Мир профессиональной деятельности программиста неизбежно носит виртуальный характер. «Программист имеет дело с очень податливым материалом: концепциями и весьма гибкими представлениями. Поскольку материал столь послушен, мы не ожидаем особых затруднений при его реализации, и отсюда наш всепроникающий оптимизм. Поскольку наши идеи неверны, мы получаем ошибки» [1]. Идея о том, что в этой сфере могут действовать объективные закономерности, психологически для него просто неприемлема.
   За последние три десятилетия возникла и сформировалась область научных исследований, получившая название метрической теории программ, объектом изучения которой стали структурные и количественные закономерности больших правильно (оптимально) построенных текстов программ, вообще говоря, безотносительно к их семантике. Первое систематическое изложение этой теории было дано М. Холстедом в 1976 г. [4]. Введенные им объемные метрики текстов программ допускают простое вычисление и практическое (в том числе автоматизированное) измерение, что делает возможным эффективную проверку полученных выводов. Принципиальное значение имеет также впервые введенная им в теорию численная мера уровня алгоритмического языка. Найденная М. Холстедом зависимость между величиной словаря программы и другими ее метрическими характеристиками оказалась следствием закона Ципфа, давно известного в лингвистике для текстов более общей природы [5, 6]. Всесторонняя проверка этих выводов, в том числе ретроспективный анализ неудачных проектов ПО ИС, позволили установить объективные причины трудностей. Так, было установлено существование программ, длина которых экспоненциально зависит от размера их словарей: «комбинаторный взрыв» исключал контроль за параметрами системы.
   В 1982 г. Ю.А. Шрейдер и Н.А. Шаров показали, что распределение Ципфа и вытекающее из него соотношение М. Холстеда следуют из общесистемного принципа минимума симметрии [6].

ВВЕДЕНИЕ

Это означает, что достаточно большой семантически корректный текст может служить моделью сложной системы, если она состоит из большого количества элементов ограниченной номенклатуры. Иначе говоря, метрическая теория программ - это одна из конкретных (количественных) интерпретаций общей теории систем.
   До сих пор речь шла об объемных параметрах (метриках) ПО, т. е. о количестве слов, модулей, иерархических уровней и т. п. Расчет их ожидаемых (проектных) значений - это одна из главных задач программометрики.
   Быстродействие современных компьютеров значительно снизило требование к временным характеристикам ПО. Однако рост скорости вычислений одновременно стимулировал интерес практики к таким областям, как, например, задачи дискретной оптимизации. Анализ трудностей, встретившихся при поиске эффективных методов их решения, привел к открытию феномена труднорешаемых задач. Он заключается в том, что для их точного решения не существует других алгоритмов, кроме перебора всех возможных вариантов. Более того, было показано, что и приближенные алгоритмы, обеспечивающие достаточно высокую точность, столь же трудоемки, как и полный перебор.
   Для практики разработки ПО наиболее важный результат теории труднорешаемых задач заключается в их каталогизации, так как формулировки таких задач внешне не отличаются от «нормальных». Практически это единственный доступный способ своевременной диагностики труднорешаемости поставленных задач, что стало важным условием успешности проекта в целом.
   Резюмируя сказанное выше, можно утверждать, что в настоящее время программная инженерия из «совокупности методов и средств» превратилась в прикладную дисциплину точно определенной области фундаментальных научных исследований. Метрическая теория программ - это не формально-математическая дисциплина, а опытная наука, одно из подходящих названий которой - «физика программ» [4].