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

.-.0 OA

- / Uui Ш На правах рукописи

ргб од

- LWAP-2000-

СИРОТА ИЛЬЯ МИХАЙЛОВИЧ

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ ПОДДЕРЖКИ ВИЗУАЛЬНОГО КОНЦЕПТУАЛЬНОГО МОДЕЛИРОВАНИЯ ПРОЕКТНО-КОНСТРУКТОРСКИХ ЗАДАЧ ПРИ СОЗДАНИИ САПР МАШИНОСТРОИТЕЛЬНОГО НАЗНАЧЕНИЯ

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

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

МОСКВА 1999

Работа выполнена на кафедре «Информационные технологии вычислительные системы» Московского Государственного Технологическс университета «СТАНКИН»

Научный консультант Официальные оппоненты

Ведущее предприятие

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

доктор технических наук,

профессор

Фролов В.П.

кандидат технических наук Бикулов С.А.

ОАО «НПО ЭНЕРГОМАШ»

Защита состоится « 1999 г. в час. мин.

заседании Диссертационного Совета Д Й63.42.02 Московского Государствен» Технологического университета «СТАНКИН».

Отзывы (в двух экземплярах, заверенные печатью учреждения) прос направлять по адресу: 101472, ГСП, г. Москва, Вадковский пер., Диссертационный Совет Д 063.42.02.

С диссертацией можно ознакомиться в библиотеке МГТУ «СТАНКИН». Автореферат разослан «-22» 1999 г.

Ученый секретарь

Диссертационного Совета Д 063.42.02 к.т.'.к (ул'с" Семячкова]

¡(5^64-5-05,0

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

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

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

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

К новым подходам в области автоматизации проектирования относится методология автоматизации интеллектуального труда (МАНТ), поддерживающая создание автоматизированных систем промышленным способом.

Процесс проектирования САПР на основе МАИТ (рис. 1.) обладает рядом преимуществ: -последовательное отображение формальных моделей

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

Рис. 1. Процесс создания САПР.

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

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

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

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

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

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

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

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

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

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

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

Научная новизна заключается в следующем:

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

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

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

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

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

Апробация работы. Результаты работы использовались при проведении лабораторных работ по дисциплине «Технология создания

автоматизированных систем» для специальности 22.03, неоднократно обсуждались на заседаниях кафедры «Информационных технологий и вычислительных систем». По материалам работы был сделан доклад на открытой научной конференции МГТУ «СТАНКИН» и учебно-научного центра Математического моделирования МГТУ «СТАНКИН» и ИММ РАН в апреле 1999 г.

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

Структура и объем работы диссертация состоит из введения, 5 глав, заключения, списка литературы (83 наименования) и 2 приложений. Работа содержит 198 страниц сквозной нумерации, включая 17 рисунков. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1. Анализ существующих методов и средств визуального моделирования при создании прикладных автоматизированных систем

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

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

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

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

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

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

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

Анализ показал, что универсальные системы, имеющие возможность настройки и охватывающие весь жизненный цикл системы (Oracle Designer, Silverrun), имеют высокую стоимость, их внедрение и эксплуатация требуют больших материальных и трудозатрат. Менее громоздкие пакеты (ERvvin, Power Designer) не позволяют провести полный цикл разработки системы, и ориентированы на методологию, поддерживающую определенный его этап. Общим для всех типов систем является жесткая привязка к аппаратно-программным средствам и отсутствие программно-независимого модельного представления.

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

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

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

- проектное решение может быть многовариантным в силу большого объема вычислительной обработки; '

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

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

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

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

Глава 2. Уточнение формального описания концептуального представления предметной задачи

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

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

КР(п) = {КР2(п),КРЗ(п)),

где KP2{ri)~ концептуальная модель n-ой предметной задачи на объектном уровне;

КРЗ(п) = {КРЗ(пт)},

где КРЗ(пт)- концептуальная модель конкретного уровня ш-ой реализации n-ой предметной задачи.

Концептуальная модель любого уровня для n-ой предметной задачи имеет вид:

KPi(z) = (Mi(z),THi(z),Fi(z)),

где z=n описывает концептуальную модель для n-ой предметной задачи объектного уровня (i=2), a z=nm описывает концептуальную модель для ш-ой реализации n-ой предметной задачи конкретного уровня (i=3).

М2(п) = А(п) - {аы} - множество предметных категорий (ПК) и

М2{пт) s В(пт) = {b'J} - множество экземпляров предметных категорий (ЭПК) для выбранной предметной задачи.

THi(z) = (Ti(z),Hi(z),Hi(z),Thi(z)) - множество статических отношений на категориях данной задачи, Ti(z) с Mi{z) х Mi(z) - множество бинарных отношений на категориях, Hi(z) с Mi(z) х Mi(z) х Mi(z) -множество тернарных отношений на категориях, Hi{z) - множество схем категорий и Thi(z) с Hi{z) х Hi(z) - множество бинарных отношений на схемах категорий для реализации предметной задачи.

Fi(z) = (Vi(z),FVi(z)) - множество динамических отношений данной предметной задачи. V2(n) = W(n) = {w^} - множество предметных зависимостей, V3(jim) = Р(пт) = {prh} - множество экземпляров предметных зависимостей, FVi(z) с Vi(z) х Vi(z) - множество бинарных отношений на множестве зависимостей.

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

Для объектного уровня:

Так как V2(п) = IV(п); Щп) = (JWs(и); Ws(п) = {wrv},TO

S

FV2(n) = {LWs{n),LWs(ri)Wt(и),LW,(n)IWs{n)}, где

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

Для конкретного уровня:

Так как У3(пт) - Р(пт); Р(пт) = У]Р(пт); Р^(пт) = {рп1}, то

РУЗ(пт) = {¿Р„ (пт),ЬР„ (пт)Р5, {пт)£Ра (пт) / />„ (ши),

ЬР„ (пт)Рт (пт\ЬР„ (пт)Ррп(пт)1 Р„ (пт)},

где (пт)Р„(и/«) = {(/>„,,еР„(пт),р,цеРи(пт)}

При этом соотношение между экземплярами предметных зависимостей и экземплярами предметных категорий описывается следующим образом:

«яг

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

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

Схематично это можно представить: Ю -> К(} + 1), / = 2, то есть:

^2-^3: К2->ГЗ, РУ2->ГУЗ

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

К,.**) -> ЬР„{пт)Р„(тп) = {(р^р^)},ЬР^(пт)Рп(пт) с ГУЗ(пт)

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

вРУЗ = вУ2УЗ >< GFF2 хвУ 2УЗ

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

Для объектного уровня интеграция функциональной составляющей формально представлена следующим образом:

п п

Для конкретного уровня интеграция представляется:

Р0 = иДит); РУ30 = \jFVXnm)

