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

На правах рукописи

ДЬЯКОНОВ Александр Геннадьевич

X

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

01.01.09 - дискретная математика и математическая кибернетика

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

Москва-2003 г-к •• Г7 ™ "

- - - :ый

~ Л ЯР

Работа выполнена на кафедре «Математические методы прогнозирования» факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

академик РАН, доктор физико-математических наук, профессор Журавлёв Юрий Иванович.

доктор физико-математических наук Кузюрин Николай Николаевич,

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

Ведущая организация: Московский физико-технический институт

(государственный университет).

Защита диссертации состоится «__»_2003 г. в_часов на

заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиКМГУ.

Автореферат разослан «___»_2003 г.

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

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

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

Н.П. Трифонов

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

Актуальность темы. Методы теории распознавания (классификации) образов широко применяются для решения практических задач во многих областях (социология, экономика, биология, геология, медицина и т.д.)- Одним из наиболее применимых для решения практических задач распознавания является комбинаторно-логический подход, основу которого заложили работы академика РАН Ю.И. Журавлёва. Возникновение этого подхода связано с применением теории распознавания в плохо формализованных областях, где не удаётся построить адекватную математическую модель. Логические алгоритмы распознавания хорошо зарекомендовали себя на практике и, как правило, могут быть использованы даже при недостатке информации. Их синтез основан на выделении в описаниях объектов (ситуаций) подописаний, которые содержат информацию о различиях классов - выделение элементарных классификаторов. Построение множества всевозможных элементарных классификаторов или части этого множества, обеспечивающей высокую надёжность логического алгоритма, связано с вычислительными трудностями переборного характера. Задачу построения элементарных классификаторов можно формально записать с помощь языка теории дизъюнктивных нормальных форм (ДНФ). Сокращённой ДНФ характеристической функции класса (равна единице на описаниях эталонных объектов выделенного класса, нулю - на описаниях эталонных объектов других классов) соответствует множество всевозможных элементарных классификаторов. Поскольку построение сокращённой ДНФ трудоёмко и не гарантирует хорошего качества распознавания, необходимо уметь строить произвольные, но не очень сложные ДНФ. В случае плохого качества распознавания их можно «пополнять» операциями обобщённого склеивания. C.B. Яблонским, Ю.И. Журавлёвым и

Ю.И. Журавлёвым

РОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

С.Петерб;

09

А.Ю. Коганом было показано, что задача эффективного построения простых ДНФ по перечню нулей разрешима. Однако до сих пор не было разработано «быстрых» алгоритмов построения ДНФ, учитывающих специфику задач распознавания. Кроме того, задача ДНФ-реализации по перечню нулей рассматривалась, главным образом, только для булевых функций, т.е. исследования имели приложения только в задачах распознавания с бинарной информацией. Поэтому представляется актуальным рассмотреть случай целочисленной информации и разработать алгоритмы, ориентированные на применение в теории распознавания. Отметим, что в 1 последние годы после некоторого перерыва появилось значительное число публикаций, посвящённых задачам минимизации функций в классе нормальных форм и их аналогов. Это связано, в первую очередь, с широким применением результатов этих работ в теории распознавания и для решения практических задач классификации.

Целью работы является:

1. Разработка эффективных алгоритмов построения ДНФ характеристических функций классов для синтеза логических распознающих процедур.

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

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

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

Методика исследования: методы дискретной математики, теории множеств и отображений, численные эксперименты на ЭВМ.

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

Апробация работы. Материалы, изложенные в диссертации, докладывались на

- Международных конференциях студентов и аспирантов по фундаментальным наукам «Ломоносов 2001», «Ломоносов 2002», «Ломоносов 2003» (Москва, МГУ);

- Всероссийской конференции «Математические методы распознавания образов - 10» (Москва, ВЦ РАН);

- Международной конференции «Интеллектуализация обработки информации - 2002» (Симферополь, ТНУ);

- кафедре «Математические методы прогнозирования» факультета

вычислительной математики и кибернетики МГУ. Разработанные алгоритмы применялись в работах по проектам РФФИ 09-01-00433,00-15-96064.

Личный вклад. Выносимые на защиту результаты получены соискателем лично.

Публикации. По теме диссертации опубликовано 8 работ [1-8], в том числе 2 в ЖВМиМФ, 1 в ДАН. Описания отдельных результатов, полученных в диссертации, включались в научные отчёты по проектам РФФИ 09-01-00433,00-15-96064. t

