1 Класс сбалансированных деревьев 20
1.1 Оптимальное решение над базисом элементарных конъюнкций 20
1.1.1 Построение оптимальных деревьев 20
1.1.2 Порядок сложности сбалансированных деревьев . 27
1.1.3 Асимптотики в классе сбалансированных схем . 30
1.2 Оптимальное решение над базисом переменных 32
1.2.1 Построение оптимальных сбалансированных деревьев 32
1.2.2 Порядок сложности в классе сбалансированных деревьев , 33
1.2.3 Асимптотики в классе сбалансированных деревьев 35
1.2.4 Случай произвольного отношения поиска 36
1.3 Случай взвешенных базисов 37
1.3.1 Критерий допустимости системы весов 38
1.3.2 Построение оптимального сбалансированного дерева 39
1.3.3 Порядок сложности оптимальных деревьев 49
2 Функция Шеннона сложности в классе древовидных схем 60
2.1 Нижняя оценка 60
2.2 Верхняя оценка 66
2.3 Оценки функции Шениопа 67
3 Алгоритмы построения решающих деревьев 69
3.1 Описание алгоритмов 69
3-1.1 Алгоритм с жестким порядком проверок (А1) . 69
3.1.2 Алгоритм первого пересечения (A2{V,
3.1.4 Сравнительный анализ алгоритмов 74
3.2 Средняя сложность алгоритма с жестким порядком проверок (А1) 82
3.2.1 Вспомогательные утверждения 83
3.2.2 Доказательство теоремы 92
Оглавление 4
3.3 Средняя сложность алгоритма первого пересечения (А2) . 92
3.3.1 Вспомогательные утверждения 93
3.3.2 Доказательство теоремы 98
Список литературы
