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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ -. ПО ВЫСШЕМУ ОБРАЗОВАНИЮ

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

-Р^б--ОД-Г-;------

2 9 МАЛ |9УЗ На правах рукописи

КАРЕЛИН Владимир Петрович

УДК 681.327:658.512.2

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

Специальности: 05.13.16 - применение вычислительной техники.

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

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

Таганрог 1995

Работа выполнена на кафедре математического обеспечения и применения ЭВМ Таганрогского государственного радиотехнического университета . ■■•-..

Научный консультант:

действительный член АЕН РФ и МАИ,

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

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

действительный член АЕН РФ, д. т. н.. профессор Топольский Н.Г действительный член МАИ, д.т.н., профессор ГорелоЕа Г.В. доктор технических наук, профессор Витиска Н.И.

Ведущее предприятие: Институт Проблем Управления РАН, г.Москва

Защита состоится "3#п ин?н£ 1995 г. в 14.00 часов на заседании диссертационного совета Д 063.13.02 по защите диссертаций на соискание ученой степени доктора технических наук при Таганрогском государственном радиотехническом университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д - 406

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан ¿О^^Я 1995 г.'

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

А.Н. Целых.

/ ■ • общая'характеристика работы.

Актуальность темы. Разработка и совершенствование методов аь.'матизации процессов проектирования, планирования и управления

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

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

