Teorema de Shannon-Lupanov

El teorema de Shannon-Lupanov determina el número de elementos necesarios para implementar un autómata en una base de autómata dada[ término desconocido ] .

Redacción

1. Para cualquier base : , donde es una constante que depende de la base. $\Sigma$ $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$ ${\ Displaystyle C_ {\ Sigma}}$

2. Para cualquier fracción de funciones , que tiende a cero cuando . $\epsilon > 0$ $F$ $L_{\Sigma }(f)\leqslant (1-\epsilon)C_{\Sigma }{\frac {2^{n}}{n}}$ $norte$

Explicaciones

Aquí , donde se toma el máximo sobre todas las funciones de variables $L_{\Sigma }(n)=\max_{f\in P(n)}L_{\Sigma }(f)$ $norte$ [ explicar ] . El signo denota la igualdad asintótica: si . El significado de la segunda declaración del teorema es que con el crecimiento, casi todas las funciones se realizan con una complejidad cercana al límite superior . $\sim$ ${\ estilo de visualización a (n) \ sim b (n)}$ $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$ $norte$ ${\ estilo de visualización L (n)}$

Prueba

La prueba está en el artículo [1] .

Notas

↑ Lupanov O. B. Sobre la síntesis de algunas clases de sistemas de control // Problemas de cibernética, M., Fizmatgiz, 1963, no. 10, pág. 63-97.

Literatura

Kuznetsov O. P., Adelson-Velsky G. M. Matemáticas discretas para un ingeniero. — M .: Energoatomizdat, 1988. — 480 p. — ISBN 5-283-01563-7 .