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

РОССИЙСКАЯ АКАДЕМИЯ НАУК

Институт проблем управления им. В.А. Трапезникова

УДК 658.512.011.56 На правах рукописи

РАЗУМОВСКИЙ АЛЕКСЕЙ ИГОРЕВИЧ

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

Специальность 05.13.12 - Системы автоматизации проектирования

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена в Институте проблем управления им. В.А. Трапезникова РАН

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

доктор технических наук Евгений Иванович Артамонов

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

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

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

Московский энергетический институт

на заседании Диссертационного совета Д 002.226.02 Института проблем управления им. В.А. Трапезникова РАН по адресу: 117997, г. Москва, ул. Профсоюзная, 65.

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

Защита состоится

к

и

Автореферат разослан «

»

2005 г.

Ученый секретарь Диссертационного совета Д 002.226.02 кандидат технических наук В .Н. Лебедев

19992

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

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

Постоянное развитие производственных процессов стимулирует появление все более совершенных интерактивных автоматизированных систем, реализующих сложные алгоритмы функционирования в реальном времени, использующих 20 и ЗЭ геометрические модели со сложными структурами данных, поддерживающих международные стандарты по представлению информации для взаимодействия с внешними объектами и системами. К ним относятся, например, системы автоматизированного проектирования (САПР), автоматизированные системы управления производством (АСУП и АСУТП), ЗСАБА-системы, промышленные информационные системы и т.п. В таких системах, как правило, на начальных стадиях проектирования наблюдается некоторая неопределенность в перечне операций в алгоритмах функционирования системы, в смысле окончательного формулирования, а также неопределенность характеристик операндов в алгоритмах, в частности, касающихся точностей представления, способов кодирования и форм их внешнего представления. Таким образом, можно выделить новый класс программных интерактивных систем с, так называемыми, недетерминированными алгоритмами (ПрИС).

Известны исследования зарубежных ученых; Г. Буча, М. Шоу в области моделирования архитектур программно реализованных систем, К. Кнута, Г. Берна в области анализа и обобщения структур данных, а также отечественных ученых: Кульбы В.В., ЬСосяченко С.А., Цвиркуна А.Д. по методам проектирования сложных систем обработки данных, Артамонова Е.И. по синтезу4 структур специализированных программно-аппаратных средств и т.п.

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

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

Цели и задачи исследования.

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

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

1. Исследование и проектирование алгоритмов функционирования, операций по формированию структур алгоритмов и уточнению их характеристик.

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

3. Анализ и разработка технологий представления и преобразования структур данных 20 и ЗЭ геометрических моделей.

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

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

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

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

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

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

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

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

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

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

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

Исследования, выполненные в диссертации, осуществлялись в рамках следующих НИР "Разработка программного обеспечения для геометрического моделирования крупногабаритных машиностроительных конструкций'" (тема 318-96/18, per. номер 01.96.0009913) по заданию РАН, "Система моделирования и проектирования крупногабаритных конструкций" (тема 465-97/18.) по заданию Миннауки РФ, "Интегрированные САПР" (463-97/18) по заданию Миннауки РФ.

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

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

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

Эффективность разработанных в диссертационной работе концепций, методик и моделей подтверждена положительным опытом их применения при разработке ряда САПР для функционирования на заводе им. Хруничева и в НПО «Энергия». Также, кроме указанных работ, многие разработанные блока и модули инструментальных средств внедрены в состав комплексов программных средств ГРАФИКА-81, ГРАФИКА-97 и ГРАФИКА-2000, созданных в ИПУ РАН и использованных при конструировании сложных объектов.

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

Основные положения работы докладывались на международных конференциях САО/САМ/РОМ-2002,

САО/САМ/РОМ-2003 и САО/САМ/РВМ-2004, а также на научных семинарах лаборатории Института проблем управления РАН.

Публикации.

По теме диссертации опубликовано 9 печатных работ.

Структура и объем диссертации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная идея технологии единого направленного процесса проектирования (ЕНП) состоит в перенесении нагрузки процесса «уточнений» с совокупной системы на отдельные ее блоки в процессе проектирования структуры ПрИС. Технология ЕНП разработки ПрИС включает:

образование локальных алгоритмов,

составление естественно-языкового тезауруса операций и операндов,

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

Алгоритм4 функционирования ПрИС характеризуется четверкой параметров:

Е={ Р,0,Г\т}, (2.1)

где Р - множество операндов; О - множество операций; Г - множество связей между операциями; т - времена выполнения операций. Множество операндов в свою очередь характеризуется тройкой:

Р={А,Ф,Л], (2.2)

где А - множество способов кодирования операндов;

Ф - множество форм представления операндов; Д - множество точностей представления операндов. Тесно связанными с порядком функционирования ПрИС в первую очередь будут точность представления и способ

кодирования информации. Точность представления операнда представленного ^ разрядами кода СХЬ определяется как величина <5/ = 1/|№|, где N1 - множество различных значений, которые могут быть присвоены операнду ^ длиной ^ в коде . Что для позиционной системы счисления с основанием

а

соответствует:

(2-3)

