Главная » 2013 » Октябрь » 29 » Скачать Метрический анализ эффективности алгоритмов минимизации частичных функций алгебры логики. Карханян, Лева Мартинович бесплатно
14:21
Скачать Метрический анализ эффективности алгоритмов минимизации частичных функций алгебры логики. Карханян, Лева Мартинович бесплатно
Метрический анализ эффективности алгоритмов минимизации частичных функций алгебры логики
Диссертация
Автор: Карханян, Лева Мартинович
Название: Метрический анализ эффективности алгоритмов минимизации частичных функций алгебры логики
Справка: Карханян, Лева Мартинович. Метрический анализ эффективности алгоритмов минимизации частичных функций алгебры логики : диссертация кандидата физико-математических наук : 01.01.09 Москва, 1984 121 c. : 61 85-1/264
Объем: 121 стр.
Информация: Москва, 1984
Содержание:
ВВЕДЕНИЕ
ГЛАВА I ОБЩАЯ ЧАСТЬ СЛОЖНОСТЬ И ОТНОСИТЕЛЬНАЯ СЛОЖНОСТЬ
ДНФ ЧАСТИЧНЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ II
§ I Определения и обозначения II
§ 2 Соотношение между параметрами всюду оцределенных и частичных булевых функции
§ 3 Оценки максимальных значений сложности однозначно определяемых,тупиковых и минимальных днф
§ 4 Относительная сложность однозначно определяемых днф
§ 41 Относительная сложность сокращенной днф
§ 42 Относительная сложность днф Квайна • •
§ 43 Относительная сложность днф суммы тупиковых
§ 44 Относительная сложность днф, получаемой ^ -алгоритмом
§ 45 Относительная сложность днф суммы
• минимальных
Введение:
Проблеме минимизации функции алгебры логики в классе дизъюнктивных нормальных форм (д.н.ф.) посвящено большое число работ, среди которых широкую известность приобрели работы С.В.Яблонского, Ю.И.Еуравлева, Ю.Л.Васильева, В.В.Глаголева, А.А.Сапо-женко и др.
Одной из основных задач минимизации булевых функций является анализ эффективности алгоритмов упрощения функций алгебры логики путем сравнения сложностей д.н.ф., получаемых в результате применения различных алгоритмов.
Исследованию эффективности классов алгоритмов, получающих
• однозначно определяемую д.н.ф. jjE3, 44] ,
• произвольную тупиковую д.н.ф.,
• минимальную в некотором смысле д.н.ф. всюду определенной булевой функции посвящен целый ряд работ (обзор по ним см., например, в [i, 39]), в которых для получения оценок разработаны довольно тонкие конструкции. Тем не менее, для многих параметров, характеризующих эффективность применения алгоритмов, не удалось получить окончательных результатов.
В данной работе рассмотрены аналогичные вопросы душ множества не всюду определенных (частичных) булевых функций. Для некоторых параметров удается получить окончательные или близкие к окончательным оценки. При этом неполная определенность позволяет существенно упростить конструирование примеров функций, обладающих экстремальными свойствами.
В связи с тем, что известные точные алгоритмы минимизации булевых функций имеют большую трудоемкость (в общем случае она соизмерима с числом тупиковых д.н.ф. минимизируемой функции), в практике получили широкое применение приближенные алгоритмы, которые, как правило, обладают малой трудоемкостью, но результат их работы может отличаться от оптимального. Несмотря на большое число таких алгоритмов, они, в основном, мало исследованы по следующему направлению: на сколько может отличаться по сложности полученная конкретным алгоритмом д.н.ф. от оптимальной. Этот вопрос в данной работе анализируется для следующих классов приближенных алгоритмов минимизации частичных булевых функций:
• алгоритмы, использующие на некотором этапе упрощения, акт удаления несущественных переменных;
• алгоритмы, выделяющие в результирующую д.н.ф. простых имп-ликантов минимального ранга;
• алгоритмы типа градиентного.
Связь между д.н.ф. (соответственно алгоритмами, получающими эти д.н.ф.), свойства и соотношения которых рассмотрены в данной работе, может быть описана схемой (см. рис. I), где выделена однозначная (указаны одной стрелкой) и ветвящаяся части (указаны двумя стрелками) процесса минимизации.
В главе I приводятся основные понятия и определения (§1), используемые в последующих главах. Показано, что значение некоторых параметров, определенных на множестве частичных и всюду определенных булевых функций, совпадают (§2). Исходя из этого факта и результатов, полученных А.П.Викулиным [4] , В.В.Глаголевым [б] и О.Б.Лупановым [зо] , выводятся оценки максимальных значений сложности д.н.ф., однозначно определяемых при минимизации булевых функций, а также оценки минимальной и максимальной сложности тупиковых д.н.ф. (§ 3).
Вопросы относительной сложности некоторых д.н.ф., однозначно определяемых при минимизации всюду определенных булевых функ
§ 4 главы I посвящен исследованию аналогичных вопросов для множества частичных булевых функций. Получены порядок роста относительной сложности сокращенной д.н.ф., д.н.ф. Квайна и д.н.ф. суммы тупиковых. Рассмотрены также вопросы относительной сложности д.н.ф., получаемой А^ -алгоритмом и д.н.ф. суммы минимальных. Оценки установлены для произвольных линейных мер сложности (м.с.).
В [2] Ю.Л.Васильевым рассматривались соотношения между длинами и сложностями тупиковых д.н.ф., реализующих одну и ту же всюду определенную булеву функцию. Было показано, что максимальное значение отношения длин (сложности) двух различных тупиковых д.н.ф. булевой функции равно 2^^ ^ . Аналогичная оценка имеет место при рассмотрении произвольных линейных м.с. [з] . В § 5 главы I эти вопросы получили асимптотически окончательные реше
• 8 ния для множества частичных булевых функций.
Гипотеза о том, что среди кратчайших д.н.ф. функции алгебры логики содержится хотя бы одна минимальная д.н.ф. той же функции, была опровергнута Ю.И.Журавлевым [14] . Вопрос о взаимоотношении между сложностями минимальных и кратчайших д.н.ф. для всюду определенных булевых функций был рассмотрен Лин Син-ляном [29] . К.Вебером [з] была обобщена м.с. для д.н.ф. всюду определенных булевых функций и установлено возможное различие при замене минимальной в некотором смысле д.н.ф. на д.н.ф., минимальную в другом смысле. В главе 2 эти вопросы исследуются для множества частичных булевых функций. Дня всех рассмотренных параметров получены окончательные результаты.
Во многих работах, посвященных минимизации частичных булевых функций, предлагается в качестве одного из этапов проводить исключение несущественных переменных. Такой этап представляется на первый взгляд вполне естественным и целесообразным, особенно, если речь идет о минимизации частичных функций, зависящих от большого числа переменных. В практике часто ставится вопрос о минимизации числа входов схемы. Однако Ю.И.Журавлевым [1б] было отмечено, что уменьшение числа элементов исходной совокупности переменных частичной функции может привести к усложнению д.н.ф. .получаемой в результате. В § I главы 3 этот эффект исследуется с количественной стороны. Именно: решается вопрос о максимальном значении отношения сложностей (длин) двух тупиковых д.н.ф. частичной функции, одна из которых зависит лишь от части переменных второй тупиковой д.н.ф. Показано, что максимальное (на множестве частичных булевых функций от ии переменных) значение отношения сложив И/ — 2* ностей (длин) асимптотически равно 2 (соответственно 2 ).
Итак, исключение фиктивных переменных может приводить к экспоненциальному усложнению результата. Отметим, что здесь исследуется вопрос об эффектах удаления несущественных переменных именно для частичных булевых функций. Для всюду определенных функций удаление или введение фиктивных переменных ничего не дает с точки зрения возможностей упрощения д.н.ф., поскольку сокращенная д.н.ф., а вместе с ней все тупиковые д.н.ф. не содержат несущественных переменных [15].
В этом же параграфе исследуются алгоритмы упрощения частичных булевых функций [б, 8-II, 36, 45] , использующие в качестве элементарных актов операцию исключения несущественных переменных. На примере алгоритма Акерса [45] показано, что использование этой операции приводит к д.н.ф., существенно (экспоненциально) отличающейся от кратчайшей (минимальной).
§ 2 главы 3 посвящен анализу эффективности применения другого класса приближенных алгоритмов упрощения частичных булевых функций, предложенных в работах [l7, 24, 32, Зб]. Общность этих алгоритмов заключается в том, что на некотором этапе в результирующую д.н.ф. включаются такие простые импликанты функции, которые имеют минимальный ранг. Показано, что д.н.ф., получаемые в результате применения этих алгоритмов, могут быть нетупиковыми и иметь экспоненциальную длину (сложность), несмотря на то, что некоторая конъюнкция, входящая в нее, реализует исходную функцию.
Для приближенного решения задачи построения тестов С.В.Яблонским [43] был предложен метод, который обычно называют градиентным или методом наискорейшего спуска. А.А.Сапоженко [37, 38] установил верхнюю оценку сложности д.н.ф., получаемых с помощью градиентного алгоритма для почти всех всюду определенных булевых функций. Из этого результата, в частности, вытекает, что для почти всех всюду определенных булевых функций, градиентным алгоритмом можно получить д.н.ф., отличающуюся по длине (по сложности) от кратчайшей (минимальной) не более, чем в •раз*
Аналогичная оценка для отношения длин д.н.ф., получаемой градиентным алгоритмом к длине вдатчайшей д.н.ф., независимо,выведена Р.Г.Нигматулиным [31].
В главе 4 рассматриваются вопросы эффективности градиентного алгоритма, а также алгоритмов типа градиентного [7, 16, 33, 34, 46] (т.е. алгоритмов, в которые градиентный алгоритм входит как основной этап). Показано, что в результате применения этих алгоритмов к построенным в работе частичным функциям, получается д.н.ф., которая отличается от минимальной в некотором смысле д.н.ф. в полиномиальное (от числа переменных И/ ) число раз. Используя результат, полученный в [3l] , доказано, что возможное значение отношения сложности д.н.ф., получаемой градиентным алгоритмом, к сложности оптимальной д.н.ф. не превышает полинома (от W ).