Проблема обоснования качества классов алгоритмов с универсальными ограничениями монотонности

• Автор: Семочкин, Александр Николаевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 91 с.

ОГЛАВЛЕНИЕ
Введение
0.1 Эволюция задачи распознавания образов
0.2 Об исходных конструкциях алгебраического подхода
0.3 О теории универсальных и локальных ограничений
0.4 Качество и надежность алгоритма
0.5 Цель, методы и содержание работы по главам
Глава I Проблема обоснования качества решения задачи распознавания с универсальными ограничениями монотонности
1.1 Исходные положения алгебраической теории универсальных
и локальных ограничений для алгоритмов распознавания
1.2 О полноте универсальных ограничений для алгоритмов классификации
1.3 Проблема обоснования качества решения задачи распознавания
1.4 Определение линейного построения частичного порядка
1.5 Описание одного класса алгоритмов распознавания с универсальными ограничениями монотонности
1.6 Постановка задачи
Глава II Линейные достроения частичного порядка на конечных множествах
2.1 Число линейных построений для частичного порядка, задающего две непересекающиеся цепи
2.2 Плотность и однородность частичного порядка
2.3 Оценки числа линейных построений частичного порядка с заданными характеристиками порядка
Глава III Оценки функционала качества для класса алгоритмов с универсальными ограничениями монотонности
3.1 Исследования класса всех монотонных отображений
3.2 Случай диагонального частичного порядка
3.3 Случай линейного порядка
3.4 Общий случай задания частичного порядка на множестве объектов
3.5 Исследование применимости полученных оценок
3.6 Оценка количества монотонных дихотомий для одного класса частичных порядков на конечном множестве
3.7 Оценки скорости сходимости функционала качества
Заключение
Литература

Введение
0.1 Эволюция задачи распознавания образов
Одной из ключевых проблем информатики является разработка,
исследование и реализация методов синтеза алгоритмических процедур преобразования и анализа информации, предназначенных для решения таких информационных задач, для которых соответствующие алгоритмы неизвестны. Эти методы уже свыше 60 лет неявно или явно составляют сердцевину математической теории алгоритмов, кибернетики и информатики. Несмотря на общность проблемы, основным предметом интенсивных исследований, развития и оформления в виде законченной математической теории стал класс задач, известных под названием задач распознавания образов.
Термин «образ» в настоящее время употребляют в самом широком смысле, имея в виду некоторое структурированное приближенное (частичное) описание изучаемого объекта или явления, причем частичная определенность описания является принципиальным свойством образа. Образ допускает рекурсивное определение: например, символ является образом, список символов является образом, образами являются только те выражения, которые построены в соответствии с двумя указанными условиями. Основное назначение образов выражается в их использовании в процессе установления соответствия объектов, то есть при доказательстве их идентичности, аналогичности, подобия, сходства и т.п., осуществляемом путем сопоставления. Подобные объекты, то есть те объекты, образы которых оказались сопоставимыми, объединяются в классы.
Сопоставление образов представляет собой основную процедуру в задачах распознавания и играет существенную роль в информатике в целом. Эта задача возникает, в частности, в различных разделах искусственного интеллекта, например в понимании естественного языка, символьной обработке

1.4 Определение линейного достроения частичного порядка
Прежде чем приступить к изучению вопроса обоснования качества алгоритмов с универсальными ограничениями монотонности, приведем определения и понятия, необходимые для дальнейших рассуждений.
Пусть определено множество £ = {а,6,с
Определение 1.4.1. Множество 5 называется частично упорядоченным множеством, а бинарное отношение л называется отношением порядка или частичным порядком, если л обладает следующими свойствами:
— свойство транзитивности: (< а,Ъ >ел а <Ь,с>ел)=>(<а,с>Ел');
— свойство рефлексивности: < а,а >е л,
— свойство антисимметричности: (< а,Ь >е л л < Ь,а >е л') => (а = Ь) где а еБ,Ь е8,с еБ.
Пусть 51 = а,Ъ,с
Ъ несравнимы по отношению порядка л, и обозначать а || пЪ.
Определение 1.4.3. Множество 2 называется линейно упорядоченным множеством или цепью, если на нём определено отношение частичного порядка Я такое, что /а,Ъ Е2,а±Ъ> <а,Ъ>ЕХ V <Ъ,а>Е2. Порядок Я в этом случае называется линейным порядком, заданным на множестве 2.