Способ кодирования операнда - есть функционал 1 к устанавливающий связь между символами операнда, записанного на

СС

неформальном языке ^о , и разрядами кодового слова С .

Определение. Алгоритм, в котором используется один способ кодирования ( а^сог^ ) и единая точность представления информации (б=соп50 называют локальным алгоритмом.

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

Каждой дуге графа инцидентной паре вершин , соседних

/Г"1*2

ярусов ставится в соответствие функционал 1 , т.е. спосоо кодирования.

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

Определение. Система ^ поддается ^-декомпозиции на системы и если для $ ^ & найдутся такие системы

и и такое отношение А е Г 9 что будет иметь место равенство

А

Если ^1 ^ $2 и Д то А- декомпозиция

определяется как собственная, хотя можно рассматривать и более

Л ?

общую декомпозицию, а именно -декомпозицию системы на

• системы которая имеет место в том случае, когда для

найдутся такие системы ¿ии такое отношение ^ , что будет выполняться равенство

£ = Д^,,...,^]

Для реализации естественно- языкового тезауруса системы

^ , декомпозированной на системы следует реализовать

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

Образование тезауруса может происходить следующими путями:

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

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

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

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

5. Производятся попытки сортировки найденных фраз и предложений по порядку смысловых конфликтных пар: 1) «Известно - Нет», 2) «Возможно - Нет», 3) «Разделимо - Нет», 4) «Достаточно - Нет».

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

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

Смысл и необходимость унификации можно понимать, в стремлении заменить определенные фразы и предложения из тезауруса «усредненными терминами».

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

^Е-ЗД (2.4)

I

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

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

F = пХ,{<р)

(2.5)

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

Если представить произвольную процедуру в виде последовательности процедур, то реализация функциональной части

XI класса будет иметь вид: Fx^ + /. Первый член

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

Результаты поиска изменяющей поведение функции f :

Во-первых: функция f может обеспечить добавление лишь вовне тела цикла, иначе будет нарушен инвариант цикла. Здесь мы

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

члена f является операцией, реализацию которой можно осуществить трояко:

- Реализовать функцию f внутри класса (модуля), - как бы

«обертывая» функцию • Здесь важно отметить необходимость

собственной простоты функции ^, т.е. отсутствие операторов GOTO или операюров выхода RETURN внутри цикла.

- Реализовать функцию f с помощью процедуры гак называемого обратного вызова - CALLBACK.

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

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

В этом ключе возможны три направления при формировании структуры ПрИС:

общность целей алгоритмов; общность терминалов алгоритмов; общность операций алгоритмов.

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

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

Ценность такой модели - гарантия адекватности любого изменения структуры системы любому моменту ее разработки.

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

В третьей главе проведена детальная разработка и анализ основных алгоритмов по работе с 20 и 30 моделями объектов в САПР. На примере реализации недетерминированных алгоритмов пересечения сплайнов первой степени, замкнутых контуров, триангуляции 21) контуров по методу Сейделя показана результативность использования естественно-языкового тезаурчса операций и операндов. В рамках предложенной технологии унификации типов данных разработан оригинальный алгоритм быстрой селекции векторных примитивов, позволяющий

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

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

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

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

1) Какой параметр контура содержит факт взаимодействия с линией; 1а) номер сегмента контура; Цикл последовательно по сегментам контура. Тип Point должен включать факт взаимодействия линии и контура.

2) Какой параметр контура содержит качество его взаимодействия с линией; 2а) Факт совпадения с одной или двумя вершинами, а также -наличие равных по значению параметров пересечения; Создание по факту сорта точки пересечения

3) Какое количество результирующих данных можно получпть; За) Бесконечное число точек пересечения. Создание хранилища точек пересечения в виде шаблонного класса вектор -vector<Point>

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

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

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

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

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

алгоритм триангуляции._

_Тезаурус алгоритма Нархеде и Маночи. (Сейделя) |_

1) Получить трапецоиды линиями сечения, исходящими

из вершин полигона_

_2) Получить монотонные полигоны_

_3) Триангулировать монотонные полигоны_

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

алгоритма._

_Авторский алгоритм триангуляции._

_1) Упорядочить точки полигона_

2) Удалить точку полигона, создать треугольник, уменьшить массив точек полигона_

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

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

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

Тезаурус последовательности решений:

1) задать подходящий набор опорных точек сплайна,

2) найти количество и качество входящих параметров, достаточных для определения сплайнового куска,

3) найти условия плавной состыковки элементарных фрагментов сплайна.

Тезаурус аналитических требований:

1) Какой класс кривых может удовлетворить простым условия описания, а также условиям задачи?

2) Какова гладкость используемых кривых? Кривые должны быть достаточно гладкими - иметь непрерывно изменяющуюся касательную

3) Как чдолжен быть организован поиск нужной кривой в выделенном классе? Наличие эффективного алгоритма построения кривой определит нужный выбор -поиск должен быть сравнительно легким.

4) Сколько точек максимально определят кривую или поверхность? Для достаточно больших массивов точек найденные кривые или поверхности должны вести себя вполне предсказуемо.

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

