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

микистгхтзо сетсто и пк>»в<хзетнАЛЬного «эдзоэлкшг ,

РОССИЙСКОЙ ОНДВРАЦИИ • • ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УгаЕЗРСИТЗТ

Ь и ОД

2 и НО л 'СО7

ЛДЦЕГ.ШРОЗ Кгс-а,

УДК 510.22:62-50

математический аппарат для опкслшш

НЕОПРЕДЕЛЕННОСТИ II ЕГО ПРИМЕНЕНИЕ В 3.\Д\ЧЛХ РАСТТОЗНАПАШШ,

т?лса;ро2гз: и ¡юглмутлцпи

05.13.05. - "Згг'гпм г: уггрсПягз яьгз^гсггсзгсй таггекп и сетгп уп?ззг:п::зв; 05.13.17. - Тссргпгсггжг оггккм шфор^тк^г*.

А з т о р е ф е р а т Г'-сс^тги'-г» ет сзязкгжЪ у»:сЯ стгпсп гжсзжт кмккгг^гк пзуг:

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

Научный руководитель - доктор технических наук, профессор Л. С.Берштейн.

соруководитель - кандидат технических каук. профессор П. А.Кадиеа.

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

доктор технических наук, профессор В.П.Карелин, кандидат технических наук, доцент А. К. Ровицкий.

Еедугдд о?гсл;;зад:л - Вучксхззте.съеьй центр Ростовского гсс дарственного ушаэерсатета

на заседании специализ!, ____________

государственного радиотехнического университета по адрес!

:кой обл.. пер. Некрасовский, 44. ау;

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

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

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

Ученый секретарь специализированного совета А.Г. Чефранс

/ J У

!, у

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

АКТУАЛЬНОСТЬ ТЕМЫ. Увеличение сложности технических средств, применяемых в народном хозяйстве, необходимость повышения качества управления техническими и организационными системами приводят к построению моделей все более крупных и сложных объектов различной природы и к слабоформализованным задачам управления ими. решение которых связывается с имитацией поведения опытного специалиста-оператора.

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

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

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

- & -

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

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

ЦЕЛЬ РАБОТЫ. Целью настоящей работы является построение математического аппарата для. описания систем, содержащих неопределенность в поведении и (или) структуре, и исследование его возможностей при решении некоторых задач распознавания, трассировки и коммутации.

ЫЕТОДЫ ИССЛЕДОВАНИЯ. При решении поставленных задач использованы методы и понятия теории множеств, теории меры, формальной логики, теории вероятностей, теории отношений, теории автоматов, теории распознавания образов.

НАУЧНАЯ НОВИЗНА, Научная новизна работы заключается в разработке математического аппарата для описания неопределенности. На защиту выносятся следующие основные результаты:

1. Обоснование способа обобщения характеристической функции множества.

2. Понятия расширенного и обобщенного описаний множеств.

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

4. Исследование свойств обобщенных операций над множествами.

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

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

- В -

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Диссертационная работа выполнялась в рамках госбюджетных и хоздоговорных НИР. проводившихся на кафедре информатики и управления в технических системах Дагестанского государственного технического университета и в АО НИИ "Сапфир".

Практическими результатами работы является:

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

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

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

ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ. Теоретические исследования, алгоритмы и структуры, приведенные в диссертационной работе, использованы в учебном процессе, а также в госбюджетной и хоздоговорной НИР, выполненных на кафедре информатики и управления в технических системах Дагестанского государственного технического университета и в АО НИИ "Сапфир", что подтверждается соответствующими актами.

АПРОБАЦИЯ РАБОТЫ. Результаты, исследований докладывались на:

- 8-й Научно-технической конференции молодых ученых и специалистов Дагестана "Автоматизация производства и использование средств ВТ в народном хозяйстве", Махачкала., 1985 г.

- 2-й Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники "Информатика-87", Ереван, 1987 г.

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

