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

• Дьяконов, Александр Геннадьевич
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Дьяконов, Александр Геннадьевич

Введение

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Дьяконов, Александр Геннадьевич, 2003 год

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.