пространства я „Л*) . Представление в виде суммы усеченных

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

п

р

/7=0

х е [X;, хм ], г=0,. Л^-1 (зл)

5^00 _ П . V

где ' - это сплайн степени дефекта

V е 5?,0 < V < я + 1 д

( ) с узлами на сетке . И

Сп п

, где ^ - множество раз

с-\

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

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

5(х)= ¿¿УВД (3.2)

р = !-П

*:_.(*)+ в'«{х). (з.з),

л/+" х/ х/+//+1 х1+1 Учитывая рекуррентное соотношение (3.3), сплайн (3.2) выражается через В -сплайны более низких степеней с коэффициентами:

ад- ^\х)вих)

р=1-п+1

где

р-1

Хрьт-1-т ~Хр Хр±пй-т ~Хр

3.4).

'О

Так как

ад

О,

= Ь1п)(х), хе[х,,хм)

(3.5).

Следовательно, 1 4 " 1 '' /+|'. Тогда по

формулам (3.4) строится матрица:

ьт

1-П

¿(0) и1-п+1 к

к

к м

Ъ\я\х)

(З.б)

Искомым значением коэффициента 8(х) будет " (х) .

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

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

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

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

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

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

Тезаурус Наименование

Массив для накопления данных v_float* data;

Адрес буфера записи данных BYTE* address;

Число транзакций при осреднении int n trans;

Счетчик транзакций int i_count;

Фильтровать группу данных do_filtering()

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

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

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

Тезаурус взаимодействия графических примитивов и ячейки основан на перечислении состояний взаимодействия произвольного графического примитива (п. 1):

GRAZE, // касательная к ребру ячейки -

единственная общая точка

PASS. //двойное (нормальное) пересечение

GRAZE_2,, // две общие точки касания

Максимальное количество касаний полигоном ячейки равно

двум.

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

Выявлены данные и операции, определяющие унификацию ячейки пространства.

1) Упорядочить каждую ячейку. Их порядковые номера в двухмерной матрице- i,j - обеспечат доступ к полному пространству отображения.

2) Задать массив хранения полигонов в ячейке.

3) Задать флаг fjsct для контроля над количеством точек пересечения ячейки полигоном, а также флаг состояния записи в клетку f_write .

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

В четвертой главе детально описаны структуры построения и функционирования сложных САПР. Разработаны алгоритмы и создано программное обеспечение для преобразования и визуализации объемных геометрических моделей, представленных в международном стандарте STEP (STEP-вьюер); комплекс программных средств по управлению испытаниями сложных объектов (ПКУИ); подсистема визуализации мониторинга экологической обстановки при уничтожении химического оружия.

1. При проектировании системы 3D STEP-вьюера, основная проблема заключалась в выборе «правильного» способа отображения сложных 3D объектов, для чего проведена структурная классификация STEP-моделей.

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

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

Файл

Блок

Блок J

фильтрации j-г

данных р——

Блок | хранения ) |первичных Г данных

операции кодирования

блок |

хранения сортированных данных

Блок хранен 3D-M ш эделей

Блок визузг изации

Рис. 1. Схема функционирования STEP- вьюера.

В рамках проведенной структурной классификации 8ТЕР-моделей основными типами реализации были выбраны следующие типы.

