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

УДК 004 4'2

На правах рукописй

Болонкин Андрей Владимирович

РАЗРАБОТКА ДИАГРАММНО-СЕТЕВОГО МЕТОДА СИНТЕЗА СТРУКТУР ИНТЕРАКТИВНЫХ СИСТЕМ

Специальность 05 13 11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

АВТОРЕФЕРАТ

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

п " ДПР 2008

Москва —

2008

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

Научный руководитель' доктор технических наук, профессор

Артамонов Евгений Иванович

Официальное оппоненты: доктор технических наук, профессор

Амбарцумян Александр Артемович

доктор технических наук, профессор Хачумов Вячеслав Михайлович

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

Московский Энергетический Институт (Технический университет)

Защита диссертации состоится 21 апреля 2008 г в 11 часов на заседании Диссертационного совета Д 002 226 03

при Институте проблем управления им В А Трапезникова РАН по адресу 117997, Москв.а, ул Профсоюзная, д 65, малый конференц-зал (МКЗ)

С диссертацией можно ознакомиться в библиотеке ИПУ РАН

Отзывы по автореферату в двух экземплярах, заверенные печатью, про.сьба направлять по адресу 117997, Москва, ул Профсоюзная, д 65, ученому секретарю Диссертационного совета Д 002 226 03 Юркевичу Е В

Автореферат разослан 20 марта 2008 г

Ученый секретарь Диссертационного совета д т н , проф

Е В Юркевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования

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

Значительный вклад в решение проблем проектирования программных систем (в т ч ИС) внесли Г Буч (G Booch), Б Боэм (В W Boehm), П Коуд (Р Coad) и Э Йордон (Е Yourdon), известны работы Г Сторрле (Н Storrle), У ван дер Аальста (W van der Aalst) В отечественной науке проблемы синтеза структур систем рассмотрены в работах Е И Артамонова, В В Кульбы, В В Липаева, А Д Цвиркуна, А А Шалыто, С А Юдицкого

В последние десятилетия активно появляются и развиваются новые технологии, поэтому проблема синтеза структур ИС становится все более актуальной Кроме того, в связи с расширением области применения ИС и их внедрением в различных сферах деятельности человека возрастает потребность в более быстром и качественном проектировании таких систем Цель работы

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

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

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

1 Исследование механизмов построения сложных ИС, современных методов их проектирования и проблем, возникающих при проектировании

2 Разработка и формализация нового метода синтеза структур ИС, позволяющего оптимизировать процесс генерации структур на основе диаграммного представления, определение возможных перспектив его использования и развития

3 Создание инструментальных средств, позволяющих проектировать сложные ИС на основе разработанного диаграммно-сетевого метода синтеза

4 Апробация разработанного диаграммно-сетевого метода синтеза и инструментальных средств проектирования

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

Научная новизна работы

1 Впервые для данного рода задач на основе UML, IDEF0 и сетей Петри разработаны структурные модели ИС, позволяющие отобразить и систематизировать варианты их структур

2 Разработаны механизмы систематизации вариантов структур ИС на основе графовых моделей с учетом полноты перебора вариантов

3 Сформулирован способ многокритериальной оценки вариантов структур ИС на основе нечеткой А-меры с учетом взаимосвязей критериев

4 Разработан и автоматизирован при помощи инструментальных средств диаграммно-сетевой метод синтеза структур ИС, включающий в себя построение структурной модели в виде диаграмм деятельности, систематизацию вариантов структуры ИС и выбор наилучших вариантов на основе многокритериальной оценки

Практическая значимость

1 На основе разработанного метода синтеза созданы инструментальные средства для автоматизации проектирования структур ИС

2 Представленные в диссертации результаты использованы для научно обоснованного построения структур ИС и поиска их наилучших вариантов в ряде проектов

• при создании системы реконструкции объемных геометрических моделей кровеносных сосудов по набору растровых ангиограмм,

• при разработке программных средств «Клиент системы учета рабочего времени» и «Синхронизатор КУС — MS Project» в ЗАО «Компания Безопасность»

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

Результаты, выносимые на защиту.

• Модели представления структур ИС, основанные на графической нотации диаграмм деятельности UML, предоставляющие возможности отображения и систематизации вариантов структур

• Диаграммно-сетевой метод синтеза структур ИС, позволяющий генерировать варианты структур систем и производить выбор наилучшего из них на основе многокритериальной оценки

• Алгоритмы и программная реализация инструментальных средств для автоматизации анализа и синтеза структур систем

Реализация результатов работы

Полученные в диссертации результаты и программное обеспечение были применены в ЗАО «Компания Безопасность» при разработке программных средств «Клиент системы учета рабочего времени» и «Синхронизатор КУС — MS Project» (подтверждено актами о внедрении)

Апробация работы

Положения диссертационной работы докладывались и обсуждались на IV, V, VI и VII международных конференциях «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта CAD/CAM/PDM» (Москва ИПУ РАН, 2004, 2005, 2006, 2007), Всероссийской научно-практической конференции с международным участием «Современная кардиология наука и практика» (СПб СПбГМА, 2007), XXXIV международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07» (Гурзуф 2007), XV международной конференции «Новые информационные технологии в медицине, биологии, фармакологии и экологии 1Т+М&Ес'07» (Гурзуф 2007)

Публикации

Основные результаты работы опубликованы в 12 печатных работах, из которых 2 статьи (среди них 2 статьи по списку ВАК)

СОДЕРЖАНИЕ РАБОТЫ

Структура и объем работы Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложений Общий объем диссертации составляет 165 с , основного текста — 142 с , включая 43 рисунка и 31 таблицу Список литературы состоит из 79 наименований

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

В первой главе рассмотрены основные понятия проектирования и моделирования ИС, приведены классификации ИС с точки зрения области применения и с точки зрения связи с внешними устройствами Рассмотрены вопросы качества ПО, способы и критерии его оценки (стандарты ISO/IEC 9126 2001, ISO/IEC 14598) Отдельно выделено понятие структуры программной системы и связь структуры системы с ее качеством Рассмотрены принципы построения структуры программных систем на основе оценки компонентов систем (Артамонов, 1991, 2004, Кульба, 1994, 2006, Ли-паев, 2001, 2002, Цвиркун, 1982) Проведен обзор методов моделирования программных систем, среди которых выделен неформальный (Flow-charts, DFD, IDEF-SADT, ЕРС, UML, SysML) и формальный подход (теории множеств и графов, конечные автоматы, сети Петри, формальные спецификации)

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

