Аннотация:
Для монотонных симметрических булевых функций $f_2^n(x_1,\ldots,x_n)=\bigvee \limits_{1\leq i<j\leq n}x_i x_j$ при растущем $n$ установлена асимптотика $L_k^{\&}(f^n_2)\thicksim (k+2)n,$ где $L_k^{\&}(f^n_2)$ — конъюнкторная сложность реализации функции $f^n_2$$k$-самокорректирующимися схемами из функциональных элементов в базисе $B=\{\&,-\}$, вес надежного конъюнктора $\geq k+2$.
Работа выполнена при финансовой поддержке РФФИ (проект № 11-01-00508) и программы фундаментальных исследований ОМН РАН “Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколени” (проект “Задачи оптимального синтеза управляющих систем”).
Образец цитирования:
Т. И. Краснова, “Асимптотика конъюнкторной сложности самокорректирующихся схем для монотонных симметрических функций с порогом $2$”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, № 3, 50–54; Moscow University Mathematics Bulletin, 69:3 (2014), 121–124