¿Cómo uso el teorema maestro para describir la recursión?

Question

Recientemente he estado estudiando recursividad; cómo escribirlo, analizarlo, etc. He pensado por un tiempo que la recurrencia y la recursividad eran la misma cosa, pero algunos problemas en tareas y cuestionarios recientes me hacen pensar que hay pequeñas diferencias, que la 'recurrencia' es la forma de describir un programa recursivo o función.

Todo esto ha sido muy griego para mí hasta hace poco, cuando me di cuenta de que hay algo llamado 'teorema maestro' utilizado para escribir la 'recurrencia' de problemas o programas. He estado leyendo la página de wikipedia, pero, como de costumbre, las cosas están redactadas de tal manera que realmente no entiendo de qué está hablando. Aprendo mucho mejor con ejemplos.

Así, algunas preguntas: digamos que se le da esta recurrencia:

r (n) = 2 * r (n-2) + r (n-1);
r (1) = r (2) = 1

es esto, de hecho, en la forma del teorema maestro? Si es así, en palabras, ¿qué está diciendo? Si estuvieras tratando de escribir un pequeño programa o un árbol de recursión basado en esta recurrencia, ¿qué aspecto tendría? ¿Debería simplemente intentar sustituir números, ver un patrón, luego escribir un seudocódigo que pudiera crear recursivamente ese patrón o, dado que esto puede ser en la forma del teorema maestro, hay un enfoque matemático más directo?

Ahora, digamos que se le pidió que encuentre la recurrencia, T (n), para la cantidad de adiciones realizadas por el programa creado a partir de la repetición anterior. Puedo ver que el caso base probablemente sería T (1) = T (2) = 0, pero no estoy seguro de a dónde ir desde allí.

Básicamente, estoy preguntando cómo pasar de una recurrencia dada a un código, y todo lo contrario. Dado que esto se parece al teorema maestro, me pregunto si existe una forma directa y matemática de hacerlo.

EDITAR: Bien, he revisado algunas de mis tareas anteriores para encontrar otro ejemplo de dónde me preguntan, 'para encontrar la repetición', que es la parte de esta pregunta que estoy teniendo la publicación de problemas con.

recurrencia que describe de la mejor manera el número de operaciones de adición en el siguiente fragmento de programa (Cuando se llama con l == 1 y r == n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

Answer 1

Hace unos años, Mohamad Akra y Louay Bazzi resultaron ser un resultado que generaliza el método Master, casi siempre es mejor. Realmente no se debe utilizar el Teorema Maestro nunca más ...

Véase, por ejemplo, esta valoración crítica: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

Básicamente, obtener su recurrencia se vea como la ecuación 1 en el papel, escoger de los coeficientes, e integrar la expresión en el Teorema 1.

Answer 2

Su método, escrito en código utilizando una función recursiva, se vería así:

function r(int n) 
{ 
    if (n == 2) return 1; 
    if (n == 1) return 1; 
    return 2 * r(n-2) + r(n-1); // I guess we're assuming n > 2 
} 

no estoy Do re lo que es "recurrencia", pero una función recursiva es simplemente una que se llama a sí misma.

funciones recursivas necesitan una cláusula de escape (algunos caso no recursivo - por ejemplo, "si n == 1 retorno 1") para evitar un desbordamiento de pila error (es decir,, La función se llama tanto que el intérprete se queda sin memoria u otros recursos)

Answer 3

Un programa sencillo que implementaría que se vería así:

public int r(int input) { 
    if (input == 1 || input == 2) { 
     return 1; 
    } else { 
     return 2 * r(input - 2) + r(input -1) 
    } 
} 

También habría que asegurarse de que la entrada no va a causar una recursión infinita, por ejemplo, si la entrada al principio fue menor que 1. Si este no es un caso válido, devuelva un error, si es válido, luego devuelva el valor apropiado.

Answer 4

"no estoy exactamente seguro de lo que es 'recurrencia' o bien"

la definición de una "relación de recurrencia" es una secuencia de números ", cuyo dominio es un conjunto infinito de enteros y cuyo rango es un conjunto de números reales ". Con la condición adicional de que la función que describe esta secuencia "define un miembro de la secuencia en términos de uno anterior".

Y, el objetivo detrás de resolverlos, creo, es ir de una definición recursiva a una que no lo es. Digamos que si tuvieras T (0) = 2 y T (n) = 2 + T (n-1) para todo n> 0, tendrías que pasar de la expresión "T (n) = 2 + T (n) -1) "a uno como" 2n + 2 ".

fuentes: 1) "Matemática Discreta con la teoría de grafos - Segunda Edición", de Edgar G. Goodair y Michael M. Parmenter 2) "Equipo Algoritmos C++," por Ellis Horowitz, Sartaj Sahni y Sanguthevar Rajasekaran.

