Временная сложность деревьев решений

• Автор: Мошков, Михаил Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1999
• Место защиты: Нижний Новгород
• Количество страниц: 182 с. : ил.

Оглавление
Предисловие
Глава 1. Введение
1.1. О теории деревьев решений
1.2. О содержании диссертационной работы
Глава 2. Условные тесты
2.1. Основные определения и обозначения
2.2. Нижние оценки сложности условных тестов
2.3. Верхние оценки сложности условных тестов
2.4. Алгоритм построения условных тестов
2.5. О сложности решения проблем оптимизации условных тестов
2.6. Сложность вычисления булевых функций из замкнутых классов
Глава 3. Деревья решений. Локальный подход
3.1. Основные определения и обозначения
3.2. Использование теории тестов при анализе деревьев решений
3.3. Локальные функции Шеннона
3.4. Проблемы локальной оптимизации деревьев решений
3.5. Мощностные характеристики тестовых таблиц
3.6. Алгоритм построения тестовых таблиц
3.7. Алгоритм построения деревьев решений
Глава 4. Деревья решений. Глобальный подход
4.1. Глобальные функции Шеннона
4.2. Проблемы глобальной оптимизации деревьев решений
4.3. Допустимые меры сложности
4.4. Выбор проверок
Глава 5. Деревья решений над системами квазилинейных проверок
5.1. Оценки сложности и алгоритмы построения деревьев решений над системами квазилинейных проверок
5.2. Предварительные леммы
5.3. Основные леммы
5.4. Доказательства теорем
5.5. Глобальные функции Шеннона для некоторых тестовых троек
Глава 6. Классы задач над системами квазилинейных проверок
6.1. Условие принадлежности задачи множеству задач над системой квазилинейных проверок
6.2. Задачи дискретной оптимизации
6.3. Задачи распознавания и сортировки
Глава 7. Ациклические программы в базисе {ж +у,х — у, 1; s(x)}
7.1. Основные определения и результаты
7.2. Доказательство теоремы

Глава 8. Распознавание слов регулярных языков, заданных
автоматными источниками
8.1. Оценки глубины деревьев решений, распознающих слова регулярного
языка
8.2. Доказательство теоремы
Глава 9. Диагностика константных неисправностей схем из
функциональных элементов
9.1. Основные понятия
9.2. Сложность алгоритмов диагностики
9.3. Сложность построения алгоритмов диагностики
9.4. Диагностика неисправностей бесповторных схем
9.5. Подход к синтезу схем и диагностике их неисправностей
Дополнение. Замкнутые классы булевых функций
1. Некоторые определения и обозначения
2. Описание всех замкнутых классов булевых функций
Литература
Предисловие
Деревья решений используются в различных приложениях как алгоритмы решения задач и как способ представления знаний. При их исследовании возникают разнообразные математические проблемы. О некоторых из них, связанных с оценками временной сложности и алгоритмами построения деревьев решений, пойдет речь в диссертационной работе.
Эта работа не охватывает всего многообразия моделей и методов, имеющихся в настоящее время в теории деревьев решений. Однако в ней делается попытка, при некоторых ограничениях на тип деревьев решений и меру их сложности, изложить теорию временной сложности деревьев решений, начиная с создания необходимых инструментов исследования, далее рассматривая деревья решений над произвольными системами проверок и кончая различными приложениями. Основные ограничения состоят в том, что изучаются только детерминированные деревья решений и меры сложности, характеризующие время их работы в худшем случае.
За исключением приложений, все исследования, относящиеся к теории деревьев решений, можно разделить на две части в зависимости от того, конечна или бесконечна рассматриваемая система проверок. Деревья решений над конечными системами проверок изучаются в теории тестов, теории информационных систем и грубых множеств, теории вопросников, теории таблиц решений, теории машинного обучения, теории поиска. Методы и результаты исследований для конечных систем проверок являются основой для изучения бесконечных систем. Понятие бесконечной системы проверок оказалось полезным в дискретной оптимизации, распознавании образов, вычислительной геометрии. Однако, деревья решений над бесконечными системами проверок изучены в значительно меньшей степени, чем для случая конечных систем проверок. Основные достижения здесь связаны с исследованием линейных и алгебраических деревьев решений. По-видимому, ранее вопросы сложности деревьев решений над произвольными бесконечными системами проверок не изучались.
В диссертационной работе разработаны методы теории тестов, относящиеся к оценкам сложности и алгоритмам построения условных тестов, служащих моделями деревьев решений. На основе методов теории тестов развиты два подхода к исследованию деревьев решений над произвольной системой проверок: локальный, когда для задачи рассматриваются деревья решений, использующие только те проверки, которые входят в описание задачи, и глобальный, когда допускается использование любых проверок из изучаемой системы. Для локального и глобального подходов рассмотрены оценки минимальной сложности деревьев решений и проблемы построения деревьев решений минимальной и близкой к минимальной сложности. Более подробно исследованы деревья решений над системами квазилинейных проверок, являющиеся обобщением линейных и алгебраических деревьев решений.
Разработанные методы исследования использованы при изучении ряда проблем,

Если это не так, то выберем в дереве С некоторую вершину го, которой приписано слово из {2ДУ). Пусть вершине го приписано слово а.
Пусть Та - вырожденная таблица. Если Л(Та) = 0, то вместо слова а припишем вершине го число 0. Если Л(Та) 0, то вместо слова а припишем вершине го число
ит(6), где 6 - строка из Л(Та). Перейдем к (£ + 2)-му шагу.
Пусть Та - невырожденная таблица. Построим с помощью подпроцесса Хр$ схему Хр$(Та). Для каждого полного пути £ схемы ХР(Т) заменим число 0, приписанное концевой вершине этого пути, на слово атг(£). Полученное в результате такой замены дерево обозначим Г. Удалим из дерева С вершину ги и добавим к дереву (3 дерево Г. Если в вершину и) входила дута, то присоединим ее к корню дерева Г. Перейдем к (4 + 2)-му шагу.
Пример 2.3.2. Обозначим Т таблицу, изображенную на рис. 2.1.1. На рис. 2.1.2 изображена схема У{Т).
2.3.3. Доказательство теоремы
Лемма 2.3.1. Пусть ф - мера, сложности сигнатуры р, иТ - невырожденная таблица из Нр. Тогда для. любого полного пути £ схемы ХР,{Т) выполняются следующие утверждения:
(а) ф(тг(0) < Мр„(Т);
(б) если Тпг(£) - невырожденная таблица, то
М„(Ттг(0) < ЛГДТ)/тах{2,/г(7г(£))}.
Доказательство. Пусть Т содержит п столбцов, которым приписаны элементы /ь
ффф0))М{Т,а). (2.3.1)
Пусть тг(£0) = (/,(!), ф-(1)) (//(т), ф(т))- Обозначим а0 = А и для г = 1,
тах{1уо(Таг_1(/,), а)): а € Ек {д(г)}}.
Пусть / - произвольный полный путь схемы ХРР1,{Т). Пусть £ = /о- Используя (2.3.1), получаем, что ф(7г(/0)) ~ Мр(Т,а) < Мр(Т). Пусть £ ф £0. Нетрудно показать, что в этом случае существуют числа г € {1
Пусть £ - полный путь схемы ХР,(Т) такой, что Ттг($) - невырожденная таблица. Учитывая, что Т'тг(£о) - вырожденная таблица, получаем, что £ ф /о- Нетрудно