Введение к работе
Актуальность темы. Несмотря на впечатляющие успехи науки и техники, остается довольно большое число задач, в решении которых самые быстродействующие компьютеры заметно уступают человеку и даже многим животным. Человек легко узнает лица и предметы, понимает речь, ориентируется в пространстве, анализирует динамические сцены.
Широкий класс среди вышеупомянутых задач представляют задачи распознавания образов, являющиеся в частном случае дискретным аналогом проблемы поиска оптимальных решений. На практике это задачи из таких областей, как геология, медицина, социология, химия — не позволяющие строить формальные модели. Это обстоятельство определило тот факт, что на первом этапе развития теории и практики распознавания образов возникло большое число различных методов и алгоритмов, применявшихся без какого - либо серьезного обоснования для решения практических задач. Такие методы, как это принято во всех экспериментальных науках, обосновывались экспериментальной проверкой — успехом решения реальных задач. Однако очевидна необходимость изучения с помощью строгих математических методов самого множества таких процедур.
Кроме обилия прикладных вопросов, исследование которых сводится к задачам этого типа, следует отметить весьма важный для математиков факт, что решение таких задач ввело в обиход большое число некорректных (эвристических) алгоритмов. Очевидно, появление каждого из таких алгоритмов можно рассматривать как эксперимент, а со всем множеством таких экспериментов и их результатов — работать, как с новым для математики множеством объектов. В результате возникают теоретические проблемы, решение которых имеет большое практическое значение. Это такие проблемы, как оценка емкости важных моделей алгоритмов, исследование корректирующих операций, синтез корректных алгоритмов минимальной сложности, решение вопросов об их устойчивости. В настоящее время перспективной представляется идея построения корректных алгоритмов методом покры-
ТИЙ1'2'3.
1 Журавлев Ю.И., Исаев И.В. Построение алгоритмов распознавания, корректных
для заданной контрольной выборки. — ЖВМ и МФ, 1979. Т. 19. № 3, — С. 726 —
738.
2 Матросов В.Л. Оптимальные алгоритмы в алгебраических замыканиях операто
ров вычисления оценок. // ДАН СССР, 1982. Т. 262. № 4. — С. 818 — 822.
J Исаев И.В. Задача синтеза корректного алгоритма распознавания, как задача построения минимального покрытия // ЖВМ и МФ, 1983. Т. 23. № 2. — С. 467 — 476.
Цель работы. Исследование важных классов алгоритмов вычисления оценок (АВО). Получение для наиболее употребительных, признаковых пространств верхних и нижних оценок границ емкости. Построение и исследование корректного алгоритма, определение его радиуса устойчивости. Разработка компьютерной программы, осуществляющей распознавание образов, предъявляемых специально созданной математической моделью реального динамического процесса, и управляющей на основании распознанных ситуаций этим процессом.
Методы исследования. При получении результатов были использованы метод є — сечений 4 и метод минимальных покрытий, позволяющий эффективно выделять в модели АВО максимальные операторы5. Использовались средства вычислительной техники для апробации полученных теоретических результатов.
Научная новизна. Все основные результаты диссертации являются новыми.
Основные результаты диссертации:
-
Получены оценки верхней и нижней границ емкости модели АВО.
-
Для алгебр вычислимых операций произвольного типа над классом всех АВО и классом АВО с опорным множеством {jlt...,jk)cz{\2,...,n} получены верхние оценки емкости исследуемых
моделей алгоритмов, инвариантные относительно выбора главных операций, при условии ограничения на их размерность.
-
Для произвольной регулярной задачи разработан метод синтеза корректного алгоритма основанный на построении минимального операторного покрытия, предложенного В.Л. Матросовым2, дана оценка радиуса устойчивости синтезированного алгоритма.
-
Разработана компьютерная программа, осуществляющая распознавание образов, предъявляемых специально созданной математической моделью реального динамического процесса и успешное управление на основании распознанных ситуаций этим процессом.
Практическая и теоретическая ценность. Первые две главы диссертации носят теоретический характер. Полученные в них результаты позволяют судить о разнообразии исследованных классов алгоритмов, дают разрешение некоторых вытекающих проблем как теоретического, так и практического характера. Третья глава, посвященная практической стороне вопроса построения корректного алгоритма, является "полигоном" для проверки ранее полученных теоретических результатов.
4 Матросов В.Л. Емкость алгебраических расширений модели алгоритмов вычис
ления оценок. // ЖВМ и МФ, 1984. Т. 24, № 11. — С. 1719 — 1730.
5 Матросов В.Л. Оптимальные алгоритмы в алгебраических замыканиях операто
ров вычисления оценок. // ДАН СССР, 1982. Т. 262. № 4. — С. 818 — 822.
Результаты и методы диссертации могут быть использованы в дальнейших исследованиях как в рамках алгебраического подхода, так и при решении других проблем теории распознавания в МПГУ, ВЦ РАН и других университетах и пединститутах.
Апробация работы. Результаты диссертации докладывались на семинарах кафедры информатики и дикретной математики МПГУ.
Публикации. Основные результаты диссертации представлены в пяти работах (см. ниже).
Структура работы. Диссертация состоит из введения, трех глав, списка литературы, содержащего 81 источник и приложения. Всего 111 страниц, 7 рисунков.