- Первом международном симпозиуме "Интеллектуальные системы - 94". Россия. Дагестан. Махачкала, 22-27 июня 1994 г.

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

- в -

тельского состава ДГТУ в 1994-1996 гг.

ПУБЛИКАЦИИ. По результатам исследований опубликовано 6 печатных работ и одна депонирована в ВИНИТИ.' технические решения защищены пятью авторскими свидетельствами.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы (50 названий) и приложения. Основная часть изложена на 155 страницах машинописного текста, содержит 24 рисунка и 4 таблицы.

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

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

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

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

В основе второго способа формализации нечеткости лежит понятие так называемого множества уровня а: А = (х I рА(х))а)). Здесь нечеткое множество понимается как иерархически упорядоченная система обычных множеств. . . .

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

тарных образует составное множество: для произвольного множества наименьшее составное, содержащее его. называется верхним, а наибольшее составное, содержащееся в данном - его нижним приближением; два множества равны приближенно снизу (сверху), если равны их нижние (верхние) приближения, и приближенно равны, если они приближенно равны сверху и снизу. Класс множеств, приближенно равных данному, называется приближенным множеством.

Еще одна концепция неопределенности,- недоопределенные множества Нариньяни.- позволяет описывать частично неизвестные множества и связана с типом данных, задаваемым четверкой объектов: Н-<+А, -А, М„, !-!„>, где +А и -А - конечные множества, а М, и М„ -натуральные числа. Множество +А (-А) - это те элементы.универсума, о которых точно известно, что они прннадлеват (не пркнадле-глт) множеству А, а числа Мж и М„ - верхняя и нижняя оценка мощности множества А.

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

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

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

модель Нариньяни построена лишь для конечных ?кстестз.

Интервальные статистические кодел! Кузнецова искусственно

- о -

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

Следует отметить подчеркивание некоторыми авторами (Павлак. Нариньяни) несводимость их моделей друг к другу и к нечетким множествам.

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

Во ВТОРОЙ ГЛАВЕ анализируется связь категорий количества и качества с основным! понятиями математики: числа, множества, элемента множества, принадлежности и включения; связь основных понятий теории множеств с тремя основными видами научных понятий: классификационными, сравнительны:«! и количественными.

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

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

Для математического исследования качественной стороны множеств последняя должна быть организована в какую-либо математическую структуру. Таковой является функция принадлежности (характеристическая функция) множества, представляющая собой предикат ("предмет а является элементом множества А"), определенный на универсуме и. Если вместо истинностных значений приписать характеристической функции числовые (1 и 0). то их можно интерпретировать- как количество элементов (одноэлементного) множества (а}еи. включенных в определяемое множество, т.е. от вопроса "Является ли предмет элементом множества?" мы переходим к вопросу "Сколько элементов одного (одноэлементного) множества включается в другое

- о -

множество?".

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