Структура и объём работы. Диссертация состоит из введения, пяти глав, разбитых на параграфы, списка литературы (49 наименований) и приложения. Нумерация теорем, лемм, утверждений, примеров и формул своя в каждой главе. Основной текст занимает 118 страниц, приложение - 5 страниц.

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы и определяется направление исследования.

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

Функция вида / : (Et)" ->{0,1}, Et = {0,1,...,£-1}, называется

бинарной. Обозначим через DF ДНФ, составленную из конъюнкций множества D,

N(D)= U {&е(Ш2Г | £(а) = 1}, Z(D) = (E2y \N(D).

KeD

Множество булевых функций, зависящих от п переменных и имеющих ровно к нулевых точек, обозначается через Р". Считается, что функция / е Р£ задана матрицей (матрицей нулей)

j II Л1*хл

ai

a.

ai

a:

в которой по строкам перечислены все нулевые точки /. При

^ = / = {*!>•.-Л), < —<Л < — для

этой матрицы введём обозначения

= ),...,(я*,...,«*)},

«i

Л

ак, ... akt

л л

Для отображения g:X->Y при Zçl введём обозначение

g(Z) = te(z) | zeZ}. В £-значном случае элементарная конъюнкция определяется как выражение

Q = mm[JMi{xl),...JMn{xn),r], = \%м\

^еEt\{0}, 0*М,сEt для всех /е {1,2,...,«}. При этом если множества произвольные, то g называется Н-конъюнкцией; отрезки - А-конъюнщией, одноэлементные и ^-элементные множества - Т-конъюнкцией. Эти обобщения понятия элементарная конъюнкция на &-значный случай произведены в работах C.B. Яблонского, У .А. Абдугалиева, А.Н. Нурлыбаева. Выражение msx\Qx,...,Qq\, где Q\,...,Qq - элементарные конъюнкции (Н-

конъюнкции, А-конъюнкции, Т-конъюнкции), называется дизъюнктивной нормальной формой (Н-ДНФ, А-ДНФ, Т-ДНФ).

В первой главе также подробно описывается как возникает задача построения ДНФ бинарных функций по перечням их нулевых точек (матрицам нулей) при синтезе логических алгоритмов распознавания. Характеристическая функция класса в задаче распознавания имеет вид /:(Е*)Л->{0,1,г} (или можно считать, что / не всюду определённая бинарная функция). При этом простые импликанты функции / соответствуют элементарным классификаторам. Многие современные алгоритмы распознавания определяются подмножеством множества элементарных классификаторов. Важнейший этап синтеза алгоритма - построение этого подмножества. Затем по каждому элементарному классификатору производится голосование. Задача построения элементарных классификаторов по функции / элементарно сводится к задаче со всюду определённой функцией /:<В4)"-Н0,1}, /(¿¡0 = 0 о/(а) = 0.

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

Пусть в матрице нулей М^ =|| а^ ||Ьп булевой функции / столбцы с номерами из Т-{1,2,...,/} образуют тест (т.е. строки подматрицы Му[Т] различны), построена последовательность множеств Г(/+1),...,Г(и) такая, что

П М,[ти)][{1 <={1,2,...,*}|а} =у}] = 0,

уе{ 0,1}

