|
Вестник Московского университета. Серия 1: Математика. Механика, 2022, номер 3, страницы 32–40
(Mi vmumm4473)
|
|
|
|
Математика
Уточненные оценки функции Шеннона для сложности схем из функциональных элементов
С. А. Ложкин Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики
Аннотация:
Ранее автором были предложены достаточно общие подходы и методы, позволяющие получать асимптотические оценки высокой и близкой к ней степени точности функций Шеннона для сложности реализации булевых функций в различных классах схем. Большинство полученных с их помощью результатов изложено в целом ряде статей, за исключением только оценок функции Шеннона, близких к оценкам высокой степени точности для сложности схем из функциональных элементов без ограничений на их структуру. В настоящей публикации, восполняющей указанный пробел, излагается модифицированная и упрощенная версия одного из упомянутых выше методов — метода синтеза схем из функциональных элементов, которая тем не менее дает возможность получать оценки требуемого уровня точности.
Ключевые слова:
булевы функции, схемы из функциональных элементов, сложность, асимптотические оценки высокой степени точности.
Поступила в редакцию: 10.02.2022
Образец цитирования:
С. А. Ложкин, “Уточненные оценки функции Шеннона для сложности схем из функциональных элементов”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2022, № 3, 32–40; Moscow University Mathematics Bulletin, 77:3 (2022), 144–153
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm4473 https://www.mathnet.ru/rus/vmumm/y2022/i3/p32
|
|