Формально неопределенность на множествах описывается следуп-1!Мм образом. Пусть U - универсум. V-{v) - система подмножеств уккверсука (назьзаемюс пе'рничкк-ш), таких, что

VvEV: vcu. и v-U.

" v£V

Для произвольного гксг.5стБа XQJ рассмотри.! совокупность первичных ннояестз v£V, имегацих с X непустое пересечение:

X-{v I vnx-э). (1)

Назовем (1) расширении описанием кногества X з систенз V. • Назовем два множества X и Y расваренко равнкот (Р-разнши. X-Y) в система V, если они янеат в этой систеке одно и то га расширенное описание. Обозначим К(Х) - хпгсс гаожгств с Р-опксанпем X.

Пусть Y-1X. Г "~X\Y - {v| v С X}. Рассмотри два гкспоства:

Хв - Uv . Хн - Uv (2)

vex ver

Видно, что Хнсхсхв. Есл! У является разбиением ужнерсума, то множества Хв и Хн совпадают с приближенными множествами соответственно Ав(Х) и Ан (X), исследовании!!! Павлаксм.

УТВЕРЖДЕНИЕ 1. Для того, чтобы разкнм Р-описанням соотьетс-

твовали непересекающиеся -классы Р-равных множеств, необходимо и достаточно, чтобы никакая пара первичных множеств не имела оСвдх элементов: \МУу26У: у1Пу2-о » (Х*У & К(Х)ПКф-в).

УТВЕРЖДЕНИЕ 2. \ZXVY £ К(Х): ХЦУЕК(Х). другими словами, масс К(Х) множеств замкнут относительно операции объединения.

Пусть М, - функция, определенная и ограниченная на подмножествах множества у. причем Ит(в)-0, и для любых у1.у2Су. для которых она существует, у1Лу2»о * М„(ушу2) - Му(у1)+М„(у2). Будем далее обозначать для любого ХС11: М„(Х)=М„(уЛХ). Как видно из определения. введенная функция - мера на множестве у. Она и является обобщением функции принадлежности мнокества.

Для произвольного хси рассмотрим множество X пар вида

X = {<У. МУ(Х)> | М„(Х) "0). которое будем называть обобщенным описанием (0-описа>;ием) мнокества X. Два множества X, уси назовем обобщенно равными (О-равны-ми. Х=У). если они имеют одно и то же обобщенное описание {если Vv£V: Му(Х) - ?•!„ (У). Ясно, что X является О-описанием всех множеств из класса К(Х) множеств, обобщенно равных множеству X.

Утверждения 3-5 обосновывают обобщение теоретико-мнокествен-ных операций,

УТВЕРЖДЕНИЕ 3. Для того; чтобы пересечение первичного мнокества V с объединением двух множеств X и У равнялась по мере максимальному, а с их пересечением - минимальному (по мере) из его пересечений с кандым их них'в отдельности, необходимо и достаточно, чтобы хотя бы одно из двух множеств: уПУ\Х или уПХ\У. -равнялось нулю по-мере. В символической форме:

VvEV: (уПУ\Х)-ОУМ„(УПХ\У)«0))*>(МУ (ХиУ)=МАХ(Му (Х).М,(У)))&= Шу (ХЛУ)=Ы1Ы(Му (Х).МУ (У))).

УТВЕРЖДЕНИЕ 4. Для того, чтобы мера пересечения первичного множества V с разностью множеств X и У равнялась минимальному из его пересечений с множествами X или 1У. необходимо и достаточно, чтобы хоть одно из множеств: у\(Х11У) или уПХЛУ. - имело бы нулевую меру.. В символической Форме (Му(у\(ХЦУ))=0 v М,(уП ПХЛУ)=0) ♦» (Му(Х\У)-МЩМу(Х), Му(1У)).

УТВЕРЖДЕНИЕ 5. Для того, чтобы УуеУ: Му (ХДУ)=МАХ(МЩМу (X). Му(1У)). МШ(МУ (IX) ,МТ (У))). необходимо и достаточно, чтобы выполнялись одновременно условия Утверждений 3 и 4. Иначе говоря. VveV: ((Му(уЛУ\Х)=0УМ7(уПХ\У)=О)Ь(Мт(у\(ХиУ))=0УМ7(уГ>>=ХЛУ)=0)) »

-11 -

•М„(ХДУ) - НАХ(Н1Н(М,(X). НТ(1У)). Н1Н(М,(1Х). М,(У))).

Будем говорить, что X обобщенно включает У, Х2У. если Ууеу: Му(У) с М,(X). Если при этом Зу€У: И,(У) < М„(Х)7 будем говорить о строгом обобщенном включении усх.

УТВЕРЖДЕНИЕ 6. Если множество У обобщенно включается в множество X, то для любого множества 2 из класса К{У) найдется мно-кество Г из класса К(Х), такое, что гср; аналогично, для любого множества Г из класса К(X) найдется множество 2 из К(У). такое, что усх •» УгектзгеШ): 2С?. усх ■» УГеК(Х)ЗгеШ): ОТ.

