автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Проектирование и оценка качества программ на основе структурно-графических представлений



, .л^Я На правах рукописи

о * Ь

Демин Антон Юрьевич

Проектирование и оценка качества программ на основе структурно-графических представлений

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертация на соискание ученой степени кандидата технических наук

Томск —

1998

Работа выполнена в Томском политехническом университете

Научный руководитель:

доктор технических наук, профессор В.К. Погребной

Официальные оппоненты:

доктор технических наук, профессор Н.Г. Марков кандидат технических наук В.В. Кручннлн

Ведущая организация:

НИИ ПММ Томского государственного университета

Защита состоится " 50 " ^¿ЛоА^ 199 $ г. на заседании диссертационного Совета Д 063.80.03 при Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84, Кибернетический центр ТПУ.

С диссертацией можно ознакомиться в библиотеке Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 53.

Автореферат разослан «_ 1С » ноября 1998 г.

Ученый секретарь диссертационного Совета к.т.н., доцент

1.1И.Л. Чудинов

Общая характеристика работы

Актуальность работы. В настоящее время разработка любого программ-юго обеспечения (ПО) не рассматривается без привлечения методов анализа ¡труктуры ПО и его структурного проектирования. Успешное развитие вычис-штельной техники и операционных систем (ОС), особенно в направлении Улучшения графических возможностей, позволило вести проектирование ПО на зснове структурно-графического представления. Такое представление ПО ллучшает такие свойства программ, как: попимаемость, эффективность, сопро-зождаемость и т. д. Так же на основе структурно-графического представления ножно решать ряд задач, связанных с анализом свойств, распараллеливанием, эптимизацией ПО, а также подготовкой его к тестированию и т. д.

Многие ученые (В.Е. Котов, В.В. Липаев, A.A. Саркисян, L. Lamport, Ra-■namorthy, и др.), ведущие исследования в этой области, отмечают недостаточ-яую развитость традиционных подходов к созданию ПО.

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

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

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

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

• недостаточной проработанностью методов анализа представления ПО и определения его свойств;

• отсутствием высокоэффективных методов синтеза ПО на основе его структурно-графического представления. Особенно это относится к ПО, созданного с помощью современной концепции объектно-ориентированного программирования (ООП);

. отсутствием набора инструментальных средств (ИС) поддержки разработки ITO на основе структурно-графического представления,

. отсутствием технологии проектирования ПО, основанного на таких методах и средствах.

Исследования и разработки проводились в Кибернетическом центре Томского политехнического университета в соответствии с утвержденными планами НИР в составе Государственной научно-технической программе по информатизации высших учебных заведений России по теме «Разработка среды программирования Паскаль-программ на основе системы ТРАНСВИР» (в соответствии с договором № 8-03/95-(5 пит/95)) и в составе программы Университеты

России по теме «Методы анализа и адаптации программ для выполнения на МВС в реальном масштабе времени».

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

1. Развитие теоретических основ представления ПО в структурно-графическом виде.

2. Разработка алгоритмов анализа структурно-графического представления и методов оценки качества программ.

3. Разработка методов проектирования ПО на основе структурно-графического представления.

4. Создание инструментальных средств, предназначенных для реализации предложенных подходов и методов.

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

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

Научную новизну полученных результатов определяют.

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

. методология анализа программ и получения их структурно-графического представления;

. система критериев оценки качества программ, представленных в структурно-графической форме.

. методы проектирования ПО на основе структурно-графического представления;

. совокупность инструментальных средств, реализующих предложенные способы, методы и методики.

Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методики, методы, алгоритмы и инструментальные программные средства. Инструментальное ПО предназначено для работы на ПЭВМ типа IBM PC AT в ОС Windows NT и создано с помощью интегрированной среды программирования Delphi 3.0. В состав разработанных ИС входят следующие пакеты программ: "Томограф Паскаль-программ", система визуального проектирования программ (СВиПП), система проектирования модели ПО для распределенных СРВ. Суммарный объем созданных программных пакетов составляет более 16000 операторов.

«Томограф Паскаль-программ» использовался при разработке программ расчета и визуализации обмотки трансформаторов и программы-тренажера для имитации работы системы преобразования и управления двигательной уста-

новкой ориентации в НГЩ «Полюс», что подтверждено соответствующим актом внедрения.

Система СВиГТП внедрена в КЦ ТПУ с 1997 в системе подготовки школьников старших классов по курсу «Информатика и вычислительная техника», что подтверждено соответствующим актом внедрения.

Система проектирования модели ПО для распределенных СРВ использовалась на кафедре Автоматизации проектирования Томского политехнического университета при выполнении цикла лабораторных работ и курсового проекта по курсу «Автоматизированные системы проектирования систем реального времени».

Основные положения, выносимые на защиту:

1. Структурно-графические представления в сравнении с текстовыми являются более удобными и понимаемыми при практическом анализе и синтезе программ как вручную, так и автоматизированными методами.

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

3. Разработанная система критериев оценки качества программ по структурно-графическому преде гавлению, совокупность методов и правил внесения изменений позволяют не только оценить качество ПО, но и создать условия для улуч[ПС!uní качества.

4. Разработанные методы проектирования ПО на основе структурно-графического представления повышают надежность разработанного Г10 и сокращают сроки проектирования

Апробация работы. Основные результаты работы докладывались и обсуждались на Международной научно-технической конференции «Научные основы высоких технологий» (г. Новосибирск. 1997 г.), на Международной научно-технической конференции «VIII Бенардосовские чтения» (г. Иваново, 1997 г.), на второй региональной научно-технической конференции студентов и молодых специалистов «Радиотехнические и информационные системы и устройства» (г. Томск, 1997 г.), на Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (г. Новосибирск, 1998 г.), на втором Российско-Корейской, международном симпозиуме по науки и технологиям KORUS 98 (г. Томск, 1998 г.).

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

Система анализа и представления ПО в структурно-графическом виде «Томограф Паскаль-программ» официально зарегистрирована в Российском агентстве по правовой охране программ для ЭВМ, баз данных и топологии интегральных микросхем (РосАПО) за №980155. «Томограф Паскаль-программ» получил сертификат соответствия № РОСС RU.ME20.H00087 в системе сертификации ГОСТ Р Госстандарта РФ.

Публикации. По результатам исследований опубликовано 9 работ, в том числе 4 статьи.

Личный вклад:

1. Основные идеи по представлению программ в структурно-графической форме принадлежат В.К. Погребному и автору.

2. Методы получения структурно-графического представления ПО из текста программ разработаны лично автором.

3. Разработка системы основных свойств программ, представленных в структурно-графическом виде проведена и автором совместно с В.К. Погребным.

4. Методы оценки основных свойств программ и теоретическое обоснование возможности их использования получены лично автором.

5. Теоретические основы проектирования ПО для распределенных систем реального времени (СРВ) на основе структурно-графического представления разработаны В.К. Погребным и Д.В. Погребным.

6. Алгоритм создания модели ПО для распределенных СРВ в виде графа потока данных разработаны лично автором.

7. Теоретическое обоснование и способы проектирования объектно-ориентированных программ на основе структурно-графического представления принадлежат лично автору.

8. Программные средства инструментальной системы анализа программ «Томограф Паскаль-программ» разработаны автором, за исключением создания части базовых классов графических примитивов, разработка которых принадлежит Д.В. Погребному.

9. Программные средства проектирования программ на основе их структурно-графического представления (система СВиПП) и программные средства для создания модели ПО для распределенных СРВ разработаны автором.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 114 наименований и приложения. Объем основного текста диссертации составляет 143 страницы машинописного текста, иллюстрированного 30 рисунками.

Содержание работы

Во введении обосновывается актуальность работы и формулируется ее цель, показывается научная новизна и практическая значимость результатов и приводится краткое содержание работы по главам.

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

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

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

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

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

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

Формулируются цель и основные задачи, решаемые в диссертационной работе.

Во второй главе излагаются развитый автором способ представления ПО в структурно-графической форме.

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

Определение 1. '(цкнои тши-<> данных называется связанный ациклический граф П - (/. (О, где Т - множество вершин, соответствующих типам данных, и множество дуг, отображающих связи построения типов

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

Определение 3. Нссоощим осромч данных называется связанный ациклический граф Е - (I.)II'', с0), где с0 - корень дерева, О' -- множество деревьев типов данных; Ж - множество ребер, связывающих корни деревьев типов данных с вершиной во.