Методы искусственного интеллекта из области теоретических исследований и разработок все шире внедряются в производство и практику. Быстрыми темпами растет сбъэм комбинаторных вычислений, что связано с повышением уровня интеллектуальности различного рч-дг автоматизированных информационно-поисковых и советующих систем. а также с широким внедрением средств вычислительной техники и обработки информации в производство и повседневную деятельность человека, где решения принимаются на ~сноре комбинаторного оценивания, прогнозирования, анализа 1! перкмрч вариантов. Сложна ть задач связанных с выработкой и принятии! н-.учк.: обоснованных {--• шений непрерывно возрастает. Все ьто дикту.-т н*? Сходимость даль нейшей разработки и исследования теории и.средств поддержки комбинаторных моделей поиска' и принятия решений.

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

Поскольку информация, используемая в процессах принятия решений часто является нечёткой т.е. неточной, неполной и зачастую носит качественный расплывчатый характер, что относится и к знаниям экспертов, то важно иметь адекватный математический аппарат для формального представления и обработки зтой информации.-¿снобы такого математического аппарата были заложены в работах Л. Заде по. теории нечётких множеств и нечёткой логики к развиты в дальнейшем многими исследователями как в России, так и за рубежом. Значительный вклад в развитие аппарата теории нечётких множеств, нечеткой логики и его прикладного аспекта внесли: Аверкин А.Н.. Алексеев A.B., Алиев P.A., Борисов А.Н. .Блишун А.Ф., Батыршин И. 3., Берштейн Л. С.. Дюбуа Д., Ежкова И. В., Куковин В. Е., Кофман

A.. Кузьмин В.Б., Каня A.A., Мамдани E.H., Мелихов А.Н.. Мицумото М.. Негойце К.В., Орловский С.А., Поспелов Д. А.. Прад А.. Силов

B. Б.. Тарасов В. Б.. Ульянов C.B.,- Церковный А. Э., Шапиро Д. И., Ягер P.P. и многие другие учёные.

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

•В связи с бурным, развитием к интр.:¡-явным внедрением в сферу прикладных научных исследований у в практику проектирования, управления и производства кетг. ,-«>:• ми^чь. знаний и искусственного интеллекта, позволявших .эд^р.^иать процессы принятия решений как в условиях чёткой, так и нечёткой исходной информации, особую

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

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

Указанный комплекс- исследований был проведен в 1973 - 1995 годах, при непосредственном участии' автора, на кафедре математического обеспечения и применения ЭВМ ТРТУ.

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

Поставленная цель определяет следующие основные задачи диссертационной работы: .

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

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

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

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

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

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

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

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

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

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

- разработаны и теоретически обоснованы оптимизационные комбинаторные модели и алгоритмы решения задач распределения и пере-

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Результаты, 'полученные автором. использовались в 14 НИР, выполненных в рамках госбюджетной и хоздоговорной тематики в соответствии с постановлением Госкомитета СМ СССР по науке И технике №5С0 от 21.11.1975 г., постановлением СМ РСФСР №610 от 12.11.1976 Г;, по планам работы секции радиоэлектроники к приборостроения Программы САПР Минвуза РСФСР, по координационному плану АН СССР по комплексной проблеме "Кибернетика" за 1981-1985 г.г., по координационному плану работ Минвуза СССР на '1981-1990 г.г., по планам НШ ИБС. по единому заказу-наряду ТРТУ на 1993-1994 r.r.v ш Межвузовской программе " Интеллектуальные системы На базе нечетких компьютеров", выполняемой

' - 9"" •. .

кафедрой МОП ЭВМ ТРТУ в рамках Программы " Университеты России".

Научные и практические результаты диссертации использованы и внедрены в НИИ многопроцессорных вычислительных систем г.Таганрога" ОКБ "Миус" г.Таганрога. НПО ''Кузробот", г.Таганрога. ОКБ "Ритм" г.Таганрога, Научно-производственное предприятие "Инфо-комп" 1фи ТРТУ. на кафедре математического обеспечения и применения .ЭВМ ТРТУ (учебный процесс).

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

Апробация работы. Основные результаты работы докладывались и обсуждались на Республиканской конференции молодых учёных и специалистов (г.Киев, 1973г.),' на 3 и 4 Всесоюзных конференциях по однородным вычислительным системам и■ средам (г:Таганрог, 197?г. .г.Киев, 1975г.),. на Региональной научно;-технической конференции по использованию вычислительной техники (г. Ростов. 1973г.), на конференциях и семинарах по методам машинного проектирования вычислительных устройств (г. Ленинград, Í9?6r., г. Запорожье, 1978г.,г.Харьков,1978г.) на семинарах по теории графов и дискретной оптимизаций, по автоматизации проектирования устройств цифровой техники (г.Ильменау, ГДР,1983г.. г.Берлин, ГДР. 1983г., г.Дрезден, ГДР,1983г.). на Всесоюзной научно-технической конференции по проблеме создания и развития интегрированных автоматизированных систем в проектировании и производстве (г.Могк-х ва,1987г.), на Всероссийской конференции "Медицинские информашг* онные системы"(г.Таганрог.1993г.). на Всероссийской с международ: ным участием конференции "Интеллектуальные САПР" (г.Геленджик, 1993г.), на Всероссийской с международным участием конференции " Персональные исследовательские комплексы и АРМ-94" (г.Таганрог, 1994г.), на научно-технической и научно-методической конференции професзоро-преподавательского состава и сотрудников ТРТУ, ежегодно с 1972 по.1995г. в г.Таганроге.

Публикации. По теме диссертации опубликовано 79 работ, в том числе 49 статей в центральных изданиях, междуведомственных и межвузовских. сборниках научных трудов, тезисов докладов Всесоюзных и Республиканских конференций, получено 30 азторских свидетельств на изобретения. Кроме того, отдельные положения диссертации нашли отражение в :14 зарегистрированных в ВНИТЦ отчетах по КИР. в трех учебных пособиях, изданных по планам Минвуза и в нескольких учебно-методических пособиях и руководствах к лабораторным и практи-

ческим занятиям. .

Структура и объём диссертационной работы. Диссертация состоит из введения, 7 глав, заключения,_ списка использованной литературы и трёх приложений. Общий объём диссертации - 333 стр., основного текста 315 стр., . включая 40 стр. рисунков и 20 стр. список литературы из 258 наименований. Имеется три приложения на 18 стр., куда вынесены способы формализации некоторых задач и наиболее трудоемкие доказательства теорем, а также акты сб использовании и внедрении результатов диссертационной работы.

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

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

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

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

Четвёртый раздел'пЬсвящёй разработке методов и алгоритмов распознавания изоморфного вложения чётких • и нечётких графоз и способам аппаратной реализации задач распознавания изоморфизма и изоморфного вложения.

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

о

- и -

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

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

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

Заключение содержит выводы по работе.

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

ограммирования.

В приложение 2 вынесены доказательства теорем раздела 2 .

В приложении 3 приведены копии актов о внедрении и использова-и результатов работы.

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

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

- методы и алгоритмы распознавания изоморфизма графов и ги-зграфов;

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

- методы и алгоритмы построения классификационных и компози-энных моделей принятия решений при нечеткой исходной информации:

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

- способы аппаратной реализации операций нечеткой логики;

- методы и, аппаратные средства поиска и преобразования дан с: - •

- 12 -СОДЕРЖАНИЕ РАБОТЫ. '

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

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

Современные системы автоматизированного проектирования, плг нирования и управления сочетают в себе свойства как организаций! ных систем, так и технологических, и представляют собой сложш человеко-машинные системы, которые в качестве активного элемен' включают человека-оператора, участвующего в выработке и принят] управляющих решений. Указанные автоматизированные системы от№ сятся к классу систем принятия решений, которые содержат как XI рошо структурированные проблемы выработки и принятия решений (В ПР). так и слабоструктурированные проблемы, содержащие как к явственные, так и количественные элементы. Для повышения эффе: тивности управления разрабатываются методы и средства автоматиз, цни процедур В и ПР. Проблемы В и ПР в организационно-технолог ческих системах имеют иерархическую структуру.

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

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

шения. Этот подход основан на распознавании сходства . постановок задач, на поиске аналогий или прецедента.

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

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

Выполнен анализ способов представления и использования нечётких знаний в системах принятия решений. Отмечается, что наряду с нечёткими правилами-продукциями используются нечеткие семантические и фреймовые сети и их варианты: ситуационные, ассоциатив-4 ные сети и др. Способ использования нечетко представленной инФор мации и нечётких знаний определяется как областью применения, так и выбранной моделью принятия решений.

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

Проведенный анализ показал, что развитие аппаратных средств поддержки моделей и систем ПР'идёт в двух направлениях. Первое

.. - 14 •• \

связано с созданием автоношшх проблемно - .ориентированных устройств и структур-с параллельным.принципом работы, предназначенных . для. решения задач преимущественно невычислительного характера. Второе направление связано с созданием специализированных приставок - сопроцессоров, универсальной ЭВМ,' аппаратных ускорителе!. эффективно реализующих некоторые.массбвые операции обработки щи преобразования данных. Наряду со средствами аппаратной поддержи моделей ПР, основанных на обработке четких данных и. знаний. важный класс составляют аппаратные средства для преобразования и обработки нечётких данных и знаний.в интеллектуальных системах с нечеткой логикой. Здесь упор делается на создание специализированных нечетких процессоров, предназначенных для использования в качестве сопроцессоров обычных ЭВМ. Широкое развитие и применение находят нечеткие контроллеры и интеллектуальные , логические регуляторы, процессоры нечеткого логического вывода.

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

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

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

- 15- "

ный. основанный на конкретной реализации метода ветвей и границ.

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

(п) (п)

Уц.ах" п * а1 (Зщ ~ 341*1' ■ • ~ (а[п/га)т ~ а{п/т] (т*1 ) ) •

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

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

Необходимо найти такое перераспределение изделий, при котором все дефицита были бы скомпенсированы зэ счет избытков изделий более высоких классов или групп при минимальных стоимостных затратах. Исходные данные представим в^виде . взвешенного: ориентированного решетчатого графа Н=(С.Г, Кб)), где с - множество вершин.

причем вес 1 (е2)- вершины £ С определяется, как разность между фактическим и плановым'выпуском 'изделий г-го типа, где г=т(1-1)+3 (1- класс. 3- группа изделия), 1=!7п. ^ТТт".

Граф Н представляется в виде решетки из пхш вершин. Из каждой вершины ребра направлены в соседние справа и снизу.

■ , - 16 - . . ..

Определение 2.1. Покрывающим множеством вершины е^ й называется подмножество всех тех. вершин графа Н, из которых существует, путь в й! '/ .

. Теорема 2.1. Для того, чтобы задача перераспределения имела . допустимое решение, необходимо и достаточно был ¡лнения условия

(УС'ЕС/С=-и С!) ( £ 1 (ё) в ее- вес-

Т.е. в.любом подмножестве С, включающем наряду с каждой вершиной g1 все вершины ее покрывающие,, сумма дефицитов не боль-' ше, чем сумма избытков. -Предположим, что уже получено некоторое допустимое решение И задачи перераспределения т.е. в графе Н для. всех вершинке С выполняется 1 (3!)>0.

Теорема 2.2. Чтобы допустимое распределение И было оптимальным. необходимо и достаточно, чтобы для всех 1€1={1,2.....п) и ■

любого допустимого распределения И' тех же изделий имело место соотношение

(1(Е1) - l'(gl),....l(gv.1) = 1'(ё1-х)) Д >1'(в1>.

где 1^) -вес 1-й вершины графа Н в распределении И, а Г^) - вес х-й вершины графа Н в распределении

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

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