Назовем У обобщенным дополнением множества.X. У-IX. если И,(У) - Му(v)-М,(X). Для О-дополнения можно сформулировать утверждение, аналогичное утверждению 6.

УТВЕРЖДЕНИЕ 7. Два утверждения: "Кнонество У равно обобщенному дополнению множества X" и "Множество У обобщенно равно дополнению множества X" логически эквивалентны: У-1Х»У=)Х.

Назовем 2 обобщенным объединением множеств X и У. ~2=УШ. если И, (2) - мах(м, (x), м„(у)). Для о-объедкнения моено сформулировать утвервдение, аналогичное утверждению 6.

УТВЕРЖДЕНИЕ 8. Два утверждения: "Множество 1 равно обобщенному объединению множеств X и У" и "Множество Ъ обобщенно равно объединению тожеств X и У" логически эквивалентны если и только если справедливы условия Утверждения 3. В символической форме (г«хиу«2-хиу) * (УуЕУ: Г!,(уПХ\У)-0 V М„(УЛУ\Х)-0).

Назовем 2 обобщении пересечением множеств X и У. г-ХЛУ, если М»(2)-М1Н(М,(Х).КТ(У))-.

Назовем 2 обобщенной разностью мнонеств X и У. г-Х\У. если М,<гнШ(М„Ш. И, (у)-Мт(У)).

УТВЕРЖДЕНИЕ 9. Обобщенная разность множеств X и У обобщенно равна обобщенному пересечению множества X с обобщенным дополнением мнокества У. Иначе говоря. ХЧУ-ХП(1У).

Назовем 2 обобщенной симметрической разностью множеств X и У, 2'Ш. если

УуЕУ: МУ(Х) - ИАХ(1ЛЫ{И, (X),!!, (v)-М¥ (У)). М1И(Г!, (У). Г!у (v) (X))).

Для О-пересечения, 0-разности и 0-симметрической разности множеств доказаны утверждения, аналогичные утверждениям 6 и 8.

УТВЕРЖДЕНИЕ 10. обобщенная симметрическая разность множеств X и У обобщенно равна обобщенному объединению обобщенных разнос-

тей множеств X с У и У с X. В символической форме ХдУ»Х\УЦУ\Х.

Связь между Р- и О-описаниями имеет вид:

Кф - и К(П и

УуЕУ: у£Р»уех в. 0<МУ (Г) <И» (v)

и (Н1 Н - и УУ£Х: 0«1,ит)<М,(У) ЗУЁХ: И,(^)-0}

у^Х

л

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

Рассмотрим множество Ьт-{Му(а).....М,(V)} возможных значений

функции Ну(X). Введем на Ьт систему У,-{т,} подмножеств, покрывающих Ьу, и расширим конструкцию 0-описания: X - {<у.ау>}. где А»

- расширенное описание некоторого множества А,£Ь, значений функции М»(X). ' Назовем X расширенным обобщенным описанием (РО-опи-

санием) множества X. Класс К(Х) содержит те подмножества универ-

■х

сума и, для которых функция Мт(X) принимает значения из А,.

В том случае., когда МУ.(Х) - числозая функция, а (единственное) множество ш,еут является отрезком т» - (Мн, На]. РО-описание

X» - «Ь- Цу. Ц|>. <Н* и». 0>. <и\Н. Шн.йв]» х УСХ у»ЯХ=в

,является недоопределенным множеством Нариньяни. -

На каждом т„еУу определим функцию М с теми же свойствами, что и у Му. Обозначим, как и ранее. М (А») - М^ (АуПЩу), ,Ау£Ьу. Теперь можно определить дважды обобщенное описание (2-0-описание) множества X:

х-{<у. Му(Х)>).