Answer 5

Zachary:

Digamos que le administren el recurrencia:

r (n) = 2 * r (n-2) + r (n-1); r (1) = r (2) = 1

¿Es esto, de hecho, en la forma del teorema maestro ? Si es así, en palabras, ¿qué dice ?

Creo que lo que su relación de recurrencia está diciendo es que para la función de "r" con "n" como parámetro (que representa el número total de conjuntos de datos que está introduciendo), lo que podemos encontrar en la enésima la posición del conjunto de datos es la salida de la posición n-1 más dos veces lo que sea el resultado de la posición n-2, sin que se realice ningún trabajo no recursivo. Cuando intentas resolver una relación de recurrencia, estás tratando de expresarla de una manera que no implique recurrencia.

Sin embargo, no creo que esté en la forma correcta para el Método del Teorema Maestro. Su declaración es una "relación de recurrencia lineal de segundo orden con coeficientes constantes". Aparentemente, según mi antiguo libro de texto Discrete Math, esa es la forma que necesitas para resolver la relación de recurrencia.

Así es la forma que dan:

r(n) = a*r(n-1) + b*r(n-2) + f(n) 

Para 'a' y 'b' son algunas constantes y f (n) es una función de n. En su estado de cuenta, a = 1, b = 2, y f (n) = 0. Siempre, f (n) es igual a cero la relación de recurrencia se conoce como "homogénea". Entonces, tu expresión es homogénea.

No creo que pueda resolver una relación de recurrencia homogénea usando el método maestro Theoerm porque f (n) = 0. Ninguno de los casos para el teorema del método maestro lo permite porque n-to-the-power- de-cualquier cosa no puede ser igual a cero. Podría estar equivocado, porque no soy realmente un experto en esto, pero no es posible resolver una relación de recurrencia homogénea utilizando el Método Maestro.

I que que la manera de resolver una relación de recurrencia homogénea es ir en 5 pasos:

1) forman la ecuación característica, que es algo así como la forma de:

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0 

Si 've solo recibió 2 instancias recursivas en su relación de recurrencia homogénea, después, sólo necesita cambiar su ecuación en la ecuación cuadrática, donde

x^2 - a*x - b = 0 

Ésta es bec ause una relación de recurrencia de la forma de

r(n) = a*r(n-1) + b*r(n-2) 

se puede reescribir como

r(n) - a*r(n-1) - b*r(n-2) = 0 

2) Después de que su relación de recurrencia se reescribe como una ecuación característica, junto encontrar las raíces (x [1] yx [2]) de la ecuación característica.

3) Con sus raíces, su solución será ahora una de las dos formas:

if x[1]!=x[2] 
    c[1]*x[1]^n + c[2]*x[2]^n 
else 
    c[1]*x[1]^n + n*c[2]*x[2]^n 

para cuando n> 2. 4) Con la nueva forma de su solución recursiva, se utiliza el condiciones iniciales (r (1) y R (2)) para encontrar c [1] y C [2]

Ir con tu ejemplo aquí está lo que obtenemos:

1) r (n) = 1 * r (n-1) + 2 * r (n-2) => x^2 - x - 2 = 0

2) Resolviendo para x

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1) 

    x[1] = ((-1 + 3)/2) = 1 
    x[2] = ((-1 - 3)/2) = -2 

3) Desde x [1]! = X [2], su soluti el tiene la forma:

c[1](x[1])^n + c[2](x[2])^n 

4) Ahora, utilice su condiciones iniciales para encontrar las dos constantes c [1] y C [2]:

c[1](1)^1 + c[2](-2)^1 = 1 
c[1](1)^2 + c[2](-2)^2 = 1 

Honestamente, no estoy seguro de lo sus constantes están en esta situación, me detuve en este punto. Supongo que tendrías que conectar los números hasta que de alguna manera obtuvieras un valor para c [1] yc [2], que satisfaga esas dos expresiones.Cualquiera que o realizar la reducción fila en una matriz C, donde C es igual a:

[ 1 1 | 1 ] 
[ 1 2 | 1 ] 

Zachary:

recurrencia que describe de la mejor manera el número de operaciones de adición en el siguiente fragmento de programa (cuando se llama con l == 1 y r == n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

Aquí 's los valores de complejidad de tiempo para su código dado para cuando r> l:

int example(A, int l, int r) {  => T(r) = 0 
    if (l == r)    => T(r) = 1 
    return 2;    => T(r) = 1 
    return (A[l] + example(A, l+1, r); => T(r) = 1 + T(r-(l+1)) 
} 

Total:      T(r) = 3 + T(r-(l+1)) 

lo demás, cuando r == l entonces T (r) = 2, ya que la sentencia if y el retorno ambos requieren 1 paso por ejecución.