Сокращение сложности задачи достигается исключением из подмножества каждого типа масок "худших" представителей. Понятие "хуже" определяется заданием несимметричного отношения <р(А,В), показывающего степень того, насколько А "хуже" В.

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

В этом же разделе исследован алгоритм раскраски вершин гра-

- л -

Фа. ос:и1Рг.-<гл1й .'3 методе 1йпоавлекнзго случайного квиска к предложена c/'zVA aoteipohito:! ibiom.-phoh новели, pevi."nayni -1 у.-. ггршпм. разря'-отаны •, -лрсисгва. реагирующие ¿ст&рюшлри-*! >■«-. члгорутм поиск.". .-J-:: • •• ./пгм шу;;: ¡. «та г I. Иссле-

дований &..гор;гл;и на ЭЛМ. '.uei.K • лло.га чтераилн л;-« L'ppniHH i'cдллирул/ьх лзьа--. -л л ;:НегтиРН0сть "in p'.'fc.'Hiaai'.HH

ira tRrot.T.:): й ипдол,-.. Пр г ■ , и-:нл; у лр'Исг^л -¡Олл л-л-ал! рклг--лкш в f • л тоодлйствя:! п-> ера""*»!!« с известными ahiii'Oi акп в а -/ (-¡;,!) рч: '-If !: - ЛИЛЛЛ г?ТЕН'Н рюкрашиь; МОГО rn»»i. ЧТО У'1?е при 11*11 OOCTdiJi.icT U'9.'«i.

Раз Исследование и ра-..мботка комбинат .'.оных !'.од?.гей

распознавший изоморфизма неориечтп,.-: .v.i ::н:-: г; аф'>'- »

Определение эквивалентности. схсдо-цч. аналогий лежит ь основе .узнавания if ггассификации в теории илкусствонш.п интил-эдкт \ и испол1 зуется при гоинятии решений на оснозо прп;лсенп. с^ной ■ из важных проблем, относящихся к установления сходства представления объектен или ситуаций, является распознавание изокорфчз?"ч графов 'РКГ) и пи гиперграфов.

Дча гьчга G --- (X. !•') и К * (V. Гj /ваяются изомер-! ними, <?'\:;и лущг лльу -лг ■■•ямщ однозначнее cv.-tipjacemifr : У - *.'. -охри»'" гее плкнкпа* ллежллл v: лзршин. Очггд^о, илсморфи. v тлорлчеепш; но ¡кв'„ди; граф л граф Н и »'•)»>." быгь задано в видл изоморфно!-: подстанолх',1' ф- :> -ф(х )1 , -л,,; и =|Xi= ¡VI,

Va иоппльзо:'-;;,ь и алгоритм?? ПГ базируются многие как теоретические, так и гп 'лллчдные г-гдз'и* ь. ь частнио'.т,. задачи почека к ПК логического г.» вела, акгома*. изацле контроля. •'■уч^у.'ТЬ^ вт подхода к разраС'ткр алгоритмов ГИГ. Первый связан с построением непереборных- алгоритмов и ссно:....:1 на использовании пнвари-чнтоп Г-торпй подход в; j. >мат процедуру перебора подстановок на мнркрст ве ыэршин при и .,••'. изоморфизм:..

Для локрищслия пере? при решении гадч-и ГП!' л дйп:-.-| таш:.: предложен с.мas,л¡ированньл! подход." основанный на использование .систем« яскспын')- инвариантев (для получэния предварительного разбиения м-гчг-тв вервд'Н сравниваемых графов на соотнесенные now-» v л; .цедури неправленног1 перебора. !'..•;,••<•• [ i ■ и

на ¡¡ишь! иьим установлении соответствий вершин ryaix.r л л, л;л-;л достаточного условия. o?fспс-чиваощего на данном шаге пр.чьиллло.лг', соответс • р I ЕЬ"ДИ1ся иазмэтка рершш« графов G и Н, "огласио которой, 'ели устэнлвлеио частичное взаимно однозначное отображение-

ц> X' - V. где X' с X, У с V, то меткой Мх вершины X € Х считается множество Г'х вершин из X' , смежных с х. Меткой Му вершины у С У является подмножество вершин из X', являющееся прообразом подмножества Ру по отображению <р, т.е. Му = Ф(Ру).

Критерием непротиворечивости частичного отображения |р: А' -V' при распознавании изоморфизма графов С и Н является спедур-г.1й. На множестве X' и V долдч-.< выполняться:если фх у, тс 4-Му: на множествах X \ X' и У \ '/' должно вьше.пнктьсл : если : -■ И(У ), то X - У. Очередная пара соответству: •: :

ргся из соответствующих классов X и У. Мчксймьл: як.) п>.рейор частичках отображений при поиске изоморфного отобрс.>':пЦ;; однородна графов степени к = п/2не превосходит величины

Т(п) = п • (](П-1)/2[)!• [(п-1)/2]! где ] А [.- наименьшее целое, не меньше А, ¿А1 - наибольшее цело« но превышающее А.

Предложен оригинальный переборный метод РИГ1, основанный на достижении сопутствующей подцели. В качестве такой направляющей подцели используется требование построения упорп-^'-л-нлг.сти серяг/н сооих сравниваемых графов, отвечающее критерию ма.'.'.^иладки двоичного кода матрицы смежности, а в упрощенном вэри^.нтн - критерию минимизации суммарной длины соединений при л;\чс ином размещении вершин. Для построения упорядоченности вершин, максимизирующей двоичной код матрицы смежности приводится система эвристических правил.'

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

Выбор очередных вершин в строящи/.ся соответствиях упорядо чсгтс:;';ях осуществляется о использованием правип оптимизации рас-♦х-сг'ь-ия. а метки »оршии слу»эт для проверки правильности произг.с-денкого выбора. При сравнении меток используется следуйте аерштс.

Тс-орема 3. \. Ьзаимну однозначное ч тображение ч>: X ■* V является изоморфном, если метки Мх и Му соответствующих июгенюъ к и :/ фх одинаковы.

Копользовчнле дополнйт-'лькой иепи гмфая'зет число вмяп*-так как при :-.ыС:>ие .¡чередног' «»стзс^^вия гозьо

•'лае* дополнительно отсекать йвсперспеыгзкыр варианты. Для случайных графов со степенями вершин k < í.a/3 оценка трудоемкости алгоритма составила величину 0 (кп). ^счётная сложность' алгоритма с учетом р ветвлений не превышает оцгчги 0(г.3) + р-0(п2). Для однородных грэфов, ар являющихся сильнорагулярными, лрудоемкос^1 пере'-па соразмерна с трудоемкостью выделения тгчриантов.

1'ааработаны. перебсрюЖ Ж'к-д к алг.ршм распознавания изо-!/орфи.':мч гиперграфой. •?/>•'т-тенрых ..кзивглеитшлш им графами К?>:ш я. Метод ос»' CJH г?. ; • :м?"ю си-лгетствтащих вершин, выполнении прицеду.'Н передачи метек мыхду инцидентными вершинами, выполни :!нч nonp-j4.j«erf«iH ¿i соответствий разбиений по числу я модности ' паггев. Для сг-^леьаи r.opiSnpa предварительно выполняв '. /я * дчг-л,:«,с разопени'') дамтвстэ вершин и р^бер обоих гиперг-рофс:. •„•уггап ;:<ичиоленпл и срагкечгя локальных Инвариантов, лолу-ч&'ших г:с х '.р;ше инцгделлий. Апгорчтм, реализующий метод сравнения гиперградов, применяв ел чля илшления ошибок в топологии БЛС осечем программы на фпртрч;;^ составил ¿93 операторов, время оасочы центра, ьного прпгрсссо.-- )ВИ ЕС-ЮЗЗ по трансляци, редактированию к вклелиенн» пр.'гр>.'«<ы .:".л ».*д\рп;: 10x1? составило 35 сек.

