Mayoración

Mayoración

Una función f (de orden 1) mayora a una g (de orden n) si y sólo si:

f(max(x_{1},x_{2}, .. ,x_{n})) \ge g(x_{1},x_{2}, .. ,x_{n})

Notación: f^{(1)} \to g^{(n)}

Contenido

Teoremas referidos a la mayoración

Lemas

Lema (A)

Las funciones recursivas base está mayoradas por f0 Sea X = x1,x2,..,xn

Demostración:

  • f_{0}(x) = s(x) \ge s(x)
  • f_{0}(x) = s(x) \ge 0 = z(x)
  • f_{0}(Max(X)) = s(Max(X)) \ge x_{j} = p^{(n)}_{j}(X)

Lema (B)

Si f_{k} \to I^{(n)} \; y \; f_{k} \to h^{(m)}_{i} \; con \; i \; = \; 1..m (2) entonces f_{k+1} \to \phi\ ( I^{(n)},h^{(m)}_{1}, h^{(m)}_{2}, ... , h^{(m)}_{m})

Demostración:

Si f_{k} \to h^{(m)}_{i} \; con \;i \; = 1..m entonces Max(h_{1}(X),h_{2}(X), .. , h_{n}(X)) \le f_{k}(Max(X))

Entonces, \phi\ ( I,h_{1}, h_{2}, ... , h_{m})(X) = I( h_{1}(X), h_{2}(X), ... , h_{m}(X))

Usando la hipótesis y fk es creciente (2).

f_{k}(Max(h_{1}(X),h_{2}(X), .. , h_{n}(X))) \le f_{k}(f_{k}(Max(X)))

Por definición de función potencia:

f_{k}(f_{k}(Max(X))) = f^2_{k}(Max(X))

Aplicando (4) varias veces ...

f^2_{k}(Max(X)) \le f^{(2+1)}_{k}(Max(X)) \le .. \le f^{(2+Max(X))}_{k}(Max(X))

Por definición:

f^{(2+Max(X))}_{k}(Max(X)) = f_{k+1}(Max(X))

Por lo tanto, f_{k+1} \to \phi\ ( I^{(n)},h^{(m)}_{1}, h^{(m)}_{2}, ... , h^{(m)}_{m})


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Coeficiente de seguridad — El coeficiente de seguridad (también conocido como factor de seguridad) es el cociente entre el valor calculado de la capacidad máxima de un sistema y el valor del requerimiento esperado real a que se verá sometido. Por este motivo es un número… …   Wikipedia Español

  • Hormigón — La técnica del hormigón está muy desarrollada permitiendo soluciones muy complejas. En este puente sobre el río Almonte (España) se ve como progresa la ejecución del primer arco desde las márgenes apoyado en tirantes provisionales faltando de… …   Wikipedia Español

  • Función de Ackermann — En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue …   Wikipedia Español

  • Grafo mediano — El mediano de tres vértices en un grafo mediano. En matemática, y más específicamente en la teoría de grafos, un grafo mediano es un grafo no dirigido en que cualesquiera tres vértices a, b, y c tienen un único mediano. Un mediano es un vértice… …   Wikipedia Español

  • Suma de Minkowski — En geometría, la suma de Minkowski es una operación sobre las partes de un espacio vectorial. A dos partes A y B asocia su conjunto suma, formado por la suma de los elementos de A y B: La suma de dos compactos es compacta, así es posible… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”