Введение к работе
"Актуальность темы. В настоящее время актуальными и важными направлениями развития математической кибернетики является разработка проблем синтеза логических схем и распознавания образов. Гто связано с тем, что от уровня развития указанных областей непосредственно зависит эффективность методов решения «ажных прикладных задат.
Автоматизированный синтез цифровых упраэляших схзм - лша из таких задач. При проектировании управлявших автоматов их комбинационные части реализуются, как иравило, на основа регулярных структур - постоянных запоминавших устройств (ПЗУ), програшируемых логических матриц (НИМ), дешифраторов и т.д. Математически комбинационно-логическая схема задается системой частичных булевых функций (СЧБФ). В процессе синтеза cxew СЧБФ заменяется системой дизъюнктивных нормальных форм (СДНФ), каждая из которых является .возможным доопределением соответст-вуюшей функции исходной системы. При этом возникает задача нахождения простых отделителей подмножеств ft - мерного единичного куба (гиперкуба).
В качестве отделителей желательно использовать единичные и нулевые подмножества булевых функций, имевших простую структуру и однозначно определяемые экстремальные нормальные формы. Этому условии отвечают монотонные функции. При синтезе комбинационно-логических сх %м для осупествления монотонных отделителей необходимо провести преобразование входных сигналов. Такое преобразование может обеспечиваться специальной ПМ. Существенным является то, что СДНФ, описывающая монотонные функции, может быть оптимально синтезирована с помошью гэвестных
методо^„ Отметим, что при этой реализации не треоуется прэдотавлени" входов в парофазном виде.
В проолеме распознавания образов особое место занимают задачи, в которых все описывающие объекта признаки являются бинарными. Важнооть этого типа задач определяется, в первую очередь тем, что в описательных науках, таких кал медицина геология и т.п., данные,, вообще говоря, задаются о невысокой степрнью точности. В силу этого замена числовчх значений признаков бинарными не приводит обычно к значимому ухудшению решения.
Пусть единичное и нулевое множества частичной булевой функции f соответствуют обучающим выборкам диух классов объектов. Как правило, основная содержательная чгсть эврис тичеоких алгоритмов распознавания образов о бинарной информацией Сетон* в выборе того или иного доопрзделчния f не весь П. -мерный единичный куб ( П. - чиоло признаков) или его чаогь. В зависимости от значения доопределенной функции принимается решение об отнесені і нового объекта к одному из двух классов.
В задачах распознавания образов естественно аппроксимировать множества, соответствующие эталонным объекта" двух классов , единичными множествами булевых функций простой структуры. Выше было указано, что для этой цели удобно использовать монотонные функции. Здесь для существования таких монотонных отделителей также необходг о провести некоторое преобразование двоичного приэнакого пространен а. Однако существенно.чтобы такое преобразование сохраняло правило доопределения задающих подмножеств. Это правило может быть задано при по-
мопш некоторой функции близости (метрики) ча П. -мерном единичном куба. Заметит.!, что важна также простота определения значений Гунгции близости на преобразованном гиперкубе.
Таким образов, разработка методов аппроксимации подмножеств вершин rt -мерного единичного куба множествами эдингад монотонных оулевьх функций позволит предложить новые метода решения упомянутых важных практических задач.
Целью диссертационное работа является изучение возможности аппроксимация подмножеств вершин П- -мерного единичного куба множествами единиц монотонных оулевых функций и разработка на данной основе методов решения прикладных задач.
Научная ловизна, состоит в том, что в диссертации впервые поставлена и рс :ена задача построения преобразования п. -мерного единичного куба, обеспечивавшего монотонность булевых функций, отделяющих своши мно~ествамн единиц подмножйсте . указанного куба при сохранении определенной на нем метрики. Решена задача аппрокоимапі произвольных булевых функций дв^мя монотонными.
Получены результаты, описгаашие структуру случайных монотонных булевых функций с .іалим числом нижних единиц.
Практическая ценность работы состоит в разраооганних на ее основе программах синтеза комбинацгонно-логичеоких схем в виде программируемых логических матриц. Полученные в диссертации алгоритмы построения биективного преобразования единичного rt -мерного куба а формулы нахождения монотонных отделяющих функций составляют содержательную часть предлагаемого метода распознавания образов в двоичном признаковом пространстве
Апробация рабли. Результата диссертационной работы доклады валим» и обсувдались на семинарах отдела методор комбинаторного анализа и проблем распознавания ВЦ АН CCGP и НИИ молекулярной электроники МЭП,
Публикации. По материалам диссертации опубликованы 4 работы.
Структура и объем работы. Диссертация состоит из введения, пяти глав, придиУенил, заключения и содержит 77 страниц машинописного текота. Список литературы включает 16 наименований.