я ,т п,т

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

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

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

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

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

<7/>(л) = (<7Р2(л), вРЗ{п)), где СР2(/?) - математическое описание визуального представления для концептуальной модели объектного уровня для п-ой задачи.

СРЗ(п) = {СРЗ(пт)}, где СРЗ(пт) - математическое описание визуального представления для концептуальной модели конкретного уровня для реализации ш задачи п.

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

ОР/(2) = {Сг,(2)}, где каждый из графов отражает соответствующую концептуальную конструкцию: концептуальную структуру на категориях, концептуальную структуру на схемах категорий, структуру зависимостей и увязку категорий и зависимостей.

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

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

Табл. 1. Состав формального описания визуальных концептуальных моделей_'_. 7' •_

Тип графа Прообраз Вершины Ребра

Т=К5 понятийный граф (М',Г/) Объектный уровень Уквг Конкретный уровень Укзз = Объектный уровень Конкретный уровень

Т=К8Б граф структуры схем предметных категорий (.т,тт) Объектный уровень Конкретный уровень Объектный уровень Конкретный уровень

т=Бг функциональный граф (/¡,РУг) Объектный уровень Узг 2(«)=.^2} Конкретный уровень Объектный уровень Конкретный уровень Езп{пт) = {е™}

т=кг содержательный граф Объектный уровень у кг 2(«.0 = ^2} Конкретный уровень Объектный уровень Екгг{пЛ) = {е%2} Конкретный уровень Еаз(пт,к1) = {е™)

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

1) для понятийного графа Сг^С") = (")) наличие

непересекающихся классов ПК определяет разбиение множества вершин на непересекающиеся подмножества:

• V,,

Ю2

И

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

ЕКБ2 (И) = Е^КБ2 (") (") ^ (")

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

Общий вид понятийного графа предметной задачи представлен на рис. 2, б).

2) для графа структуры схем предметных категорий Ск^2(п) = С(Укз32(п),ЕК552(п)) наличие непересекающихся классов схем ПК определяет разбиение множества вершин на непересекающиеся подмножества:

Г2 КХ52

"и

Гш2(") = 00,^(л) П У^п) = 0,

I

Наличие непересекающихся классов бинарных связей между схемами ПК определяет разбиение множества ребер на непересекающиеся подмножества:

(и)

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

3) для функционального графа С522(") = С(У$22(п),Е522 (л)) (рис. 3, б)) разбиение множества вершин на непересекающиеся подмножества определяет наличием непересекающихся подмножеств предметных зависимостей:

Непересекающиеся подмножества бинарных связей ПЗ отображаются в виде непересекающихся подмножеств ребер графа:

Е322 (и) = Е\22 (И) и Е^22 (И) и Е121 (И)

При этом ребра первого типа соответствуют связям вида "упорядочивание", ребра второго типа - связям «состав», ребра третьего типа - связям вида «компоновка».

21.1_

Определение массы инструментального блока с инструментальной бабкой

т2Л ¿22

Определение массы Определение

—^ инструментальной массы

бабки привода

¿2.2

г2А

Определение массы электродвигателя

Расчет массы всего инструментального блока

гЗЛ

Формирование обозначения инструментальной бабки по ее типу

сверлильная расточная фрезерная

г3.2

гЗ.З

г3.4

г4.1

Формирование обозначения (вида УЕ412_)

а)