Формальные методы основаны на использовании тех или иных математических абстракций, что позволяет проводить доказательства и вывод различных свойств системы на основе математических свойств используемых абстракций Отдельно выделены высокоуровневые сети Петри, предоставляющие возможность детального моделирования системы, декомпозиции ее структуры, выявления свойств структуры системы на основе строгих математических формализмов В то же время, формальные методы обладают малой степенью наглядности, поэтому актуально объединение формального и неформального подхода в едином методе синтеза структур программных систем Известны работы на стыке этих подходов (Storrle, 2004, Campos, 2006), но описанные в них методы требуют развития и доработки

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

Во второй главе разработан метод синтеза структур ИС, отличающийся одновременным применением формального и неформального подходов, детальным учетом свойств объектов информации ИС, использованием стандартной нотации диаграмм деятельности UML для отображения алгоритма функционирования ИС и многокритериальной оценки параметров ИС для выбора ее наилучшей структуры

Сформулированы механизмы построения структур ИС описание алгоритма функционирования с помощью диаграмм деятельности, выделение локальных алгоритмов и локальных структур алгоритмов, декомпозиция, генерация вариантов структуры ИС, выбор наилучшего из них Под локальным алгоритмом (JIA) понимается сильно связная часть общего алгоритма функционирования системы с последовательным выполнением операций над данными, представленными с одинаковой точностью и одним способом кодирования Каждому ЛА соответствует набор блоков — локальных структур (ЛС), которые реализуют JIA с различными характеристиками и показателями качества Вариант структуры представляет собой множество способов организации структуры рассматриваемой ИС, отличающихся применяемыми ЛС, их последовательностью, а также взаимосвязями и характеристиками составляющих операций Синтез структур ИС предлагается проводить при помощи генерации различных вариантов структуры на основе альтернатив, заданных на диаграммах деятельности, оценки каждого варианта и последующем выборе наилучшего из них

Для оценки вариантов структуры предлагается применять многокритериальную оценку в совокупности с методологией исследования пространства вариантов (Design Space Exploration — DSE), определяющей понятия меры, метрики и критериев качества Выбраны метрики ПО, описывающие характеристики ЛС К ним относятся метрики сложности алгоритма (цикломати-ческая сложность, сложность вызовов, GOTO-сложность, глубина вложенности условных операторов), метрики сложности структур данных (количество используемых типов данных, переменных, объем используемой оперативной памяти), метрики объема исходного кода (различные способы подсчета числа строк исходного кода), метрики ресурсов (загруженность процессора, объем требуемого дискового пространства, время выполнения)

Многокритериальную оценку вариантов структуры ИС предлагается проводить на основе понятия нечеткой А-меры и дискретного интеграла Шоке В качестве способа задания нечеткой А-меры предлагается способ, основанный на числе входов Применение этих методов позволяет не только объединить разнотипные критерии, но проводить оценку вариантов структуры ИС в случае, когда одни критерии оценки влияют на другие

Каждый вариант структуры будем рассматривать как альтернативу Обозначим конечное множество альтернатив Т, а конечное множество критериев оценки X = , , хп} Каждая альтернатива а е Т ассоциирована с набором характеристик ха = (х", ,х£) G R", где для любого г е X

х" обозначает частичную оценку а с точки зрения критерия г

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

Этап анализа подразделяется на 5 шагов

1) Формулирование целей и требований к системе

Цели и требования описываются в произвольной текстовой форме, при этом каждое требование представляется в виде отдельного пункта для упрощения дальнейшей формализации Требования должны быть направлены на достижение целей

2) Составление списков характеристик и критериев оценки системы

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

Далее на основе требований, определенных на шаге 1, и характеристик задаются критерии оценки системы (т е признаки, с помощью которых производится оценка качества) Каждый критерий представляет собой связку следующих элементов характеристика, тип критерия, нижняя и верхняя граница Тип определяет поведение критерия минимизация, максимизация, равенство, принадлежность отрезку «Равенство» задает требование равенства нижней границе (верхняя граница при этом не рассматривается) «Принадлежность отрезку» задает требование принадлежности отрезку, определенному нижней и верхней границей Последний тип критерия применим только к характеристикам целого и вещественного типа

Сравнение критериев заключается в определении для каждого критерия весовых коэффициентов шг Весовые коэффициенты могут быть определены с помощью парных сравнений метода анализа иерархий (МАИ) Но поскольку критерии могут быть зависимыми и оказывать влияние друг на друга, для определения их совокупного влияния предлагается использовать нечеткую А-меру (Sugeno, 1974)

Пусть Л е (1,+оо) Функция fj,\ 2х —* [0,1] называется нечеткой А-мерой на множестве X, если

1) цх(0) = 0,

2) цх(Х) = 1,

3) fj,\(А U В) < (J>\(A) + (¿\(В) + Xfj,\(A)fj,\(B) для любых непересекающихся A,BQX

Для определения нечеткой А-меры был выбран способ задания, при котором весовые коэффициенты являются натуральными числами За иг обозначим нормализованные коэффициенты cot щ = ^^ Тогда преобразование фь [0,1] —> [0,1], s G [0, +оо], такое, что

(и), если s = 0,

, , . и, если s = l, ФАЩ = I

1 — (1 — и), если s = +оо,

г в противном случае

il, если 0 < и < 1, где {и) = < и s = А+1, позволяет ввести нечеткую А-меру

I 0, если и = 0,

следующим образом

Мл (А) = фх+ï [ ХЛ' Vie А )

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

3) Составление списка объектов

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

Также следует ввести список характеристик объектов, позволяющих обозначить множество различных форм указанных объектов В числе характеристик могут быть такие как способ кодирования, форма представления, точность, что позволяет ввести систематизацию операндов и операций над ними с помощью графовой модели Поскольку объекты обычно имеют дискретную природу, предлагается ввести счетное множество значений характеристик Таким образом, каждая характеристика Сг связана с множеством значений {с?,ьсг2> >СгЛг,}, где Nt — количество возможных значений, которые может принимать г-ая характеристика Следовательно, каждый объект может быть

представлен в П™ i Nt формах, определяемых различными сочетаниями характеристик (то — количество характеристик)

4) Создание иерархической структуры процессов

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

Также на данном шаге предполагается задание характеристик для каждого процесса Характеристики задаются в соответствии со списком, составленным на шаге 2 Обязательным является задание характеристик для всех неделимых процессов Возможно задание характеристик для процессов более высокого уровня Поскольку при построении иерархии используется принцип проектирования «сверху-вниз», характеристика процесса более высокого уровня приоритетна и будет перекрывать такие же характеристики для вложенных процессов

5) Создание диаграмм деятельности (Activity Diagrams)

