Shannon-Lupanovs teorem

Shannon-Lupanovs sats bestämmer antalet element som krävs för att implementera en automat på en given automatbasis[ okänd term ] .

Formulering

1. För varje bas : , där är en konstant beroende på basen. $\Sigma$ $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ ${\displaystyle C_{\Sigma ))$

2. För vilken bråkdel av funktioner som helst , för vilka tenderar att bli noll som . $\epsilon > 0$ $f$ $L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ $n$

Förklaringar

Här , där maximum tas över alla funktioner hos variabler $L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)$ $n$ [ förklara ] . Tecknet betecknar den asymptotiska likheten: om . Innebörden av det andra påståendet i satsen är att med tillväxt realiseras nästan alla funktioner med komplexitet nära den övre gränsen . $\sim$ $a(n)\sim b(n)$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $n$ $L(n)$

Bevis

Beviset finns i artikeln [1] .

Anteckningar

↑ Lupanov O. B. Om syntesen av vissa klasser av styrsystem // Problems of Cybernetics, M., Fizmatgiz, 1963, nr. 10, sid. 63-97.

Litteratur

Kuznetsov O. P., Adelson-Velsky G. M. Diskret matematik för en ingenjör. — M .: Energoatomizdat, 1988. — 480 sid. — ISBN 5-283-01563-7 .