Полное, законченное математическое представление формы детали, в котором все ее внутренние точки соединены (80ЬЮ_М(ЮЕЬ). Пустоты представляются закрытыми оболочками (с1озес1_8Ье11), которые определяют так, что нормали оболочки указывают внутрь пустот (МАТЧ41Р0Ь0_80ЬГО_ВК.ЕР-МАМР0ЬО_8ОЬт_ВОШОАЯУ^РКЕ8ЕЫТАТ1(Ж-ваЕРзатн_Уот8).

Простая форма граничного представления модели, в которой все части поверхностей являются плоскостями, а все ребра являются прямыми линиями (РАСЕТЕО_В11ЕР-

РАСЕТЕО^АШРОЬО_ВОиШАКУ^ЕРКЕ8ЕЫТАТ1<т

Модель описывается набором открытых или закрытых оболочек размерности 2 (8НЕЬЬ_ВА8ЕО_8ШРАСЕ_МСЮЕи.

Каркасное представление механических частей детали содержит информацию только о пересечении поверхностей, формирующих границу детали, но не должно содержать информацию о самих поверхностях ^ЩЕРЯАМЕ^МСЮЕЬ).

Сущность используют для передачи моделей, когда топологическая структура не задана (GEOMETRIC_SET). Геометрические элементы, которые составляют геометрический набор: точки, кривые и поверхности.

Объединение двумерных и трехмерных точек и кривых (GEOMETRIC_CURVERSET), не содержащее поверхностей.

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

Для каждого вида кривой и поверхности существует собственный механизм развертывания, иначе говоря, преобразования 3-D точки в её плоский образ. Здесь является важным определение системы координат связанной с конкретной поверхностью. В случае, когда имеется цилиндрическая поверхность, система координат задается центром основания цилиндра, осью вращения, а также направлением, указывающим нулевой угол отсчета. . В случае, когда имеется цилиндрическая поверхность, система координат задается центром основания цилиндра, осью вращения, а также направлением, указывающим нулевой угол отсчета. Чтобы получить плоский образ 3-D точки, принадлежащей данной цилиндрической поверхности, требуется, используя локальную систему координат, найти полярные координаты точки, затем, легко получаются результирующая точка:

Х=Р*<Р ,

Y = z.

Иногда могут использоваться дополнительные ограничения на расположение результирующей точки на плоскости. Например, ограничение границ плоского образа; удобно применять сегмент [1,1], при этом левая граница соответствует углу ~ 71, а правая -ж . И так, точка за точкой преобразуются все 3-D кривые, ограничивающие данную цилиндрическую поверхность, в том числе - границы отверстий.

Аналогичным образом следуют при нахождении алгоритма

разбиения & -сплайновых поверхностей, имеющих подобные

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

данную ^-сплайновую поверхность как упорядоченную совокупность плоских планов, кривая, принадлежащая этой поверхности, будет состоять из кусков, каждый из которых лежит в определенном плане и может быть своевременно обработан в рамках этого плана. Оказалось удобным представлять поверхность в виде плоской равномерной матрицы (mXn) с горизонтальным и вертикальным размером равным единице. Размер каждой ячейки такой матрицы будет зависеть от количества Х- и Y- разбиения. Каждая ячейка при том однозначно соответствует определенному плану.

Исходные требования к методу отображения исчерпывались условием максимальной концентрации информации, которая успешно реализована через интерфейсы DIRECT3DRM, а также условием независимого и централизованного доступа к отдельным элементам и свойствам графического образа 3D объекта.

Основной проблемой в решении организовать определенным образом рабочее пространство - есть и остается проблема времени чтения больших файлов. В случае STEP - файлов основные временные затраты, установленные путем многократного тестирования, приходятся на операции кодирования (БОК) и составляют относительную величину более 16/1.

Найденный способ решение этой проблемы - установление внешнего (пользовательского) контроля над процессом работы программы. Это организовано в виде непрерывной строки время-состояние внутренней базы данных 3D- объекта, расположенной в статус - строке главного окна программы. Программа выставлена на сайте и свободно распространяется через сеть Интернет. Кроме того, она совместно распространяется с системой расчетов методом конечных элементов «Зенит-95».

2. Реализован комплекс программных средств по управлению испытаниями разгонных блоков РКТ (ПКУИ), созданный в рамках совместной работы с заводом им. Хруничева.

Следует отметить наиболее важные вопросы, возникшие на этапе проектирования и программирования ПКУИ. Это -периодическая визуализация (по таймеру) схем объектов испытания средствами WINDOWS GDI; сетевая передача блоков данных посредством протокола NETBIOS; реализация модуля фильтрации

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

Программный комплекс, реализующий построение и взаимодействие модулей динамической модели объекта, должен учитывать следующие её особенности:

-характер поступающих на вход программной системы данных;

-качество каналов связи с объектом;

-наличие алгоритмов фильтрации поступающей информации;

-присутствие фактора времени обработки текущих данных;

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

I бто* вывода и визуализации

Рис. 2. Схема функционирования ПКУИ.

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

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

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

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

3. Создано программное обеспечение для осуществления мониторинга экологической обстановки.

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

Управление процессом визуализации осуществляется путем включения кнопок с названиями - «Выбор вещества», «Таблица параметров», «Графики», «Метеостанция», расположенных на основных и вспомогательных полях мнемосхемы.

В приложениях приведены избранные тексты программной реализации ЭТЕР-вьюера и комплекса программных средств по управлению испытаниями сложных объектов (ПКУИ). Представлены изображения сложных машиностроительных объектов, визуализированных посредством БТЕР-вьюера. Приведены также виды рабочего состояния ПКУИ в момент слежения за потоком текущей информации.

Заключение.

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

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

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

3. Проведен анализ структур данных, используемых в САПР. Проведена систематизация структур данных по способам кодирования и точности представления информации. Введено понятие полноты неявных алгоритмов, в соответствии с которым разработаны алгоритмы и программное обеспечение взаимных преобразований наиболее распространенных в САПР форматов данных. Программное обеспечение выставлено на сайте для свободного распространения в сети Internet.

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

5. Проведен анализ основных алгоритмов по работе с 2D и 3D моделями объектов в САПР. На примере реализации

недетерминированных алгоритмов пересечения сплайнов первой степени, замкнутых контуров, триангуляции 2D контуров по методу Сейделя показана результативность использования естественноязыкового тезауруса их операций и операндов. Недетерминированность алгоритмов присутствует при автоматической обработке контуров, без вмешательства человека в процесс обработки, и объясняется трудностью предсказания конфигурации ломаных линий контуров при их последовательном просмотре. С использованием естественно-языкового тезауруса разработаны оригинальные алгоритмы и программное обеспечение автоматической обработки контуров. Программное обеспечение распространяется в составе комплексов «Графика-81» и «Графика-01-Т».

6. Проведен анализ международного стандарта STEP для описания объемных геометрических моделей объектов. С использованием методов проектирования полученных в диссертационной работе разработаны алгоритмы и создано программное обеспечение для визуализации STEP моделей. Программное обеспечение выставлено на сайте для свободного распространения в сети Internet и внедрено на ряде машиностроительных предприятий.

7. С использованием полученных в диссертационной работе методов проектирования разработаны алгоритмы, общие структуры, структуры данных и программное обеспечение систем визуализации параметров в процессе испытания разгонных блоков РКТ и визуализации параметров при уничтожении химического оружия. Системы STEP-вьюер, программный комплекс управления испытаниями (ПКУИ), подсистема визуализации мониторинга экологической обстановки внедрены. Получены акты о внедрении.

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

1. Артамонов Е.И., Разумовский А.И., Шурупов A.A. Система проектирования каминов. Автоматизация проектирования, 4, 1998, с. 33-40.

2. Артамонов Е.И., Высотин О.В., Разумовский А.И., Макаров A.M., Шурупов A.A. Объемное геометрическое моделирование орбитального комплекса «МИР». Автоматизация проектирования, 4, 1998, с. 3-8.

3. Разумовский А.И. Комплекс программных средств по управлению испытаниями сложных объектов. Материалы международной конференции CAD/CAM/PDM-2002, с. 395-399.,ISBN 5-201-14937-5

4. Разумовский А.И. Анализ и исследование разработки алгоритма пересечения контуров. Материалы международной конференции СAD/CAM/PDM-2003, ISBN 5-201-14954-5.

5. Разумовский А.И. Ассоциация частных алгоритмов. Материалы международной конференции С AD/C AM/PDM-2003, ISBN 5-201-14954-5.

6. Разумовский А.И. Исследование и построение алгоритма треангуляции произвольных полигонов. Материалы международной конференции С AD/C AM/PDM-2003, ISBN 5-201-14954-5.

7. Артамонов Е.И., Разумовский А.И., Ромакин В.А., Зверков В.В., Петухов В.В.. Сравнительные характеристики средств виртуальной реальности на примере моделирования эргономических характеристик пультов безопасности АЭС. Материалы международной конференции С AD/C AM/PDM-2003, ISBN 5-20114954-5.

8. Артамонов Е.И., Разумовский А.И., Ромакин В.А., Ефремов И.С., Чернявский А.Г., Федосеев А.И. Использование средств виртуальной реальности при моделировании конструкции Большого Космического Рефлектора. Материалы международной конференции CAD/CAM/PDM-2003, ISBN 5-201-14954-5.

9. Разумовский А.И Использование метода "тезауруса" при проектировании систем с недетерминированными алгоритмами CAD/CAM/PDM-2004, ISBN 5-201-14977-4.

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

В работах [1,2] - автором были созданы объемные геометрические модели крупногабаритных конструкций, в том числе модулей орбитальной станции «МИР», разгонного блока ракеты «Протон». В работах [3, 7, 8] - автором предложен метод организации структур геометрических данных для программных комплексов: STEP-вьюер, ПКУИ, а также использования средств виртуальной реальности. В работах [4,5,6,9] - автором разработаны алгоритмы для применения в САПР.

Зак. 65. Тир. 100. ИПУ.

РНБ Русский фонд

2006-4 19998

Содержание

Введение

Глава 1. Исследование принципов построения и методов проектирования 16 структур интерактивных систем

1.1 Сущность, виды и модели систем

1.2 Классификация и особенности программных интерактивных систем 18 1.2.1 Методы проектирования и программирования САПР

1.3 Образцы программирования сложных систем

1.3.1 Программирование через операции и программирование через объекты

1.3.2 Модели, используемые для проектирования САПР.

1.3.3 Стили построения архитектур сложных систем.

1.4 Жизненный цикл программной системы

1.5 Проблематика проектирования программных систем с 34 недетерминированными алгоритмами.

Актуальность темы

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

Известны исследования зарубежных ученых: Г. Буча, М. Шоу в области моделирования архитектур программных систем, К. Кнута, Г. Берна в области анализа и обобщения структур данных, а также отечественных ученых: Кульбы В.В., Косяченко С.А., Цвиркуна А.Д. по методам проектирования сложных систем обработки данных, Артамонова Е.И. по синтезу структур специализированных программно-аппаратных средств и т.п.

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

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

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

Отдельным вопросом является создание больших программных систем. Большая программная система - это крупное капиталовложение, и производитель и заказчик не может себе позволить выкидывать сделанное при каждом изменении внешних требований, хотя и здесь наблюдаются тенденции к эволюции. Сложная программная система иерархична, и уровни этой иерархии представляют различные уровни абстракции, причем один будет надстроен над другим и каждый может быть рассмотрен отдельно. Каждому уровню абстракции соответствует набор устройств, которые совместно обеспечат функции высокого и низкого уровней. Одновременно, каждый из абстрактных элементов системы несет в себе «отпечаток» хранения, доступа и передачи информации.

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

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

При создании таких систем большое внимание уделяется разработке стандартов по методологии организации систем, стандартов на неизменные части систем и на структуру данных для обмена с прикладными частями. Таким образом разработан международный стандарт по CALS-технологиям. При проектировании программного обеспечения получила распространение CASE-технология (Computer- Aided Software Engineering), техника и средства структурного анализа SADT (Structured Analyzes and Design Technique), включающего метод интегрального описания, интегральной спецификации IDEF (Integrated Computer Aided DEFinition method), стандарт для описания данных об изделии (STEP), стандарты представления текстовой информации (SGML) и графики и т.п.

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

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

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

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

Цель и задачи исследования

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

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

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

Анализ и разработка методов структурной организации и математических моделей ПрИС.

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

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

Методы исследования

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

Научная новизна

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

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

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

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

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

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

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

Практическая ценность работы

Исследования, выполненные в диссертации, осуществлялись в рамках следующих НИР "Разработка программного обеспечения для геометрического моделирования крупногабаритных машиностроительных конструкций" (тема 318-96/18, per. номер 01.96.0009913) по заданию РАН, "Система моделирования и проектирования крупногабаритных конструкций" (тема 46597/18.) по заданию Миннауки РФ, "Интегрированные САПР"( 463-97/18) по заданию Миннауки РФ.

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

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

Эффективность разработанных в диссертационной работе концепций, методик и моделей подтверждена положительным опытом их применения при разработке ряда САПР для функционирования на заводе им. Хруничева и в НПО «Энергия». Также, кроме указанных работ, многие разработанные блока и модули инструментальных средств внедрены в состав комплексов программных средств ГРАФИКА-81, ГРАФИКА-97 и ГРАФИКА-2000, созданных в ИПУ РАН и использованных при конструировании сложных объектов.

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

Основные положения работы докладывались на международных конференциях САБ/САМ/РОМ-2002, САБ/САМ/РОМ-2003 и САБ/САМ/РОМ-2004, а также на научных семинарах лаборатории Института проблем управления РАН. Публикации.

По материалам выполненных исследований опубликовано 9 печатных работ.

Структура работы.

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

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

1. Проведен анализ международного стандарта STEP для описания объемных геометрических моделей объектов. С использованием методов проектирования полученных в диссертационной работе разработаны алгоритмы и создано программное обеспечение для визуализации STEP моделей - STEP-вьюер. Программное обеспечение выставлено на сайте для свободного распространения в сети Internet и внедрено на ряде машиностроительных предприятий.

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

3. Создана подсистема визуализации мониторинга экологической обстановки объекта ПУ-327. Геометрические и графические алгоритмы, разработанные с использованием метода тезауруса и унификации операций, были успешно применены для построения системы экологического мониторинга.

Заключение.

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

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

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

3. Проведен анализ структур данных, используемых в САПР. Проведена систематизация структур данных по способам кодирования и точности представления информации. Введено понятие полноты неявных алгоритмов, в соответствии с которым разработаны алгоритмы и программное обеспечение взаимных преобразований наиболее распространенных в САПР форматов данных. Программное обеспечение выставлено на сайте для свободного распространения в сети Internet.

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

5. Проведен анализ основных алгоритмов по работе с 2D и 3D моделями объектов в САПР. На примере реализации недетерминированных алгоритмов пересечения сплайнов первой степени, замкнутых контуров, триангуляции 2D контуров по методу Сейделя показана результативность использования естественно-языкового тезауруса их операций и операндов. Недетерминированность алгоритмов присутствует при автоматической обработке контуров, без вмешательства человека в процесс обработки, и объясняется трудностью предсказания конфигурации ломаных линий контуров при их последовательном просмотре. С использованием естественно-языкового тезауруса разработаны оригинальные алгоритмы и программное обеспечение автоматической обработки контуров. Программное обеспечение распространяется в составе комплексов «Графика-81» и «Графика-01-Т».

6. Проведен анализ международного стандарта STEP для описания объемных геометрических моделей объектов. С использованием методов проектирования полученных в диссертационной работе разработаны алгоритмы и создано программное обеспечение для визуализации STEP моделей. Программное обеспечение выставлено на сайте для свободного распространения в сети Internet и внедрено на ряде машиностроительных предприятий.

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

1. Артамонов Е.И., Хачумов В.М. Синтез структур специализированных средств машинной графики. М., Институт проблем управления.-1991.

2. Вендров A.M. Проектирование программного обеспечения экономических информационных систем, М., Финансы и статистика, 2000.

3. Артамонов Е.И., Разумовский А.И., Шурупов A.A. Система проектирования каминов. Автоматизация проектирования, 4, 1998, с. 33-40.

4. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление. М.

5. Моисеев H.H. Математика ставит эксперимент. М.: Наука, 1979- 222 с.

6. Тамм Б.Г., Пуусенн М.З., Таваст P.P. Анализ и моделирование производственных систем. М.: Финансы и статистика , 1987. - 191 с.

7. Краткая философская энциклопедия / Под ред. Е.Ф. Губенога, Г.В. Кораблева, В.А. Лутченко. -М.: Прогресс, 1994. с. 203-205.

8. Искусственный интеллект : в 3 кн., кн. 2 Модели и методы: Справочник/ Под ред. Д.А. Поспелова. М.: Радио и связь, 1990. - 304 с.

9. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ: учебное пособие для вузов. М.: Высшая школа, 1989. - 367 с.

10. Осуга С. Обработка знаний М.: Мир, 1989. - 293 с.

11. Силич В.А. Содержательные модели систем и их использование при проектировании АСУ. Томск.: ТГУ , 1984. - 115 с.

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

13. Искусственный интеллект: в 3 кн.: справочник / Под ред. Э.В. Попова. — М.: Радио и связь, 1990. 464 с.

14. Элти Дж., Кумбс М. Экспертные системы: концепции и примеры. — М.: Финансы и статистика, 1987. 191 с.

15. Поспелов Д.А. Логико-лингвистические модели в системах управления. -М.: Энергоиздат, 1981.-231 с.

16. А. Закис, Н. Приезжий, Системы сквозного проектирования., Материалы технической конференции "Корпоративные базы данных '97".

17. Абт К. И., Фостер Р.Н., Ри Р. Г. Методика составления сценариев. В кн. Руководство по научно-техническому прогнозированию. — М.: Прогресс , 1977.-С. 132-162.

18. Кант И. Критика чистого разума. . пер. с нем., изд. «ТАЙМ-АУТ», Санкт-Петербург, 1993., 478 с.

19. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. - 368 с.

20. Артамонов Е.И. Проектирование структур программных средств CAD/CAM систем. - Автоматизация проектирования, N2, 1997.

21. Богданов А. А. Тектология: (Всеобщая организационная наука). В 2-х книгах: Кн.1\2. Москва: Экономика, 1989.- 304X351.

22. Северилов В.А. Методы декомпозиции прикладных программ и процессов их разработки. Сб.науч.тр. Декомпозиционные методы проектирования систем. Киев. ИК им. В.М. Глушкова АН УССР, 1988, с 2132.

23. Боровская Т.Н. Синтез структур реконфигурируемых САУ. Сб.науч.тр. -Декомпозиционные методы проектирования систем. Киев. ИК им. В.М. Глушкова АН УССР, 1988, с 13-20.

24. Грицык В.В., Дубров Я.А., Домбровский Б.Т. Декомпозиционные методы в исчислениях систем и параллельной обработке информации. Сб.науч.тр. -Декомпозиционные методы проектирования систем. Киев. ИК им. В.М. Глушкова АН УССР, 1988, с 3-13.

25. Hoare C.A.R., Proof of a structured program: The sieve of Eratosthenes, Comp. J., 15, N 11, 1972, 321-325.

26. Hoare C.A.R., An axiomatic basic for computer programming, Comm. ACM, 12, 1969, 567-583.

27. Ройс Уокер., Управление проектами по созданию программного обеспечения., М., Лори. 2002, 425 с.

28. М. М. Горбунов-Посадов., Расширяемые программы, М.,Полиптих, 1999,336 с.

29. Гегель Г. Наука логики. Ч. 1. М., 1970.

30. Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. -М.: Диалог- МИФИ, 1996. 240 с.

31. Wegner P. Dimensions of object-oriented modeling. IEEE Computer 25(10) 1992, pp. 12-19.

32. Элиенс А. Принципы OO разработки программ. «Вильяме» M.2002. 496 с.

33. Зиглер К. Методы проектирования программных систем. М. Мир, 1985.

34. Сэлтон Г. Автоматическая обработка, хранение и поиск информации. -М.: Сов. радио , 1973. 560 с.

35. Проблема программно-целевого планирования и управления. / Под ред. Поспелова Г.С. М.: Наука, 1981. - 464 с.

36. Поспелов Д.А. Моделирование рассуждений. М.: Радио и связь , 1989. -183 с.

37. Маслов С.Ю. Обратный метод установления выводимости в классическом исчислении предикатов. ДАН СССР, 1964. Т. 159. - С. 17-20.

38. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем. М.: Мир , 1973. - 344 с.

39. Бар Р. Язык Ада в проектировании систем. М.: Мир , 1988. - 320 с.

40. Керрол JI. История с узелками. М.: Мир , 1973. - 407 с.

41. Поппер К. Логика и рост научного знания. М.: Прогресс , 1983. - 608 с.

42. Ковальски Р. Логика решения проблем. М.: Наука , 1990. - 280 с.

43. Рубцов С.В. Системы управления бизнес-процессами и корпоративная культура. PC WEEK/RE, N47, 2001, с.32.

44. On the criteria to be used in decomposing systems into modules, Commun. Ass. Comput. Mach.,Vol.l5, PP 1053-1058, Dec. 1972.

45. D.L.Parnas, D.p.Siewiorek, Use of transparency in the design of hierarchically structured systems, Commun. Ass. Comput. Mach.,Vol.18, PP 401-408, July. 1975.

46. Baines R.W., Colquhoun G.J. An integration and analysis tool for engineers. -Assembly Automation, Aug 1990.

47. Stat S.B. ШРО and Integrated Program design. IBM System J., 1976, N2, P143-154.

48. Zachman J. A framework for information architecture. IBM systems journal, V26, N3, 1987.

49. McClur C. The CASE Experience BYTE, 1989, April, P235-245.

50. An introduction to SADT. SofTech, Inc., Waltham, MA 1976.

51. Godwin A.N., Gleeson J.W., Gwillian D. An assessment of the IDEF notations as descriptive tools. Information systems, V14, N1, P13-28, 1989.

52. Papalambros Fanos Y., Chirebdast Mehran . An integrated environment for structural configuration design. J.Eng.Des. 1990, N1, P73-96.

53. Banerjee S.K. Information systems design for computer integrated manufacture a methodology. - Production management and manufacturing technology, 1991, C79-100.

54. Норенков И.П. Разработка САПР. Издательство МГТУ им. Баумана, 1994.

55. D.L.Parnas On the Criteria To Be Used in Decomposing Systems into Modules, Commun. Ass. Comput. Mach., Vol. 15, No. 12, December 1972 pp. 1053 1058.

56. Э.Дейкстра. Дисциплина программирования., M., Мир, 1978, 275 с.

57. Д. Грис Наука программирования. М.: Мир, 1984. - 289 с.

58. М. Shaw, R. DeLine, D. Klein, T. Ross, D. Young, G. Zelesnik. Abstraction for Software Architecture and Tools to Support Them. IEEE Transactions on Software Engineering, Vol. 21, No. 4, 1995.

59. Liskov B.H., Zilles S.N. Programming with abstract data types, ACM Sigplan Notices 9, pp 50-59.

60. Liskov, B. A Design Methodology for Reliable Software Systems, in Tutorial on Software Design Techniques. Third Edition. New York, NY: IEEE Computer Society, 1980, p.66.

61. Parnas, D. L., Clements, P. and Weiss, D. The Modular Structure of Complex Systems. IEEE Transactions on Software Engineering, March 1985, vol.SE-11(3), p.260.

62. S. Kumar and D. Manocha. Interactive display of large scale NURBS models. Technical Report TR94-008, Department of Computer Science, University of North Carolina, 1994.

63. R. Seidel. A simple and fast incrémental randomized algorithm for Computing trapezoidal décompositions and for triangulating polygons. Computational Geometry: Theory and Applications, 1(1): 51-64, 1991.

64. Dani Lischinski. Incrémental Delaunay triangulation. In Paul Heckbert, editor, Graphics Gems IV, pages 47-59. Academic Press, Boston, 1994.

65. A. Narkhede and D. Manocha. Graphics Gems 5, Editor: Alan Paeth, Academic Press, 1995.

66. Артамонов Е.И., Загвоздкин B.A., Шурупов A.A., Щегольков М.Ю. Языки взаимодействия пользователя с ЭВМ в системе «Графика-81». М., Институт проблем управления.-1993.

67. Артамонов Е.И., Исмаилов Ш-М.А., Кокаев О.Г., Хачумов В.М. Специализированные алгоритмы и устройства обработки массивов данных. Махачкала, Дагестанское книжное издательство.-1993.

68. Артамонов Е.И., Высотин О.В., Разумовский А.И., Макаров А.М., Шурупов А.А. Объемное геометрическое моделирование орбитального комплекса «МИР». Автоматизация проектирования, 4, 1998, с. 3-8.

69. Разумовский А.И. Комплекс программных средств по управлению испытаниями сложных объектов. Материалы международной конференции CAD/CAM/PDM-2002, с. 395-399.,ISBN 5-201-14937-5

70. Разумовский А.И. Анализ и исследование разработки алгоритма пересечения контуров. Материалы международной конференции СAD/CAM/PDM-2003, ISBN 5-201-14954-5.

71. Разумовский А.И. Ассоциация частных алгоритмов. Материалы международной конференции С AD/CAM/PDM-2003, ISBN 5-201-14954-5.

72. Разумовский А.И. Исследование и построение алгоритма треангуляции произвольных полигонов. Материалы международной конференции С AD/CAM/PDM-2003, ISBN 5-201-14954-5.

73. Dijktra, Е. 1979. Programming Considered as a Human Activity. Classics in Software Engineering. New York, NY: Yourdon Press, p.5.

74. Pamas, D. December 1985. Software Aspects of Strategic Defense Systems. Communications of the ACM vol.28(12), p. 1328.

75. Г. Буч, Якобсон А. Унифицированный процесс разработки программного обеспечения., Питер, 2002.

76. Холл А.Д. Опыт методологии для системотехники. М.: Сов. радио, 1975.-448 с.

77. Уинстон П. Искусственный интеллект. М.: Мир , 1980. - 519 с.

78. Разумовский А.И Использование метода "тезауруса" при проектировании систем с недетерминированными алгоритмами CAD/CAM/PDM-2004, ISBN 5-201-14977-4.

79. Кульба В.В., Микрин Е.А., Павлов Б.В. Проектирование информационно- управляющих систем долговременных орбитальных станций, М., Наука, 2002, 350 с.

80. Кульба В.В., Кононов Д.А., Косяченко С.А., Шубин А.Н. Методы формирования сценариев развития социально- экономических систем, М., СИНТЕГ, 2004, 255 с.