Аннотация:
При заданном на $n$-мерном булевом кубе биномиальном распределении вероятностей рассматривается сложность реализации булевых функций неветвящимися программами с условной остановкой. При $n\to\infty$ установлен порядок величины средней сложности почти всех $n$-местных булевых функций.
Ключевые слова:
булевы функции, биномиальное распределение, средняя сложность.
Полный текст:
PDF файл (370 kB)