Метрический анализ эффективности алгоритмов минимизации частичных функций алгебры логики

• Автор: Карханян, Лева Мартинович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 121 c. : ил

ВВЕДЕНИЕ

ГЛАВА I. ОБЩАЯ ЧАСТЬ. СЛОЖНОСТЬ И ОТНОСИТЕЛЬНАЯ СЛОЖНОСТЬ

Д.Н.Ф. ЧАСТИЧНЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ ... II

§ I. Определения и обозначения

§ 2. Соотношение между параметрами всюду определенных и частичных булевых функций

§ 3. Оценки максимальных значений сложности однозначно определяемых,тупиковых и минимальных д.н.ф

§ 4. Относительная сложность однозначно определяемых

д.н.ф. ....;, ... , .

§ 4.1. Относительная сложность сокращенной

д.н.ф

§ 4.2. Относительная сложность д.н.ф. Квайна . •

§ 4.3. Относительная сложность д.н.ф. суммы
тупиковых
§ 4.4. Относительная сложность д.н.ф., получаемой -алгоритмом
§ 4.5. Относительная сложность д.н.ф. суммы
Iм - минимальных
§ 4.6. Заключение
§ 5. Сравнение сложности тупиковых д.н.ф
ГЛАВА 2. МЕТРИЧЕСКОЕ СРАВНЕНИЕ МИНИМАЛЬНЫХ В РАЗЛИЧНОМ
СМЫСЛЕ Д.Н.Ф.ЧАСТИЧНЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ
§ I. Используемые понятия и вспомогательные
утверждения
§ 2. Сравнение Ь -минимальных и - минимальных
д.н.ф

§ 3. Сравнение 1с -минимальных и ^ - минимальных
д.н.ф
§ 4. Сравнение ^ -минимальных и б - минимальных
д.н.ф
§ 5. Сравнение р* - и минимальных д.н.ф
§ 6. Заключение
ГЛАВА 3. ВОПРОСЫ ЭФФЕКТИВНОСТИ НЕКОТОРЫХ КЛАССОВ
ПРИБЛИЖЕННЫХ АЛГОРИТМОВ МИНИМИЗАЦИИ ЧАСТИЧНЫХ
БУЛЕВЫХ ФУНКЦИЙ
§ I. Об отрицательных эффектах, связанных с исключением несущественных переменных
§ 2. Об эффективности выделения простых импликантов
минимального ранга
ГЛАВА 4. ОБ ОТНОСИТЕЛЬНОЙ ЭФФЕКТИВНОСТИ ГРАДИЕНТНОГО
АЛГОРИТМ МИНИМИЗАЦИИ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИИ
§ I. Определения и обозначения
§ 2. Разброс при замене кратчайшей д.н.ф. на д.н.ф.,
получаемую градиентным алгоритмом
§ 3. Разброс при замене ^ - минимальной д.н.ф
д.н.ф., получаемую градиентным алгоритмом
§ 4. Разброс при замене & - минимальной д.н.ф
д.н.ф., получаемую градиентным алгоритмом
§ 5. Другие алгоритмы типа градиентного
ЗАКЛЮЧЕНИЕ ИЗ
ЛИТЕРАТУРА

Проблеме минимизации функции алгебры логики в классе дизъюнктивных нормальных форм (д.н.ф.) посвящено большое число работ, среди которых широкую известность приобрели работы С.В.Яблонского, Ю.И.Журавлева, ЮЛ.Васильева, В.В.Глаголева, А.А.Сапо-женко и др.
Одной из основных задач минимизации булевых функций является анализ эффективности алгоритмов упрощения функций алгебры логики путем сравнения сложностей д.н.ф., получаемых в результате применения различных алгоритмов.
Исследованию эффективности классов алгоритмов, получающих
- однозначно определяемую д.н.ф. [13, 44] ,
- произвольную тупиковую д.н.ф.,
- минимальную в некотором смысле д.н.ф.
всюду определенной булевой функции посвящен целый ряд работ (обзор по ним см., например, в [I, 39]), в которых для получения оценок разработаны довольно тонкие конструкции. Тем не менее, для многих параметров, характеризующих эффективность применения алгоритмов, не удалось получить окончательных результатов.
В данной работе рассмотрены аналогичные вопросы для множества не всюду определенных (частичных) булевых функций. Для некоторых параметров удается получить окончательные или близкие к окончательным оценки. При этом неполная определенность позволяет существенно упростить конструирование примеров функций, обладающих экстремальными свойствами.
В связи с тем, что известные точные алгоритмы минимизации булевых функций имеют большую трудоемкость (в общем случае она соизмерима с числом тупиковых д.н.ф. минимизируемой функции), в

кает справедливость теоремы 3.
Следствие (из теоремы 3 при $!> = I). При любом справедливо равенство
Если К->°° » то ^и ^^Л'к
2. Разброс при замене & -минимальной д.н.ф. на ^ - минимальную д.н.ф.
Теорема 4. Если К.-> «*=> , то
Доказательство. Рассмотрим функцию К/(К'т »^1 пг, ) . Имеем & СРг)
риг. И ^ СЪз_)- 1:(И_- КЛ-0Г-1Ч)+ .
Нижняя оценка для * (О . Предположим,что £ - '^1 /2-^ » где , 5?Л - целые числа. Пусть
ПГ= К~1-г1[-ЛС~с'<Г£1]-К> где с = 2 + 3*4 */2г . Тогда нетрудно проверить, что ^СРО^Г^.т.в. М^СЮф^у.
При достаточно больших выполняются условия (7),
& ()- ^ ГЛ~С >ГСй У>1>£ 0^)= О и, значит,
у.)? V 00= £ (Та)/6 =рор-
- ^ = р (»-!)“ 2^[Vк,-стс'/2г]Г«/к.-СЛС'1 и
Нижняя оценка для (*), (»О . Выберем и = [-У У1~1 + р - р1 7 Ж = 13 и <1Г~ И'4^3 + 1-»^--'
- [р ГЛ.-1+ . Тогда при достаточно больших К- выполняются условия (7), ^ = *Ь ( И-- ИЛ- 07“- 1 4" £ )
^ t ( [ Р [ ']]“ 1 )*Ър1 ЛГ1+р~1 ]*Р»П' = ^(3>1),