Введение
1 Глава 1. Базовые понятия и определения . 25
1.1 Необходимые определения 25
1.2 Линейные и аффинные преобразования 28
1.3 Модели компактного представления бинарного дерева - виды диаграмм 30
1.4 Бинарные диаграммы решений - формальный подход 37
1.5 Бинарные диаграммы решений с разделением общих частей для функций с несколькими выходами 39
1.6 Минимизация не полностью заданных функций 40
1.7 Выводы 41
2 Глава 2. Линейные и аффинные преобразования переменных и обоснование алгоритмов 43
2.1 Проблема сокращения размера бинарных диаграмм с помощью линейных и аффинных преобразований 43
2.2 Линейные и аффинные преобразования переменных и сокращение размера бинарных диаграмм решений 44
2.3 Матричное задание линейных и аффинных преобразований 47
2.4 Теорема 2.1 50
2.5 Теорема 2.2 52
2.6 Анализ влияния линейных и аффинных преобразований над соседними переменными на бинарное дерево 53
2.7 Идея алгоритма сокращения размера БДР. 58
2.8 Выводы 59
3 Глава 3. Построение алгоритмов 60
3.1 Построение алгоритма 60
3.2 Алгоритм упорядочения дерева. 64
3.3 Модифицированный алгоритм (А1) 65
3.4 Метод двухуровнего перебора (А2) 66
3.5 Алгоритм выявления симметрии (A3) 67
3.6 Алгоритм однородности (А4) 67
3.7 Выводы 69
4 Глава 4. Теоремы и экспериментальные оценки эффективности алгоритмов 70
4.1 Число шагов алгоритма однородности 70
4.2 Пример сокращения БДР функции XOR5 алгоритмом А4 73
4.3 Экспериментальная оценка уменьшения бинарных диаграмм 75
4.4 Эффективность работы алгоритмов и их совокупностей на функциях с одним выходом для различного числа входящих переменных 77
4.5 Функции с несколькими выходами 77
4.1 Описание программного комплекса 80
4.2 Выводы. 81
Заключение 83
Литература 85
Приложения 96
Исходные тексты программ 96
