WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

МАКСИМОВ ЮРИЙ ВЛАДИМИРОВИЧ

ПОСТРОЕНИЕ ЛОГИЧЕСКИХ КЛАССИФИКАТОРОВ ПРИ ОГРАНИЧЕНИЯХ НА СЛОЖНОСТЬ ОПРЕДЕЛЯЮЩИХ ИХ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2012

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

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

Официальные оппоненты: Доктор физико-математических наук, профессор, академик РАН Матросов Виктор Леонидович, ФГБОУ ВПО Московский педагогический государственный университет, ректор.

Кандидат физико-математических наук Песков Николай Владимирович, ЗАО «Форексис», ведущий разработчик.

Ведущая организация: Московский государственный университет им. М.В. Ломоносова, факультет ВМК

Защита состоится 2012 г. в часов на заседании диссертационного совета Д 212.156.05 при Московском физикотехническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета).

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

Ученый секретарь диссертационного совета Федько Ольга Сергеевна

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

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

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

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

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

При синтезе логических алгоритмов классификации число нулей характеристической функции класса (число эталонных объектов), как правило, не велико. С учетом этой особенности, С.В. Яблонским, Ю.И. Журавл евым, А.Ю. Коганом, А.Г. Дьяконовым и другими исследователями были предложены эффективные алгоритмы, которые позволяют строить достаточно простые ДНФ для различных классов булевых функций с малым числом нулей. Однако, вопрос о точных границах сложности ДНФ булевых функций с малым числом нулей остается в настоящее время открытым несмотря на многочисленные работы в этом направлении.

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

1. Исследование типичной и экстремальной сложности минимальных и кратчайших ДНФ булевых функций с малым числом нулей;

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

3. Разработка механизмов получения высоких нижних оценок сложности ДНФ булевых функций с малым числом нулей.

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

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

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

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

Методика исследования: методы теории вероятностей, теории сложности, дискретной математики, алгебры и теории множеств.

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

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

Апробация работы. Результаты, изложенные в диссертации, а также их практические приложения в разное время докладывались на - 15-ой всероссийской конференции «Математические методы распознавания образов» (Петрозаводск, 2011);

- 35-ой конференции-школе «Информационные технологии и системы» (Петрозаводск, 2012);

- 9-ой Международной конференции «Интеллектуализация обработки информации»(Черногория, 2012);

- постер сессиях в рамках международных летних школсеминаров по информационному поиску и базам данных RuSSIR/EDBT (Санкт-Петербург, 2011) и RuSSIR (Ярославль, 2012);

- научных семинарах кафедры «Интеллектуальные системы» факультета управления и прикладной математики МФТИ(2009–2012), отдела Интеллектуальных систем ВЦ РАН(2009–2012) и Лаборатории структурных методов анализа данных в предсказательном моделировании при МФТИ (2012).

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

Публикации. По теме диссертации опубликовано 5 работ, в том числе 2 [1,2] — в изданиях из списка рекомендованного ВАК РФ.

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

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

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

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

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

Скажем, что свойство A выполнено для «почти всех» булевых функций из некоторого класса P = P (n), если при n доля функций класса, для которых указанное свойство не выполнено, стремится к 0.

В работе обозначено через Bn = {0, 1}n множество всех булевых векторов размерности n; через 1n (0n) обозначен вектор размерности n состоящий только из единиц (нулей соответственно); через #x обозначен вес булева вектора x, то есть минимум из числа его нулей и единиц; а через n+ обозначено множество {1, 2,..., n}. Предполагается, что каждая булева функция f, рассматриваемая далее, задана своей матрицей нулевых точек (матрицей нулей), обозначаемой через Mf, по строкам которой перечислены все различные нули функции. Подматрица произвольной матрицы M, образованная пересечением строк i1, i2,..., it и столбцов j1,..., jr, обозначена через Mij,j2,...,jr.

,i2,...,it Ненулевой вектор Bk назван в работе разложимым по векторам 1,..., t, если выполнены следующие равенства = 1 2 ... t, <, 1 >=<, 2 >=... =<, t >= 0, где под символом < , > понимается скалярное произведение векторов и . Кроме того, если i, j < i, j >= 0 при i = j, то вектор назван ортогонально разложимым по векторам 1,..., t. В случае = 1k в условиях предыдущего определения вектора {i}t названы ортогональным разложением единицы.

