Shannon-Lupanov tétel

A Shannon-Lupanov tétel meghatározza, hogy egy adott automata alapon hány elem szükséges egy automata megvalósításához[ ismeretlen kifejezés ] .

Megfogalmazás

1. Bármely bázisra : , ahol a bázistól függő konstans. $\Sigma$ $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ ${\displaystyle C_{\Sigma ))$

2. A függvények tetszőleges töredékére , amelyre nullára hajlik, mint . $\epsilon > 0$ $f$ $L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ $n$

Magyarázatok

Itt , ahol a maximum átveszi a változók összes függvényét $L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)$ $n$ [ magyarázza ] . Az előjel az aszimptotikus egyenlőséget jelöli: ha . A tétel második kijelentésének jelentése az, hogy növekedéssel szinte minden függvény a felső korláthoz közeli komplexitással valósul meg . $\sim$ $a(n)\sim b(n)$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $n$ $L(n)$

Bizonyítás

A bizonyíték az [1] cikkben található .

Jegyzetek

↑ Lupanov O. B. A vezérlőrendszerek egyes osztályainak szintéziséről // A kibernetika problémái, M., Fizmatgiz, 1963, 1. sz. 10. o. 63-97.

Irodalom

Kuznetsov O. P., Adelson-Velsky G. M. Diszkrét matematika egy mérnök számára. — M .: Energoatomizdat, 1988. — 480 p. — ISBN 5-283-01563-7 .