Теорема Шеннона — Лупанова

Теорема Шеннона — Лупанова определяет число элементов, необходимых для реализации автомата в заданном автоматном базисеШаблон:Термин.

Формулировка

1. Для любого базиса $\mathrm{\Sigma }$: $L_{\mathrm{\Sigma }}(n)\sim C_{\mathrm{\Sigma }}\frac{2^n}{n}$, где $C_{\mathrm{\Sigma }}$ — константа, зависящая от базиса.

2. Для любого $ϵ>0$ доля функций $f$, для которых $L_{\mathrm{\Sigma }}(f)⩽(1-ϵ)C_{\mathrm{\Sigma }}\frac{2^n}{n}$ стремится к нулю с ростом $n$.

Пояснения

Здесь $L_{\mathrm{\Sigma }}(n)=\underset{f\in P(n)}{\max }{L}_{\mathrm{\Sigma }}(f)$, где максимум берется по всем функциям от $n$ переменныхШаблон:Пояснить. Знак $\sim$ обозначает асимптотическое равенство: $a(n)\sim b(n)$, если $\underset{n\to \mathrm{\infty }}{\lim }\frac{a(n)}{b(n)}=1$. Смысл второго утверждения теоремы в том, что с ростом $n$ почти все функции реализуются со сложностью, близкой к верхней границе $L(n)$.

Доказательство

Доказательство есть в статье.

Литература

• Шаблон:Книга