Shannon-Lupanovova věta

Shannon-Lupanovův teorém určuje počet prvků potřebných k implementaci automatu v daném automatu.[ neznámý termín ] .

Formulace

1. Pro libovolný základ : , kde je konstanta v závislosti na základu. $\Sigma$ $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ ${\displaystyle C_{\Sigma ))$

2. Pro jakýkoli zlomek funkcí , pro které má tendenci k nule jako . $\epsilon > 0$ $F$ $L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ $n$

Vysvětlivky

Zde , kde je maximum převzato všechny funkce proměnných $L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)$ $n$ [ vysvětlete ] . Znaménko značí asymptotickou rovnost: if . Význam druhého tvrzení věty je ten, že s růstem jsou téměř všechny funkce realizovány se složitostí blízkou horní hranici . $\sim$ $a(n)\sim b(n)$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $n$ $L(n)$

Důkaz

Důkaz je v článku [1] .

Poznámky

↑ Lupanov O. B. K syntéze některých tříd řídicích systémů // Problémy kybernetiky, M., Fizmatgiz, 1963, no. 10, str. 63-97.

Literatura

Kuzněcov O. P., Adelson-Velsky G. M. Diskrétní matematika pro inženýra. — M .: Energoatomizdat, 1988. — 480 s. — ISBN 5-283-01563-7 .