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

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

Г и С/1 2 4 НОЯ '007

АСЛАНЯН Левон Акопович

ЛОГИКО-КОМБИНАТОРНЫЕ ЗАДАЧИ ДИСКРЕТНОГО МОДЕЛИРОВАНИЯ: СИСТЕМЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

Специальность: 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

Москва - 1997

Работа выполнена в Институте Проблем Информатики и Автоматизации Национальной Академии Наук Армении и Ордена Трудового Красного Знамени Ереванского Государственного

Университета

Официальные оппоненты: академик РАО,

доктор физико-маематических наук, профессор В.Л Матросов

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

доктор физико-математических наук, профессор Л.А. Шоломов

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

Защита состоится "_£."

м

1_1997г. в Их часов на заседании диссертационного совета Д002.32.06 при Вычислительном центре РАН г. Москва, ул. Вавилова, д. 40

С диссертацией можно ознакомиться: в библиотеке ВЦ РАН

Автореферат разослан "Я." -Л}_1997г.

Ученый секретарь диссертационного совета Д002.32.06 кандидат физико - математических наук С.М. Швартин

Обшая характеристика работы

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

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

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

Одна из ранних работ применения формальных методов для реше-

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

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

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

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

3Ю. И. Журавлев, В. В. Никифоров. Алгоритмы распознавания, основанные на вычислении оценок. Кибернетика, 3:1-11, 1971.

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

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

Актуальность темы

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

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

Развитие задач метрической теории булевых функций - одного из двух указанных нами составляющих выбранного технологического подхода было связано с основопологающими работами К. Шеннона и с растущими нуждами направления создания электронных вычислительных машин стремительно развивающегося с середины XX века. Существенный вклад в эту теорию внесла российская школа ученых, Ю. И. Журавлев, О. Б. Лупанов, С. В. Яблонский, В. В. Глаголев, Ю. Л. Васильев, А. А. Сапоженко и др.

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

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

4В. М. Караханян. Минимизация булевых функций в классе шаровых покрытий. Tanulrndnyok, 135:39-50, SzTAKI, МТА, Budapest, 1982.

5JI. В. Баскакова, Ю. И. Журавлев. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств. ЖВМ и МФ, г.21, 5:1264-1275, 1981

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

Обшая методика исследования

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

Цель работы

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

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

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

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

Научная новизна

В плане научной новизны можно выделить следующие результаты:

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

• исследовано асимптотическое поведение свойства компактности на подмножествах п-мерного единичного куба и основные свойства структуры множества всех решений дискретной изопериметрической задачи,

• исследованы задачи моделирования логического уровня в задачах распознавания образов, построены иерархические системы гипо-

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

Практическая ценность

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

• разработка и программная реализация системы КАРС — кластерный анализ, распознавание и стастистика (платформа ЕС ЭВМ, алгоритмический язык Фортран), с внутренним языком управления, базой данных, со стандартно принятым набором алгоритмов кластерного анализа и распознавания, и классом алгоритмов логических отделителей,

• создание технологии и программной системы для оптического распознавания символов, использующее бинарное отображение (bit map) символов и развитых алгоритмических систем распознавания и классификации графических примитивов (программная реализация для IBM PC, С 6.00),

• создание технологической среды работы с базами данных и решение задачи информационного обеспечения управления производи ством с включением подсистем управления окон, генерации меню, отчетных печатных табличных и графических форм, оператив-них просмотров, структур создания моделей данных и справочников и организация поиска по справочникам. Данная технологическая среда разработана как нулевая оболочка, которая заполняясь содержанием различных проблемных задач превращается в соответствующее сетевое рабочее место и реально приближена к приложениям типа обеспечения ведения производственной кон-структорско - технологической документации, разработки производственного плана, учета материалов и финансов и др. (IBM PC, Novell NetWare 3.12, CLIPPER 5.1). В работе, в частности в подсистеме работы с системными справочниками широко используются алгоритмы поиска и распознавания, основанные на основных результатах данной работы,

• созданы программные системы решения сейсмологических задач:

