Методы и алгоритмы линейных и аффинных преобразований для модели бинарных диаграмм решений

• Автор: Колпаков, Антон Валериевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Казань
• Количество страниц: 139 с. : ил.

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

1 Глава 1. Базовые понятия и определения

1.1 Необходимые определения

1.2 Линейные и аффинные преобразования

1.3 Модели компактного представления бинарного дерева виды диаграмм.

1.4 Бинарные диаграммы решений формальный подход

1.5 Бинарные диаграммы решений с разделением общих частей для функций с

несколькими выходами

1.6 Минимизация не полностью заданных функций.

1.7 Выводы
2 Глава 2. Линейные и аффинные преобразования переменных и обоснование
алгоритмов
2.1 Проблема сокращения размера бинарных диаграмм с помощью линейных и
аффинных преобразований..
2.2 Линейные и аффинные преобразования переменных и сокращение размера
бинарных диаграмм решений.
2.3 Матричное задание линейных и аффинных преобразований
2.4 Теорема 2.1.
2.5 Теорема 2.2.
2.6 Анализ влияния линейных и аффинных преобразований над соседними
переменными на бинарное дерево
2.7 Идея алгоритма сокращения размера БДР.
2.8 Выводы
3 Глава 3. Построение алгоритмов
3.1 Построение алгоритма
3.2 Алгоритм упорядочения дерева
3.3 Модифицирова1ШЫЙ алгоритм А1
3.4 Метод двухуровнего перебора А2
3.5 Алгоритм выявления симметрии АЗ.
3.6 Алгоритм однородности А4
3.7 Выводы
9 4 Глава 4. Теоремы и экспериментальные оценки эффективности алгоритмов
4.1 Число шагов алгоритма однородности
4.2 Пример сокращения БДР функции ХСЖ5 алгоритмом А4
4.3 Экспериментальная оценка уменьшения бинарных диаграмм.
4.4 Эффективность работы алгоритмов и их совокупностей на функциях с одним выходом для различного числа входящих переменных
4.5 Функции с несколькими выходами
4.1 Описание программного комплекса
4.2 Выводы
т Заключение.
Литература


Смысл минимизации линейными преобразованиями заключается в поиске наименьшего или приемлемого по размеру (в смысле количества узлов) в бинарной диаграмме решений преобразованной функции по сравнению с исходной БДР. Для получения исходной функции из преобразованной применяется схема, показанная на рисунке 5. Для задания линейных преобразований используются матрицы размерности пхп вместо матриц размером Т х2" применяемых в спектральных методах, где п - число входящих переменных. Рис. Схема получения исходной функции из преобразованной. Этот подход к минимизации интересен простой реализацией результатов вычислений: достаточно преобразовать входящие переменные умножением на матрицу размерности пхп и получается значительно упрощенная схема. Для преодоления проблем, связанных с большой размерностью БДР при реализации булевских умножений, и для более компактного представления функций были предложены расширения структуры БДР. Этой области посвящено достаточно много современных работ. PKDD (Pseudo-Kronecker Decision Diagrams) [6], ZBDD[]. В бинарной диаграмме на каждом узле применяется разложение Шеннона. При этом кроме объединения изоморфных ветвей применяется удаление узла, если его исходящие ветви указывают на один узел. Другие виды диаграмм решений, используют различные комбинации типа разложения и метода сокращения «вырожденных» узлов, как например, ZBDD (Zero suppressed Binary Decision Diagram - Бинарные диаграммы решений с подавлением нуля). В ZBDD - вместо удаления вершины, у которой исходящие ветви указывают на один узел, применяется удаление узлов, если единичный выход указывает на 0. Этот метод в общем случае хуже, чем в бинарной диаграмме решений (BDD), но значительно лучше в некоторых специальных случаях, например при реализации булевских умножений. Диаграммы решений Кронекера (K. DD) являются расширением BDD путем использования разложений positive Davio Expansion и Negative Davio Expansion. В этом случае на каждом уровне применяется либо разложение Шеннона, либо Davio Expansion, либо Negative Davio Expansion. Псевдо-Кронекеровские диаграммы решений (PKDD) - расширение KDD, но в этом случае на одном уровне можно использовать разложения positive Davio Expansion и Negative Davio Expansion, либо разложение Шеннона. В работе [6] описываются преимущества PKDD над BDD, но при этом опять возникает проблема построения оптимального PKDD. Процесс построения оптимальной псевдо-кронекеровской диаграммы решений сам по себе является процессом оптимизации и для этого требуются большие вычислительные ресурсы. Поэтому при построении PKDD также применяются эвристические алгоритмы. РКГЮ составляет около % от базовой функции. В работе [7] описан метод точной минимизации ВЭЭ, с использованием линейных преобразований над входящими переменными. Метод является расширением линейными преобразованиями метода перестановок, и имеет сложность АЧ, где N = 2” - количество значений функции. Значение N1 является слишком большой величиной, и поэтому применение метода возможно только для функций от небольшого количества переменных (не более 6). Несмотря на то, что были созданы достаточно эффективные алгоритмы для сокращения размера ВЭЭ, они базируются на различных переборах, - осталась открытой проблема построения эвристического логического метода, не базирующегося на различном переборе возможных вариантов. Дело в том, что созданные алгоритмы базируются на методах перестановки и поиска линейных преобразований, но ограничивают их различными способами, чтобы получить сложность алгоритма, приемлемую для вычислений. То есть, например, в качестве ограничения используется перебор не по всем переменным, а только по нескольким соседним и тому подобное. Но ключевым фактором остается перебор. В данной же работе производится поиск критерия, который позволит уменьшить сложность ВЭО путем поиска преобразований над соседними переменными. Это приведет к полиномиальной сложности алгоритма относительно размера таблицы значений функции (2"). Для обеспечения возможности полного перебора всех возможных значений для нахождения характерных случаев неоптимальности, исследования при построении критериев производились на функциях небольшого размера (до 4-х переменных).