Статья в сборнике "Математические вопросы кибернетики" №21, Москва, 2023
Авторы:Ложкин С.А.
Уточненные оценки функции Шеннона для сложности схем из некоторых классов
Аннотация:
Ранее автором были предложены достаточно общие подходы и методы, позволяющие получать асимптотические оценки высокой и близкой к ней степени точности функций Шеннона для сложности реализации булевых функций в различных классах схем. Большинство полученных с их помощью результатов изложено в целом ряде статей, за исключением только оценок высокой степени точности функции Шеннона для сложности схем из функциональных элементов из некоторых классов. В настоящей публикации, восполняющей указанный пробел, излагается модифицированная и упрощённая версия одного из упомянутых выше методов: метода синтеза схем из функциональных элементов в произвольном базисе, который даёт возможность получать верхние оценки их сложности требуемого уровня точности за счёт 'эффективного' использования ветвления выходов у базисных элементов с минимальным приведённым 'весом'.
Ключевые слова:
Булева функция, схемы из функциональных элементов в произвольном базисе, сложность, асимптотические оценки высокой степени точности