Га злел 4. Г'^нСо г;;:; г.- • •' er.:-. 'ритме* и средств аппаратной П'ч;дер'кки рааюькавашп извкорфног'' ?,тсмлгния четких и нечётких гра-фи^.

Зг?яг,ча распознавания и .i./K».»pii«v. и сложения графов (РНВГ) является КР-пслаий :¡ ;:;¡ei?T ра*»п.> прикладное значение. Чтобы найти изоморфное вложение гра?:, ;; - (X.F) в граф Н - (Y. Р;, где IX| < I Y¡ , нужно пг-т^уи i i, однозначное отображение <р . X - Y¡,

Г'лу У ¡Я Y, тыте, что ip(Fx) £ (Ру Л Y,). Отображение устанавливается при выполнении следующих необходимых- условий:

1) если у - ;?х та piy' > р/у). где р(х) и р(у) - локальные '-.гьпени верный :: С- ч у С '■':

2; волн х3е fxl то из ук - и y¡ - тх. иледает yt € ?yk. гпплпожен ".^¡•«O'jpiiLr/. . РКСГ. хнов^тый на поиске улижимоети ЛРР.-Ч--1 D. ирстрйенкогз дл.» rpäOa G. - Б rptffc Н, четорло '" , ...Wi.v.Ct? i-' -"иГ'Елснл.' соог:f. —;. i¡> .'.".".."у .. »■•¿.т ■.*-, :*-v .•-.и-: _ ..... ^.-„рщ.^иж 1: л ' :.....«ч'п-л::- г- л^-'тглуп^ ппямого и еб-

..л,,,!-- .о .. ■ - íui'vrMH аеропора прим;

ютея при»»« .•■«•.¡•i».i .¡слаог.» пореСорд д

ра.-омотрекнога алгоритм« ол-пн.'!--■■ ь,,..м..,..!г;

г I

Л < г • П С • Г;!.

Ш % -

к=ч>(1)

где r-j-IFXi I. т,, = |РУк1. I=(l,£.....|'Х|), n=!vj.

В данном ра;у.гле зьализиоуэтся также существующие способы аппаратной реаяязашш алгоритмон РИГ и РИВГ. Рас >г>трен алгоритм случайного напраи.пенного поиска изсморЛього вложения, позволяющий распараллелить процесс сравнрнмя графов к удобный для реал'-гзациг на асинхронной ав^оматчой модели Критерий, исполняемый для проверки правильности устанавливаемого алгоритмом соответствия, вытекает из справедливости следующего \;зержденил.

Теорема 4.1. Если между вершинами X и Y,cY графов О и !! ус тановлено взаимно однозначное соответствие » X-Y гло что д>тр каждого Х[ еХ:

1) при Y, «У и при «.»чикаковом числе реО-эр i»-;.G> -ii(H) наполняется условие <р(х,)- Л Г(фхг). то <f ость отно-тенле -изоморфизма гра

x^F.Vj фов G и К,- т. е ОН;

2) при !Y1 >iX| и п(Н))m(G) к Ц.1. выполнении условий

4>\-<j 1 'i Г 1 Xh CFXi

отношение * ааднет изоморфно? глежение С ь Н.

Приведены структурные схема аътомагной моделч и ьерояткос'1-ного подавтомат?, мзделпрующ&го вершну вкладываемого графа G. Время работы алгоритма при отыскании ь/южемия графа G с 10 ьерт -нами и локальной степенью к « 6 ь граф Н с ш(Н) = 20,25,30,... ,45 вершин и к - 6 на ЭВМ БЭСМ-4Й составило в среднем от £ Д'.> 12 сек. Предложенный алгорчтм эффективен при параллельной реализации на автоматкой модели, где время отыскания изоморфного вложения для рассмотренных примеров не превышает Ю-3 се;с.

' Разработаны и теоретически обоснованы метод и алгоритм отыскания i - вложения и t - изоморфизма нечетких графов. Нечетки* графом G(X,V) называется пара (X,V), гдеХ - множество вершин, г V - нечеткое отображение X - X. Для каждой вершины х £ X. множество V(x) является нечетким подмножеством в X. Сгепзнь принадлежности вершины xt нечеткому множеству V(x; обозначим v(x,хх;. Если заданы нечеткие графы Н = (Y, W) и G » (X, V). то t - вложени» G в Н определится как соответствие q>: Х- V (Y'c Y), для которой

выполняется условие

( Ух^е х ) ( \(хд ) - у?( 9(х1).«р(х]) ) >" г ) Здесь мера соответствия величины Ь величине а(вложение а Ь) устанавливает' операция нечеткого следствия

а -> b = |

äVb' - •( по Л. Заде ),

min(l,i-a+b) - ( по ЛукасеЕИчу ).

