Построение обобщенных полиномов минимальной степени над алгоритмами вычисления оценок

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

Оглавление
Введение

1 Основные определения и обозначения

1.1 Вводные понятия.

1.2 Условия существования корректною алгоритма.

1.3 Оценка степени полинома

2 Оптимизационная задача

2.1 Алгоритмы в обобщнном алгебраическом замыкании .

2.2 Формулировка оптимизационной задачи

2.3 Декомпозиция оптимизационной задачи

2.4 Геометрическая интерпретация.

2.5 Теорема о существовании решения
2.6 Решение вспомогательной задачи.
ОГЛАВЛЕНИЕ З
2.6.1 Сведение к последовательности задач квадратичного программирования.
2.6.2 Решение задачи квадратичного программирования методом линеаризации
2.6.3 Решение задачи квадратичного программирования обобщнным методом Ньютона
2.6.4 Метод последовательного квадратичного программирования
3 Эффективные методы решения
3.1 Эффективный перебор вспомогательных задач
3.2 Последовательное уменьшение области ограничений
3.3 Модификация алгоритма для работы на многопроцессорных системах
3.4 Минимизация числа слагаемых
3.5 Использование методов увеличения эффективности при
минимизации числа слагаемых
4 Проведение экспериментов
4.1 Описание экспериментов.
4.2 Обобщнный полиномиальный алгоритм над неправильным набором распознающих операторов.
ОГЛАВЛЕНИЕ
4.3 Решение задач
4.3.1 Методика проведения экспериментов
4.3.2 Задача Ii
4.3.3 Задача .
4.3.4 Задача
4.3.5 Задача
4.3.6 Выводы.
4.4 Оценка эффективности.
Список литературы


Вводные понятия. Условия существования корректною алгоритма. Алгоритмы в обобщённом алгебраическом замыкании . Геометрическая интерпретация. Решение вспомогательной задачи. Сведение к последовательности задач квадратичного программирования. Описание экспериментов. Обобщённый полиномиальный алгоритм над неправильным набором распознающих операторов. Задача «Sonar». Выводы. Оценка эффективности. Данная работа посвящена некоторым вопросам построения корректных алгоритмов в алгебре над множеством алгоритмов вычисления оценок для задач распознавания. В частности, предлагается метод построения алгоритма специального вида, являющегося обобщением полиномиального алгоритма. Также предложены подходы для существенного повышения эффективности реализации этого метода. Основы алгебраического подхода в теории распознавания были заложены в работах . И. Журавлёва и его учеников. Этот взгляд на теорию распознавания стал возможен благодаря показанному в работе [6] представлению алгоритмов распознавания в виде композиции распознающего оператора и оператора, задающего решающее правило. Такое разделение • на два разнотипных оператора позволило описывать алгоритмы в виде композиции более простых алгоритмов, используя для этого элементы из алгебраического замыкания. И. Журавлёвым был предложен [4, 5. ABO). В [7] вводится понятие регулярности задачи распознавания и доказывается теорема существования корректного алгоритма в алгебраическом замыкании АВО для любой регулярной задачи. Первые оценки степени корректного полинома и вопросы его устойчивости были получены в [8]. Задача нахождения полиномов наименьшей степени является весьма существенной для построения алгоритмов высокой точности. Это определяет постоянный интерес исследователей к данному вопросу. Дальнейшие результаты оценки степени корректного полинома были получены В. Л. Матросовым. В работе [] был получен критерий корректности замыкания семейства АВО конечной степени. На основании этого критерия им была показана неполнота линейного замыкания модели АВО []. В работе [] Т. В. Плохонина развила этот результат, показав неполноту квадратичного замыкания модели АВО. В своей докторской диссертации В. Л. Матросовым [] получен аналогичный результат для общего случая —при любой фиксированной степени существует задача распознавания, для которой в замыкании этой степени нельзя получить корректный алгоритм. В. Л. Матросову удалось улучшить верхние оценки степени и количества слагаемых для замыкания классического семейства АВО []. Кроме того, им было предложено обобщение АВО (семейство АВО над упорядоченным полем G) и показано, что это обобщение содержит корректный алгоритм в линейном замыкании [].