i=Рангом ДНФ в теории сложности булевых функций называется число содержащихся в ней литералов, а длиной ДНФ число входящих в нее конъюнкций. Указанные величины для произвольной ДНФ D обозначим rank(D) и |D| соответственно. Минимальная ДНФ соответствует ДНФ минимального ранга, а кратчайшая ДНФ соответствует ДНФ минимальной длины. Анализ различных мер сложности вызван неэквивалентностью понятий минимальной и кратчайшей ДНФ, доказанной Ю.И. Журавлвым.

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

Обозначим через Pn максимальный по включению класс разk личных булевых функций от n переменных, имеющих в точности k различных нулей. Булева функция f Pn называется приk веденной, если в ее матрице нулей отсутствуют нулевой и единичный столбцы, а также столбцы одинаковые с точностью до k-инверсии. Приведенные функции класса Pn = P2 -1 образуют k k класс Cn полных функций. Ю.И. Журавл и А.Ю. Коганом евым было показано, что построение ДНФ всякой булевой функции класса Pn с малой сложностью сводится к построению соответk ствующей ей приведенной, а при k < log2 n-log2 log2 n+1 нулей, построение ДНФ почти всех из них сводится в асимптотике к построению ДНФ полной функции.

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

Классы Pn, n, Cn, n и n естественным образом возниk k k k,m кают на практике при решении задач анализа данных, а также важны при изучении статистических свойств булевых функций.

Лемма 1.1. Почти все булевы функции класса Pn при k k = 2 log2 n + (1) являются приведенными.

Лемма 1.2. Почти все приведенные функции от n переменных, имеющие в точности k нулей, не содержат соседних нулей при n .

k Лемма 1.3. Выберем произвольное > 0. При m < k log n (1 + ), k = o(2n) и n почти все функции класса n содержатся в классе n.

k k,m i Литерал x назван в работе собственным литералом конъi юнкции K ДНФ D функции f(x1, x2,..., xn), если K — единственi ная конъюнкция D, содержащая x. Это понятие существенно i при анализе сложности ДНФ.

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

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

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

Заметим, что литерал xj функции f(x1, x2,..., xn) Pn вхо k дит в ДНФ не менее одного раза, если в матрице нулей M функции f не существует столбцов и их инверсий, которые бы обраj зовывали вместе со столбцом Mk ортогональное разложение + единицы. Достаточно заметить, что если функция f не имеет соседних нулевых точек, то множество точек, смежных с нулями функции, не может быть покрыто с использованием одной конъюнкции.

Обобщение этого замечания дается основной технической леммой данного параграфа. Разрезанием матрицы M, являющейся тестом, на t частей при t 1, назовем совокупность подматриц {Mi}t таких, что матрицы M1, M2,..., Mt имеют одинаi=ковое число столбцов; каждая строка матрицы M присутствует хотя бы в одной матрице Mi, 1 i t; число строк матрицы M совпадает с суммой числа строк в матрицах {Mi}t.

i=Рассмотрим приведенную булеву функцию f(x1,..., xn), заданную матрицей нулей Mf и не имеющую смежных нулевых i точек. Зафиксируем ее литерал x, i {0, 1}. Пусть D — некоi торая ДНФ функции f. Выделим в D различные конъюнкции, i в количестве t штук, содержащие литерал x.

i i Лемма 2.4 (Случай конкретной ДНФ). Литерал x вхоi дит еще как минимум в одну отличную от выделенных конъюнкцию из D, если при любом разрезании матрицы Mf на t частей M1, M2,..., Mt существует такая матрица Mj, что для функции j заданной матрицей Mj, ни одна из выделенных конъюнкций i не определяет разбиение x.

i Целью второго параграфа второй главы является применение полученных результатов к построению нижних оценок сложности функций классов Cn и n.

k На основе леммы 2.4 устанавливается ряд свойств полных и приведенных булевых функций высокой размерности. На основе леммы 2.4 и статистических свойств биномиальных коэффициентов устанавливается оценка Теорема 2.2. Минимальная ДНФ полной булевой функции от ( ) n переменных имеет ранг не меньший 3n 1 - e- log2 n/36.