Определение 4. Дерево процедур и функции — это связанный ациклический граф Р = (О, и, Р')), где О - множество вершин, соответствующих процедурам и функциям, ра - корень, соответствующий головной программе; и -множество дуг, задающее отношение вложенности подпрограмм. То есть для подпрограмм / и J (/ * /) существует дуга (г, /) е V, если подпрограмма } описана внутри подпрограммы /'.

Определение 5. Деревом структурных операторов называется ациклический связанный граф 5 = {О, V, о0), где О - множество вершин, соответствующих оператором, во - корень дерева, и - множество дуг, определяющих структуру вложенности операторов друг в друга.

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

Определение 6. Схема Паскаль-модулей есть связанный граф М = (В, U. то), где В - множество вершин, поставленных в соответствие Паскаль-модулям; то - вершина, отвечающая головной программе; U - множество дуг. отвечающих межмодульным связям. При этом (г, J) е U , если в модуле i в предложении USES включено имя модуля j.

Определение 7. Деревом классов называется связанный ациклический граф С = (К, R, Р, U, к0), где К - множество вершин, поставленных в соответствие классам; к0 - корень дерева, отвечающий классу-предку, который является базовым для всех других классов; R - множество вершин, отвечающих полям классов; Р - множество вершин, соответствующих методам классов; U - множество дуг, задающих отношения наследственности и отношения принадлежности полей и методов определенным классам.

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

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

Определение 8. Динамически строящимся деревом для дерева 7= (Л', II), называется дерево Y' = (Х\ U'), где X' czX, U' с U, а дерево Y называется деревом -прот о тип ом.

Определение 9. Динамически строящееся дерево Y' = (Х\ U') является полностью свернутым, если U' = 0,Х'~ {-V}, *о' ~ соответствует корню дерева-прототипа.

Определение 10. Динамически строящееся дерево Y' = (Х\ U') является полностью развернутым, если U' = U, X' = X, для Y-(X., U) - дерева прототипа.

Первоначально динамически строящееся дерево отображается в полностью свернутом состоянии и уже достраивается вершинами, соответствующими вершинам дерева-прототипа.

Динамически строящееся дерево может быть построено не только для дерева типов данных, дерева процедур и функций, дерева структурных операторов, дерева классов, но и для схемы Паскаль-модулей.

Описанные деревья взаимосвязаны между собой. Например, каждой вершине дерева процедур и функций соответствует дерево структурных операторов и всеобщее дерево данных. Для отображения таких деревьев разработана методика работы с взаимосвязанными деревьями.

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

рассмотрении ПО

Теорема 1. Множество вершин Ь' = {/,'}, являющихся листьями динамически строящегося дерева 1" = (А", II') для дерева структурных операторов (х, е X' л/.'с Л", но —:Э (/, ', xJ') е I/'), соответствует множеству фрагментов текста программы, полностью покрывающих исполняемую часть программы.

Из теоремы 1 следует, что с помощью динамически строящегося дерева для дерева структурных операторов можно декомпозировать исполняющую часть программы на фрагменты. При этом программа разбивается на фрагменты, соответствующие листьям в динамически строящемся дереве.

Для выбранного уровня декомпозиции программы можно получить дополнительные структурно-графические представления: блок-схему и граф потока Оаиных.

Определение 11. Блок-схема — это ориентированный граф Н = (А7, II, по) с вершинами специального вида, соответствующий условиям:

1. Граф й имеет единственную входную вершину по, и в эту вершину не входит ни одна дуга.

2. ГпгнЬ (! по содержит параллельных дуг и петель;

3. Конечное множество дуг !■'= {?/.}. /= 1,.... 1: отражает отношение предшествования по выполнению между операторами программы;

4. Конечное множество вершин Л' = {''/,}, ,и = О,..., М, представляеI совокупность операторов В - {/>„}, и = О,..., Л/, программы. Причем между ними существует взаимно однозначное соответствие, (каждая вершина представляет только один оператор программы и, наоборот, каждый оператор программы в графе представляется только одной вершиной).

5. Конечное множество вершин N = ¡л = О,..., М, представляет совокупность сложно-составных операторов В' = {й',,}, и = 0,..., \1, программы. Причем иежду ними существует взаимно однозначное соответствие. Поскольку любой вершине п^ соответствует сложно-составной оператор, то она представляет группу простых операторов.

