Teorema Shannon-Lupanov

Teorema Shannon-Lupanov determină numărul de elemente necesare implementării unui automat într-o bază de automată dată.[ termen necunoscut ] .

Formulare

1. Pentru orice bază : , unde este o constantă în funcție de bază. $\Sigma$ $L_{\Sigma}(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ $C_{\Sigma }$

2. Pentru orice fracție de funcții , pentru care tinde spre zero ca . $\epsilon > 0$ $f$ $L_{\Sigma}(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ $n$

Explicații

Aici , unde maximul este preluat peste toate funcțiile variabilelor $L_{\Sigma}(n)=\max _{f\in P(n)}L_{\Sigma}(f)$ $n$ [ explica ] . Semnul denotă egalitatea asimptotică: dacă . Sensul celei de-a doua afirmații a teoremei este că, odată cu creșterea, aproape toate funcțiile sunt realizate cu o complexitate apropiată de limita superioară . $\sim$ $a(n)\sim b(n)$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $n$ $L(n)$

Dovada

Dovada este în articolul [1] .

Note

↑ Lupanov O. B. Despre sinteza unor clase de sisteme de control // Probleme de cibernetică, M., Fizmatgiz, 1963, nr. 10, p. 63-97.

Literatură

Kuznetsov O. P., Adelson-Velsky G. M. Matematică discretă pentru un inginer. — M .: Energoatomizdat, 1988. — 480 p. — ISBN 5-283-01563-7 .