Следствие 2.2.2. Минимальная ДНФ булевой функции класса n имеет ранг не меньший чем 3n (1 - o(1)) при k = log2n k log(2)n - (1).

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

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

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

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

Теорема 2.3. Ранг ДНФ реализации D функции f класса n k,m ограничен снизу выражением 10 5n (k/2 - m) rank D > n -, при = 3 3(1 + ) k 10 13n 1 rank D > n -, при < <.

3 9 + 3 4 В третьей главе приведены эффективные методы синтеза ДНФ булевых функций различных классов.

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

Продемонстрируем идею конструкции на примере. Рассмотрим булевы функции Pn-1 и Pn, заданные матриk k цами нулей и соответственно и связанные соотношениями + + n-1 = n-1, n = 1 2, 1k n = 3 4, k+ k+ k+ k+ k+ k+ k+ k+ 0k = 1 2 = 3 4. Тогда ДНФ D может быть k+ k+ k+ k+ получена из ДНФ D следующим образом D = D xnx1x2 xnx3x4.

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

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

j i Путем между внешними литералами x и x в HT, в работе i j названа последовательность переходов между внешними литераi лами внутри ребер гиперграфа, начинающаяся в x и заканчиi j вающаяся в x. Заметим, что гиперграф HT может быть достаj точно велик, однако на практике нам нужна лишь его небольшая часть, которая может быть конструктивно выделена без анализа всего графа.

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

Дальнейшие доказательства основаны на том, что в матрице нулей с большим числом столбцов можно эффективно выделить последовательность ортогональных разложений с небольшим (относительно числа столбцов) числом ребер. Лемма 3.утверждает, что в матрице высокой размерности указанная последовательность может содержать число ребер асимптотически равное числу столбцов матрицы нулей. Обозначим через E(H) множество гиперребер гиперграфа H.

Лемма 3.1. Пусть для приведенной функции f(x1, x2,..., xn) и теста T существует последовательность ортогональных разложений ST, содержащая все внешние литералы. Тогда функция f реализуется ДНФ DS, определяемой равенством T DS = DT K[e], T eE(ST ) i1 i2 it i1 i2 it где K[e] = x 1x 1 · · · x 1 при e = {x, x,..., x }, а DT — i1 i2 it i1 i2 it произвольная ДНФ реализующая функцию заданную тестовой подматрицей.

Лемма указывает на естественный алгоритм построения ДНФ булевой функции высокой размерности. Первый шаг алгоритма состоит из построения соответствующего гиперграфа на n вершинах. На втором шаге строится ДНФ булевой функции, переменным которой соответствуют внешние вершины гиперграфа.

С использованием указанного подхода и построением последовательностей ортогональных разложений, основанных на разбиении булева куба на цепи, доказаны теоремы 3.1, 3.2 (с использованием теоремы 2.2) и 3.3.

Теорема 3.1. Функция класса Cn с числом нулей k не менее 8 может быть реализована ДНФ ранга, не большего 3n + 6n/ log2 n + 6n0.93 log2 n.

Теорема 3.2. Полная функция может быть реализована ДНФ, содержащей 3n(1 + o(1)) литералов и n(1 + o(1)) конъюнкций при n ; при этом ни одна из границ асимптотически не улучшаема.

Теорема 3.3. Почти все приведенные функции класса Pn при k n 2k-1-kC, где C — произвольная положительная постоянная, могут быть реализованы ДНФ с числом литералов 3n(1 + o(1)) и числом конъюнкций n(1 + o(1)), при k . Каждая из полученных границ является асимптотически точной.

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

Теорема 3.4. Функции класса Cn не обладают минимальными ДНФ среди функций класса Pn, n = 2k-1 - 1.

k Второй параграф третьей главы посвящен оценке сложности булевых функций классов Pn и n.

k k Дальнейшие доказательства основаны на применении идеи редукции. Сформулировать идею можно следующим образом.

