RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2022, номер 3, страницы 32–40 (Mi vmumm4473)

Математика

Уточненные оценки функции Шеннона для сложности схем из функциональных элементов

С. А. Ложкин

Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики

Аннотация: Ранее автором были предложены достаточно общие подходы и методы, позволяющие получать асимптотические оценки высокой и близкой к ней степени точности функций Шеннона для сложности реализации булевых функций в различных классах схем. Большинство полученных с их помощью результатов изложено в целом ряде статей, за исключением только оценок функции Шеннона, близких к оценкам высокой степени точности для сложности схем из функциональных элементов без ограничений на их структуру. В настоящей публикации, восполняющей указанный пробел, излагается модифицированная и упрощенная версия одного из упомянутых выше методов — метода синтеза схем из функциональных элементов, которая тем не менее дает возможность получать оценки требуемого уровня точности.

Ключевые слова: булевы функции, схемы из функциональных элементов, сложность, асимптотические оценки высокой степени точности.

УДК: 519.95

Поступила в редакцию: 10.02.2022


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2022, 77:3, 144–153

Реферативные базы данных:


© МИАН, 2024