Диаграммы деятельности представляют собой набор диаграмм, отражающих разложение структуры проектируемой системы на составляющие и взаимосвязи между процессами и объектами, заданных на предыдущих шагах Эти диаграммы основаны на диаграммах деятельности UML с некоторыми ограничениями на число элементов в каждом конкретном случае Элементы альтернативы и слияния (DecisionNode/MergeNode), изображаемые в виде ромбов, предлагается использовать только для отображения различных вариантов структуры Кроме этого, другим (менее предпочтительным в силу меньшей наглядности) способом отображения альтернативных вариантов структуры системы являются случаи нескольких исходящих и входящих дуг для объектов

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

Этап синтеза состоит из 4 шагов

1) Составление расширенного списка объектов

На основе первоначального списка объектов и списка характеристик объектов, составленных на шаге 3 этапа анализа, для каждого объекта может

быть построена то-мерная структура всевозможных форм представлений, из которой затем могут быть удалены заведомо несуществующие (т — число характеристик объектов) Получившийся список назовем расширенным списком объектов Например, при задании двух характеристик с множествами значений С\ = {сц,си} я С2 — {021,022,023}, а также двух объектов в первоначальном списке получаем расширенный список, в котором число объектов равно 2 N1 N2 = 2 2 3 = 12

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

3) Генерация вариантов структуры системы

Поиск вариантов построения структуры системы производится на графе структуры системы, построенного на основе узлов диаграмм деятельности ActivityNode, как поиск всех возможных путей в нем Графом структуры системы G = (V,, Е) назовем совокупность множеств вершин V, соответствующих недекомпозируемым узлам ActivityNode диаграмм деятельности, и соединяющих их ориентированных дуг Е, имеющих веса Веса вершин должны удовлетворять следующим правилам

а) Для вершины, обозначающей элемент альтернативы/слияния, каждая исходящая дуга имеет такой же вес, как и каждая входящая дуга При этом веса входящих и исходящих дуг должны быть равны

где тип — соответственно число входящих и исходящих дуг для рассматриваемой вершины

б) Для вершины, обозначающей элементы процесса или разветвления/соединения, веса входящих дуг равны между собой, веса исходящих дуг равны между собой, и каждая исходящая дуга имеет вес, равный сумме весов

входящих дуг, поделенной поровну между исходящими

— и>к >

оЫ _ тй

и>1 — ЦЦ ,

Уг,к — 1 ,т,гф к, Vз,1 =1~п,з ф I,

и)

оЫ

У^»П гп

п

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

4) Оценка вариантов построения системы и выбор наилучшего из них

Многокритериальную оценку найденных вариантов построения системы предлагается проводить при помощи дискретного интеграла Шоке (Choquet), основанного на нечеткой Л-мере значимости критериев Для использования совокупных характеристик вариантов в интеграле Шоке их следует нормализовать в соответствии с типом связанных с ними критериев

Л =

о,

если > М»,

если тг<1рг< М„ 1 4>ь ^ тг

если срг ^ Мг,

Мг — т,

1, если ^ то;

Л = 4 1 "" Ж^' еСЛИ <(Рг< Ми О, если <рг ^ тг

Л Л