ДНФ D булевой функции (x1, x2,..., xn) может быть представлена в виде D = x1D x1D, где функции и заданы бу левыми матрицами с меньшим число столбцов и строк. Более того, при малом k ДНФ большинства функций класса Pn могут k быть представлены через ДНФ функций с числом нулей слабо отличающимся от n/2. Следовательно, после применения редукционных разложений к первым t столбцам случайной функции класса Pn можно ожидать, что число функций, множество нулей k которых значительно превышает n/2t, будет невелико. Отметим, что функции с числом нулей не более log2 n-(n) при (n) могут быть реализованы с использованием не более n(1 + o(1)) конъюнкций, а реализация произвольной функции может потребовать максимум nk конъюнкций.

Теорема 3.5. Зафиксируем произвольную монотонную функцию g(n), принимающую только положительные значения, которая удовлетворяет условиям g(n) = o(n1/6), g(n) при n . Положим k = k(n) > log2n/2. Пусть, дополнительно, для функции g(n) при определенном выше k = k(n) выполнено ( ) ( ( { }) ) 1 ng(n) > 2 1 - log2 max, 1 + (1).

2]k/n[ k Определим k0 = k0(n) равенством k0 = log2 n - log2 n · g(log2n).

Тогда для почти всех функций класса Pn при n выполk(n) нено k k|Df| n · 2]log ( )[(1 + o(1)), где ]x[ обозначено минимальное целое число не меньшее x.

Следствие 3.5.1. Выберем k = log2n-(log2n), где 0.5<<1.

Пусть k = k(n) > log2 n-(log2n). Тогда для почти всех функций класса Pn при n выполнено k(n) k nk k |Df| n · 2]log ( )[(1 + o(1)) 2 (1 + o(1)), log2n где ]x[ обозначено минимальное целое число не меньшее x.

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

Задача классификации, решаемая в настоящей главе, формулируется следующим образом. Рассматриваются две выборки векторов n-мерного признакового пространства: обучающая и контрольная. Каждому из элементов обучающей выборки сопоставлено (известное) подмножество конечного множества классов K1, K2,..., Kl. Решение задачи состоит в том, чтобы по имеющимся данным о выборках восстановить классы объектов, образующих контрольную выборку.

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

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

Рассматривается задача классификации с непересекающимися классами Z. Обозначим B(Z) минимум по всем возможным разбиениям объектов контрольной выборки на классы максимального числа корректно классифицируемых алгоритмами вычисления оценок объектов контрольной совокупности задачи Z. В работе приведен ряд полиномиальных методов получения верхних оценок величины B(Z).

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Максимов Ю. В. Простые дизъюнктивные нормальные формы булевых функций с малым числом нулей // Доклады РАН. Серия «Математика». — 2012. Т. 445 №2 — С. 143–145.

2. Максимов Ю. В. Корректные алгебры над алгоритмами вычисления оценок в множестве регулярных задач распознавания с непересекающимися классами. // ЖВМиМФ. — 2009.

Т. 49 №7 — С. 1327–1339.

3. Максимов Ю. В. Нижние оценки сложности реализации дизъюнктивными нормальными формами булевых функций специальных классов. // Труды 9-ой международной конференции «Интеллектуализация обработки информации» — М.: «МАКС Пресс», 2011. — С. 75–77.

4. Максимов Ю. В. Эффективная реализация некоторых классов булевых функций дизъюнктивными нормальными формами // Труды конференции ИТИС–35. ISBN 978-5-90115819-7. — 2012. — С. 105–107.

http://www.itas2012.iitp.ru/pdf/1569607247.pdf 5. Максимов Ю. В. Эффективная реализация логических алгоритмов в задачах классификации с малым числом эталонов // Труды всероссийской конференции ММРО–15. — М.:

«МАКС Пресс», 2011. — С. 77–79.

МАКСИМОВ ЮРИЙ ВЛАДИМИРОВИЧ ПОСТРОЕНИЕ ЛОГИЧЕСКИХ КЛАССИФИКАТОРОВ ПРИ ОГРАНИЧЕНИЯХ НА СЛОЖНОСТЬ ОПРЕДЕЛЯЮЩИХ ИХ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ АВТОРЕФЕРАТ Подписано в печать 28.09.2012.

Печать трафаретная Усл.п.л. – 1,Заказ № 3741 Тираж: 90 экз.

Типография «11-й ФОРМАТ» ИНН 77263309115230, Москва, Варшавское ш., (499) 788-78-www.autoreferat.ru







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.