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

Разделы:

Теорема Шеннона — Лупанова определяет число элементов, необходимых для реализации автомата в заданном автоматном базисеa:not(:hover){border-bottom:1px dotted;text-decoration:none}}]]>[неизвестный термин].

Содержание

1 Формулировка
2 Пояснения
3 Доказательство
4 Примечания
5 Литература

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

1. Для любого базиса Σ{displaystyle Sigma }

$Sigma$ : LΣ(n)∼CΣ2nn{displaystyle L_{Sigma }(n)sim C_{Sigma }{frac {2^{n}}{n}}} ${displaystyle L_{Sigma }(n)sim C_{Sigma }{frac {2^{n}}{n}}}$ , где CΣ{displaystyle C_{Sigma }} ${displaystyle C_{Sigma }}$ — константа, зависящая от базиса.

2. Для любого ϵ>0{displaystyle epsilon >0}

$epsilon > 0$ доля функций f{displaystyle f} $f$ , для которых LΣ(f)⩽(1−ϵ)CΣ2nn{displaystyle L_{Sigma }(f)leqslant (1-epsilon )C_{Sigma }{frac {2^{n}}{n}}} ${displaystyle L_{Sigma }(f)leqslant (1-epsilon )C_{Sigma }{frac {2^{n}}{n}}}$ стремится к нулю с ростом n{displaystyle n} $n$ .

Пояснения

Здесь LΣ(n)=maxf∈P(n)LΣ(f){displaystyle L_{Sigma }(n)=max _{fin P(n)}L_{Sigma }(f)}

${displaystyle L_{Sigma }(n)=max _{fin P(n)}L_{Sigma }(f)}$ , где максимум берется по всем функциям от n{displaystyle n} $n$ переменныхa:not(:hover){border-bottom:1px dotted;text-decoration:none}}]]>[прояснить]. Знак ∼{displaystyle sim } $sim$ обозначает асимптотическое равенство: a(n)∼b(n){displaystyle a(n)sim b(n)} ${displaystyle a(n)sim b(n)}$ , если limn→∞a(n)b(n)=1{displaystyle lim _{nto infty }{frac {a(n)}{b(n)}}=1} ${displaystyle lim _{nto infty }{frac {a(n)}{b(n)}}=1}$ . Смысл второго утверждения теоремы в том, что с ростом n{displaystyle n} $n$ почти все функции реализуются со сложностью, близкой к верхней границе L(n){displaystyle L(n)} ${displaystyle L(n)}$ .

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

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

Примечания

↑ Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, М., Физматгиз, 1963, вып. 10, c. 63-97.

Литература

Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — 480 с. — ISBN 5-283-01563-7.