Выбор габарита инструментальной бабки

б)

Формирование полного

обозначения инструментальной бабки

г4.2 тА.З г

Формирование обозначения (вида УЕ411_) Формирование обозначения (вида УЕ413_)

Выбор массы инструментальной бабки по обозначению

1 гКитТ1^ПТГЛ»»П ПТ ЧЛ М

За; функцио станка а цача нирования ■регатного

kl.l г

Условие -

kl.2

Средства

ol.l

o2.1

Деталь (заготовка)

a)

Узел

Ky

rl.l

r3.2

M.

■да

г7.1

kl.3 |

Цель

1:п

о2.2

о3.1

Сборочная единица (инстр. блок)

Деталь

М„

г7.3

Ои

Тпр ГиНБ Мщ. Ощш

г3.1 г5.1 г7.2 г2.1

КсЕ

М„

г2.2 rl.2 г7.4

)Hfr7.2Wr7.3Wr2.l)->(r2-2J

Рис. 3. Отображение понятийной структуры в понятийный граф

4) для содержательного графа GKZ7(n) = G(VKZ1(n), EKZ2 (л)) (рис/ 4, а)) множество вершин графа состоит из двух подмножеств: VKZ2(nm) = VxKZ1(nm) u V^ZJ(nm),VlKZ2(nm) n V£Z2 = 0

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

EKZ1{n,k) = {e%2)

KZ2 KZ2,KZ2\ KZ22-, ekm km \vij >vjv )

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

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

• определение типологии вершин функционального графа, соответствующих простым предметным зависимостям;

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

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

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

Компонент Средства

Объект Узел СЕ

Признак Ку Тпр ТиНБ Гин Б Млв МПр Мине ОиНБ1 Оин Б2 КСЕ Мин БЛ

21.1 г

т2А Г

г3.1 *

г4.1 *

х4.2 *

г4.3 *

г3.2 • • *

гЗ.З • • *

г3.4 ч •

г2.2 • • +

г2.3 • *

г2.4 • • • • *]

б)

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

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

(вида 2). Признаком простой вершины у^р графа будет соотношение для степени вершины <3е§222(у^2) = 1. При > 1 вершина у^22

будет сложной.

Пусть имеется простая вершина у^р графа С822 (п). На графе 0К22{п) с ней связан набор вершин, и^, которые, в свою очередь, задают подмножество вершин 6-го уровня графа • это подмножество

вершин опирается подграф Сх52(и,5у) графа С7Л31(п). Тип простой вершины у^2 определяется уровнем замыкающей вершины подграфа Ск32(п). Для того, чтобы формально определить тип простой вершины, нужно сформировать подграф («,лу) и определить уровень его замыкающей вершины (рис. 5, подграф для вершины с).

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

1. Для каждой вершины выделенного по содержательному подграфу набора ип выполняется построение пути до корневой вершины понятийного графа

2. Для множества путей Р ={/>(у^?2)} анализируется количество

и

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

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

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

Табл. 2. Типология предметных зависимостей

Уровень замыкающей Класс Типология предметных

вершины подграфа соответствующей зависимостей в

понятийного графа ПК концептуальных моделях

1 Цикл З.Зн 1.1

2 Процесс 3.2

3 Задача 53= 3.1

4 Компонент 5.2

5 Объект 5.1

Функциональный граф

Понятийный граф „

;.......................... Дополнительный

подграф а для Ь и с

Содержательный граф Рис. 5. Дополнительная обработка

Замыкающая вершина содержательного подграфа для с

д Содержательный подграф для с

Вершины понятийного графа, связанные с ветииной с

Вершины понятийного графа, связанные с веошиной Ь Вершины понятийного графа, связанные с вешпиной а

Формирование понятийной структуры для сложных вершин функционального графа

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

