Временная сложность деревьев решений Мошков, Михаил Юрьевич

Краткое описание

Мошков, Михаил Юрьевич.Временная сложность деревьев решений : диссертация ... доктора физико-математических наук : 01.01.09. - Нижний Новгород, 1999. - 182 с. : ил.

Оглавление диссертациидоктор физико-математических наук Мошков, Михаил Юрьевич
Предисловие
Глава 1. Введение.
1.1.0 теории деревьев решений
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. Задачи распознавания и сортировки
Глава Т. Ациклические программы в базисе {х +у,х — у, 1; 5(ж)}
7.1. Основные определения и результаты.
7.2. Доказательство теоремы 7.1.
Глава 8. Распознавание слов регулярных языков, заданных автоматными источниками.
8.1. Оценки глубины деревьев решений, распознающих слова регулярного языка.
8.2. Доказательство теоремы 8.1.
Глава 9. Диагностика константных неисправностей схем из функциональных элементов
9.1. Основные понятия
9.2. Сложность алгоритмов диагностики.
9.3. Сложность построения алгоритмов диагностики.
9.4. Диагностика неисправностей бесповторных схем
9.5. Подход к синтезу схем и диагностике их неисправностей
Дополнение. Замкнутые классы булевых функций.
1. Некоторые определения и обозначения
2. Описание всех замкнутых классов булевых функций