Т(Л £ {1,2,...,/-1}, у = ¿ + 1,...,». В тестовом подходе ДНФ функции / строится в виде

[/>Т=[АТ V (1)

У=Г+1

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

К*=х1Га1& & х

ч

а ДНФ [1)г]р зависит от переменных л^,...,*, и строится специальным образом по матрице =

п к

Лемма 2.2. ДНФ [1>гГ V V УК), где - произвольная

/=/+1 /=1 1

ДНФ функции /т(х1,...,х,),реализует функцию /.

Таким образом, достаточно уметь строить ДНФ по тестовой подматрице размера к у. г, где t<k, а почти всегда t-¿Ио^к+ о($.о%2к)• Такое построение может быть осуществлено существующими алгоритмами.

В диссертации описан алгоритм А*в построения множеств ¿У. Его применение даёт, вообще говоря, более экономный способ ДНФ-реализации булевых функций в виде (1). В §2.2 замечено, что хотя теоретическая оценка | О* |<| ВТ \ +(и - 1)к может достигаться, как правило, получаются более короткие ДНФ.

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

мов синтеза ДНФ по перечню нулей строят нетупиковые нормальные формы с «неравномерным» вхождением переменных.

Показано, что с помощью тестового подхода можно получать явные ДНФ-формулы функций из некоторых важных классов. Например, получены простые ДНФ-представления почти всех функций из при к <, log2 п - log2 log2 п +1.

В §2.7 описана задача ДНФ-реализации по перечню булевых подкубов (интервалов), на которых функция обращается в ноль, т.е. задача синтеза по конъюнктивной нормальной форме (КНФ).

Лемма2.6. При п>к существует функция, заданная матрицей нулевых интервалов размера кхп, такая, что её сокращённая ДНФ является тупиковой и имеет длину d, d > \_п / k]k.

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

Выделен частный случай, когда применим тестовый подход: нулевые интервалы не пересекаются. Тогда исходная задача сводится к задаче с подматрицей, строки которой также соответствуют непересекающимся интервалам. Размеры подматрицы - kxt, где t <, k(k -1)/2 (равенство может достигаться).

В третьей главе исследована задача выполнения быстрых умножений ДНФ с «небольшим» числом нулей в нельсоновской схеме

Lf =Df (2)

При перемножении пары ДНФ Df, Dj в (2) справедливо Dy = Df & Df = [D/ uûjfv [D. \ Djf & [Dj \ D)f, где D/ ={Ke D, | N( {£} )r\Z(Dj)-0}. Достаточно построить множество Dj и Df, выполнить перемножение с сокращениями

[Д \ Я/У & [£>, \= и из П удалить все конъюнкции, поглощаемые конъюнкциями из множества и£)/. Кроме того, если Кх,Кг е Д \ £>/:

N({^1» п £ N({^2» п , то конъюнкция К1 может не участвовать в перемножении (при этом в искомую ДНФ Д? заносятся некоторые конъюнкции). Предложенный метод значительно сокращает число умножений в (2). Задачу об оптимальном умножении (упорядочивании множителей) предлагается решать минимизируя некоторую функцию

убывающую по первому и второму аргументам и возрастающую по третьему и четвёртому.

Более эффективно можно производить умножения на скобки КНФ (совершенной КНФ). При реализации алгоритмов построения ДНФ на ЭВМ одними из наиболее трудоёмких операций являются выделение памяти под конъюнкции и удаление конъюнкций. Поскольку заранее неизвестно число всех конъюнкций, с которыми придётся работать, ДНФ представляют в виде динамических списков. В §3.4 предложена реализация метода Нельсона, при которой минимизируется число операций создания/удаления конъюнкций.

Для умножения (х,=/* достаточно произвести умножение в

[Д! и...иД/ V Д' V&(ь V... Vх„), (3)

где Д = {АГ",...,^} - множество конъюнкций из £>, не содержащих букв из множества ,хи}, К? = & х-, Д, - содержащих ровно одну букву из этого множества, а остальные конъюнкции образуют

множество £>2. После формального умножения в (3) достаточно проверить только поглощения вида

М({х^}) С Щ{К}), К = х,. &*, е £>„..

Но такую проверку можно осуществить до выделения памяти под новую конъюнкцию. Память выделяется только в том случае, если не будет поглощаться другими конъюнкциями. В §3.5 предложен быстрый метод построения ДНФ по матрице нулей, основанный на обобщённой формуле С.В. Яблонского

/=1 1=1

где >2, - произвольные множества. По аналогии с (3)

искомая ДНФ функции /* ищется в виде V V В? так, чтобы

ЛЧЛ) = ВД>)\{(0,...,0)}. Пусть /,. 1 = 1,2,.тогда и

я

U

при i,je{l,2,...,q): гф j. Это позволяет, не осуществляя перемножения, занести в D* конъюнкции, обеспечивающие покрытие всех нужных точек, кроме, быть может, точек из

ffy«O\{(0,...,0)}.

(=1

Но это множество легко покрыть конъюнкциями вида Xj&K°&...

При умножении на скобку совершенной КНФ по обобщённой формуле C.B. Яблонского память также используется экономно. В §3.2 рассматривается булева функция

заданная матрицей нулей М^=[МУ\МХ], состоящей из двух

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

Определение. ДНФ функции / называется тестовой (относительно переменных уг,...,у(), если она состоит из конъюнкций, в каждую из которых входит не более одной буквы из множества {х1,...,хп,х1,...ухп}, а дизъюнкция конъюнкций, в которые не входит ни одной буквы из этого множества, реализует булеву функцию с матрицей нулей Му. о Тестовая ДНФ функции / всегда существует и может быть

построена тестовым алгоритмом. Пусть Б | = {х?К | х°К е П),

Эш[И] = Б\{КеО | ЗГеР : Щ{К})аЩ{К'})}> ргД1>] = 8т[Я\Я|,. и{КхКг | у^еБ^у^еБ|-}].

Теорема 3.1. Если ДНФ Бр, реализующая функцию /, является тестовой, то рг, [... рг2 [р^ [£>]]...] = , где - сокращённая

ДНФ булевой функции ^(х1,...,хИ) с матрицей нулей Мх.

Предложенный метод построения сокращённых ДНФ при специальном выборе матрицы Му и тестовой ДНФ Б «превращается» в метод Блейка / метод Нельсона (можно реализовать любую последовательность умножения скобок). Поэтому из теоремы 3.1 следует, в том числе, что методами Нельсона и Блейка может быть построена сокращённая ДНФ. Для метода Блейка указана последовательность шагов такого построения.

Четвёртая глава посвящена решению задачи построения ДНФ бинарных функций ¿-значной логики по перечню нулей. В §4.1 на к-значный случай обобщён тестовый подход и предложены эффективные методы синтеза Н-ДНФ, А-ДНФ, Т-ДНФ. В §§4.2 - 4.4 описан

~ап . - Ощ'

II ЯЛ • агп. , МАш

м3 =

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

Матрица нулей бинарной функции /к{х1,...,хп) переводится в матрицу нулей булевой функции /2(х11,...,х1р,...,хгЛ,...,хщ>):

... 8р(ап) ... ¿¡К,) ... 8р(а1п)~ ^(аг1) ... 8р(аг1) ... ... 8р(ат)

Здесь 8(а)-(81(а),...,8р(а))-»(Е2)р -инъективное отображение, которое будем называть кодировкой, а бинарную матрицу

" 4(0) ... 8р{0) "

8,(к-1) ... 8р(к-1)

матрицей кодировки 8. Заметим, что кодировка 8 задаёт взаимно однозначное соответствие А:

Определение. Конъюнкция К = & х?" • • • & хУ называется

кодирующей при кодировке 8, если для всех у е {1,2,..., п} Ы]{К,8) = {а&Щ | V/еУ] 81(а) = сг^}*0. Теорема 4.2. Для любой кодирующей конъюнкции К существует Н-конъюнкция Т]{К) такая, что А4 (Л^( {£}) п А ((Е* )")) = ЛГ( {г]{К)}).

Заметим, что Н-конъюнкция Т](К), кроме того, эффективно строится по конъюнкции К и матрице кодировки:

7] (К) = тт[;ч(ВД(^)„.., ^я(а:)<5)(лй),1]. Теорема 4.4. Для множества кодирующих конъюнкций £)' ДНФ , реализующей булеву функцию /2, справедливо /к = тах[т}(К)].

Для построения ДНФ характеристической функции класса /:(Е^)И ->{0,1, г} достаточно перекодировать матрицу нулей

функции /, построить ДНФ булевой функций и удалить в ней конъюнкции равные нулю на всех наборах из (Д(Ь) | /(¿) = 1}. Оставшиеся конъюнкции - кодирующие, и преобразованием //(•) получаем Н-ДНФ функции /. Далее в диссертации обсуждаются свойства кодировок и возможность эффективного синтеза ДНФ специального вида (А-ДНФ, Т-ДНФ и др.).

Теорема4.5. При к>3 для того, чтобы для любой Н-конъюнщии Q существовала кодирующая конъюнкция К такая, что Q = Т]{К) необходимо и достаточно, чтобы в матрице кодировки была единичная подматрица

"1 0 0 ... 0"

0 1 0 ••• 0

0 0 0 ... 1_

размера кхк с точностью до инверсий и перестановок столбцов.

При кодировке 3Е простые импликанты функции /2, составленные из букв с отрицаниями, имеют вид

К = &хи-&хп1. (4)

/еУ] 11 е*Гя * '

Если = {1,2,...,А:} для некоторого Уе{1,2,...,«}, то К - некоди-рующая. В противном случае автоматически выписывается г/(К), поскольку

У/е{1,2,...,«} = | меУу}.

При кодировке 3Е всевозможным кодирующим простым импликан-там (4) взаимно однозначно соответствуют всевозможные простые Н-импликанты функции /к.

Теорема 4.8. Всевозможным кодирующим простым импли-кантам функции /2, составленным из букв без отрицаний, при

кодировке 8е взаимно однозначно соответствуют всевозможные простые Т-импликанты функции /к.

Заметим, что все кодирующие простые импликанты /2, составленные из букв без отрицаний, имеют вид

где Ус{1,2,...,и}, с {1,2,...,£}, а некодирующие - х]ах]Ь,

\<а<Ь<к (их число не превосходит к(к-\)п/2). Т-конъюнкция 7](К) также просто выписывается по (5), поскольку

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

Теорема 4.9. Для того, чтобы произвольной кодирующей конъюнкции К соответствовала А-конъюнкция Т](К), и для любой А-конъюнкции б существовала конъюнкция К такая, что Т]{К) = Q, необходимо и достаточно, чтобы матрица кодировки сводилась к матрице

М3 =

"0 0 ... 0 0"

1 0 ... 0 0

1 1 ... 0 0

1 1 ... 1 0

1 1 ... 1 1

Кодировка 8М позволяет эффективно синтезировать А-ДНФ, поскольку все некодирующие простые импликанты функции ^

имеют вид ХрХр, 1 <а<Ь<к, а кодирующие можно формально записать в виде

К ~ ^Ц^Ь,*^-*^ &---&ХяалХпЬя>

полагая х]к = х}й = 1 для всех у'е {1,2,...,и}. При этом г){К) = шш!^]^),..., ^0я1Ьв_ц(хп),Ц. Определение. Допустимая для бинарной функции / элементарная А-конъюнкция тт] (д^),..., ^^ ^] (х„), 1] называется квазипростой импликантой функции /, если для всех у е{1,2,...,«} справедливо

1. Если а, > 0, то конъюнкция

л ] )> • • •' ] (х;)> • • • (*„), 1] не является допустимой для /.

2. Если Ь] < к -1, то конъюнкция

не является допустимой для /.

Теорема 4.10. Всевозможным кодирующим конъюнкциям из сокращённой ДНФ функции /2 при кодировке 8М взаимно однозначно соответствуют всевозможные квазипростые импликанты функции /к.

В пятой главе описана модель логических алгоритмов, реализованная на ЭВМ, а также уточнена постановка задач распознавания, для решения которых предназначена эта модель. Приведены результаты вычислительных экспериментов. Решались как модельные задачи:

- распознавание чётности (задача распознавания с классами Кх ={(а1,...,а6)е(В4)6 | Зщ,щеЪ : а, а4 + а5 +а6 = 2т2},

£2={(о1,...,а6)е(Е4)6 | Ут'е%а1+а2+а3*2т'*а4+а5+а6}),

- распознавание нормы (Я, ={йе(Е2)я | ||й[|>]и/2[}, К2 =(Е2)" \ АГ,)Э

- распознавание с примесями (в обучающую выборку «примешивались» объекты с неверной классификацией);

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

В приложении представлена статистика работы алгоритмов, предложенных в диссертации: время построения ДНФ, некоторые характеристики построенных ДНФ.

Наилучшим для использования при синтезе логических алгоритмов распознавания оказался метод последовательного умножения по обобщённой формуле C.B. Яблонского.

ЗАКЛЮЧЕНИЕ

На защиту выносятся

- Тестовый подход к задаче ДНФ-реализации и все алгоритмы, разработанные в рамках этого подхода, в том числе для построения ДНФ, обладающих специальными свойствами.

- Метод последовательного конъюнктивного умножения скобок совершенной КНФ. основанный на обобщённой формуле C.B. Яблонского.

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Дьяконов А.Г. Дизъюнктивные нормальные формы булевых функций с малым числом нулей // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2001». - М.: Изд. отдел ВМиК МГУ, 2001. - С. 6-7.

2. Дьяконов А.Г. Поиск логических закономерностей в задачах распознавания образов с помощью эффективного синтеза ДНФ // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2003». - М.: Изд. отдел ВМиК МГУ, 2003. - С. 5-6.

3.ДьяконовА.Г. Построение дизъюнктивных нормальных форм в логических алгоритмах распознавания // Ж. вычисл. матем. и матем. физ. - 2002. Т. 42. № 12. - С. 1899-1907.

4. Дьяконов А.Г. Построение дизъюнктивных нормальных форм в задачах распознавания образов с бинарной информацией // Доклады Академии наук. - 2002. Т. 383. № 6. - С. 747-749.

5. Дьяконов А.Г. Построение дизъюнктивных нормальных форм квазибулевских функций А-значной логики // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2002». - М.: Изд. отдел ВМиК МГУ, 2002. - С. 10-11.

6. Дьяконов А.Г. Построение ДНФ характеристических функций классов в логических алгоритмах распознавания // Тезисы докладов Международной научной конференции ИОИ-2002. - Симферополь: Крымский научный центр НАН Украины, Таврический национальный университет, 2002. - С. 35-36.

7. Дьяконов А.Г. Тестовый подход к реализации дизъюнктивными нормальными формами булевых функций с малым числом нулей И Ж. вычисл. матем. и матем. физ. - 2002. Т. 42. № 6. - С. 924-928.

8. Дьяконов А.Г. Эффективная реализация логических алгоритмов распознавания // Доклады 10-й Всероссийской конференции ММРО-Ю. -М.: Изд-во «АЛЕВ-В», 2001. - С. 51-53.

(2./g( 112781

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 04.07.2003 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 526. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.ВЛомоносова.

Введение

Глава 1. Основные определения и обозначения. Обзор предыдущих работ

1.1. Некоторые обозначения

1.2. Обзор методов синтеза ДНФ по перечню нулей

1.3. Обзор: нормальные формы £-значной логики

1.4. Задача распознавания образов

1.5. Задача распознавания с целочисленной (бинарной) информацией. Логические алгоритмы распознавания

1.6. Эффективная реализация логических алгоритмов распознавания

1.7. Основные результаты диссертации

Глава 2. Тестовый подход к задаче ДНФ-реализации

2.1. ДНФ [Z)*]F, построенная по матрице нулей

2.2. Оценка сложности ДНФ [Z)*]F

2.3. Построение тупиковой ДНФ ^

2.4. Построение ДНФ булевой функции по перечню её нулей с помощью тестового подхода

2.5. Построение ДНФ характеристических функций классов.

Равномерные ДНФ

2.6. Построение явных ДНФ-формул с помощью тестового подхода

2.7. ДНФ-реализация по матрице нулевых интервалов

Глава 3. Построение ДНФ последовательным умножением

3.1. Умножение ДНФ

3.2. Некоторые свойства тестовых ДНФ

3.3. Умножение на скобку совершенной КНФ

3.4. Реализация метода Нельсона на ЭВМ

3.5. Построение ДНФ по формуле С.В. Яблонского

Глава 4. ДНФ-реализация функций &-значной логики. Кодировки

4.1. Тестовый подход для ДНФ-реализации квазибулевских функций

4.2. Определение кодировки. Соответствие конъюнкций

4.3. Возможность построения произвольной ДНФ с помощью кодировки. Построение сокращённых Н-ДНФ и Т-ДНФ

4.4. Построение А-ДНФ и квазисокращённой А-ДНФ с помощью кодировки

Глава 5. Тестирование алгоритмов распознавания imiMMiMMMiiiiWHlHiMiHwmniumwwMHmMmM

Проблема построения кратчайших, минимальных или достаточно простых ДНФ для булевых функций и функций Аг-значной логики была одной из основных в исследованиях по дискретному анализу и математической кибернетики, проводимых в СССР в 50х - 70* годах прошлого столетия. С.В. Яблонским, Ю.И. Журавлёвым, А.А. Сапоженко, Ю.Л. Васильевым, В.В. Глаголевым, У.А. Абдугалиевым, А.Н. Нурлыбаевым и др. были получены фундаментальные результаты, показывающие, что задачи минимизации, как правило, являются весьма трудоёмкими и реально неразрешимыми даже при относительно небольшом числе переменных. Так как прикладное применение ДНФ ограничивалось, в основном, решением систем булевых уравнений, для чего были получены при других подходах более эффективные методы, интерес к задачам минимизации в дальнейшем существенно уменьшился, что отразилось и на числе публикаций.

В последние десятилетия снова появилось значительное число публикаций, имеющих отношение к исследованию задач эффективного представления булевых функций и функций &-значной логики в классе ДНФ и их обобщений. Это вызвано, в первую очередь, использованием ДНФ для синтеза логических распознающих процедур при решении задач распознавания образов. Как известно, большинство применений теории распознавания связано с плохо формализованными областями науки и практики. Для этих областей не удаётся построить адекватную математическую модель, поэтому строится алгоритм, аппроксимирующий нужную зависимость по прецедентам, т.е. примерам корректной работы алгоритма: входные данные (описания объектов распознавания) и результаты работы алгоритма (классы этих объектов). Для построения таких алгоритмов потребовалась разработка специального математического аппарата, поскольку прецедентов, как правило, не очень много и, например, традиционные статистические методы не всегда давали нужный эффект. Комбинаторно-логический подход, основы которого заложили работы Ю.И. Журавлёва, оказался одним из самых эффективных при решении задач распознавания. В этом подходе по исходной информации определяются логические закономерности (подописания объектов, содержащие информацию о различиях классов). Например, в случае, когда описания объектов целочисленные, естественно использовать аппарат теории ДНФ. С помощью ДНФ или их аналогов доопределяют характеристические функции классов, заданные только в некоторых точках (описаниях объектов), а элементарные конъюнкции играют роль логических закономерностей. Сокращённая ДНФ задаёт всевозможные доопределения характеристической функции и всевозможные логические закономерности, однако, её длина растёт экспоненциально с ростом «размеров» задачи. Кроме того, доопределение существенно влияет на вид синтезируемого алгоритма распознавания. Так, часто сложность логической распознающей процедуры линейно зависит от суммы длин построенных ДНФ, поскольку алгоритм осуществляет голосование по всем найденным логическим закономерностям.

Это и определило направление исследований, результаты которых описаны в настоящей диссертации. Отметим основную специфику рассматриваемой задачи. Число переменных характеристических функций классов может быть достаточно велико, поскольку объекты описываются, как правило, большим числом признаков. Число нулей и единиц этих функций мал о (интересен случай небольшого числа прецедентов). Универсальный способ построения искомой ДНФ характеристической функции класса -построить ДНФ всюду определённой функции, которая обращается в ноль только на нулях характеристической функции, а затем удалить лишние конъюнкции. Заметим, что при решении задач распознавания образов не требуется построение именно экстремальных (минимальных и/или кратчайших) ДНФ, поскольку они не гарантирует высокого качества распознавания. Из результатов С.В. Яблонского и Ю.И. Журавлёва следует, что, по-видимому, решение задачи построения экстремальной ДНФ методами, исключающими перебор, невозможно, но построение ДНФ близких к экстремальным для функций с «малым» числом нулей возможно за приемлемое время.

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

Автор выражает огромную благодарность своему научному руководителю академику РАН Юрию Ивановичу Журавлёву, который оказал значительное влияние на формирование научного мировоззрения автора, а также всем своим коллегам и Учителям из Московского государственного университета и ВЦ РАН.

1. Абдугалиев У.А. К вопросу представления функций А>значной логики нормальными формами // 1.Сб. «Дискретный анализ». - Новосибирск: ИМ СО АН СССР, 1969. - Вып. 15. - С. 3-24.

2. Абдугалиев У.А. О нормальных формах &-значной логики // Кибернетика. — 1967. №1.-С. 16-20.

3. Алексанян А.А. Дизъюнктивные нормальные формы над линейными функциями (Теория и приложения) / Под ред. Ю.И. Журавлёва. Ереван: Изд-во Ереван, ун-та, 1990. -200с.

4. Асланян Л. А. Об одном методе распознавания, основанном на разделении классов дизъюнктивными нормальными формами // Кибернетика. 1975. №5.-С. 103-110.

5. Баскакова JI.B., Журавлёв Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // Ж. вычисл. метем, и матем. физ. 1981. Т.21. №5. - С.1264-1275.

6. Бонгард М.М. Моделирование процесса узнавания на цифровой счётной машине//Биофизика. 1961. Т. 6. Вып. 2. - С. 129-141.

7. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. - 320с.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.-416с.

9. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. М.: Наука, 1974. - 312с.

10. Дмитриев А.И., Журавлёв Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений // Дискретный анализ. -Новосибирск: ИМ СО АН СССР, 1966. Вып. 7. - С. 3-17.

11. Доклады X Всероссийской конференции «Математические методы распознавания образов». М.: Изд-во «АЛЕВ-В», 2001. - 342с.

12. Дьяконов А.Г. Дизъюнктивные нормальные формы булевых функций с малым числом нулей // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2001». — М.: Изд. отдел ВМиК МГУ, 2001. С. 6-7.

13. Дьяконов А.Г. Построение дизъюнктивных нормальных форм в логических алгоритмах распознавания // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. № 12.-С. 1899-1907.

14. Дьяконов А.Г. Построение дизъюнктивных нормальных форм в задачах распознавания образов с бинарной информацией // Доклады Академии наук. 2002. Т. 383. № 6. - С. 747-749.

15. Дьяконов А.Г. Построение дизъюнктивных нормальных форм квазибулевских функций &-значной логики // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2002». М.: Изд. отдел ВМиК МГУ, 2002. - С. 10-11.

16. Дьяконов А.Г. Построение ДНФ последовательным перемножением // Ж. вычисл. матем. и матем. физ. 2003. Т.43. - (в печати).

17. Дьяконов А.Г. Тестовый подход к реализации дизъюнктивными нормальными формами булевых функций с малым числом нулей // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. № 6. - С. 924-928.

18. Дьяконов А.Г. Эффективная реализация логических алгоритмов распознавания // Доклады 10-й Всероссийской конференции ММРО-Ю. М.: Изд-во «АЛЕВ-В», 2001. - С. 51-53.

19. Дюкова Е.В. Алгоритмы распознавания типа «Кора»: сложность реализации и метрические свойства // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. - Вып. 2. - С. 99-125.

20. Дюкова Е.В. Асимптотически оптимальные методы дискретного анализа информации в задачах распознавания: Дис. . докт. физ.-матем. наук. М. ВЦ РАН. 1996.-232с.

21. Журавлев Ю.И. Локальные алгоритмы вычисления информации. I // Кибернетика. 1965. № 1. - С. 12-19.

22. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Пробл. кибернетики. М.:Наука, 1978. - Вып. 33. — С. 5-68.

23. Журавлев Ю.И. Об отделимости подмножеств вершин «-мерного единичного куба // Труды Математического института им. В.А. Стеклова. -М.: Изд-во АН СССР, 1958. Т. 51. - С. 143-151.

24. Журавлев Ю.И. Об оптимальных алгоритмах выбора // Докл. АН СССР. -1957. Т. 121. № 3. С. 701-703.

25. Журавлев Ю.И. Теоретико-множественные методы в алгебре логики // Проблемы кибернетики 1962. № 8. - С. 5-44.

26. Журавлев Ю.И., Коган А.Ю. Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи // Докл. АН СССР. -1985. Т. 285. № 4. С. 795-799.

27. Журавлев Ю.И., Коган А.Ю. Алгоритм построения дизъюнктивной нормальной формы, эквивалентной произведению левых частей булевых уравнений нельсоновского типа // Ж. вычисл. матем. и матем. физ. 1986. Т. 26. №8.-С. 1243-1249.

28. Журавлев Ю.И., Платоненко И.М. Об экономном умножении булевых уравнений // Ж. вычисл. матем. и матем. физ. -1984. Т. 24. № 1. С. 164—166.

29. Коган А.Ю. Дизъюнктивные нормальные формы булевых функций с малым числом нулей. Каталог функций с четырьмя нулями. — М.: ВЦ АН СССР, 1986. 18с.

30. Коган А.Ю. Методы минимизации бинарных функций с малым числом нулей: Дис. канд. физ.-матем. наук. М. ВЦ АН СССР. 1987. 138с.

31. Мазуров В.Д., Казанцев B.C., Белецкий Н.Г., Кривоногое А.И., Смирнов А.И. Вопросы обоснования и применения комитетных алгоритмов распознавания //Распознавание, классификация, прогноз. -М.: Наука, 1989. С. 114—148.

32. Нурлыбаев А.Н. О нормальных формах А>значной логики // Сборник работ по математической кибернетике. М.: ВЦ АН СССР, 1976. - Вып. 1. С. 56-68.

33. Платоненко И.М. О реализации алгоритмов типа «Кора» с помощью решения систем булевых уравнений специального вида // Сообщения по прикладной математике. М.: ВЦ АН СССР, 1983.-21с.

34. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. -М.: Наука, 1989. Вып. 1. - С. 176-201.

35. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк. // Ж. вычисл. матем. и матем. физ. -1976. Т. 16. № 6. С. 1559-1570.

36. Трофимов С.В. Об оптимальном уменьшении числа уравнений в системах нельсоновского типа // Ж. вычисл. матем. и матем. физ. 1986. Т. 26. № 10. — С. 1552-1558.

37. Фиников Б.И. Об одном семействе классов функций алгебры логики и их реализации в классе П-схем // Докл. АН СССР. 1957. Т. 115. №2. -С. 247-248.

38. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Труды МИ АН СССР. М.: Изд-во АН СССР, 1958 -Т. 51.-С. 270-360.

39. Яблонский С.В. Функциональные построения в Дг-значной логике // Труды МИАН СССР. -М.: Изд-во АН СССР, 1958 Т. 51. - С. 5-142.

40. Blake A. Canonical expressions in Boolean algebra / Dissertation. Chicago. 1937.

41. Ganster H., GelautzM., PinzA., Binder M., Pehamberger H., BammerM., Krocza J. Initial results of automated melanima recognition // Proceedings of the 9th Scandinavian conference on image analysis. Uppsala, Sweden. June 1995. — P. 209-218.

42. Nelson R.J. Simplest normal truth functions // J.Symbolic Logic. 1955. -Vol. 20.2.-P. 105-108.