в котором множество Ат значений функции М,(X) задано своим обобщенным описанием Му(Х)-{<шт. М (А,)>).

~ Шу

Вообще. Ы-обобщенным описанием (И-О-описанием) множества X назовем такое 0-описание, обобщенная функция принадлежности которого задана своим (К-1)-обобщенным описанием.

Если нормировать 0-функцию принадлежности Му(X)(Х)/М„(v), то обобщенное описание X порождает нечеткое (в смысле Заде) подмножество множества V: Ху={<у.м»(X)>>. Нормировкой соответствующих 0-функций порождаются и нечеткие множества типа 2, 3 и т.д.

Рассмотрим один частный случай системы V. в котором для любых у1.у2£У: у1*у2=>у1Пу2-0. Будем рассматривать лишь такие мно-

аества X.Y...си. для которых Vv£V: либо v£X. либо vHX-e. и пусть

W - класс всех таких множеств. Очевидно, VxeW: X-Uv ; VvEV:

vPX*a

(v£X)v(v6|X); если X£W. то lxew; если X..yew.то XUYEW. xnyew. Таким образом. W является алгеброй множеств, а

ру(Х) - Mr(X) / J Mv (v> -VtV

элементарная нормированная мера. Мера Р(X) для любого X из U

находится как сумма Р(Х)- I р¥(Х). причем. P(e)-0, Р(U)=1

v€X

P(XUYU...)=Р(Х)+Р(У)+... для X.Y.... из W. таких, что попарно ХПУ=о. Таким образом, введя соответствующие ограничения на систему V и класс рассматриваемых множеств, мы получили аксиоматику теории вероятностей.

Введенная система понятий применяется к отношениям на множествах и к автоматам.

Пусть задано отношение D мнокеств X и У: D(X,Y) = {(x. у)}. где D(X. У) - подмножество множества ХхУ. -

Введем на декартовом произведении этих мнокеств систему vxy " ivxy} первичных подмножеств, vxy - {(х, у)}. Тогда D(X.Y)-{vxy|vxynD(X,Y)*<3} - расширенное описание отношения D(X.Y) в системе VXY.

Рассмотрим проекции первичного множества vxy на множество X: [lpl(vxy)-vx»{xl (х. у) CD). Очевидно, совокупность Vx всех таких множеств vx покрывает множество X. следовательно, ее мояно использовать в "качестве системы первичных подмнозеств множества X.

УТВЕРЖДЕНИЕ 11. Если D(X.Y) - расширенное описание отношения D(X.Y) в системе VXY. то X-inpl(vxy) |vxy с D(X,Y)} является расширенным описанием множества X в системе Vx .

Пусть теперь каядому vxy с vXY сопоставлена функция Нт . с рассмотренными выше свойствами. Тогда D(X.Y)»

-{<vxy,Mv(D)>IMv(D)*0}' - обобщенное описание отношения D.

Пусть задан автомат S=*(X.Y,Z,А.В), где Х»{х). У=(у). Z-{z) -алфавиты соответственно входной, состояний и выходной, функции А={(х.у1.у2)} - переходов. В-{(х.у, z)> - выходов. Функции А и В -трехместные отношения. Если любое из этих отношений задано своим расширенным или обобщенным описанием, будем говорить, что мы имеем соответственно расширенное или обобщенное описание автомата S.

В ТРЕТЬЕЙ ГЛАВЕ показано использование введенных понятий при разработке алгоритмов и устройств для обработки информации. Если

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

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

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

ром распознанных текстур.

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

Обозначим Х„ характеристический вектор '¿ножества Xf~lv и назовем его v-вектором множества X, тогда IX» I = MV(X).

Пусть система V и два множества X и Y таковы, что выполняются условия утверждения 3. Тогда, если Z-XUY, то IZ,I « MAX(iX„l. IY,I). Если Z-ХЛУ. то IZJ - MIN(IXVI, |YVI). В первом случае Zv получается в результате поразрядной дизъюнкции, а во втором - поразрядной конъюнкции векторов X» и Yv. Если для X и Y выполняются условия утверждения 4, тогда, если Z-XVY, то IZVI = MIN(IXVI. I~YVI). и вектор Zv получается в результате поразрядного выполнения отрицания импликации над векторами X, и YT. Ее л: для X и Y выполняются условия утверждения 5. тогда, если Z=*XAY, то IZvI= =МАХ(MIN(IXVI. I~YVI), М1И(1-Х»I. IY,I)). Здесь вектор Z, получается при поразрядно;! суммировании по модула два векторов Xv и Yv.

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

Рис.1. Структура устройства для обработки двоичных векторов. 1 и 2 - информационные входы, 3 - выход. 4,5.12 - настроечные входы, б и 7 - дешифраторы кода, 8 - блок поразрядных логических* операций, 9 - регистр, 10 - сдвигатель, 11 - шифратор.

- 16 -

устройстве для логической обработки у-вектороз.

Дешифраторы 6 и 7 преобразует значение функции 1!, (X). или нормы IX, I. в двоичный вектор с соответствующим числом единиц, в котором единичные и нулевые значения упорядочены (например, единицы стоят правее нулей). После выполнения поразрядного отрицания. когда этот порядок меняется на обратный, сдвигатель Ю" восстанавливает его обменом правых и левых компонент (относительно середины вектора). Согласно утверадениям ю и 11. логическому блоку достаточно выполнять лишь операции поразрядных дизъюнкции, конъюнкции и отрицания, так как остальные (при соответствующих условиях) могут быть сведены к этим трем.

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

Пусть и - множество (микро-) ячеек дискретного рабочего поля. V - система макроячеек, покрывающих ДРП. Будем рассматривать множества X! (микро-) ячеек, образующие проводящие соединения.

Построение каждого пути Х1 выполняется в два этапа. На первом выполняется трассировка по какроячейкак (построение 0-описа-ния пути Х^ где функция К,(Х1) является мерой'занятости путем X! множества ячеек, образующих данную макроячейку v) для чего необходимо знать, возможно ли проведение пути через какдую макроячейку V в данном направлении, причем целесообразно учитывать степени занятости какроячеек во всех возможных направлениях. В этом случае функция М,(Х1) будет принимать не числовые, а векторные значения: К„(Х!) - (ММХ,). 11%(X!-).....1!%(Х1)). где И%(Х,) -

занятость макроячейки V в к-то.ч направлении (количество направлений в плоскости связано с принятый отношением соседства ячеек).

Применение 0-описаниЯ (при некоторых упрощающих предполоее-ниях) сокращает время трассировки максимально в К раз, где к«(Мг+(Н-1)г)/((1»'/С!г+(}1ЛМ)*). Здесь N - средняя длина трассы. О --размер макроячейки.

Второй вариант задачи трассировки связан с установлением соединения в сети связи, в качестве которой рассматривается однородная коммутационная регистровая структура (КРС). Ее однородность не позволяет одновременно настраивать новый канал- связи н вести передачу информации по полученным ранее каналам. Обобщенное

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

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

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

В ЗАКЛЮЧЕНИИ сформулированы -основные результаты работы.

В ПРИЛОЖЕНИИ приводятся документы, подтверждающие внедрение результатов диссертационной работы.

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

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

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

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

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

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

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

6. Показана связь расширенных описаний с приближенными множествами Павлака; связь между расширенным и обобщенным 'описаниями множеств; совпадение одного частного случая 0-описания с расширенно заданной О-функцией принадлежности и недоопределенного множества Нариньяни; показано, что обобщенное описание множества в системе первичных множеств порождает нечеткое подмножество этой системы; что дополнительные ограничения на систему первичных множеств и класс рассматриваемых кнокеств приводит к аксиоматике теории вероятностей. Таким образом.' описание неопределенности строится конструктивно - как описание-, некоторого класса обычных множеств, причем известные способы списания неопределенности оказываются различный? стадиями этого процесса.- С точки зрения теории множеств эти стадии, по мере введения новых, ограничений-, образуют последовательность: расширенные описания (и приближенные множества Павлака): обобщенные описания (и • недоо1гргделенные множества Нариньяни); нечеткие !.шо:гества Заде; теория вероятностей.

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

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

8. Разработано устройство для выполнения обобщенных операций над информацией, представленной двоичными векторами. Обработка характеристических векторов не требует многозначных элементов или арифметических устройств на основе сумматора с длинными цепями переноса, следовательно, устройства для обработки нечетких данных могут строиться rçjjc высокопроизводительные параллельные логические процессоры.

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

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

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

1. И.А.АЯдемиров. О .нечетких операциях над четкими множествами. 8-я научно-техническая конф-я молодых ученых и спец-тов Дагестана "Автоматизация производства и использование средств ВТ в народ.хозяйстве". Тезисы докладов. Махачкала.. 1985г. стр. 10.

2. И.А.Айдемиров. О нечетком описании четких множеств. 2-я Всес.конф-я по актуальным проблемам информатики и вычислительной техники "Информатика-87". Тезисы докладов. Изв. АН Арм. ССР. Ереван. 1987 г.. стр. 190-191.

3. И.А.Айдемиров. О нечеткой и вероятностном описании множеств в интеллектуальных системах. Системный анализ и принятие решений в задачах ав8томатизированного обеспечения качества и надежности изделий приборостроения и радиоэлектроники. Российская научно-техническая конференция. Тезисы докладов. Махачкала. 1991г.. стр. 71 - 72.

4. И.А.Айдемиров. Вероятность и нечеткость в теории множеств. Депонирована в ВИНИТИ 20.12.93 г. N 3116 В93. 21 стр. 45.

5. И. А. Айдемиров. Неопределенность и теория^шожеств. Информатика и вычислительная техника. Теория и приложения. Меквуз. на-уч-тех. сб. Махачкала, изд. ЛГУ, 1994 г.

6. И.А.Айдемиров.' Обобщенное описание множеств и иерархические системы. Первый международный симпозиум "Интеллектуальные системы - 94".Сб.мат. и сообщ. Россия. Дагестан, Махачкала, 22-27 июня 1994г., стр. 46-48.

7. И.А.Айдемиров. Обобщенное описание множеств и конечные автоматы. Известия вузов. Приборостроение. 1995. Т. 38 N 3-4. стр. 19-21.

8. A.C. СССР Но 1446616 МКИ G 06 F 7/00. 23.12.88, БИ 47. И.А.Айдемиров. Устройство для обработки логической информации.

9. A.C. СССР No 1702385 МКИ G 06 F 15/20. 30.12.91.БИ 48. И. А. Айдемиров. Ф. Н.Бодин. Устройство для. сжатия двоичных векторов.

,10. A.C. СССР N0 1476484 МКИ G 06 F 15/20. 30.04.89. БИ 16. И.А. Айдемиров.Ф.Н. Бодин.Устройство для сжатия двоичных векторов.

11. A.C. СССР N0 1280608 МКИ G 06 F 7/02. 30.12.86. БИ 48. И. А. Айдемиров и др. Устройство для сравнения чисел.

12. A.C. СССР Но 1298748 МКИ G 06 F 9/46. 23.03.87, БИ И. И.А.Айдемиров. Многоканальное устройство приоритета.

В работах, опубликованных в соавторстве [9, 10. 11] предложил линейную структуру устройства [9. 10], триггеры в каждой ячейке [10]. сдвиговый регистр для хранения и преобразования исходного вектора. [9]. последовательную' по разрядам процедуру сравнения и логическую схему для совмещения процессов сравнения и