Нечеткие графы G и Н будут t - изоморфными, если существует' такое t - вложение G b Н. которое является одновременно t - зло-гением Н в G. Изоморфизм четких графов является частным случаем t - изоморфизма нечетких графов.-

Очевидно, любое отображение tр: .X Y определяет t - влозкенке G в Н с некоторым конкретным значением

,t = tnl.tl tviXi.Xj) - w'WXj >;ф(Х3Ш • . л *i,x.iex ' i

Интерес представляет^ отыскание t ~ вложения либо, с заданным значением t, либо с^ наибольшим возможным. t\^ Разработайный алгоритм отыскания t - вложения представляет собой конкретизацию известного метода ветвлений и отсечений.' и основан на определении для вершин xiXjyiV оценки г(х,у), характеризующей степень истинности того, .что в искомом t - вложении вершине х £ X соот ветствует вершина у £ Y, т. е. <р х = у.

Доказывается следующее утверждение

Теорема 4.2.- Для любых ХцеХ, y'j6Y. и любого t - влохсения G ь Н такого, в котором установлений соответствие хк—> у1, имеет место

t <Г(Х*,У1). .

Оценка г(х.у) позволяет при заданной t рассматривать в качестве перспективных только те варианты соответствий х-- у, для которых rix,у) > t,'что приводит к быстрому отсечению ряда вари антов при поиске t вложений. - .

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

■При выработке и ПР в сложных плохофермализуемых ситуация? возможен подход, основанный на' использовании ранее накопленного опыта, выраженного в виде совокупности нечетких правил-продукций Модели вывода; основанные на композиционной схеме Д. Зпде и яи.да щиеся приближенным обобщением дедуктивного вывода, находят широкое применение при построении нечетких моделей су . а также ЭС.

в

- 22 -

работающих с нечетко, описанными знаниями.

В этом разделе рассмотрены модели принятия решений на основе композиционного правила вывода, реализуемого как с использованием нечеткого отношения, так и непосредственно по системе нечетких продукций вида: " Если А, то В", где А и В нечеткие подмножества, определенные соответственно на базовых множествах X = 1 =

ГЛП и Y - {у.,}. j = ITS. Причем А = {/1А (х)/х), х е X. а В = %(У)/У). у £ Y. где /1А(х), piß (у) £ to, 1] - функции принадлежности соответственно нечетких .множеств А и В.

Нечеткое отношение R формализует систему нечетких продукций вида: " Если х есть At. то-у есть Bt". где 1 = Пп, следующим образом . . ;