Для изучения информационных связей в ПО строится граф потока данных. Определение 12. Графом потока данных (ГПД) называется ориентированный граф /? = (Л', Д ГД гдеЛ:- множество вершин соответствующих сложно-составным операторам, представленных листьями в динамически строящемся дереве; /> - множество вершин, соответствующих данным, используемым в программе, причем единице данных могут быть поставлены в соответствие несколько вершин; II- множество дуг таких, что

[если с1,еВ исплользуегся в п,. е N 3 (с/„л,) е и ^

[еслиг/, еВ изменяется в«(ел

Определение 13. Множество вершин N из Я., соответствующих сложно-составным операторам, назовем переходами, а множество вершин В из Л, соответствующих данным, назовем позициями.

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

В третьей главе рассматриваются методы оценки качества ПО с помощью структурно-графических представлений. Методы оценки качества заключаются в анализе текстового описания ПО, получении структурно-графических представлений и определения по ним основных свойств программ.

Даны определения всем свойствам, по которым проводится оценка ПО. В работе утверждается, что предложенное структурно-графическое представление ПО повышает качество программ по свойствам понимаемое™ и сопровождаем ости .

В дальнейшем используются следующие обозначения:

~ полустепень захода для вершины пр;

¡1 - полустепень исхода для вершины

- множество непосредственных предшественников вершины и^; - множество предшественников вершины п,,\

Гл (пм) - множество непосредственных последователей вершины ни;

Г '' (/¡/;) - множество последователей вершины пм,

р[Цц, пх\ - длина пути из вершины яц в вершину

Для оценки качества по критерию вложенности используется представление ПО в форме деревьев.

Определение 14. Коэффициент вложенности ут для дерева Т = (М, II, щ) - самая максимальная длинна пути от корня дерева п0 к его листьям {/, } е/\;.

1/г = тахр[и0,/,], если V/ -> 3 (/,-,и7-) е и.

Введена операция присоединения деревьев друг к другу, и доказано монотонность и транзитивность коэффициента вложенности для введенной операции.

Определение 15. Присоединением дерева Т2 = {Ы2, и2, п20) к дереву 7; = (N1, 1/1, що) по вершине п1к(п1к е А";) называется дерево Т3 = (Л^, Щ, изо), Тз =

Т] Ф;. Т2, полученное в результате следующих действий:

1. Совмещения вершины п,К дерева 7} и корня дерева п2о (п-,к = п:,/)

2. Множество дуг дерева является объединением множества дуг дерева

Т, и Т3 (Из - Ь, и и:).

3. N¡=N¡^N2.

ТЕОРЕМА 2. Если дерево Т$ получено в результате присоединения дерева Т2 к дереву 7'/ по любому к, то коэффициент вложенности для дерева 7} 17 ? больше или равен коэффициенту вложенности для дерева 7) — \'п и больше или равен коэффициенту вложенности дерева Т2 - Ут2. Если V к Тз = 7/ Фа Т2, то Утз > л \*гз> Уп

Теорема 3. Если коэффициент утз для дерева Т2 больше коэффициента вложенности ут1 дерева 7) и если коэффициент вложенности утз дерева Тз больше коэффициента вложенности дерева Т2, то есть Уп < ут2 л Ур2 < Угз, то у-п < утз-

Также, для оценки вложенности введен средний коэффициент вложенности.

Определение 16. Средним коэффициентом вложенности рт для дерева Т = (М, и, по) называется величина, пропорциональная сумме длин всех путей из корня по дерева Т к его листьям {/,} = /V и обратно пропорциональная количеству этих путей.

¿рКД]

= - м V;-а (/,,«,) е и.

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

В работе приведены результаты исследования текстов программ, написан ных классиком структурного программирования Н. Виртом. Исследование проводились для выявления наиболее используемых уровней вложенности. Н; основании исследований выработан ряд рекомендаций по установлению уровн; вложенностей.

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

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

Определение 17. Коэффициентом логической сложности программы представленной блок-схемой Я = (М, II, п0) для полностью развернутого динамически строящегося дерева называется величина £ = пр*

<Г(л0) = 0 л <1 + (пт) = 0.

Определение 18. Цикяоматическим коэффициентом сложности программы, представленной блок-схемой Я = (Л,г, II, по) дам полностью развернутого динамически строящегося дерева структурных операторов, называется величина л = Х-У + Ь, гдеХ=\Ц\ - количество ребер в блок-схеме, У = |Л| +1 - количество вершин (вместе с щ), Ь - число связанных компонент. Для блок-схемы, представляющей безошибочную программу, 1=1.

Определение 19. Суммой двух блок-схем //у = (Л^, [/¡, пщ) и блок-схемы П2 = (А'з, и2, »02) называется блок-схема Н3 = (N3, II¡, Поз) Н3 = Н] @ Н2, полученная в результате выполнения следующего алгоритма.

Алгоритм 1. (Алгоритм сложения блок-схем).

Шаг 1. Исходные данные: Н1 = (N1, п0О и Н2 = (М2, II2, Щ2), где N/ и N2 множества вершин, Пп\ и По2 - начальные вершины, II/ и 112 - множества дуг. Пусть Пк1 и Пк2 - конечные вершины

Шаг 2. Добавить в Я? все вершины из Н/, кроме конечной вершины: Лг3=и«„ для с1 * (пп) VI

I

Шаг 3. Добавить в Я? все вершины из Н2, кроме начальной вершины:

о,.

для (пц) ¿0 VI.

Шаг 4. Добавить в Я? все дуги из Н], кроме дуг имеющих конец в конечной

вершине: =и(и;1,и„) для Г' (пп) \/пц.

1

Шаг 5. Добавить в Н3 дуги соответствующие дугам в Н1, которые захо-

дят вПк/: из=из<и

для Г+ (пц) = Пк1 Упа

где п]2 е Г (пп) V].

Шаг б. Добавить в Нз дуги из Н2, не берущие начало в поу.

и, =и,, о|и(«,2,",2) (п,:)*п„2 Уп,2. I '

Шаг 7. Конец.

Введенная операция суммирования двух блок-схем соответствует блок-схеме, полученной из соединенных текстов программ, соответствующих слагаемым.

Теорема 4. /¡шаоматический коэффициент сложности Аз блок-схемы Нз, полученной в результате суммирования двух блок-схем Н; и Н2, равен сумме цюаоматическах коэффициентов сложности Л/ и А? блок-схемы Я; и Яг

Таким образом, доказано, что введенная оценка сложности логической структуры ПО через цикломатический коэффициент сложности является аддитивной. Из свойства аддитивности следует и монотонность.

Для оценки связанности используется структурно-графическое представление ПО в виде ГПД.

Определение 20. Коэффициентом связанности программы, представленной ГПД Я = (¿V, Р, II), называется величина Д равная числу дуг в этом графе. р=\Щ.

ТЕОРЕМА 5. Коэффициент связанности Д,- сШ ГПД, построенного из суммы двух программ, больше или равен сумме связанности каждой программу к, ,, /?.

Таким образом, введенный коэффициент связанности пригоден для оценки качества ПО по критерию связанности.

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

Для оценки распараллеливаемое™ программы используется структурно-графическое представление ПО в виде ГПД, причем ГПД представляется специальным образом. Для этого множество структурных операторов О разбивается на подмножества Д.

Определение 21. Подмножества Д множества О называются ярусами.

Причем множество операторов Д первого яруса тождественно множеству операторов, которые информационно независимы. Множество операторов П2 второго яруса тождественно множеству операторов, информационно зависимых хотя бы от одного оператора первого яруса. Множество операторов Д г-го яруса тождественно множеству операторов, информационно зависимых хотя бы от одного оператора (г - 1)-го яруса. Также для любого яруса выполняются следующие условия:

V/ Д * 0 Дп Д = 0 (г * у).

Определение 22. ГПД соответствующей упорядочиванию функциональных операторов по ярусам, соответствующим подмножествам Д>, ... , Д, ... множества О называется ГПД « ярусно-парачлелъной форме (ЯПФ).

Для получения ГПД в ЯПФ предложен следующий алгоритм:

Алгоритм 2.Алгоритм перестроения ГПД в ЯПФ.

Шаг 1. Упорядочить множество переходов N так, чтобы каждый переход занимал свой отдельный ярус с 0 по N. И чтобы их порядок не противоречил порядку выполнения соответствующих операторов. Установить г =/.

Шаг 2. Пронумеровать все переходы в соответствии с занимаемыми ярусами.

Шаг. 3. Если для перехода и,- выполняется условие Г ' (п-^ п Г ~ (п^ т* 0 для любого >у, принадлежащего предшествующему ярусу, то перейти к шагу 9.

Шаг 4. Если для перехода и,- выполняется условие Г ' (п,) п Г * (п^ & 0 для любого п], принадлежащего предшествующему ярусу, то перейти к шагу 9.

Шаг 5. Если для перехода я,- выполняется условие Г~(п,) пГ + (п,) ^ 0для любого п¡, принадлежащего предыдущему ярусу, то перейти к шагу 9.

Шаг б. Исключить переход n¡ с яруса, к которому он принадлежал £2к •= £2к I и,. Включить переход и; на предыдущий ярус Ок.] = Ок-\ и "/•

Шаг 7. Если ярус, на котором находился переход щ, пуст (Д. = 0), то уи = / +1, |ЛТ| выполнить операцию переноса перехода на предыдущий уровень

■Ос*0'-0~1 =^к*(]Ч)-1 и Пц.

Шаг 8. Перейти к шагу 3.

Шаг 9. Увеличить г (1 — / +1). Если г > \Щ, то перейти к шагу 10, иначе перейти к шагу 3.

Шаг 10. Конец.

При оценки уровня распараллеливаемости приведен ряд величин, важнейшими из которых являются ширина и высота ЯПФ ГПД.

Определение 23. Шириной ЯПФ ГПД, называется максимальная ширина из значений ширины ярусов, входящих в ГПД. /? = шах Д.