Для решения поставленной задачи необходимо вначале рассмотреть процесс объединения понятийных подструктур для двух произвольных вершин функционального графа. Объединение производится по каждому уровню вершин подграфов. В общем случае замыкающие вершины исходных понятийных структур могут находиться на разных уровнях, поэтому для упорядочения процесса объединения необходимо сначала построить дополнительный граф GKS2(n'a)> содержащий замыкающую вершину для исходных подграфов. Процесс объединения осуществляется по каждому уровню вершин для дополнительного подграфа G^г(п,а) и подграфов для простых вершин G^^sr), GKS2(n>sk)> начиная с верхнего уровня подграфа GKS1(n>a)-

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

р\( KSI KS1 л = р\, KSI KS2 ï_sv*S2 KS2

.,KS2 _„КУ2 ЛК52Л, A52 ,,KS2 \_ *52/ KS2 „KS2 ч (л+1) у =iVl)/>e (Vjri >V(X+IW) = C (vyk ,V(J,+I)/)

объединение производится по закону идемпотентности X & X = X :

pi/ KS2 KS2 u dVV*52 ч

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

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

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

Последовательность:

О^м=1К11(1> (V*",о &... & г,) &...

/ I

Итерация:

I

Альтернатава:

-иЗД^.у® )Л ...& ^.(У«2^) & ...

/ I

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

Определение типологии сложных вершин функционального графа

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

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

Глава 4. Разработка методики визуализации концептуальных моделей проектно-конструкторских задач

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

В соответствии со структурой процесса создания САПР (рис. 1) концептуальное моделирование производится после этапа предпроектного обследования предприятия. Визуальное концептуальное моделирование является подвидом общего процесса концептуального моделирования. Работа с визуальным представлением системы знаний производится на

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

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

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

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

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

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

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

Свойства визуального представления понятийной структуры

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

проекта соответствует одной из пар уровней, имеющихся в иерархии предметных категорий: / и (/ + 1), где / = 1...5. На диаграммах имеется 12 ячеек по 6 в 2 строках.

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

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

Код диаграммы имеет вид Цкласс старших ПК] [номер листа]_[номер диаграммы в лист£],['10мср часхи диаграммы]. Номера частей диаграммы присваиваются им при разбиении понятийной конструкции между диаграммами. Код элемента диаграммы имеет вид [код класса ПК][код группы].[код в группе].[дополнительный код].

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

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

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

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

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

Код диаграммы имеет вид Цномер листа]_[номер строки диаграммы в листе].[номер столбца диаграммы]. Листы имеют уникальный целый номер в пределах проекта. Номер строки диаграммы равен номеру строки ее родительской диаграммы +1. Номер столбца - номер первой слева незанятой позиции в текущей строке.

Код элемента диафаммы имеет вид [латинская буква] [номер строки ячеек].[номер в строке]. Код элемента уникален в пределах листа.

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

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

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

Спецификации

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

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

1. Создание рабочего комплекта диаграмм.

2. Задание всех необходимых параметров диаграмм и их элементов.

3. Кодирование.

4. Создание спецификаций. Спецификации создаются на основе свойств диаграмм и их элементов.

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

6. Доработка. В случае выявления на предыдущем шаге неточностей в модели, модель дорабатывается.

Рис. 7. Структура этапа формирования концептуальной модели предметной задачи.

На этапе дополнительной обработки модели (рис. 8) производится определение типологии предметных зависимостей и расслоение модели по виду информации.

Рис. 8. Структура этапа дополнительной обработки концептуальной модели

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

1. Определение типологии простых предметных зависимостей. Результатом данного шага будет список простых предметных зависимостей с указанием их типа. Для его составления необходимо:

выделить все простые предметные зависимости, создать их список; задать текущую ПЗ;

определить тип текущей ПЗ в соответствии с предложенным алгоритмом;

занести текущую ПЗ в результирующий список;

если есть еще ПЗ, перейти к следующей, иначе закончить.

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

выделяются все сложные ПЗ, создается их список; производится ранжирование списка по вложенности ПЗ; задается текущая сложная ПЗ;

для текущей сложной ПЗ выделяются входящие в нее простые ПЗ; на основании предложенного алгоритма строится содержательная структура для текущей сложной ПЗ;

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

если есть еще сложные ПЗ, переход к следующей, иначе закончить.

3. Определение типологии сложных предметных зависимостей. Наличие полученной на предыдущем шаге содержательной структуры

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

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

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

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

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

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

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

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

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

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

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

В качестве среды и средств реализации были выбраны соответственно операционная система Windows 95/98/NT и язык С++.

Программный комплекс "CODA" состоит из двух основных частей -графического интерфейса пользователя (ГИП) и программного ядра. Действия пользователя воспринимаются ГИП и обрабатываются в ядре. Результаты работы ядра отражаются в изменениях внешнего вида

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

И соответствии со структурой программного комплекса, функции его ядра делятся на следующие группы:

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

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

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

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

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

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

Сопс«р1ид1 МосЫсг • [Определение массы инстр.бжжа1

Рис. 9. Фрагмент рабочего экрана

Код задачи | Код П3]~

Наименования ПЗ | Степень форм-и | Статус) Особое свойство П3| Замечания |

ВСЕ

15 0.0

15 00

21.1

22.1

Определение массы инструментального блока с инструментальной бабкой Определение массы инструментальной бабки

22 2 Определение массы привода

пр | пр |

►

15_0.0 22.3 Определение массы ста

электродвигателя

15_0 0 22.4 Расчет массы инструментального анл блока

15_0.0 23.1 Тип инструментальной бабки ста

ЭЛ I

пр ?

15_0 О Ц5_0 0 1_5_0 О 15_0.0 1-5_0 О 15 00

23 2 Выбор габарита инструментальной эмп бабки

23 3 Формирование полного обозначения ста инструментальной бабки

23.4 Выбор массы инструментальной ста бабки по обозначению

24.1 Формирование обозначения вида ста УЕ412_

24.2 Формирование обозначения вида ста УЕ411_

24.3 Формирование обозначения веда ста УЕ413

эл ]