— сбор, хранение и обработка базы данных землетрясений по их основным параметрам (время, место (гипоцентр), мощность, инструмент регистрации), связь данных с географической картой, оценка сейсмического риска и выработка сейсмического прогнозного критерия на основе ретроспективного анализа данных и алгоритмов распознавания образов (IBM

' PC, PASCAL 5.5),

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

образователен, с автоматизацией обработки временного канала и привязки полезного сигнала по времени на основе методов распознавания образов (IBM PC, PASCAL 5.5),

— дискретизация сейсмического сигнала с графического образа (scanner, PCX, GIF) (IBM PC, С 6.00),

— создана геоинформационная система города для анализа последствий разрушительного землетрясения.

Основные результаты работы доложены в ВЦ Российской Академии Наук, в ИПИА НАН Армении, на конференции "Математические методы распознавания образов", ГГущино, 1995г., на международной конференции "Intelligent and Cognitive Systems", Institute for studies in Theoretical Physics and Mathematics, Tehran, September, 1996 (пленарный доклад), на семинаре в Institute of Computer and Communication Systems, National Technical University of Athens, May, 1997.

Содержание работы

Работа структурно состоит из шести глав и списка литературы.

Первая глава - введение.

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

числа fc-мерных максимальных интервалов частичных булевых функции с к(п) единицами и 1(п) нулями -

Д(п, *(»),!(«)) = Нп)\п) <p(Ek), где

<^2"-fc(n) 4=1

ср(Ек) =

2Ь ' " " " 1°2"-!(п) — 2п —1(п)—2к)

О1=0;£>2,<»3| - .«п-4+1'!;0

Проводятся ряд последующих этапов упрощения формул. Рассматриваются эквивалентные формы представления например

7=0

и доказывается сведение к обобщенным числам Стерлинга Б(1,к,Ь) 1к(п,к(п),1(п)) ~ СкпТ

- к)1

1(п)1

_ 1 _ („ _ 1ЛЧ / Пк

S(l(n), п — к, 2"~* — 1 — (га — fc)) / _ C2T^(n)_2*

\ 1^2 "-Цп) /

когда —+ 0 при п —* оо, где

к: ,'=о

Комбинаторно представляет число всевозможных разме-

щений 2 различных объектов по к + < одинаковым ячейкам при условии, что к фиксированных ячеек окажутся не пустыми.

Рассматриваются также частные асимптотические формулы, доказываемые на основе рассмотрения некоторых комбинаторных струк^ тур:

Если —0, и —у оо при п —► оо, то 1к(п,к(п),1(п)) ~

4 х ' \ с2»-г(п) /

Если Цп111Гк) 0 при п -> оо, то 1к(п,к(п),1(п)) ~

Л-*) / /пгЛ(п) \ _ _ 2"—2Ь—1(п)

\ ^2"-г(п) /

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

1к(п,к(п),1(п)) ■< 1к(п,к(п),1(п)) =

Ск2п~к (1 -

1 ч'(п)

2п~к

1-1-

2п~к — 1

1(п)

п—к

I

\ °2"-;(п) /

и что окончательно

1ь(п,к(п),1()г)) ~ Д(п,й(п),1(п))

при о, и —+ О с п -* оо.

Раздел 2.6 посвящен исследованию оценок сложности сокр. д.н.ф. для различных классов полностью определенных булевых функций. Доказаны ряд утверждений - оценок (утв. а) - с1)). В <1), например, доказывается, что доля тех функций класса Рг(тг), граф соседства единичных вершин которых состоит из одной связанной компоненты и г изолированных вершин, подчинена вероятностному распределению Пуассона со средним значением А = 1/2. Технически это доказательство использует теорему непрерывности факториальных моментов распределений из теории вероятностей.

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

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

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

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

Доказывается, что правило F0, состоящее только в использовании соотношения логических отделителей к обучающему множеству может быть применено при доопределении почти всех функций /0 £ ^М^) с точностью, стремящейся к 1 при п —► оо, если для исходной функции f выполнено условие Alo U Ali Э -А;(а) хотя бы для одного номера г, г = 1,2, • • • и точки ä £ Еп, где множества Ai{öt) построены при некотором к < [loglogn] — 1. Здесь AI о и Ali - множества обучения и Ai(ä) шар радиуса г с центром в точке а.

Как было сказано, правило логического отделения по множеству обучения А1о и Ali разбивает Еп на три подмножества точек (для случая двух классов) - достижимых только от А1о, достижимых толь-

