Русская Википедия:Теорема Шеннона — Лупанова

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

Пояснения

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

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

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

Литература

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