эл /

эл /

эл /

Рис. 10. Форма РЗ для подзадачи.

Код задачи Код П31 Код П31 Код П31 Оценка связи Код связи Тип связи

► 15 0.0 21.1 22.1 21.1 а 21.122.121.1 сост

15 0.0 г2.1 г2.2 21.1 поел 22.122.221.1 коми

15 0.0 ¿2.1 г3.1 22.1 1 22.123.122.1 сост

15 0.0 г2.2 г2.3 21.1 поел г2.2г2.321.1 комп

15 0.0 г2.3 г2.4 21.1 поел 22.322.421.1 комп

15 0.0 г2.4 г1.1 21.1 1 22.421.121.1 сост

15 0.0 г3.1 г3.2 22.1 поел 23.123.222.1 комп

15 0.0 г3.1 г4.1 23.1 пер 23.124.123.1 сост

15 0.0 г3.1 г4.2 23.1 пер 23.124.223.1 сост

15 0.0 г3.1 24.3 23.1 пер 23.124.323.1 сост

15 0.0 г3.2 гЗ.З 22.1 поел 23.223.322.1 комп

15 0.0 гЗ.З г3.4 22.1 поел 23.323.422.1 комп

* 15 0.0 г3.4 г2.1 22.1 1 23.422.122.1 сост

Рис. 11. Форма Р4 для подзадачи.

На рис. 9 приведен фрагмент рабочего экрана программы, с диаграммой декомпозиции подзадачи «Определение массы инструментального блока с инструментальной бабкой». Автоматически получаемые спецификации подзадачи представлены на рис. 10 и 11. Полученная диаграмма и спецификации являются отображением формального описания этой же подзадачи, приведенного на рис. 2 б).

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

По теме диссертации опубликованы следующие работы:

1. Волкова Г.Д., Сирота И.М. Автоматизация проектирования прикладных систем. // «Автоматизация и управление в машиностроении», №7, 1999.

2. Волкова Г.Д., Сирота И.М. Графическое моделирование концептуальных представлений проектно-конструкторских задач, «Материалы открытой научной конференции МГТУ «СТАНКИН» и учебно-научного центра Математического моделирования МГТУ «СТАНКИН» и ИММ РАН», М., «Станкин», 1999, стр. 56.

Введение

Глава 1. Анализ существующих методов и средств визуального моделирования системы знаний проектно-конструкторских задач на этапе проектирования САПР.

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

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

1.1.2. Требования к методам визуального моделирования автоматизированных систем.

1.2. Особенности ' модельного представления проектно-конструкторских задач при проектировании САПР.

1.2.1. Отличительные особенности САПР

1.2.1.1. Особенности процесса проектирования

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

1.2.1.3. Новый подход к проектированию САПР

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

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

1.3.1. Общие положения

1.3.2. Обзор методологий визуального моделирования.

1.3.2.1. SADT (IDEF0)

1.3.2.2. IDEF

1.3.2.3. ERA/IDEFlx

1.3.2.4. IDEF

1.3.2.5. Метод диаграмм потоков данных

1.3.2.6. UML

1.3.2.7. DATARUN

1.3.2.8. Oracle CASE Method

1.3.2.9. SSADM

1.3.3. Визуальные нотации

1.3.4. Сравнение методологий

1.4. Обзор средств поддержки визуального проектирования

1.4.1. Общие положения

1.4.2. Характеристики САБЕ-средств.

1.4.2.1. Средства анализа

1.4.2.2. Средства анализа и проектирования

1.4.2.3. Средства проектирования баз данных

1.4.2.4. Средства разработки приложений

1.4.2.5. Средства реинжиниринга

1.4.2.6. Средства документирования

1.4.3. Сравнительный анализ САБЕ-средств

1.5. Использование средств визуального моделирования при создании САПР.

1.6. Выводы и цель работы.

Глава 2. Уточнение формального описания концептуального представления предметной задачи.

2.1. Состав концептуального представления предметной задачи.

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

2.2.1. Общие положения

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

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

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

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

2.5. Выводы.

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

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

3.2. Формальное описание визуального представления концептуальных моделей.

3.2.1. Общие положения

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

3.2.2.1. Общие положения

