Автоматизация задачи определения сложности булевой функции

булевы функции формулы базис Жегалкина меры сложности минимизация декомпозиция синтез функциональные уравнения схемы.

Разработка модели организации процесса патентных исследований на предприятии ракетно-космической отрасли, Вычислительные тесты по декомпозиционному алгоритму для транспортной задачи, ...

УДК 519.714 Автоматизация задачи определения сложности булевой функции А. <...> А.А. Дородницына РАН, Москва, 119991, Россия Основной задачей теории декомпозиции булевых функций являются разработка и исследование методов разложения произвольной булевой функции, зависящей от большого числа переменных, на систему функционально связанных булевых функций, каждая из которых зависит от меньшего числа переменных. <...> С задачей декомпозиции тесно связана задача минимизации булевых функций, т. е. задача о нахождении такого аналитического представления функции, при котором число букв в нем минимально. <...> Разработан метод синтеза булевых формул, предназначенный для эффективного построения схем из функциональных элементов, в том числе и для схем минимальной сложности. <...> Полученный алгоритм может быть реализован с помощью параллельного программирования. <...> В данной работе изучаются задачи минимальной по различным показателям сложности реализации булевых функций (БФ) в базисе Жегалкина (в классах формул или схем из функциональных элементов (ФЭ)), находящие многочисленные приложения в информационной индустрии. <...> Проводимые исследования в области математической кибернетики и дискретной математики показывают, что получение требуемого минимального решения по определенным показателям сложности неизбежно предполагает использование алгоритмов переборного характера. <...> В ряде работ созданы теория локальных алгоритмов оптимизации, алгоритмов вычисления оценок, алгебраическая теория алгоритмов и показано, что можно даже в явном виде строить экстремальные по качеству алгоритмы для решения очень широких классов трудно формализуемых задач, а также разрабатываются математические и прикладные аспекты теории интеллектуальных систем [1, 2]. <...> А.А. Гурченков, Е.К. Егорова необходимость в информационных и вычислительных ресурсах для образования, науки и техники сохраняется. <...> Следовательно, теория алгоритмов и их минимизация <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт