Shannon-Lupanov-lause

Shannon-Lupanov-lause määrittää, kuinka monta elementtiä tarvitaan automatin toteuttamiseen tietyllä automaatikantalla[ tuntematon termi ] .

Sanamuoto

1. Jollekin perustalle : , jossa on vakio kannasta riippuen. $\Sigma$ $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ ${\displaystyle C_{\Sigma ))$

2. Kaikille funktioiden murto-osille , joiden arvo on nolla kuin . $\epsilon > 0$ $f$ $L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ $n$

Selitykset

Tässä , jossa maksimi on otettu kaikkiin muuttujien funktioihin $L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)$ $n$ [ selitä ] . Merkki tarkoittaa asymptoottista yhtäläisyyttä: jos . Lauseen toisen lauseen tarkoitus on, että kasvun myötä lähes kaikki funktiot realisoituvat monimutkaisesti lähellä ylärajaa . $\sim$ $a(n)\sim b(n)$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $n$ $L(n)$

Todiste

Todiste on artikkelissa [1] .

Muistiinpanot

↑ Lupanov O. B. Joidenkin ohjausjärjestelmien luokkien synteesistä // Kybernetics-ongelmat, M., Fizmatgiz, 1963, no. 10, s. 63-97.

Kirjallisuus

Kuznetsov O. P., Adelson-Velsky G. M. Diskreetti matematiikka insinöörille. - M .: Energoatomizdat, 1988. - 480 s. — ISBN 5-283-01563-7 .