0, если (рг ф тг,

1, если I-рг = тг

0, если (рге[тг,Мг],

1, если 1рг ф [то,, Мг]

для минимизируемои характеристики,

для максимизируемои характеристики,

для критерия равенства,

для критерия принадлежности отрезку,

(1)

где (рг — исходное значение г-го критерия, Мг = тахХгех<Рг ~ максимальное значение г-го критерия, то, = тгп^х'Рг — минимальное значение г-го критерия

Пусть (л —- нечеткая мера на множестве X Дискретным интегралом Шоке функции / X —► [0,1] по отношению к ¿и называется величина

п

М{х) = Е [/« - /(.-иМАо)> (2)

г=1

где (,) означает такую перестановку индексов, что 0 ^ /(!) ^ ^ /(„), = ,хп}, и£(0)=0

Таким образом, сначала нормализуются все характеристики каждой альтернативы с помощью формул (1), затем с использованием значений нечеткой А-меры, полученных на шаге 2 этапа анализа, вычисляется интеграл Шоке по формуле (2) В соответствии с полученными значениями интеграла Шоке для каждой альтернативы их можно упорядочить в порядке убывания интегральных оценок Наиболее предпочтительный с точки зрения заданных критериев вариант структуры будет находиться в начале списка вариантов

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

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

• единство и целостность метода, сквозное проектирование структуры системы (от целей и требований до наилучшего варианта структуры),

• систематизация форм объектов системы и преобразований между ними,

• иерархическое представление системы и возможность декомпозиции,

• использование диаграмм деятельности как распространенной нотации,

• применение многокритериальной оценки на основе нечеткой А-меры (что в отличие от простых весовых коэффициентов позволяет учитывать взаимодействие критериев)

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

В табл 1 проведено сравнение метода синтеза и подходов, на которых он основан (ЗАБТ-ГОЕРО, 11МЬ, высокоуровневые сети Петри)

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

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

Характеристика ЗАБТ-ГОЕГО имь Высокоуровневые сети Петри Диаграммно-сетевой метод синтеза

Систематизация объектов информации системы и преобразований между ними - - - +

Иерархическое представление процессов и возможность декомпозиции + + + +

Наглядное представление взаимосвязей между иерархическими диаграммами + - ± +

Выделение управляющих элемент, ов (соединение/разветвление слия-ние/альгернатива и др) - + ± +

Разделение гипов связей (по управлению, по данным) + + - +

Отображение объектов наряду с процессами + + +

Применение формальных методов - - + +

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

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

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

Рис. 1. Пользовательский интерфейс Синтезатора

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

В третьей главе описаны механизмы работы и процесс проектирования на основе метода синтеза некоторых программных средств «Клиент системы учета рабочего времени» и «Синхронизатор Контрольно-учетной системы и MS Project», созданных и внедренных в ЗАО «Компания Безопасность». Оба средства разработаны в рамках Контрольно-учетной системы (далее КУС), предназначенной для автоматизации информационного обмена, ведения электронного документооборота, планирования и назначения задач, учета рабочего времени сотрудников. Изначально созданная сторонним разработчиком КУС была доработана под нужды Компании и внедрена в рамках Департамента программного обеспечения Компании.

Клиент системы учета рабочего времени (далее Клиент УРВ) представляет собой инструмент для ведения учета рабочего времени сотрудников Целью создания Клиента УРВ является повышение скорости работы с системой по сравнению со стандартным клиентом

В работе рассмотрены различные варианты структуры системы УРВ, среди которых — изначальный вариант с применением стандартных «толстых» клиентов, а также два альтернативных варианта с применением специализированных «толстых» клиентов, использующих API КУС, и с применением «тонких» клиентов, работающих напрямую с БД В случае первой альтернативы снижается нагрузка на сервер, становится возможным корректное обращение к БД через API Во втором случае возрастает скорость обмена с сервером благодаря использованию прямого обращения к БД

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

Программное средство «Синхронизатор Контрольно-учетной системы и MS Project» (далее Синхронизатор) предназначен для автоматизации обмена проектной информацией между КУС и календарными планами в формате MS Project Целями создания Синхронизатора являются организация связей между записями КУС и задачами в календарных планах MS Project, а также повышение эффективности синхронизации данных между этими системами

Аналогично случаю с Клиентом УРВ рассмотрено два случая использование API КУС и прямое обращение к БД С помощью метода синтеза создана модель, описывающая альтернативные способы организации системы На основе модели проведена генерация вариантов построения структуры и получены их интегральные оценки по тем же критериям В результате оценки для реализации был выбран вариант, использующий API КУС, как наиболее эффективный с точки зрения сложности и временных затрат

В четвертой главе описано построение на основе диаграммно-сетевого метода синтеза системы для реконструкции объемных геометрических моделей (ОГМ) кровеносных сосудов по набору растровых изображений ангио-грамм Основными задачами исследования является анализ существующих алгоритмов и разработка инструментальных программных средств для создания ОГМ по растровым изображениям

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

1 Распознавание растровых изображений ангиограмм и построение векторной двумерной модели

2 Анализ информации и построение векторной трехмерной модели

3 Визуализация объемной геометрической модели Сформулированы следующие требования к системе

• система должна работать на типичных конфигурациях персональных компьютеров (минимальная конфигурация для комфортной работы пользователя Pentium 1 GHz, RAM 512 MB, HDD 100 MB free, стандартный графический адаптер, клавиатура, мышь, ОС - MS Windows ХР),

• чистое время работы алгоритмов (расчетов без участия пользователя) не должно превышать 1 минуты,

• применяемые в расчетах алгоритмы должны давать максимальное качество результата среди всех возможных в данном случае вариантов

В соответствии с требованиями составлен список характеристик оценки ИС

• Относительное качество результата Q — целочисленная, минимизируемая

Вычисляется в рамках каждой категории алгоритмов на основе нечеткой меры в соответствии со следующей шкалой оценки

0 — совершенно не соответствует ожиданиям,

1 — есть некоторый результат,

2 — приемлемый результат, смотрится выигрышно на фоне остальных,

3 — отличный результат, один из лучших в данной категории

• Объем требуемой памяти М, Б — целочисленная, максимизируемая,

• Время выполнения Г, мс — целочисленная, аддитивная,

• Цикломатическая сложность С], число независимых ветвей алгоритма — целочисленная, аддитивная,

• Сложность кода Сг, число операторов программы — целочисленная, аддитивная,

• Сложность данных Сз, число структур данных — целочисленная, аддитивная

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

Q е [0,3], Q max, М mm, Т 6 [0,60000], Т —» тгп, С\ —► тгп, С2 —> тгп, С3 —» тгп

При анализе работ выделены объекты и исследованы характеристики алгоритмов, задействованных в процессе реконструкции ОГМ кровеносных сосудов На завершающем шаге этапа анализа составлен набор диаграмм деятельности, определяющий взаимосвязи между процессами и объектами

Рис. 2. Граф структуры системы реконструкции ОГМ кровеносных сосудов

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

Завершающим шагом синтеза является оценка полученных вариантов и их ранжирование. В соответствии с характеристиками процессов, заданных на этапе анализа, произведена оценка каждого варианта структуры (табл. 2). На основе минимальных и максимальных значений каждого критерия среди всех вариантов и в соответствии с (3) все значения критериев для каждого варианта нормализованы по формулам (1). Для каждого варианта вычислены значения интеграла Шоке в соответствии с (2), отраженные в последнем столбце табл. 2. По данным значениям все варианты структуры системы упорядочены по убыванию, и как имеющий наибольшую оценку наилучшим признан вариант №341, заключающийся в использовании методов Canny, утончения (thinning) и слежения (tracking) при распознавании растровых изображений, преобразования полученной векторной двумерной модели в объемную, визуализации ОГМ при помощи библиотеки GLE.

Разработан прототип системы реконструкции и диагностики кровеносных сосудов в соответствии с выбранным вариантом структуры (рис. 3). Система позволяет восстанавливать ОГМ кровеносных сосудов по набору изображений, полученных с ангиографа. Модель сосудов может управляться пользователем, а также в интерактивном режиме могут быть настроены параметры применяемых алгоритмов. Полученная таким образом модель дает возможность лучшего представления о состоянии кровеносных сосудов пациента и I выявления атеросклероза или тромбофлебита.

В приложениях приведены диаграммы и описание классов метода синтеза (приложение 1), диаграммы вариантов использования, диаграммы деятельности и диаграммы классов Синтезатора (приложение 2), диаграммы деятельности системы реконструкции ОГМ кровеносных сосудов (приложение 3), акты о внедрении (приложение 4).

Таблица 2. Варианты структуры системы реконструкции (первые 5 вариантов)

№ Описание варианта Q M T Ci Co c3 M(x)

341 Canny - Thinning — Tracking — Photograininetry — Vector — GLECalc — GLTrans ■ GLE 3 704413 7236 46 546 117 0,58

119 Median — CS — Laplasian — AdapThres Thinning — Tracking — Photograrnmetry -Vector - GLECalc GLTrans - GLE 2 704264 7534 37 465 120 0,55

279 Gauss — CS — Laplasian — AdapThres — Thinning — Tracking — Photograrnmetry — Vector - GLECalc - GLTrans - GLE 2 704264 7544 40 463 119 0,55

342 Canny — Thinning — Tracking — Photograrnmetry — Vector — OpenGLCalc - OpenGL 3 704413 7237 51 573 117 0,54

115 Median — CS - Prewitt - AdapThres Thinning — Tracking — Photograrnmetry — Vector - GLECalc - GLTrans - GLE 2 704264 8425 38 470 122 0,53

jJflx]

Загрузить |

ПБ-3

Г GVF Г" Середина W Границы р Сохранять

Г Обрисовка

Г" Квадрат

Сторона

квадрата:

[3

Параметры Canny -...................................................

Отклонение (sigrns):

Нижний порог:

J- ¡Г"

Верхний порог:

-J- F"

Рис. 3. Пользовательский интерфейс системы реконструкции

Заключение

В диссертации получены следующие основные теоретические и практические результаты

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

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

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

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

5 На основе разработанного диаграммно-сетевого метода синтеза создан набор инструментальных средств под названием «Синтезатор» для анализа и синтеза структур систем Синтезатор обладает интуитивным пользовательским интерфейсом и позволяет автоматизировать основные шаги процесса проектирования систем при помощи диаграммно-сетевого метода синтеза

6 С применением диаграммно-сетевого метода синтеза показаны новые возможности проектирования систем на примерах системы реконструкции ОГМ кровеносных сосудов, программных средств Контрольно-учетной системы в ЗАО «Компания Безопасность», а также на примерах из областей помимо разработки программного обеспечения

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Основные результаты проведенных исследований опубликованы в 12 печатных работах

1 Болонкин А В Сравнительный анализ отечественных SCADA-систем // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2004) Материалы 4-й междунар конф M ИПУ РАН -

2004

2 Геометрическое моделирование на OpenGL методическое пособие / Артамонов Е И , Болонкин А В , Ромакин В А , Тенякшев A M — M МТУСИ,

2005 - 34 с

3 Болонкин А В Сравнительный анализ технологий системного проектирования // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/САМ/PDM-2005) Материалы 5-й междунар конф M ИПУ РАН -

2005

4 Болонкин А В Методы синтеза структур программных систем // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2006) Материалы 6-й междунар конф M ИПУ РАН - 2006

5 Болонкин А В Преобразование растр-вектор изображений сосудов // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2006) Материалы 6-й междунар конф M ИПУ РАН -

2006

6 Артамонов Е И , Болонкин А В Диагностика заболеваний сердечнососудистой системы на основе трехмерных моделей // Прил к журналу «Вестник СПбГМА им И И Мечникова», №2, 2007 - С 10

7 Особенности обучения студентов технических специальностей в рамках курса «Инженерная и компьютерная графика» / Артамонов Е И , Болонкин А В , Ромакин В А , Тенякшев A M // Материалы XXXIV междунар конф «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07» — Прил к журналу «Открытое образование» — 2007 — С 130-131

8 Артамонов Е И , Болонкин А В , Щегольков M Ю Разработка новых методов диагностики, документирования, подготовки и проведения хирургических операций на основе виртуальных объемных геометрических моделей // Материалы XV междунар конф «Новые информационные технологии в медицине, биологии, фармакологии и экологии 1Т+М&Ес'07» — 2007 — С 108-109

9 Болонкин А В Инструментальные средства для генерации, оценки и выбора структур систем // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2007) Материалы 7-й междунар конф М ИПУ РАН - 2007

10 Артамонов Е И, Болонкин А В Реконструкция объемных геометрических моделей кровеносных сосудов по набору растровых изображений // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2007) Материалы 7-й междунар конф М ИПУ РАН -2007

11 Артамонов Е И , Болонкин А В Построение объемных геометрических моделей объектов по их растровым изображениям // Информационные технологии и вычислительные системы, №2, 2008

12 Артамонов Е И , Болонкин А В Синтез структур систем векторизации изображений // Информационные технологии в проектировании и производстве, №2, 2008

Личный вклад автора в совместные работы

В работах [2, 7] автором предложены алгоритмы создания объемных геометрических моделей и применение метода синтеза в сфере образования В работах [5, 6, 8,10,11,12] автором проведено исследование алгоритмов распознавания растровых изображений ангиограмм, фотограмметрии и моделированию трубчатых поверхностей, предложены принципы реконструкции ОГМ кровеносных сосудов и ее программная реализация

Заказ № 123/03/08 Подписано в печать 04.03.2008 Тираж 80 экз. Усл. пл. 1,25

000 "Цифровичок", тел. (495) 797-75-76; (495) 778-22-20 Л^)) www.cfr.ru ; е-таИ:т/о@с/г.ги

ВВЕДЕНИЕ

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

СТРУКТУР ИНТЕРАКТИВНЫХ СИСТЕМ

1.1. Понятие интерактивной системы.

1.2. Критерии оценки качества интерактивных систем.

1.3. Понятие структуры интерактивной системы.

1.4. Синтез структуры интерактивной системы.

1.5. Обзор методов проектирования структур интерактивных систем

1.5.1. Неформальный подход

1.5.2. Формальный подход.

1.6. Требования к методу синтеза.

Актуальность исследования

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

Значительный вклад в решение проблем проектирования программных систем (в т. ч. ИС) внесли Г. Буч (G. Booch) [7, 8], Б. В. Боэм (В. W. Boehm), П. Коуд (P. Coad) и Э. Йордон (Е. Yourdon), известны работы Г. Сторрле (Н. Storrle) [72, 73, 74], У. Ван дер Аальста (W. М. P. van der Aalst) [36]. В отечественной науке проблемы синтеза структур систем рассмотрены в работах Е. И. Артамонова [3, 4], В. В. Кульбы [15, 18, 26], В. В. Липаева [13, 14], А. Д. Цвиркуна [15, 31], А. А. Шалыто [10, 32], С. А. Юдицкого [34].

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

Цель работы

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

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

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

1. Исследование механизмов построения сложных ИС, современных методов их проектирования и проблем, возникающих при проектировании.

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

3. Создание инструментальных средств, позволяющих проектировать ИС на основе разработанного диаграммно-сетевого метода синтеза.

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

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

Научная новизна работы

1. Впервые для данного рода задач на основе UML, IDEF0 и сетей Петри разработаны структурные модели ИС, позволяющие отобразить и систематизировать варианты их структур.

2. Разработаны механизмы систематизации вариантов структур И С на основе графовых моделей с учетом полноты перебора вариантов.

3. Сформулирован способ многокритериальной оценки вариантов структур сложных программных систем на основе нечеткой А-меры с учетом взаимосвязей критериев.

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

Практическая значимость

1. На основе разработанного метода синтеза созданы инструментальные средства для автоматизации проектирования структур ИС.

2. Представленные в диссертации результаты использованы для научно обоснованного построения структур ИС и поиска их наилучших вариантов в ряде проектов:

• при создании системы реконструкции объемных геометрических моделей кровеносных сосудов по набору растровых ангиограмм;

• при разработке программных средств «Клиент системы учета рабочего времени» и «Синхронизатор КУС — MS Project» в ЗАО «Компания Безопасность».

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

Результаты, выносимые на защиту:

• Модели представления структур ИС, основанные на графической нотации диаграмм деятельности UML, предоставляющие возможности отображения и систематизации вариантов структур.

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

• Алгоритмы и программная реализация инструментальных средств для автоматизации анализа и синтеза структур систем различного назначения.

Реализация результатов работы

Полученные в диссертации результаты и программное обеспечение были применены в ЗАО «Компания Безопасность» при разработке программных средств «Клиент системы учета рабочего времени» и «Синхронизатор КУС — MS Project» (подтверждено актами о внедрении).

Апробация работы

Положения диссертационной работы докладывались и обсуждались на IV, V, VI и VII международных конференциях «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта. CAD/CAM/PDM» (Москва: ИПУ РАН, 2004, 2005, 2006, 2007), Всероссийской научно-практической конференции с международным участием «Современная кардиология: наука и практика» (СПб: СПбГМА, 2007), XXXIV международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07» (Гурзуф: 2007), XV международной конференции «Новые информационные технологии в медицине, биологии, фармакологии и экологии 1Т+М&Ес'07» (Гурзуф: 2007).

Публикации

Основные результаты работы опубликованы в 12 печатных работах, из которых 2 статьи (среди них 2 статьи по списку ВАК).

Основное содержание работы

В первой главе рассмотрены основные понятия проектирования и моделирования ИС, приведены классификации ИС с точки зрения области применения и с точки зрения связи с внешними устройствами. Рассмотрены вопросы качества ПО, способы и критерии его оценки. Отдельно выделено понятие структуры программной системы и связь структуры системы с ее качеством. Рассмотрены принципы построения структуры программных систем на основе оценки компонентов систем. Проведен обзор методов моделирования программных систем, среди которых выделен неформальный (Flow-charts, DFD, IDEF-SADT, ЕРС, UML, SysML) и формальный подход (теории множеств и графов, конечные автоматы, сети Петри, формальные спецификации). На основе исследования методов моделирования программных систем и анализа работ определены требования к методу синтеза структур систем.

Во второй главе разработан диаграммно-сетевой метод синтеза структур ИС, отличающийся одновременным применением формального и неформального подходов, детальным учетом свойств объектов информации ИС, использованием стандартной нотации диаграмм деятельности UML для отображения- алгоритма функционирования ИС и многокритериальной оценки параметров ИС для выбора ее наилучшей структуры. Сформулированы механизмы построения структур ИС на основе анализа параметров объектов и процессов системы, а также многокритериальной оценки вариантов структур в совокупности с использованием методологии исследования пространства вариантов (Design Space Exploration — DSE), нечеткой А-меры и дискретного интеграла Шоке.

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

В третьей главе проведен анализ разработанного метода синтеза, сравнение его с другими методами, показаны его сильные и слабые стороны, определены возможности его применения. Также показана необходимость разработки инструментальных средств проектирования структур сложных ИС на основе диаграммно-сетевого метода синтеза и описано разработанное программное средство для автоматизации такого проектирования. Кроме того, приведены примеры проектирования структур некоторых программных средств — «Клиент системы учета рабочего времени» и «Синхронизатор КУС — MS Project», разработанных в ЗАО «Компания Безопасность», Описаны механизмы работы данных систем, приведено детальное изложение шагов метода синтеза при их проектировании.

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

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

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

Структура и объем работы

Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложений. Общий объем диссертации составляет 167 е., основного текста — 144 е., включая 45 рисунков и 33 таблицы. Список литературы состоит из 79 наименований.

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

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

2. Проведено исследование и реализация ряда методов обработки изображений для распознавания кровеносных сосудов. Среди них:

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

- методы сегментации (сегментация по общему порогу, адаптивная пороговая сегментация, оператор Робертса, оператор Собела, метод Превитта, лапласиан гауссиана, метод Кэнни);

- методы фильтрации (медианный фильтр, фильтр Kuwahara, утончение);

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

Для каждой реализации получена оценка характеристик.

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

4. Проведено исследование и реализация ряда методов объемной визуализации трубчатых поверхностей (применение библиотеки GLE, визуализация с помощью примитивов OpenGL). В результате исследования для каждой реализации получена оценка характеристик.

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

ЗАКЛЮЧЕНИЕ

В диссертации получены следующие основные теоретические и практические результаты.

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

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

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

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

5. На основе разработанного диаграммно-сетевого метода синтеза создан набор инструментальных средств под названием «Синтезатор» для анализа и синтеза структур систем. Синтезатор обладает интуитивным пользовательским интерфейсом и позволяет автоматизировать основные шаги процесса проектирования систем при помощи диаграммно-сетевого метода синтеза.

6. С применением диаграммно-сетевого метода синтеза показаны новые возможности проектирования систем на примерах системы реконструкции ОГМ кровеносных сосудов, программных средств Контрольно-учетной системы в ЗАО «Компания Безопасность», а также на примерах из областей помимо разработки программного обеспечения.

1. Абакаров А. Ш., Сушков Ю. А. Программная система поддержки принятия решений «MPRIORITY 1.0» // Исследовано в России. Электрон. науч. журн. — Долгопрудный, МФТИ, 2005. — Режим доступа: http: / / zhurnal.ape.relarn.ru / articles /2005/207.pdf.

2. Алгоритмы и методы. Графы. Поиск маршрутов Электронный ресурс. — Режим доступа: http://algolist.manual.ru/maths/graphs.

3. Артамонов Е. И., Хачумов В. М. Синтез структур специализированных средств машинной графики. — М.: ИПУ РАН, 1991.

4. Арчибальд Р. Д. Управление высоко-техпологичными программами и проектами. — М.: ДМК Пресс, 2004.

5. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. — М.: Бином, 1998. — 560 с.

6. Буч Г., Рамбо Дж., Якобсон А. Язык UML: руководство пользователя. М.: ДМК, 2001. - 432 с.

7. ГОСТ Р ИСО/МЭК 12207-99. Информационная технология. Процессы жизненного цикла программных средств. Государственный стандарт Российской Федерации, 1999. — Госстандарт России. Москва, 2000.

8. Гуров В., Нарвский А., Шалыто А. Исполняемый UML из России // «PC Week/RE». №26, 2005. С. 18-19.

9. Зайцев Д. А. Декомпозиция сетей Петри // Кибернетика и системный анализ, №5, 2004. С. 131-140.

10. Котов В. Е. Сети Петри. М.: Наука, 1984. — 160 с.

11. Липаев В. В. Выбор и оценивание характеристик качества программных средств: методы и стандарты. М.: СИНТЕГ, 2001. — 228 с. — (Информационные технологии).

12. Липаев В. В. Системное проектирование сложных программных средств для информационных систем. М.: СИНТЕГ, 2002. — 268 с. — (Управление качеством).

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

14. Марка Д. А., МакГоуэн К. Методология структурного анализа и проектирования SADT. — М.: Мета Технология, 1993.

15. Моделирование бизнеса. Методология ARIS / Каменнова М., Громов А., Ферапонтов М. и др. — М.: Весть-МетаТехнология, 2001. — 334 с.

16. Оптимальные модульные системы реального времени (анализ и синтез) / Кузнецов Н. А., Кульба В. В., Косяченко С. А. и др. — М.: ИППИ РАН, 1994.

17. Орлик С. Введение в программную инженерию и управление жизненным циклом ПО Электронный ресурс. — 2005. — Режим доступа: http: / / software-testing.ru/lib / se.

18. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984. — 264 с.

19. Путятин Е. П., Аверин С. И. Обработка изображений в робототехнике. — М: Машиностроение, 1990. — 320 с.

20. Раскин Дж. Интерфейс: новые направления в проектировании компьютерных систем. — М.: Символ-плюс, 2005. — 272 с.

21. Саати Т. Принятие решений. Метод анализа иерархий. — М.: Радио и связь, 1993. — 316 с.

22. Садовский В. Н. Основания общей теории систем: логико-методологический анализ. — М., 1974.

23. Самойлин Е. А. Оценка эффективности программных методов обработки изображений // Програм. продукты и системы. — 2003. №4. — С. 34-37.

24. Теоретические основы проектирования информационно-управляющих систем космических аппаратов / Кульба В. В., Микрин Е. А., Павлов Б. В., Платонов В. Н.; под. ред. Микрина Е. А.; Ин-т проблем упр. им. В. А. Трапезникова РАН. — М.: Наука, 2006. — 579 с.

25. Тодорой Д. Н. Расширяемые средства машинной графики / Под ред. С. Я. Виленкина. — М.: Радио и связь, 1983. — 208 с.

26. Толковый словарь русского языка. Под редакцией Д. Н. Ушакова. — ACT. Астрель, 2000.

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

28. Фиошин М. Основы р-исчисления Электронный ресурс. — Режим доступа: http://progr.tsi.lv/research/picalc.pdf.

29. Цвиркун А. Д. Основы синтеза структуры сложных систем. — М.: Наука, 1982.

30. Шалыто А. А. Switch-технология. Алгоритмизация и программирование задач логического управления. — СПб.: Наука, 1998. — 628 с.

31. Юдицкий С. А., Мачергут В. 3. Логическое управление дискретными процессами. — М.: Машиностроение, 1992.

32. A model based method for retinal blood vessel detection / Vermeer K. A. et al. // Computers in Biology and Medicine, 2004, #34. — P. 209-219.

33. Aalst, W. M. P. van der. The Application of Petri Nets to Workflow Management // The Journal of Circuits, Systems and Computers, 8(1), 1998. P. 21-66.

34. Blood vessel segmentation using moving-window robust automatic threshold selection / Wilkinson M. H. F. et al. IEEE, 2003.

35. Chaudhuri S., Blythe S. A., Walker R. A. A Solution Methodology for Exact Design Space Exploration in a Three-Dimensional Design Space // IEEE Transactions on very large scale integration (VLSI) systems, Vol. 5, No. 1, March 1997.

36. Dumke R. R., Foltin E. Metrics-based Evaluation of Object-Oriented Software Development Methods. — University of Magdeburg, 1996.

37. Eisenmann H., U'Ren J. SysML — OMG's upcoming standard for a standardized systems modeling language // 6th NASA ESA Workshop on Product Data Exchange. — Friedrichshafen, 2004.

38. Erbas C. System-Level Modeling and Design Space Exploration for Multiprocessor Embedded System-on-Chip Architectures : PhD dissertation. — Amsterdam University Press, 2006.

39. Features for Automatic Pulmonary-Embolism Detection / Bouma H., Vilanova A., Quist M. J. et al. — Technische Universiteit Eindhoven, 2004.

40. Fuller R., Carlsson C. Fuzzy multiple criteria decision making: Recent developments // Fuzzy Sets and Systems, 78. — 1996. — P. 139-153.

41. Ganesan S., Prevostini M. Bridging the Gap between SysML and Design Space Exploration. University of Lugano, Switzerland, 2006.

42. Garmendia L. The Evolution of the Concept of Fuzzy Measure. — Universidad Complutense of Madrid, 2006.

43. Grabisch M., Roubens M. Application of the Choquet Integral in Multicriteria Decision Making // Fuzzy Measures and Integrals — Theory and Applications. — Physica Verlag, 2000. — P. 415-434.

44. Hyatt L. E., Rosenberg L. H. A Software Quality Model and Metrics for Identifying Project Risks and Assessing Software Quality. — NASA's Goddard Space Flight Center, 1996.

45. Hypermedia Image Processing Reference Электронный ресурс. / Fisher R., Perkins S., Walker A., Wolfart E. — University of Edinburgh, 2004. — Режим доступа: http://homepages.inf.ed.ac.uk/rbf/HIPR2.

46. IDEF3 Process Description Capture Method Report. — Knowledge Based Systems, Inc., 1995.

47. IEEE Standard for a Software Quality Metrics Methodology (IEEE Std 1061-1998). IEEE, 1998.

48. Integration Definition for Function Modeling (IDEF0). Federal Information Processing Standards Publication. — Knowledge Based Systems, Inc., 1993. 128 p.

49. ISO/IEC 9126-1:2001. Software engineering — Software product quality. Part 1: Quality model. — International Organization for Standardization/International Electrotechnical Commission, 2001.

50. Janneck J. W., Esser R. Higher-order Petri net modelling techniques and applications // Workshop on Software Engineering and Formal Methods. — 2002.

51. Kan S. H. Metrics and Models in Software Quality Engineering. — MA: Addison Wesley, 2002.

52. Kawamoto P. N. Applications of Petri Net Theory in the Design of Hardware/Software Systems. — 1996.

53. Lalonde M., Gagnony L., Boucherz M.-C. Non-recursive paired tracking for vessel extraction from retinal images. — Centre de recherche informatique de Montreal, 2000.

54. Linas Vepstas' GLE Tubing and Extrusion Электронный ресурс. — Режим доступа: http://linas.org/gle.

55. Maciel P., Barros E., Rosenstiel W. A Petri Net Model For Hardware/Software Codesign. Design Automation for Embedded Systems. 1999, #4. - P. 243-310.

56. Marichal J.-L. Behavioral Analysis of Aggregation in Multicriteria Decision Aid // Preferences and Decisions under Incomplete Knowledge. Studies in Fuzziness and Soft Computing. Vol. 51. — Heidelberg, Physica Verlag, 2000. P. 153-178.

57. McCabe T. J. A Complexity Measure // IEEE Transactions on Software Engineering, Vol. 2, No. 4, December 1976. P. 308-320.

58. Mellor S., Balcer M. Executable UML. A Foundation for Model-Driven Architecture. MA: Addison-Wesley, 2002. — 368 p.

59. Murata T. Petri nets: Properties, analysis and applications. — Proceeding of the IEEE, 1989.

60. OMG Systems Modeling Language Specification Электронный ресурс. Proposed Available Specification. — OMG, 2007. — Режим доступа: http: //www.sysml.org/docs/specs/OMGSysML-PAS-07-02-03.pdf.

61. OpenGL — The Industry's Foundation for High Performance Graphics Электронный ресурс. — Режим доступа: http://www.opengl.org.

62. Orthopedic surgery training on personal computer / Surin A. I., Surina O. N., Klimenko S. V., Howe Tet Sen // Int. Conference GraphiCon'OO. Moscow, MSU, 2000. - P. 234-241.

63. Petri Nets World Электронный ресурс. — University of Hamburg. — Режим доступа: http://www.informatik.uni-hamburg.de/TGI/PetriNets.

64. Registering External and Internal Morphological Images of Coronary Vessels / Radeva P., Rotger D., Nofrerias E. et al. — Computer Vision Center, University Autonoma of Barcelona, 2002.

65. Rust C., Stappert F., Kiinnemeyer R. From Timed Petri Nets to to Interrupt-Driven Embedded Control Software. — University of Paderborn, Germany.

66. Software and Systems Engineering — High-level Petri Nets — Concepts,. Definitions and Graphical Notation. Final Draft International Standard ISO/IEC 15909. 2000.

67. Software and Systems Engineering — High-level Petri Nets. Part 2: Transfer Format. International Standard ISO/IEC 15909-2. WD Version 0.9.0. — 2005.

68. Storrle H. An Evaluation of High-End Tools for Petri-Nets. — Miinchen: Ludwig-Maximilians-Universitat, Institut fur Informatik, 1998.

69. Storrle H. Structured nodes in UML 2.0 activities // Nordic Journal of Computing, 2004, Volume 11, Issue 3.

70. Storrle H. Towards a Petri-net Semantics of Data Flow in UML 2.0 Activities. — Miinchen, Elsevier Science, 2004.

71. Sugeno M. Theory of fuzzy integrals and its applications : PhD thesis. — Tokyo Institute of Technology, 1974.

72. Takahagi E. On Identification methods of A-fuzzy measures using weights and A j j Japanese Journal of Fuzzy Sets and Systems, vol. 12, no. 5. 2000. - P. 665-676.

73. Unified Modeling Language: Infrastructure. Version 2.0. OMG, 2005. — 218 p.

74. Unified Modeling Language: Superstructure. Version 2.0. OMG, 2005. — 770 p.

75. Visualization and Interaction Techniques for the Exploration of Vascular Structures / Hahn H. K., Preim В., Selle D. et al. — Bremen, Center for Medical Diagnostic Systems and Visualization. — IEEE Visualization 2001 (Vis'2001). P. 395-402.