Shannon-Lupanovs sætning

Shannon-Lupanov-sætningen bestemmer antallet af elementer, der kræves for at implementere en automat på en given automatbasis[ ukendt udtryk ] .

Ordlyd

1. For enhver basis : , hvor er en konstant afhængig af basis. $\Sigma$ $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ ${\displaystyle C_{\Sigma ))$

2. For enhver brøkdel af funktioner , som har en tendens til nul som . $\epsilon > 0$ $f$ $L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ $n$

Forklaringer

Her , hvor maksimum overtages alle funktioner af variable $L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)$ $n$ [ forklar ] . Tegnet betegner den asymptotiske lighed: hvis . Betydningen af den anden sætning i sætningen er, at med vækst realiseres næsten alle funktioner med kompleksitet tæt på den øvre grænse . $\sim$ $a(n)\sim b(n)$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $n$ $L(n)$

Bevis

Beviset findes i artiklen [1] .

Noter

↑ Lupanov O. B. Om syntesen af nogle klasser af kontrolsystemer // Problems of Cybernetics, M., Fizmatgiz, 1963, nr. 10, s. 63-97.

Litteratur

Kuznetsov O. P., Adelson-Velsky G. M. Diskret matematik for en ingeniør. — M .: Energoatomizdat, 1988. — 480 s. — ISBN 5-283-01563-7 .