3.2.2.2. Формальное описание визуального представления структуры предметных категорий.

3.2.2.3. Формальное описание визуального представления структуры схем предметных категорий.

3.2.2.4. Формальное описание визуального представления структуры предметных зависимостей.

3.2.2.5. Формальное описание визуального представления взаимосвязей предметных зависимостей и предметных категорий.

3.2.3. Формальное описание визуального представления концептуальных моделей конкретного уровня

3.2.3.1. Общие положения

3.2.3.2. Формальное описание визуального представления структуры экземпляров предметных категорий.

3.2.3.3. Формальное описание визуального представления структуры схем экземпляров предметных категорий.

3.2.3.4. Формальное описание визуального представления структуры экземпляров предметных зависимостей.

3.2.3.5. Формальное описание визуального представления взаимосвязей предметных зависимостей и предметных категорий.

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

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

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

3.3.1. Общие положения

3.3.2. Определение типологии простых вершин функционального графа.

3.3.3. Формирование содержательной структуры для сложных вершин функционального графа.

3.3.4. Определение типологии сложных вершин функционального графа.

3.4. Выводы.

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

4.1. Концептуальное моделирование при создании

САПР машиностроительного назначения

4.2. Требования к визуальному представлению концептуальных моделей.

4.2.1. Особенности визуального представления

4.2.2. Восприятие визуальных образов

4.3. Состав визуального представления концептуальных моделей.

4.3.1. Общие положения

4.3.2. Свойства визуального представления понятийной структуры.

4.3.3. Свойства визуального представления функциональной структуры.

4.3.4. Свойства визуального представления содержательной структуры.

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

4.4.1. Общие положения

4.4.2. Формирование понятийных структур

4.4.3. Формирование функциональных структур

4.4.4. Формирование содержательной структуры

4.5. Дополнительная обработка визуальных моделей.

4.5.1. Определение типологии элементарных предметных зависимостей.

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

4.5.3. Определение типологии сложных предметных зависимостей.

4.5.4. Расслоение моделей под постоянную и проектную информацию.

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

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

5.2. Выбор программно-технических средств реализации.

5.3. Структура программного комплекса

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

5.3.2. Основные функции ядра

5.3.2.1. Функции моделирования

5.3.2.2. Функции формирования изображения

5.3.2.3. Функции анализа параметров модели

5.3.2.4. Функции работы с файлами проекта

5.3.2.5. Вспомогательные функции

5.4. Общие принципы функционирования разработанного программного комплекса.

5.4.1. Основные функции главного меню программного комплекса.

5.4.2. Рабочий экран и панели инструментов

5.4.3. Контекстные меню.

5.5. Работа в "CODA"

5.5.1. Основные действия пользователя "CODA" при работе с проектом.

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

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

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

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

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

- предпроектное обследование организации;

- проектирование САПР;

- подготовка реализации;

- изготовление САПР.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Анализ существующих методов и средств визуального моделирования системы знаний проектно-конструкторских задач на этапе проектирования САПР

Заключение и общие выводы

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

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

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

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

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

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

6. Разработана автоматизированная система поддержки визуального построения системы предметных зависимостей при создании САПР машиностроительного назначения. С использованием данного программного средства в АО «Мое СКВ АЛ и АС» была проведена разработка автоматизированной подсистемы проектирования узла стойка.

1.Калянов Г.Н. CASE структурный системный анализ (автоматизация и применение). М.: Лори, 1996

2. Мартинес Ф. Синтез изображений. Принципы, аппаратное и программное обеспечение. Пер. с франц. М.: Радио и связь, 1990. 192 с.

3. Организация взаимодействия человека с техническими средствами АСУ. В 7 кн. Кн. 4. Отображение информации; Практ. Пособие / В. С. Гасов, А. И. Коротаев, С. И. Сенькин. Под ред. В. Н. Четверикова. М. : Высш. шк., 1990. 111 с.

4. Разработка САПР. В 10 кн. Кн. 1. Графические системы САПР., А. В. Петров, В. М. Черненький; М. : Высшая школа, 1990. 148 с.

5. Гилой В. Интерактивная машинная графика: структуры данных, алгоритмы, языки. Пер. с англ./Под ред. Ю.М. Баяковского. М.: Мир, 1981.

6. Принс М.Д. Машинная графика и автоматизация проектирования. М.: Советское радио, 1975. 230 с.

7. Дейт Дж. К. Введение в системы баз данных. Киев: Диалектика, 1998. 784 с.

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

9. Чен П.П.Ш. Модель "сущность-связь" шаг к единому представлению о данных/СУБД, №3, 1995.

10. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем, М., Финансы и статистика ,1998

11. Автоматизированное проектирование и производство в машиностроении / Ю. М. Соломенцев, В. Г. Митрофанов,

12. A. Ф. Прохоров и др.; Под. общ. ред. Ю. М . Соломенцева,