Определение 24. Высотой ЯПФ ГПД называется число ярусов, входящих в ЯПФ ГПД. 1/ = \П\.

Для выявления уровня распараллеливаемое™ ПО на реальной ЭВМ предложен алгоритм перестроения ГПД в ЯПФ при заданном количестве процессоров.

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

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

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

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

Второй этап проетегировапия заключается в задании смысловых свойств всем вершинам блок-схемы. Так для вершин, соответствующих операторам IF ... THEN, IF ...THEN ... ELSE, WHILE ... DO, REPEAT ... UNTIL, задаются логические условия, которые будут проверяться при выполнении оператора. Для операторов присваивания задаются операнды и последовательность арифметических операций, выполняемых над операндами. Для оператора цикла FOR ... ТО ... DO задаются пределы изменения переменной цикла.

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

После выполнения двух первых этапов проектирования создается полная блок-схема исполняемой части программы, по которой производится автоматическая генерация текста программы.

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

Второй метод проектирования предназначен для проектирован!« многомодульных, объектно-ориентированных программ. Поэтому основным элементом проектирования при создании обьектно-ориентированных программ является структура классов. По свойству наследования структура классов представима деревом, поэтому для ее проектирования используют расширенное дерево классов, вершинами которого могут являться классы, поля, методы, Паскаль-модули, данные. Для задания связей между Паскаль-модулями используется схема Паскаль-модулей. Для генерации исполнительных частей методов классов можно применять как традиционные средства (текстовые редакторы), так и предложенный метод проектирования по блок-схеме.

Этапы проектирования ПО многомодульных, объектно-ориентированных программ приведены на рис. 2.

В главе кратко изложен метод проектирования ПО для распределенных СРВ. Данный метод опирается на представление ПО с помощью ГПД.

1. Построение расширенного дерева классов.

2. Построение схемы Паскаль-модулей из вершин, содержащихся в дереве.

3. Проектирование связей между Паскаль-модулями.

4. Проверка правильности построения схемы Паскаль-модулей.

11. Работа с программой традиционными средствами (редактирование, трансляция, компиляция, тестирование).

Рис. 2. Схема этапов проектирования объектно-ориентированных программ.

Необходимо заметить, что проектирование и моделирование программ для распределенных СРВ является отдельной научной проблемой и подробное решение этих задач не рассматривается в данной работе.

В главе также описаны инструментальные средства, реализующие предложенные методы.

«Томограф Паскаль-программ» предназначен для анализа теста Паскаль-ярограмм и представления их в структурно-графической форме: дерева типов

данных, дерева процедур и функций, дерева структурных операторов, схемы Паскаль-модулей, дерева классов, блок-схем, ГПД, а также, для перестроения ~ПД вЯПФ.

Система визуального проектирования программ (СВиПП) предназначена тля проектирования программ по структурно-графическому представлению: меширенному дереву классов, схеме Паскаль-модулей, блок-схемам.

Программы «Томографа Паскаль-программ» и системы СВиПП созданы тля IBM-совместимых ЭВМ с операционными системами Windows 95, Win-lows NT в среде разработки профессиональных приложений Delphi 3.0. Общий >бъем разработанного ПО на языке Паскаль составляет 16000 операторов.

Основные результаты работы