ко от A^i и достижимых от Aio и Ali одновременно. Это множества - М/, М/ и М.{.

В этих терминах доказывается, что если к(п) и 1(тг) есть о(2")

при га —► оо и существует j0, такое, что fc(ra)2j0_n —► О

и 2_n Е СЧ(п) —оо, то для почти всех функций класса 1=0

Ф2(п,к(п),1(п)) | М{ о(2п), при гаоо.

Доказывается также, что если i(n) > 0 и с(п) - произвольная ограниченная функциия, такая что —► 0 при га —► оо, то для почти всех функций / класса Ф2(п,к(п),1(п)) | М/ |~о(2п).

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

Пусть /о булевая функция с к\ и к2 компактными множествами нулей и единиц. Пусть Д - доопределение функции /, проведенное на основании условия F0. Если I > = о(2га), при га —> оо

и множество ЛЛо(/) U ■M-i(f) формируется как случайная выборка

мощности I из множества Еп, то почти всегда функция Д является таким доопределением функции /, которое совпадает с /о с точностью, стремящейся к 1 с п —оо.

Доказано, что число таких функций не менее 2 е'где е\(п) -произвольная функция аргумента п, ех(п) —► 0 при п —* оо.

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

Для произвольного подмножества А С Еп скажем, что вершина о: £ А является граничной, если (а) £ А, - шар радиуса

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

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

В разделе 4.3.1 проводятся основные построения, используемые в решении дискретной изопериметрической задачи. Определяется стандартная последовательность £к - как специальное упорядочение вершин га-мерного единичного куба Еп. Исследуются начальные отрезки этой последовательности - стандартные размещения. В этом разделе,

еВ. Бляшке. Круг и шар. Наука, 1967.

в частности доказывается, что для каждого а, 0 < а < 2", внутренние точки множества вершин последовательности (начального отрезка) = {âi, ¿2,..., äa} предшествуют его граничным точкам.

В разделе 4.3.2 приводится основная изопериметрическая теорема: стандартное размещение произвольной мощности a, 0 < а < 2™, в вершинах тг-мерного единичного куба Еп обладает минимальным числом Г(а) граничных точек. Этот результат был доказан разными

7 Я

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

Специальное строение стандартного размещения позволяет определить значение числа граничных точек для оптимальных размещений произвольной мощности. Если А С Еп стандартное размещение мощности

I А 1= £ Сп + Ь где 0 < к < п и 0 < 6 < С*+1, t=о

то справедливо следующее (единственное) представление числа 6:

с _ y^ifc—mi+l i pfc-ma+2 . . . _L -r

n—mi ' n—Ш2 ' n—mT '

где 1 < m i < шг < • • • < mT < п.

Пусть Pfe(ô) число внутренних точек стандартного размещения X™, которые принадлежат к-му слою Еп и получаются в результате соответствующего размещения 6 точек в к + 1-ом слое. Тогда

• рк(б) = cknzz\ + + • • • +

TL. H. Harper. Optimal numberiiigs and isoperimetric problems on graphs. Journal of combinatorial theory 1., 1:385-393, 1966.

8G. Katona. The Hamming-sphere has minimum boundary. Studia Scient. Math. Hungarica, 10:131140, 1975.

В разделе 4.3.3 исследуются разбиения решений дискретной изопе-риметрической задачи (описание свойств - характеристик решений).

Для произвольного оптимального подмножества А и произвольного номера г, 1 < г < п,

Мг(0 1> ECU-

t=о

Доказывается, что для произвольного оптимального подмножества А С Еп либо существует такая координата хi = 1, 2, ..., тг, что для разбиения А = A°(i) U Al(i) справедливо соотношение

|Г(А)| = | Г(А°(г)) | -)- | Г(А1(г)) |,

или же А = 5^_2(5). В обоих случаях подмножества A°(i) и Аг({) оптимальны соответственно в подкубах Е^{г) и E"(i). Этим мы получаем ключ ко многим индуктивным доказательствам.

Аналогичное количественное описание разбиений решений задачи рассмотрено в разделе 4.3.4. Доказывается, что для произвольного оптимального подмножества А С Еп мощности С^ + 6, 0 < 6 < с; и каждого г, 1 < г < п,

I A°(i) |> £ CU-

t=о

Для произвольного оптимального подмножества А критической мощности и для каждого номера г, 1 < г < п,

min(| A°(i) |, | АЧО I) < «т = £ CU - (CU-V-

t=о

Результаты предыдущих разделов обобщаются в 4.3.5. Пусть А подмножество мощности C\t -f 6, 0 < 6 < С К

Оптимальное подмножество А С Еп содержит шар радиуса к, т.е. существует такая точка а £ А, что С А.

Для специального класса критических мощностей доказывается, что существует такая точка а £ А, что 5£(а) С А С До-

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

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

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

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

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

Основные результаты

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

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

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

• найдено асимптотическое распределение подмножеств п-мерного единичного куба по заданной компактности,

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

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

• разработан широкий класс программных технологий и сред для решения актуальных прикладных задач распознавания образов.

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

1. Л. А. Асланян. О сложности сокращенной дизъюнктивной нормальной формы частичных булевых функций.1. Ученые Записки, Естественные науки, Ереванский Государственный универ: ситет, 1:11-18, 1974.

2. Л. А. Асланян. О сложности сокращенной дизъюнктивной нормальной формы частичных булевых функций.П. Ученые Записки, Естественные науки, Ереванский Государственный университет, 3:16-23, 1974.

3. Л. А. Асланян. О применениях сокращенной дизъюнктивной нормальной формы в задачах доопределения частичных булевых функций. Молодой научный работник, Естественные науки, Ереванский Государственный университет, 20(2):65~75, 1974.

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

5. Л. А. Асланян. Алгоритмы распознавания с логическими отделителями. В Сборник работ по Математической кибернетике, стр. 116-131. Вычислительный центр, АН СССР, Москва, 1976.

6. Л. А. Асланян, В. М. Караханян. Описание множества всех решений дискретной изопериметрической задачи. Доклады Академии наук, Ари. ССР, Ереван, 65(4):211-215, 1977.

7. JI. А. Асланян. Изопериметрическая задача и смежные экстремальные задачи для дискретных пространств. Проблемы Кибернетики, Москва, 36:85-127, 1979.

8. JI: А. Асланян, И. А. Акопова. Докозательства некоторых оценок сокращенных дизъюнктивных нормальных форм булевых функций. Ученые Записки, Естественные науки, Ереванский Государственный университет, 1:14-23, 1980.

9. JT. А. Асланян. О длине кратчайшей дизъюнктивной нормальной формы слабо определенных булевых функций. Прикладная математика, Ереванский Государственный университет, 2:32-40, 1982.

10. Л.- А. Асланян. Дискретная изопериметрическая проблема - асимптотический случай. Доклады Академии наук, Арм. ССР, Ереван, 7^(3):99-103, 1982.

11. Л. А. Асланян. К вопросу минимизации систем слабо определенных булевых функций. В Некоторые задачи автоматизации проектирования, стр. 51-86. SzTAKI, МТА, Tanulmanyok, 135. Budapest, 1982.

12. Л. А. Асланян. О единственности компактных булевых функций с точностью до изоморфизма. Working Paper, МТА SzTAKI, Budapest, E/17:l-ll, 1983.

13. Л. А. Асланян, А. К. Казарян, А. А. Саакян. Нестандартные задачи распознавания в сейсмологии. Во II Всероссийской с участием стран СНГ конференции, Распознавание образов и анализ изо-

бражений: новые информационные технологии, Ульяновск, 27-29 августа 1995.

14. Л. А. Асланян, В. Г. Саакян. Прогнозный критерий, основанный на выделении опорных событий. Во II Всероссийской с участием стран СНГ конференции, Распознавание образов и анализ изображений: новые информационные технологии, Ульяновск, 27-29 августа 1995.

15. Л. А. Асланян, В. М. Караханян. Распознавание образов и информационно поисковые системы. В VII Всероссийской конференции, Математические методы для оптимизации распознавания образов, Пухцино, 25-30 сентября 1995.

16. L. Н. Aslanian and I. A. Akopova. On the distribution of the number of interior points in subsets of the n—dimensional unit cube. In Colloquia Mathematica Societatis Yanos Bolyai, 37. Finite and Infinite Sets, pages 47-58, (Eger) Hungary, 1981.

17. L. H. Aslanian. The discrete modeling technologies. In I International Conferece on Application of Critical Technologies for the Needs of Sosiety, September 14-17, Yerevan, 1995.

18. L. H. Aslanian. On Components and Design of Industrial Information Systems. In Information Technologies, ПАР NAS RA, 17pp., 1997.