13. B.Г. Митрофанова. М.: Машиностроение, 1986. 256 с.

14. Энкарначчо Ж., Шлехтендаль Э. Автоматизированное проектирование. Основные понятия и архитектура систем. Пер. с англ. М.: Радио и связь, 1986. 288 с.

15. Грувер М., Зиммерс Э. САПР и автоматизация производства. Пер. с англ. М.: Мир, 1987. 528 с.

16. Разработка САПР. В 10 кн. Кн. 7. Проблемы и принципы создания САПР. Практ. пособие / В. Е. Климов; Под ред. А. В. Петрова М.: Высшая школа, 1990. 142 с.

17. Разработка САПР. В 10 кн. Кн. 3. Проектирование программного обеспечения САПР. Б. С. Федоров, Н. Б. Гуляев; Под ред. А. В. Петрова. М. : Высшая школа, 1990. 134 с.

18. Корячко В.П., Курейчик В.М., Норенков И. П. Теоретические основы САПР: Учебник для вузов. М. : Энергоатомиздат, 1987. 400 с.

19. Соломенцев Ю.М., Волкова Г. Д. Представление знаний при автоматизации проектно-конструкторской деятельности / Межотрасл. научн.-техн. сб. «Техника. Экономика» Сер. «Автоматизация проектирования» М. : ВИМИ, 1994, вып.4, с. 3-6.

20. Джонс Дж. К. Методы проектирования. Пер. с англ. -М.: Мир, 1986. 326 с.

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

22. Разработка САПР. В 10 кн. Кн. 2. Системно-технические задачи создания САПР. А. Н. Данчул, Л. Я. Полуян; Под ред. А. В. Петрова. М.: Высшая школа, 1990. 126 с.

23. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М. Брейера. М.: Мир, 1977. 282 с.

24. Разработка САПР. В 10 кн. Кн. 8. Математические методы анализа производительности и надежности САПР. Практ. Пособие /В. И. Кузовлев, П. Н. Шкатов. Под ред. А. В. Петрова. М.: Высш. шк., 1990. 144 с.

25. IDEF1 Information Modeling. A Reconstruction of the Original Air Force Wright Aeronautical Laboratory-Technical Report AFWAL-TR-81-4023. Ed.: Mayer R. J., Knowledge Based Systems, Inc.

26. Mayer R.J., Menzel C.P., Painter M.K., deWitte P.S., Blinn T., Perakath B. Iformation integration for concurrent engineering (IICE) IDEF3 process description capture method report AL-TR-1995-XXXX., Interim technical report, 1995.

27. Integration definition for information modeling (IDEF1X) A standard announcement. Federal Information Processing Standards Publication 184, 1993.

28. Crompton P.N. Computer Systems: Standards Manual, Pitchmark Ltd, 1996.

29. Silverrun-ERX. Technical Papers. Silverrun Technologies Inc.

30. Быков В. П. Методическое обеспечение САПР в машиностроении. J1. : Машиностроение. Ленингр. Отделение, 1989. 255 с.

31. Тамм Б.Г., Пуусепп М.Э., Таваст P.P. Анализ и моделирование производственных систем. / Под общ. ред. Б. Г. Тамма. М.: Финансы и статистика,. 1987. 191 с.

32. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. Пер. с англ. М. : Издательство Бином, СП6.:Невский диалог, 1999. 560 с.

33. Калянов Г.Н. Номенклатура CASE-средств и виды проектной деятельности. СУБД, №2, 1997. с.61-64.

34. Калянов Г.Н. Как внедрить CASE в вашей организации? PC Week (RE), №17, 1999.

35. Калянов Г.Н. Консалтинг при автоматизации предприятий: подходы, методы, средства. М.:Синтег, 1997. 230 с.

36. Crompton P.N. Computer Systems Standards Manual, Oracle CASE Method, Pitchmark Ltd, 1996.

37. Mayer R.J., Menzel C.P., deWitte P.S., Perakath В., Fillion F., Futrell M.T., Lingineni M. IDEF5 Method Report, 1995

38. C. Ashworth, L. Slater. An introduction to SSADM Version 4, McGraw-Hill, 1993.

39. Калянов Г.H., Козлинский А.В., Лебедев В.Н. Сравнительный анализ структурных методологий. Системы Управления Базами Данных №5-6/97 стр. 75-7 8

40. Калянов Г.Н., Козлинский А.В., Лебедев В.Н. Сравнение и проблема выбора методов структурного системного анализа // PC WEEK/RE, 1996. №34 (27 августа).

41. Е.З. Зиндер. Новое сиситемное проектирование: информационные технологии и бизнес-реинжиниринг. СУБД, №4, 1995.

42. Calvert D. The Booch Method of Object-Oriented Design, http://hebb.cis.uoguelph.ca/~deb/27343/Lectures /booch.html, 1997.