Диссертационная работа посвящена созданию методов проектирования и щепки качества 110 на основе структурно-графических представлений. Полу-[сны следу ющие основные научные и практические результаты'

• Разработан способ представления ПО в структурно-графическом виде, а [.менно, в виде, ограниченного дерева модулей, дерева процедур и функций, ерева данных, дерева классов, дерева структурных операторов, блок-схемы и рафа потока данных;

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

• Разработана иерархическая система критериев оценки качества ПО с по-ющыо полу ченных структурно-графических представлений;

. Предложен ряд правил улучшения качества программ путем улучшения ачества по некоторым критериям;

• Предложена методология проектирования программ по их структурно-рафическому представлению. Основное внимание уделено проектированию бъектно-ориентированных программ;

. Создан ряд ИС: «Томограф Паскаль-программ», система СВиПП, ИС для эздания модели ПО на распределенной СРВ. Разработанное ПО функциониру-г на IBM PC/AT совместимых ЭВМ в операционных средах Windows 95, Win-dws NT. Общий объем разработанных программных комплексов составляет олее 16000 операторов.

Полученные результаты могут служить основой для проведения НИР в на-равлении создания CASE-технологии разработки ПО, включающей предло-енную технологию проектирования ПО в качестве основной части.

Основные публикации по теме диссертации

1. Погребной В. К., Демин А. 10., Погребной Д. В. Томография и структурно-графическое представление программ. // В научно-техническом сборнике: Математическое и программное обеспечение САПР. Выпуск 1. Под ред. В. К. Погребного. -Томск: изд. Томского политехнического университета, 1997. - с. 816.

2. Погребной В. К., Демин А. Ю., Погребной Д. В. Организация параллельного выполнения программ на основе их структурно-графических представлений. // В научно-техническом сборнике: Математическое и программное обеспечение САПР. Выпуск 1. Под ред. В. К. Погребного. - Томск: изд. Томского политехнического университета, 1997,- с. 36-39.

3.Демин А. Ю. Трансляция алгебраических выражений в системе ТРАНС-ВИР. // В научно-техническом сборнике: Математическое и программное обеспечение САПР. Выпуск 1. Под ред. В. К. Погребного. - Томск: изд. Томского политехнического университета, 1997. - с. 54-60.

4. Демин А. Ю. Метод распараллеливания алгоритмов при проектировании СРВ. // В трудах Международной научно-технической конференции «Научные основы высоких технологий». Т. 2. Идентификация, измерение характеристик и имитация случайных сигналов (модели, алгоритмы, аппаратно-программное и метрологическое обеспечение). - Новосибирск: изд. Новосибирского государственного технического университета, 1997. - с. 192-196.

5.Демин А. Ю. Модели представления алгоритмов при проектировании СРВ. // В сборнике тезисов докладов Международной научно-технической конференции «VIII Бенардосовские чтения». Иваново: изд. Ивановского государственного энергетического университета, 4-6 июня 1997. - с. 89-89.

6. Демин А. Ю. Метод представления и анализ алгоритмов при проектировании АСУ ТП. // В сборнике тезисов докладов Второй региональной научно-технической конференции студентов и молодых специалистов «Радиотехнические и информационные системы и устройства». Томск: издательство Томского государственного университета систем управления и радиоэлектроники, 20-22 мая 1997. с. 72-74.

1 .Демин А. Ю. Изучение структурных свойств программ на основе их графического представления. // В сборнике трудов Международной научно-технической конференции «Новые информационные технологии в университетском образовании». Новосибирск, изд. НИИ МИОО НГУ, 1998. с. 101-101.

8. Демин А. Ю. Синтез объектно-ориентированных программ на основе их структурно-графических представления. // В сборнике трудов Международной научно-технической конференции «Новые информационные технологии в университетском образовании». Новосибирск, изд. НИИ МИОО НГУ, 1998. с. 102102.

9. Demin A. Yu. Technology of program designing on the basis of structural-graphic representation. // In abstracts the second Russian-Korean int. symp. on Sei. and Tech.. Tomsk, 1998. c. 238-238.

ВВЕДЕНИЕ.

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ И ПРОБЛЕМЫ

ПРОЕКТИРОВАНИЯ ПО НА ОСНОВЕ СТРУКТУРНЫХ ПРЕДСТАВЛЕНИЙ.

1.1. Проблемы и особенности автоматизации проектирования ПО.

1.1.1. Необходимость представления алгоритмов в виде программ.

1.1.2. Система языков программирования.

1.1.3. Подходы при автоматизации проектирования ПО.

1.2. Формальные способы представления алгоритмов.

1.2.1. Исследование алгоритмов с помощью вычислимых функций и конечных автоматов.

1.2.2. Динамические модели программ.

1.2.3. Модели представления структуры ПО.

1.3. Распараллеливание алгоритмов.

1.3.1. Методы статического распараллеливания.

1.3.2. Теоретико-графовый подход к . распараллеливанию последовательных алгоритмов.

1.3.3. Распараллеливание программ методом последовательного углубления.

1.3.4. Методы распараллеливания циклических структур.

1.3.5. Распараллеливание операций линейного участка.

1.3.6. Методы распараллеливания внутри линейных участков.

1.3.7. Оптимальное распараллеливание алгоритмов.

1.3.8. Анализ методик распараллеливания алгоритмов.

1.4. Задачи исследования.

В настоящее время разработка любого программного обеспечения (ПО) не рассматривается без привлечения методов анализа структуры ПО и его структурного проектирования [5]. Успешное развитие вычислительной техники и операционных систем (ОС), особенно в направлении улучшения графических возможностей, позволило вести проектирование ПО на основе структурно-графического представления. Такое представление ПО улучшает такие свойства программ, как: понимаемость, эффективность, сопровождаемость и т. д. [2]. Так же на основе структурно-графического представления можно решать ряд задач, связанных с анализом свойств, распараллеливанием, оптимизацией ПО, а также подготовкой его к тестированию и т. д.

Многие ученые (В.Е. Котов, В.В. Липаев, A.A. Саркисян, Россия; L. Lamport, Ramamorthy, США и др.), ведущие исследования в этой области, отмечают недостаточную развитость традиционных подходов к созданию ПО [5,18].

В ряде работ они подчеркивают плохую проработанность теоретических основ и совокупности методов для проектирования ПО на основе представления его в виде графа, схемы, структуры и пр.

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

Основываясь на анализе современного состояния проблемы разработки высоконадежного и эффективного ПО на основе его структурно-графического представления, можно сделать вывод о том, что актуальность данной темы определяется: отсутствием высокоэффективных методов анализа ПО и представления его в структурно-графической форме; 5 недостаточной проработанностью методов анализа представления ПО и определения его свойств; отсутствием высокоэффективных методов синтеза ПО на основе его структурно-графического представления. Особенно это относится к ПО, созданного с помощью современной концепции объектно-ориентированного программирования (ООП); отсутствием набора инструментальных средств (ИС) поддержки разработки ПО на основе структурно-графического представления; отсутствием технологии проектирования ПО, основанного на таких методах и средствах.

Исследования и разработки по теме проводились в рамках ряда важнейших госбюджетных и хоздоговорных работ.

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

1. Развитие теоретических основ представления ПО в структурно-графическом виде.

2. Разработка методов анализа структурно-графического представления и оценки качества программ.

3. Разработка методов проектирования ПО на основе структурно-графического представления.

4. Создание инструментальных средств, предназначенных для реализации предложенных методов.

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

Апробация работы. Исследования и разработки проводились в Кибернетическом центре Томского политехнического университета в соответствии с утвержденными планами НИР в составе Государственной научно-технической 6 программе по информатизации высших учебных заведений России по теме «Разработка среды программирования Паскаль-программ на основе системы ТРАНСВИР» (в соответствии с договором № 8-03/95-(5 пит/95)) и в составе программы Университеты России по теме «Методы анализа и адаптации программ для выполнения на МВС в реальном масштабе времени».

Основные результаты работы докладывались и обсуждались на Международной научно-технической конференции «Научные основы высоких технологий» (г. Новосибирск, 1997 г.), на Международной научно-технической конференции «VIII Бенардосовские чтения» (г. Иваново, 1997 г.), на второй региональной научно-технической конференции студентов и молодых специалистов «Радиотехнические и информационные системы и устройства» (г. Томск, 1997 г.), на Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (г. Новосибирск, 1998 г.), на второй Российско-Корейской, международной конференции по науки и технологии KORUS 98 «Technology of program designing on the basis of structural-graphic representation» (г. Томск, 1998 г.). Инструментальные средства — система анализа и представления ПО в структурно-графическом виде «Томограф Паскаль-программ» официально зарегистрирована в Российском агентстве по правовой охране программ для ЭВМ, баз данных и топологии интегральных микросхем (РосАПО). «Томограф Паскаль-программ» получил сертификат соответствия № РОСС RU.ME20 .Н00087 в системе сертификации ГОСТ Р Госстандарта РФ.

Томограф Паскаль-программ» внедрен в НПЦ «Полюс», где использовался при разработке программ расчета и визуализации обмотки трансформаторов и программы тренажера для имитации работы системы преобразования и управления двигательной установкой ориентации, что подтверждено соответствующим актом внедрения. Система визуального проектирования программ (СВиПП) внедрена в КЦ ТПУ с 1997 в системе подготовки школьников стар7 ших классов по курсу «Информатика и вычислительная техника», что подтверждено соответствующим актом внедрения.

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

По результатам исследований опубликовано 9 работ, в том числе 4 статьи.

Личный вклад:

1. Основные идеи по представлению программ в структурно-графической форме принадлежат В.К. Погребному и лично автору.

2. Методы получения структурно-графического представления ПО из текста программ разработаны лично автором.

3. Разработка системы основных свойств программ, представленных в структурно-графическом виде, проведена В.К. Погребным и лично автором.

4. Методы оценки основных свойств программ и теоретическое обоснование возможности их использования получены лично автором.

5. Теоретические основы проектирования ПО для распределенных систем реального времени (СРВ) на основе структурно-графического представления разработаны В.К. Погребным и Д.В. Погребным.

6. Методы создания модели ПО для распределенных СРВ, представленных в виде графа потока данных (ГПД) разработаны лично автором.

7. Теоретическое обоснование и способы проектирования объектно-ориентированных программ на основе структурно-графического представления принадлежат лично автору.

8. Программные средства инструментальной системы анализа программ «Томограф Паскаль-программ» разработаны автором, за исключением создания части базовых классов графических примитивов, разработка которых принадлежит Д.В. Погребному.

9. Программные средства проектирования программ на основе их структурно-графического представления (система СВиПП) разработаны автором. 8

Краткое изложение основного содержания работы.

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

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

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

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

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

Формулируются цель и основные задачи, решаемые в диссертационной работе.

Во второй главе описывается совокупность представления программ в структурно-графической форме. 9

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

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

Подробно описан метод декомпозиции программы на отдельные фрагменты на основе представления в виде деревьев.

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

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

В третьей главе разработана иерархическая система критериев оценки качества программ по структурно-графическому представлению и даны их определения.

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

10

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

Рассмотрены методы оценки структурной сложности ПО. Описан способ оценки качества ПО по критерию связанности. Доказаны свойства эквивалентности и аддитивности предложенной оценки.

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

Предложен алгоритм перестроения графа потока данных в ярусно-параллельную форму при заданном количестве процессоров.

В четвертой главе рассматриваются методы, позволяющие на основе структурно-графического представления проектировать ПО. Вся излагаемая теория базируется на основе современных САБЕ-технологий, которые позволяют не только анализировать свойства модельного представления ПО, но также предусматривают, что модель может выступать как одно из средств проектирования ПО.

Разработан метод проектирования исполняемой части программы на основе блок-схемы.

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

Кратко изложен метод проектирования ПО для распределенных СРВ. Данный метод опирается на представление ПО с помощью ГПД. Необходимо заме

11 тить, что проектирование и моделирование программ для распределенных СРВ является отдельной научной проблемой и подробное решение этой проблемы не рассматривается в данной работе.

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

Описаны ИС анализа Паскаль-программ и представления их в структурно-графической форме - «Томограф Паскаль-программ». Приведена его структурная схема.

Подробно описаны ИС для проектирования многомодульных, объектно-ориентированных программ - система СВиПП.

Изложены принципы построения ИС для создания модели на основе ГПД. В работе решаются такие основные задачи проектирования ПО, как задачи декомпозиции; определения структуры ПО в целом и на всех иерархических уровнях; оценка качества ПО путем анализа основных структурных свойств; распараллеливания (преобразования алгоритмов к ярусно-параллельной форме); проектирования программ, строящихся на объектно-ориентированных принципах.

Научную новизну полученных в работе результатов определяют: . способ представления программ в структурно-графическом виде, а именно совокупность представления в виде взаимосвязанных деревьев, графа управляющих связей, графа информационных связей; методология анализа текста программ и получения их структурно-графического представления; система критериев оценки качества программ представленных в структурно-графической форме.

12 методология проектирования ПО на основе его структурно-графического представления; совокупность инструментальных средств, реализующих предложенные способы, методы и методики.

Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методики, методы, алгоритмы и инструментальные программные средства. Инструментальное ПО предназначено для работы на ПЭВМ типа IBM PC AT в ОС Windows NT, разработано с помощью интегрированной среды программирования Delphi 3.0. Суммарный объем разработанных программных комплексов составляет более 16000 операторов.

Разработанные ИС внедрены в учебный процесс на кафедре Автоматизации проектирования Томского политехнического университета при выполнении цикла лабораторных работ и курсового проекта по курсу «Автоматизированные системы проектирования систем реального времени», а также при работе со школьниками при проведении подготовительных занятий по курсу «Информатика и вычислительная техника», что подтверждено соответствующим актом о внедрении.

ИС - «Томограф Паскаль-программ» использовался при разработке программ расчета и визуализации обмотки трансформаторов и программы-тренажера для имитации работы системы преобразования и управления двигательной установкой ориентации в НПЦ «Полюс», что подтверждено соответствующим актом внедрения.

Основные положения, выносимые на защиту:

1. Структурно-графические представления в сравнении с текстовыми являются более удобными и понимаемыми при практическом анализе и синтезе программ как вручную, так и автоматическими методами.

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

13 моделей позволяют повысить уровень формализации при решении задач автоматизированного проектирования и анализа программ.

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

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

Автор выражает глубокую благодарность научному руководителю В.К. Погребному за большую помощь в подготовке диссертационной работы, ценные замечания и советы. Автор также выражает признательность Д.В. Погребному за ценные советы при программировании ИС.

14

1. СОВРЕМЕННОЕ СОСТОЯНИЕ И ПРОБЛЕМЫ ПРОЕКТИРОВАНИЯ

ПО НА ОСНОВЕ СТРУКТУРНЫХ ПРЕДСТАВЛЕНИЙ

4.4. Основные выводы по главе

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

2. Для проектирования многомодульных, объектно-ориентированных программ предложен метод, основанный на представлении ПО в виде расширенного дерева классов. Этот метод включает в себя метод проектирования по блок-схеме, который используется для создания тел методов.

142

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

4. На основе ГПД можно вести проектирование программных комплексов для распределенных СРВ.

5. Для анализа Паскаль-программ и представления их в структурно-графической форме создано ИС - «Томограф Паскаль-программ».

6. Для проектирования многомодульных, объектно-ориентированных программ создано ИС - система СВиПП.

7. Изложены принципы ИС, которые позволяют строить и задавать параметры моделям на основе ГПД.

143

ЗАКЛЮЧЕНИЕ

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

1. Разработан способ представления ПО в структурно-графическом виде, а именно, в виде: ограниченного дерева модулей, дерева процедур и функций, дерева данных, дерева классов, дерева структурных операторов, блок-схемы и графа потока данных.

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

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

4. Предложен ряд правил улучшения качества программ путем улучшения качества по некоторым критериям.

5. Предложена методология проектирования программ по их структурно-графическому представлению. Особый упор сделан на проектирование объектно-ориентированных программ.

6. Создан ряд ИС: «Томограф Паскаль-программ», система СВиПП, ИС для создания модели ПО на распределенной СРВ. Разработанное ПО функционирует на IBM PC/AT совместимых ЭВМ в операционных средах Windows 95, Windows NT. Общий объем разработанных программных комплексов составляет более 16000 операторов.

144

Полученные результаты могут служить основой для проведения НИР в направлении создания САБЕ-технологии разработки ПО, включающей предложенную технологию проектирования ПО в качестве основной части.

145

1. Кориков A.M., Сафьянова Е.Н. «Основы системного анализа и теория систем» учебное пособие Томск, 1989. / Под ред. д.т.н. Ф.П.Тарасенко. Издательство Томского университета.

2. Саркисян А. А. Повышение качества программ на основе автоматизированных методов. М.: Радио и связь.-160 с.

3. Вязгин В.А., Федоров В.В. Математические методы автоматизированного проектирования. -М.: Высш. шк., 1989. -183с.

4. Кнут, Дональд Э. Искусство программирования для ЭВМ: В 7-ми т.: Пер. с англ./ Д. Кнут. — М.: «Мир», 1976. Т.1: Основные алгоритмы/ Пер. Г. П. Бабенко и Ю. М. Баяковского: Под ред. К. И. Бабенко и В. С. Штаркмана.-1976. 735с.

5. Технология проектирования комплексов программ АСУ. /В.В. Липаев, Л.А. Серебровский, П.Г. Гаганов и др.; Под ред. Ю.В. Астафьева, В.В. Липаева- М.: Радио и связь, 1983. 264 с.

6. Йодан Э. Структурное программирование и конструирование программ: Пер. с англ./ Под ред. П.Н. Королева -М.: Мир, 1979. -416 с.

7. Жоголев Е.А. Технологические основы модульного программирования. -Программирование, 1980, № 2, с. 44-49.

8. Хьюз Дж., Мичтон Дж. Структурный подход к программированию: Пер. с англ. /М.: Мир, 1960. -278 с.

9. Stay J.E. Hypo and integrated program design. -IBM System J., 1976, № 2, p. 143154.

10. Fudji M.S. Independent verification of highly reliable programs COMPSAC 77. -Proc/IEEE Comput., Soc., I Int. Comput. Software and Appl. Conf., Chicago, 1977, New York, № 9, 1977, p. 38-44.

11. Ramamorthy ett al. On the automated generation of program test data. -IEEE Trans. 1976, v. SE -2, № 4, p. 78-92.146

12. Ершов А.П. Технология разработки систем программирования. -В кн.: Системное и теоретическое программирование /ВЦ СО АН СССР, Новосибирск, 1972, с. 136-184.

13. Мамиконов А.Г., Цвиркун А.Д., Кульба В.В. Автоматизация проектирования АСУ. -М.: Энергия, 1981. -328 с.

14. Мессих И.Г., Собкин С.С., Штрик А.А. Методы автоматического анализа характеристик комплексов программ и распределение ресурсов производительности вычислительных систем. -Управляющие системы и машины. 1980, № 1, с. 28-32.

15. Мультипроцессорные системы и вычисления: Пер. с англ. /Под ред. Ф.Г. Энслау -М.: Мир, 1976. -384 с.

16. Штрик А.А. Производительность однородных многопроцессорных комплексов с общей памятью. Управление системы и машины. 1978, № 3, с.55-61.

17. Биэкман М. Проектирование систем реального времени: Пер. с англ. /М.: Мир, 1977. 345 с.

18. Липаев В.В. Проектирование программных средств: Учеб. пособие для вузов по специальности «Автоматические системы обработки информации и управление»-М.: Высш. шк., 1990. -303 с.

19. Грицык В.В. Распараллеливание алгоритмов обработки информации в системах реального времени. Киев: Наук, думка, 1981. -215 с.

20. Грис Д. Наука программирования: Пер. с англ. /Под. Ред. А.П. Ершова. -М.: мир, 1984.-416 с.

21. Дейкстра Э. Дисциплина программирования: Пер. с англ. /Под. ред. Э.З. Любимского. -М.: Мир, 1976. -288 с.

22. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов. -М.: Радио и связь, 1983. -272 с.

23. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. -М.: Наука, 1981. -256 с.147

24. Янг Ч. Алгоритмические языки реального времени. Конструирование и разработка: Пер. с англ. /Под ред. В.В. Мартынюка: -М.: Мир, 1985. -400 с.

25. Холстед М.Х. Начала науки о программировании: Пер. с англ. -М.: Финансы и статистика, 1981.-128 с.

26. Гонца М.Г. Что такое технология программирования. -Кишинев, издательство Штиинда, 1989. -67 с.

27. Вирт Н. Систематическое программирование. Введение. -М.: Мир, 1977. -183 с.

28. Дал У., Дейкстра Э., Хоор К. Структурное программирование. -М.: Мир,1975. -248 с.

29. Вельбицкий И.В. Р-технология программирования. -Киев: Наукова думка,1976. -279с.

30. Сборочное программирование /Лаврищева Е.М., Грищенко В.М.: Отв. Ред. Андон Ф.И.: АН Украины. Институт кибернетики им. В.Н. Глушкова. -Киев: Наукова думка, 1991. -216 с.

31. Редько В.Н. Композиционная технология программирования. -Киев: Издательство общества «Знание», 1981.

32. Ершов А.П. Опыт интегрального подхода к актуальной проблематике программного обеспечения //Кибернетика -1984. -№ 3 с. 11-21.

33. Льюс Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. Пер. с англ. В. А. Исаева и др.; Под ред. В. Н. Агафонова. -М.: Мир, 1979. -644 с.

34. Гласс Р. Руководство по надежному программированию: Пер. с англ. /Под ред. В.М. Рабиновича. -М.: мир, 1982. -256 с.

35. Характеристики качества программного обеспечения /Б. Боэм, Дж. Браун, X. Каспар и др.; Пер. с англ. Е.К. Масловского. -М.: Мир, 1981. -208 с.

36. Зиглер К. Методы проектирования программных систем: Пер. с англ. /Под ред. Я.А. Хетагурова-М.: Мир, 1985. -328 с.148

37. Cottrel J., Workman D. GRASP: An Interactive Environment for Software Development and Maintenance //DataBase. -1980. -Vol.11, № 3, p.84-87.

38. Davcev D. Some New Observations About Software. Sci. Indications For Estimating Software Quality //Information Processing and Management, 1984, -Vol.20, № 1-2. -p.245-247.

39. Безбородов Ю.М. Индивидуальная отладка программы. -М.: Наука, 1982. -192 с.

40. Ван Гассел Д. Стиль, разработка, эффективность, отладка и испытание программ: Пер. с англ. /Под ред. Э.А. Трахтенгерца. -М.: Мир, 1981.-319 с.

41. Майерс Г. Искусство тестирования программ: Пер. с англ. /Под ред. Б.А. Позина. -М.: Мир, 1982. -176 с.

42. Arthur I. Software Quality Measurement of Datamation. -1984. -Vol.30, № 21. -p.l 15-120.

43. Саркисян А.А. Машинонезависимая оптимизация исходных программ. -М: Радио и связь, 1985. -208 с.

44. Тыугу Э.Х. Концептуальное программирование. -М.: Наука, 1984. -344 с.

45. Казро М.И. Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). -М.: Финансы и статистика, 1981. -157 с.

46. Лавров С.С. Синтез программ//Кибернетика. -1982. № 6 -с. 11-16.

47. Камынин С. С., Любимский Э.З. Алгоритмический машинно-ориентированный язык -АЛМО //Алгоритмы и алгоритмические языки. -1967. -Вып. 1. —с. 5-58.

48. Хорн Э., Винклер Ф. Проектирование модульных программных структур /Вычислительная техника соц. стран. -1987. -Вып. 21. -с.64-72.

49. Фишер П. Братиславская программная система BPS //Вычислительная техника соц. Стран. -1984. -Вып. 15 -с.62-69.

50. Бутаков Е.А. Методы создания качественного программного обеспечения ЭВМ. -М.: Энергостоииздат, 1994. -232 е., ил.

51. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. -М.: Мир, 1985.149

52. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. -Новосибирск: Наука, 1966. -308 с.

53. Колмогоров А.Н., Успенский В.А. К определению алгоритма. -УМН, 1958, 13, № 4, с. 3-28.

54. Марков А.А. Теория алгоритмов. -Труды математического института АН СССР-им. В. А. Стеклова, 42, М.: Изд-во АН СССР, 1954.

55. Kleene S.C. General recursive functions of natural numbers. -Math. Ann., 1936, 112, p. 727-742.

56. Church A. An unsolvable problem of elementary number theory. Amer. J.Math., 1936, 58, p.345-363.

57. Post E.L. Finite combinatory processes formulation 1. -J. Symbolic Logic, 1936, 1. P.103-105.

58. Русский перевод: Пост Э. Конечные комбинаторные процессы формулировка 1. - В кн.: Успенский В.А. Машина Поста. М.: Наука, 1979, с.89-95.

59. Turing A.M. On computable numbers with an application to the Entscheidungsproblem. -Proc. London Math. Soc. (2), 1937, 42., p.230-265. Correction/ -Proc. London Math. Soc.(2), 1947, 43, p.544-546.

60. Программирование и алгоритмические языки. / Н. А. Криницкий, Г. А. Миронов, Г. Д. Фролов; Под ред. А. А. Дородницина. -2-е изд. Перераб. и доп. -М.: Наука, 1979, 509 с.

61. Котов В.Е. Теория параллельного программирования : Прикл. Аспекты. -Кибернетика, 1974, № 1, с 1 16.

62. Котов В.Е. Теория параллельного программирования : Прикл. Аспекты. -Кибернетика, 1974, № 2, с 1 18.

63. Головкин Б. А. Параллельная обработка информации: Программир., вычисл. методы, вычисл. системы. Техн. Кибернетика, 1979, №2, с. 116-151.

64. Головкин Б. А. Методы и средства параллельной обработки информации. В кн.: Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М. : Наука, 1979, с. 85- 193 - (Итоги науки и техники. Т. 17).150

65. Поспелов Д. А. Введение в теорию вычислительных систем. М. : Сов. Радио, 1972,-280 с.

66. Халимов А. И. К вопросу о распараллеливании программ. -Пробл. Кибернетики, 1974, №28, с. 157-176.

67. Халимов А. И. Метод последовательного углубления и некоторые его приложения. В кн.: Теория и практика системного программирования. Киев : Инт кибернетики АН УССР, 1976, с. 180-192.

68. Халимов А. И. Распараллеливание арифметических выражений методом последовательного углубления. Программирование, 1979, № 2, с. 48 -54.

69. Белкина М. В., Трахтенгерц Э. А. О выделении модулей в системе программ. Автоматика и телемеханик, 1977, №7, с. 192-196.

70. Беляков М. И., Натансон Л. Г. Распараллеливание циклов и другие оптимизирующие преобразования транслируемых программ. Программирование, 1975, №4, с. 45-50.

71. Бусленко Н. П. Автоматизация имитационного моделирования сложных систем. М. : Наука, 1976. - 175 с.

72. Косарев Ю.Г. Распараллеливание по циклам. Вычисл. системы, 1967, № 24, с. 3-20.

73. Миренков Н. Н, Структурное параллельное программирование. Программирование, 1975, № 3, с. 3-14.

74. Миренков Н. Н, Симонов С. А., Выявление параллелизма в циклах методом имитации их выполнения. Кибернетика, 1981, № 3, с. 28-33.

75. Нариньяни А. С. Теория параллельного программирования. Формальные модели. Кибернетика, 1974, № 4, с. 1-15.151

76. Нариньяни А. С. Теория параллельного программирования. Формальные модели. Кибернетика, 1974, № 5, с. 1-14.

77. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М. : Наука, 1981,- 254с.

78. Форд JI. Р., Фалкерсон Д. Р. Потоки в сетях. М. : Мир, 1966,- 272 с.

79. Нуриев Н. М. Информационно логические связи в схемах программ над массивами. - Кибернетика, 1979, № 1, с. 78-86.

80. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под. Ред. В. Е. Котова, И. Маклашко,- М. : Наука, 1982,-212 с.

81. Вальковсий В. А., Котов В. Е. Автоматическое построение параллельных программ. Распараллеливание выражений и циклов. Новосибирск, 1979.- 40 с. (Препринт / АН СССР, Вычислю центр Сиб. отд-ния ; № 146).

82. Martin D. F., Estrin G. Models of computations and systems-evalution of vertex probabilities in graph models of computations.- Joum. ACM? 1967, 14, № 2, p. 281299.

83. Squir I. S. A translation algorithm for a multiple Processor Computer.- Proc. 18 th ACM Nat. Conf. Colorado : Denver, 1963, P. 174-191.

84. Di Manso M., Frisiani A. L., Olimpo G. Loop optimisation for parallel proce-sing.- Computer Journ., 1981, 22, № 3, p. 184-189.

85. Hellerman H. Parallel processing of Algebraic Expressions.- IEEE Trans, on Electronic Computers, EC-15, № 1, January, 1966, p. 82-91.

86. Stone. One-pass compilation of arithmetic expressions for a parallel processor.-Communic. ACM, 1967, 10, № 4, p. 215-223.

87. Ramamoorthy С. V., Gonzalez M. J. A survey of techniques for recognizing parallel programs. Proc. FICC AFIPS, USA, 1969, 35, p. 1-15.

88. Распараллеливание алгоритмов обработки информации. Том 1 / Под ред. А. Н. Свенсона, Киев : Наук. Думка, 1985.- 280 с.152

89. Гантер Р. Методы управления проектированием программного обеспечения: Пер. с англ. -М.: Мир, 1981.-392 с.

90. Грицык В. В. Деркач Б. Т. Алгоритмы распараллеливания обработки информации Львов, 1979,- 50 е.- (Препринт / АН УССР. Физ. мех. ин-т.; № 24).

91. Грицык В. В. Деркач Б. Т. Математическая модель задачи управления вершин графов. В кн.: Эффективность распараллеливания алгоритмов обработки информации. Львов, 1979, с. 56-57 - (Препринт / АН УССР. Физ. мех. ин-т.; № 15).

92. Грицык В. В. Деркач Б. Т. Оптимальные ЯПФ при распараллеливании линейных алгоритмов. В кн.: Эффективность распараллеливания алгоритмов обработки информации. Львов, 1979, с. 32-35 - (Препринт / АН УССР. Физ. мех. ин-т.; №15).

93. Пашкевич с. Д. Основы мультипрограммирования для специализированных вычислительных систем. М. : Сов. радио, 1972,-183 с.

94. Мерилл Т. Вычислительные цепи и упрощение машинных программ. Экс-пресс-информ. Сер. Вычисл. техника, 1963, № 1, с. 14-30.

95. Котов В. Е. Введение в теорию схем программ .- Новосибирск : Наука, 1978,-257 с.

96. Андерсон Б.Д. Основания теории систем, конечные и неконечные условия.-В кн.: Математические методы в теории систем. М. : Мир, 1979, с. 49-133.

97. Биркгоф Г., Барти Т. Современная прикладная алгебра. М. : Мир, 1976. -400 с.

98. Бусленко Н. П., Калашников В.В., Коваленко И. Н. Лекции по теории сложных систем. М. : Сов. радио, 1973.- 439 с.

99. Нечипоренко В. И. Структурный анализ систем (эффективность и надежность).- М. : Сов. радио, 1977,- 214 с.

100. Клини С. Введение в математику. -М. : Изд-во иностр. лит., 1957. 526 с.153

101. Колесник А. М. Преобразования и распараллеливание операторов цикла Алгол 60,- Минск, 1980.- 36 е.- (Препринт / АН БССР. Ин-т математики; № 4 (84)).

102. Петер Р. Рекурсивные функции / под ред. А. Н. Колмогорова. М. : Изд-во иностр. лит., 1954. - 264 с.104. "Гришина Е.В. Разрешимость функциональной эквивалентности на подклассе схем потоков данных. -Новосибирск: ВЦ СО АН СССР, 1982. —43 с.

103. Орлов В. А. Теория графов и комбинаторика. Учебное пособие. Томск. Изд. ТПУ им. С.М. Кирова, 1988. -96 с.

104. Сваами М., Тхуласирамин К. Графы, сети и алгоритмы: Пер. с англ. /Под ред. В.А. Горбатова. -М.: Мир, 1984. -455 с.

105. Характеристики качества программного обеспечения /Б.Боэм, Дж.Браун, Х.Каспар и др. Пер. с англ. Е.К. Масловского. -М: Мир, 1981. -208 с.

106. Технология проектирования комплексов программ АСУ /В.В. Липаев, Л. А. Серебровский, П.Г. Гаганов и др. /Под ред. Ю.В. Асафьева, В.В. Липаева. -М.: Радио и связь, 1983. -264 с.

107. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. -М.: Мир, 1985. -406 с. ил.

108. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. -М.: Радио и связь, 190ю -256 с.

109. Воеводин В.В. Математические модели и методы в параллельных процессах. -М.: Наука. Гл. ред. физ.-мат. Лит., 1986. -296 с.

110. Погребной В. К. Автоматизированное проектирование систем реального времени. Учебное пособие. Томск, изд. ТПИ, 1989. -96 с.

111. Научно-производственный центр1. ПОЛЮС"

112. М 634050, г.Томск, пл.Кирова 2, НПЦ "Полюс" Тел./факс (382-2) 44-77-66 / 44-51-91, телетайп ТОМСК 128173 "Курс" E-mail: POLUS@ONLINE.TOMSK.NET1. СХ. №на№от1. УТВЕРЖДАЮ»

113. Зам. Генерального директора1. НПЦ «Полюс»

114. Ю. А. Шиняков «/Н ¿>? 1998 г.о внедрении НИОКР

115. Рекомендуем использовать «Томограф Паскаль-программ» при разработке программного обеспечения на языке Паскаль, для просмотра и анализа структуры программы.

116. Начальник лаборатории №381 Начальник КБ № 64