R =■ U Ru= U AjxBj; /%(х,у) = шах [min Ma®- (У)1 -1 1 11

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

{ Ак о Rp вК' }. к = О. где множество ВК' совпадает с Вк с заданной степенью р. Элементы г, 3 матрицы Rp определяются решением системы логических уравнений вида

{ V (а/х) & г13)- [b]*'- е,bjk)+ е].. I=l7n, J=T7nT , где t ='i -p. ,

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

В'= A'oR. . Мв- (у) = шах min (ДА• (х), щ (х,у)) ' ■ х '

Результирующее нечеткое множество В можно вычислять и непосредственно по системе из N нечетких продукций, . без предварительного построения отношения R. Однако в этом случае усложняется аппаратная реализация процедуры вывода" и затраты оборудования возрастают в 2Nm .раз. где m - длина-выходного -слова В' ,а потребность в объеме памяти возрастает в k = 2N/max(n. m) раз. Поэтому отказ от использования нечеткого отношения R. будет оправдан лишь в том случае,' (когда в процессе работы системы ПР продукции изменяются и нет.времени формировать новое отношение R..

Рассмотрены методы аппаратной реализации композиционного вы-

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

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

Лся)-(х.у). = <«а(Х) " Ь(У) & (К<х) - ¡к (У)), описывающая нечеткое отношение К а ХхУ, моделирующее высказывание ж. Модель строится в результате композиции элементарных высказываний. Данная модель требует меньших ресурсов памяти ЭВМ по-сравнению с матричным представлением -нечеткого отношения и удобна для параллельной реализации на специализированной многопроцессорной структуре. : ;

: Раздел 6. Методы • построения нечетких классификационных моделей принятия решений и средства их аппаратной поддержки.

Классификационные МПР (И,I, Ю описывают разбиение 1={Ц} многомерного пространства И=Ххухг признаков-факторов 1,4,1. наиболее существенно влияющих на выбор управляющих решений г^Л,- на нечеткие области Ь^ь (эталонные классы), соответствующие этим решениям. В данном разделе приводится способ построения функция-принадлежности. характеризующих каждый из сформированных эталонных классов.

Предположение о том. что оператор всегда выбирает решение с максимальной степенью предпочтения, ' позволяет упростить модель путем замены разбиения Ь на обычное четкое разбиение 1>Ым,') .пространства И. Справедливо утверждение

. " Теорема 6.1. Для любой точки х, у, класс, к которому она принадлежит с наибольшей степенью^ разбиении Ь, и-класс, к которому она принадлежит в разбиении М пространства И, соответствуют . одинаковым решениям.

Использование четкого разбиения й вместо нечеткого Ь позволяет экономить объем памяти, необходимой для хранения эталонных образов, представив последние в виде системы отрезков а5, Ь3. С!. соответствующих значениям сц.53. Т(г лингвистических переменных, описывающих признаки X.У,Ъ.

Основной задачей, возникающей при построении нечётких клас- '

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

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

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

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

новлено, что с точки зрения увеличения скорости ии^иипш, мизаи",5 затрат оборудования . оптимальными являются параллельные

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

Раздел 7. Элементы специализированных' средств4 аппаратной пиддг-ржки интеллектуальных систем принятия решений.. ..'

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

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

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

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

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

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

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

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

- 27 -

за один такт работы устройства.

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

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

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

ВЫВОДЫ.' ТЕОРЕТИЧЕСКИЕ- И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ.

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

Основные научные положения диссертации кратко могут (>и~\ сформулированы следующим образом:

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

■ - 28 -ний, методы построения- средств аппаратной поддержки1интеллектуальных систем принятия решений и выделены перспективные направления исследований;

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

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

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

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

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

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

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

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

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

. - 29 - .

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

- разработан ряд .'элементов и устройств для реализации операций с нечёткими множествами и операда нечеткой логики в макси-минном базисе Л. Заде и в базисе с ограниченными операциями Лука-севича;

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

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

. Результаты,, полученные в диссертации. - используются при выполнении хоздоговорных к госбюджетных научно-исследовательских работ, выполняемых на кафедре математического обеспечения и применения ЭВМ ТРТУ,' в разработках ОКБ. "МИУС", НИИ МВС. ОКБ "Ритм". Научно-производственного предприятия "Инфокомп" при ГРТУ, в раз-' работках НПО "Кузробот" г.Таганрога, з учебном процессе ТРТУ.

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

1. Мелихсв А.Н., Карелин В.П. Методы распознаёакия изоморфизма и изоморфного вложения четких и нечетких графов: Учебное пособие,- Таганрог: Изд. ТРТУ, 1995,- 112 с.

2. Методическая разработка по курсу "Системы искусственного интеллекта" по теме "Проблема вывода в системах обработки знаний"/-Изд. ТРТУ. В.И.Кодзчигов, В.П.Карелин. Л.Н.Мелихов.Та-' гаНрог, 1994Г - 4? с:

3. Мелихов А.Н..Карелин В.II..Курейчик В.М. О разрезании графов на подграфы. // В кн. Математическое моделирование и теория электрических цепей. 'Енп. 10. - Киев:' Наук, думка, !973. с. 70-75.

4. Карелин В.П. Вопросы «зомерфного вложения графа задачи в граф цифровой интегрирующей структуры.// Тезисы' докл.областной н. -т. конференции'по использованию ВТ. Ростов н/Д. 1973. с. 43-44.

5. Карелин В. П. . Миронов Б.Н. Эффективный алгоритм определения

- 30 -

изоморфизма графов.//Тезисы докл.. области, н.-т. конф. .по использованию- ВТ. Ростов н/Д, 1973. с. 19.

6. Гузик Б.Ф..Карелин В.П. .Миронов Б.Н. Об изоморфнрм вложении сетей цифровых интеграторов в однородную структуру с- неисправными коммутирующими элементами / Изв. АН СССР.Техн. кибернетика.-1973.N4 с.81-92. 4

7. Карелин В.П.,Калашников В. А. Об одном подходе к проектированию межсоединений БИС.// Матэр. республ. кснф. молод, ученых. Киев.1973, с.31-34.

е. Карелин В.П..Калашников В. А. Один подход к решению задачи трассировки межсоединений.// Изв. СКНЦВШ.Техническ. науки.N1, 1974, с. 12-15.

9. Карелин В.П..Миронов Б.Н.Алгоритм определения изоморфизма однородных неориентированных графов.//Изв.АН СССР. Техн. кибернетика, 1975, N-2. с.145-148.

10. Карелин В.П. .Миронов Б.Н.Алгоритм случайного направленного поиска изоморфного вложения графов на автоматной модели.-В кн. : Однородные цифровые вычислительные и интегрирующие структуры, Таганрог,ТРТЙ. 1976,вып. 6. с. 8.4-93.

11. Карелин В. П.,Калашников В.А. Автоматизация этапа получения ортогональной трассировки соединений БИС.// Сб. тезисов семинара "Конструирование микроэлектронной аппаратуры".Ленинград: ЛДНТП, 1976, с.ЗЭ.

12. Карелин В.П..Калашников В. А. Алгоритм последовательной опти-

■ мизации при решении задачи проводного монтажа.// Управляющие системы и' машины. - Киев: Наук, думка. 1977, N1,0.123-127: .

13. Карелин В. П., Миронов Б. Н. Синтез ассинхроного вероятностного автомата, моделирующего поиск изоморфного вложения графов. В кн.: Методы построения алгоритмических моделей сложных систем. Вып. 2. Таганрог: Изд. ТРТИ, 197,7,. с. 103-110.

14. Карелин В.П..Калашников В. А.,Вокалова Е.В. Алгоритм ортого- . нальной трассировки межсоединений- с использованием моделирующих матриц.//. Электронная техника. Сер.З, Микроэлектроника. . Вып.5(77), 1978, с.46-54'.

15. Карелин В. П. Применение методов бивалентного программирования для решения задач оптимального размещения модулей на плате.// Сб. Оптимум номинала и задачи принятия решений. Таганрог:ТРТИ, 1978, вып. 2, с. 152-159.'

16. Карелин'В. П.,Калашников В.А. ^Применение метода бивалентного

программирования, для решения некоторых задач проектирования. _ '•// Микроэлектроника.'Том 3,вып.5,1979. с.338-407.

17. Карелин В.П., Миронов Б.Н. Алгоритм оптимальной раскраски вершин графа, ориентированный на реализацию в асинхронной автоматной модели. // Изв. СККЦВШ.Технич. науки. N2.1979.0.

18. Калашников:В.А..Карелин В.П.,Вокалова Ё.В. Алгоритм трассировки с использованием моделирующих матриц.//Изв.СКНЦВШ.Техн. науки. «3,1979, с. 27-30.

13. Карелин В.П..Калашников В.А. .Королев А. Г. Решение задачи минимизации числа межслойнкх переходов с применением бивалентного программирования.// Межвузовск. республиканский сб.АСУ, вып. ?.. Харьков, 1979. с. 72-76.

20. Карелин В.П. .Ковалев С.М. Об одной задаче упаковки нескольких рюкзаков.//Изв. СКНЦВШ.Технич.наукид980. N2; с. 21-23.

21. Карелин В. П. Методическая разработка по курсу 'Исследование операций". Тема: "Модели дискретного программирования"./Таганрог: Изд.ТРТИ, . 1980';- 27 с. ' .

22. Карелин В. П. Алгоритм распределения .заданий для нескольких машин разной- производительности. //Междуведомстз. тёматич. научи, сб. Методы автоматизации проектирования, программирования, моделирования.- Таганрог:Изд.ТРТИ,1982, вып.2. с.104-116.

23. Карелин В.П:.Ковалёв С.М. Применение аппарата теории множеств для решения задачи комплектования набора фотошаблонов.// 4 Микроэлектроника. Том. И, вып. 2. Москва. 1982. с. 104-108.

24. Карелин В.П..Ковалев С.И. Распознавание размытых структур как модель принятия решений в задачах проектирования.// Межвуз.сб. Автоматизация проектирования электронных схем.- Таганрог: Изд. ТРТИ, 1982. вып. 1.-С. 50:53.

25. Карелин В.П., Ковалев С.М. Распознавание нечеткого отображения-как модель принятия решений в сложных,'ситуациях. Деп.ВИНИТИ, 1982. N 6254-82 ДЕП. '

26. Карелин В!П.Ковалев',С,И.' Модель принятия решений'.на основе нечеткого распознавания.//Межвуз. сб. Методы автоматизации проектирования, программирования и моделирования. -Таганрог: Изд.ТРТИ, 1982, ВЫП. 2. - С. 45-50.

27. Карелин В. П., Ковалев С. М.. Баронец в. Д. Принципы построил расплывчатых, алгоритмов управления произбодственными процессами. // оптимум номинала и задачи принятия решений.-Таганрог.: Изд. ГРТИ, 1983., Вып. 3.-С. 76-80. (Рукопись депонирована в

- 32 -

ВИНИТИ 21.03.83 N 11473-83 ДЕП).

28. Кравченко П.П.; Карелии В.П. Методы распределения загрузки многопроцессорных вычислительных систем: Учебное пособие,-Таганрог: ТРТИ. 1983. - 46 с.

29. Карелин В.П..Ковалев С,М. Метод оптимального решения задачи перераспределения.// Изв. СКНЦВШ. Технич.науки. 1983. N1,с.29-33.

30. A.c. 1024S02, СССР, G06 F 7/02. Устройство для выделения максимального числа. / В.П.Карелин, Б.Н.МироноЕ,- Опубл. 1983. Бюл. N23.

31. Мелихов А.Н..Карелин В.П. .Ковалёв С.М. Моделирование нечетких алгоритмов принятия решений на многопроцессорных вычислительных структурах.// Междуведомственный тематич. научн. сб. Многопроцессорные вычислительные структуры. Вып. 3. - Таганрог. 1983, с. 63-66.

32. Карелин В.П..Ковалев С.М. Объективизация экспертной информа-. ции при построении нечеткой модели конструктора. // Межвуз.

научн. сб. Автоматизация проектирования электронных схем. Вып. 2. - Таганрог. 1983. с. 13-16..

33. Карелин В.П..Ковалев. С.М. Метод построения мсдели. имитирующей алгоритм поиска управляющих решений оператора.// Изв.АН СССР. Техн.кибернет. 1983. N5 - с.181-187.

34. Карелин В.П.,Калашников В. А. Алгоритм раскраски графов для расслоения совмещенной топологии .схемы.// Межвуз. научн.сб. Автоматизация проектирования электронных схем. Вып.З, Таганрог: ТРТИ, 1984, с. 23-30.

35. Мелихов А.Н..Карелин В.П.,Ковалев С.М. Моделирование процессов принятия решений на основе нечетких классификационных схем. Электронное моделирование. 1984. Том 6. N3. С.3-6.

36. Мелихов А.К..Карелин В.П..Ковалёв С.М. Принятие решений при. управлении производственными процессами на основе нечёткого алгоритма распознавания.//Изв. АН CCCF. Техн. кибернет.1984,N6. С. 100-105.

37. A. c. 1108437, СССР, G06 F 7/02. Устройство для выделения экстремального числа./ В.П.Карелин. Б.Н.Миронов.- Опубл. 1984. Бюл. N30.

38. А. с. 1156060, СССР. G06 F 7/02. Устройство для выделения экстремального числа. / В. П. Карелин, Б: Н. Миронов. - Опубл. 1985. Бюл.N18. '

39. Калашников В.А.,Карелин В.П..Королёв А.Г. Метод решения,за-

'- 33 - _

дачи минимизации числа межслойных переходов. //Электронное моделирование. Том 7, N5. Киев: Наук, думка. 1985. с. 42-45.

40. Мелехов А.Н..Карелин В.П..Ковалёв С.М. Построение классификационных моделей на основе экспертной информации и обучающей, выборки. Изв. СКНЦВШ. Технич.науки. N1.1986.- С. 42-45.

41. Карелин В.П.,Каркищенко А.Н..Гитис С.А. Использование продукционных экспертных систем в САПР СБИС. //Тезисы докл. Всесоюзн. научн.-технич. конф. - Москва, 1987. С. 32.

42. Калашников В.А., Карелин В.П.. Молдавский Л.Н. Метод локализации ошибок в топологии БИС при контроле на соответствие электрической схеме. //Изв. СКНЦВШ. Технич.-Науки, 1987, N -2,

с. 46-50.

43. А.с.1345188, СССР, G06 F 7/02.. Устройство, для выделения максимального числа. / В. П. Карелин. В.Н.Рэшетняк.- Опубл 1987. . Бюл. N7.

44. Мелихов- Ä.H.,Карелин В.П..Ковалёв С.М, Построение нечёткой классификационной модели принятия решений на основе обучающей выборки. Электронное моделирование.'. N1.1987. - С. 2-7.

45. A.c. Í365576, СССР; G05 F 7/06. Устройство для сортировки чисел. /'В. П. Карелин и др. - Опубл. 1988-. Бвл.Ш.

4.6. A.c. 137607Э, СССР, G06 F 7/02. Устройство для сравнения чисел./ В.П.Карелин и В.А.Авдеев.- Опубл. 1988. Бюл.N7.

47. А.с.1444753, СССР, GÓ6 F 7/50. Устройство для вычисления раз- ч ности двух члсел. / В.П.Карелин и др. - Опубл. 1983. Бюп.М4б.

48. Карелин В.П..Калашников В.А., Молдавский Л.Н. Алгоритмический подход к- решению задач контроля топологии БИС. Деп. ВИНИТИ N5183-В88 2Э. 06.88' г.

49. А. с. 1449984 СССР. G06 F7/34. Устройство для »пк-д-ж-ния максимального числа. /В. П Кяраяин и др. Опубл. 196.9. Нюл.!.' .

50. A.c. 1451867," СССР. Gl 1 С 19/00,- НОЗ 147/12'. Буферный регистр. /В.П:Карелин и'др.- Опубл. 1989. Бюл.N2.

51. А. с. 1487028,'СССР, G06 р 7/50.' Устройство для вычитания. / В.П.Карелин и др. - («публ. iV39. Бюл.шг.

52. А. с. 1.5G9868 СССР.. G06 F-7/02. Устройство для цлвтчнкя чпоол. А.Н. Мелихов. 3. П.}(арелнк. Опубл. 1989. Бюл. М-35.

53. А. с. 1520508. СССР'. G0-: F 7'06. Устройство коммутации н v,¡.-тировки./ В'. ГГ. Карелин и др. - Опубл. 1989. Бюл. N41.

54. А. с. 1524055, СССР, G06 F 15/20. Устройство для раскраски графов/ В.М.Глушань. В. П. Карелин. - Опубл.' 1989.■ Бюл.' 1143.

- 34 - .

55. А.с.1525699, СССР. G06 F 7/02. Устройство для сравнения множеств./ В.П.Карелин и др.- Опубл. 1989. Бюл.N44.

56. А.с:.1541593, СССР, G06 F 7/06..Устройство для сравнения./ В.П.Карелин и др. - Опубл. 1990. Бюл. N5.

57. А,с.1546961 СССР, G06 F7/02. Устройство для сравнения чисел./ . А. Н. Мелихов, В. П. Карелин, Д. М. Чехов Опубл. 1990. Бюл. N-8.

58. А.с.1589268, СССР, G06 F 7/50. Устройство для выполнения операций над нечеткими переменными. / В.П.Карелин,A.II.Мелихов. - Опубл. 1990. Бюл. N32.

59. А. с. 1590999, СССР, (j5Ó6 F 7/02. Устройство для выделения экстремального числа./'В.П.Карелин и др.- Опубл. 1990. Бюл.N33.

60. А.с.1619252, СССР," GOß F 7/00. Устройство для обработки нечеткой информации./ В.П.Карелин и др.- Опубл. 1991. Бюл-Nl.

61. А.с.1635216, СССР, G11 С 15/00. Ассоциативная ячейка памяти. / В.П.Карелин и др. - Опубл. 1991. Бюл.N10.

62. А. с. 1644133, СССР. G06 F 7/50. Устройство для вычитания. / В.П.Карелин и др. - Опубл. 1991. Бюл.N15.

63. А.с.1645970, СССР, G0S F 15/419. Устройство для раскраски гра-•фов/ В.П.Карелин и др.- Опубл. 1991. Бюл.N16.

64: А.с.1647562. СССР. G06 F 7/06. Устройство для сортирозки двоичных чисел./ В.П.Карелин и др.- Опубл. 1991. Бюл.N17.

65'. А. с. 1649533, СССР. G06 F 7/08. Устройство для сортировки чисел. / В.П.Карелин их др. - Опубл: .1991. Бюл.N18.

65. A.c.1654813, СССР. G06 F 7/50. Устройство для вычитания. / В.П.Карелин и др.- Спубл. 1991. Бюл.N21.

67. А.с.1683004, СССР, G06 F 7/02. Устройство для анализа нечетких данных./ В.П.Карелин и др. - Опубл: 1991. Бюл.N37.

' 68. А.с.1711189, CCCF, G06 F 15/419. Устройство для раскраски графов/ В.П.Карелин и др.- Опубл. 1992. Бюл.N5.'

"69. Мелихов А.Н..Карелин В.П..Решетняк В.Н.■ Устройство для сравнения. Патент РФ N 1541593 от 25.11.93.

'70. А. с. 1753428 СССР, G06 F7/02.. Устройство для определения экстремальных чисел./Б. П. Карелин и'др. Опубл. 1992. БЮЛ. N-2S.

71. Карелин В. П. .Коровин С.Я..Мелихова O.A. Представление и обработка нечётких знаний в медицинских информационных системах.// Междуведомств, сб. Медицинские информационные системы.Вып.4. Таганрог, 1993,- с.192-197.

72. Глушань В. М., Карелин В. П.'.. Курейчик В. М. Средства аппаратной поддержки.обработки данных и- знаний в интеллектуальных САПР.

- 35 - ,

//Междуведомств, научн. сб. Интеллектуальные САПР. - "Таганрог: ТРТУ, 1994. Вып. 4. сЛЗО.

73.- Карелин В.П. Распознавание изоморфизма графов к гиперграфов на основе метода сопутствующих подцелей и сравнения помечающих подмножеств.//Сб. материалов Всероссийской научно-техн. конференции " Персональные исследовательские комплексы и АРМ-94", Таганрог. 1994.

74. Глушань В. М..Карелин В.П. Комбинаторные модели поиска и принятия решений на основе распознавания отрбражения графов.// Сб. материалов Всероссийской научно-техн. конференции " Персональные исследовательские комплексы и АРМ-94". Таганрог. 1994. '

75. Положительное решение на выдачу патента на изобретение по за явке N 5060410 от 17.03.94. Устройство для вычислений.

/ В.П.Карелин и др. ,■' 1 .

76. Карелин В. П. Модели нечеткого вывода й их аппаратная реализация. // Междуведомственный те^Йтич. научк. сб. Многопроцессорные вычислительные структуры.Вып. 15. - .Таганрог. 1995, с.21-25.

Среди работ, опубликованных в соавторстве, личный вклад автора диссертации следующий: [1,5,6,9,10,13,42.48.39,74] - выполнена постановка задач, предложил способы проверки правильности установленного соответствия изоморфизма и разработал способы сокращения перебора; [2, 24-26/, 31, 32,35,36. 40.71]. - предложил в ка- " честве модели принятия решений использовать нечеткие модели распознавания и классификации; [3]- предложил способ оценки качества декомпозиции графа; [8,11,14.18] - разработал латричную модель канальной "трассировки и алгоритмы минимизации числа занятых каналов; [12] - постановка задачи, разработка алгоритмов размещения и декомпозиции; [16,19,21,39] - разработал методы формализации задач в виде .псевдобулевых функций й конкретизацию метода ветвей и границ; [17,34] - разработал алгоритм раскраски вершин графа, ориентированный'на аппаратную реализацию; [20,28,29] -.предложил подход, основанный на последовательном распределении нагрузки, разработал алгоритмы распределения ■ и перераспределения; [23] -разработал модель сокращения пространства поиска и спссоб сравке-ия множеств; [27,33,41] - предложил способ построения модели на основе формализации нечётких инструкций; [30.37.33.43.59.67] -предложил использовать унитарный код, способы аппаратной реализации операций с нечёткими множествами и операций в логике Л.Заде:

[45,53,61,64,65] - разработал способы.и алгоритмы аппаратной■реализации операций выделения экстремального числа; [46,51,58.60,62, 66] -. предложил реализовать операции нечёткой логики Лукасевича ' путём сдвига в регистрах унитарных кодов чисел; [47,50,5о, 57.72,76] -'разработал подходы и способы аппаратной реализации определения сходства нечётких множеств на основе операцииЧвычитания и аппарат-, ные способы отыскания экстремумов; [49,52,57,70] - предложил способ аппаратной реализации операций, обеспечивающих получение нечёткого композиционного вывода; [54,63,68] - предложил способы аппаратной реализации сокращения перебора при поиске оптимальной раскраски графа.

о