43. Йодан Э. Структурное проектирование и конструирование программ. М.: Мир, 1979. 415 с.

44. Нечипоренко В.И. Структурный анализ систем. М. : Советское радио, 1977.

45. Integration definition for function modeling (IDEFO) / Draft Federal Information Processing Standards Publication 183, 1993.

46. INFORMATION INTEGRATION FOR CONCURRENT ENGINEERING (IICE) IDEF4 OBJECT-ORIENTED DESIGN METHOD REPORT, 1995.

47. Волкова Г.Д., Курышев С. M. Анализ и моделирование традиционного процесса решения предметных задач. Автоматизация и управление в машиностроении, №7, 1999.

48. Б.А.Позин. Современные средства программной инженерии для создания открытых прикладных информационных систем. СУБД №1, 1995.

49. Bpwin Factsheet, http://www.logicworks.com/bpwin, 1997 .

50. Маклаков С. Золотой ключик BPwin, Мир ПК, №5, 1999, с. 42-47.

51. Горчинская О.Ю. Designer/2000 новое поколение CASE-подуктов фирмы Oracle. СУБД. №3. 1995

52. Benbrook H., Finta M., Scott A., Wingate G., Designer/2000: System Modeling and Tools, vol. 1

53. Advanced Information System и др., Oracle 8. Энциклопедия пользователя./Киев : ДиаСофт, 1998г., 8 62 с.-/Kf

54. Панащук С. А. Разработка информационных систем с использованием CASE-системы Silverrun. СУБД. 1995. №3.

55. SILVERRUN Technologies Ltd. SILVERRUN-BPM. 1998. http://www.silverrun.com/product/bpm/srbpm.htm.

56. SILVERRUN-ERX, An introduction to SILEVRRUN data modeling approach.

57. Musseman F. PowerDesigner: Strategic Modeling Solution for Fleet Bank. Product Review. DM Review.1998. №2.

58. Горин С.В., Тандоев А.Ю. CASE-средство S-Designor 4.2 для разработки структуры базы данных. СУБД. 1996. №1.

59. Sybase PowerBuilder. The bridge from client/server to Web and distributed applications.

60. Петров Ю.К. JAM инструментальное средство разработки приложений в информационных системах архитектуры «клиент/сервер», построенных на базе РСУБД. СУБД. 1995. №3.

61. Compuware UNIFACE. UNIFACE Technology Overview.

62. Gilbert J. A Comparison of Five Object Oriented Design Tools, Hitachi Telecom, 1996.

63. Developing Visio Solutions, Visio Corporation, 1997.

64. CAD Systems Development: Tools and Methods/Ed.: D. Roller, P. Brunet. Berlin: Springer, 1997. 362 c.

65. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем. М. : Высшая школа. 1980.

66. Искусственный интеллект. Книга 3. Программные и аппаратные средства: Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990. 368 с.

67. Калянов Г.Н. Российский рынок CASE-средств. / PC Week/RE, №26, 1998.

68. Волкова Г.Д., Сирота И.М. Автоматизация проектирования прикладных систем. // Автоматизация и управление в машиностроении, №7, 1999.

69. Е.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных. Системы Управления Базами Данных # 1/95 стр. 145-160.

70. Э.Ф. Кодд. Расширение реляционной модели для лучшего отражения семантики. Системы Управления Базами Данных #2/95

71. М.Р. Когаловский. Абстракции и модели в системах баз данных. Системы Управления Базами Данных #04-05/98.

72. Искусственный интеллект. Книга 2. Модели и методы: Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990. 304 с.

73. Перспективы развития вычислительной техники. В 11 кн.: Справ. Пособие / Под ред. Ю. М. Смирнова. Кн. 1: Информационные семантические системы / Н. М. Соломатин. М.: Высш. шк., 1989. 127 с.

74. ЭВМ в проектировании и производстве / Под ред. Г.В. Орловского. JT.: Машиностроение.

75. Разработка САПР. В 10 кн. Кн. 4. Проектирование баз данных САПР. О. М. Вейнеров, Э. Н. Самохвалов; Под ред. А. В. Петрова. М.: Высшая школа, 1990. 152 с.

76. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. -М. : Вузовская книга, 1998. 280 с.

77. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. Пер. с англ. М.: Мир, 1998. 653 с.

78. Харари Ф. Теория графов. М.: Мир, 1973. 300 с.

79. Тимковский В.Г. Дискретная математика. Булевы функции и графы / Учебное пособие. М.: Станкин, 1984. 88 с.

80. Зубов B.C. Справочник программиста. Базовые методы решения графовых задач и сортировки. М. : Филинъ, 1999.

81. Свами М., Тхуласираман К. Графы, сети, алгоритмы. М.: Мир, 1984.

82. Зыков A.A. Основы теории графов. М.: Наука, 1987.