Come si usa il teorema Master per descrivere la ricorsione?

Question

Recentemente ho studiato la ricorsione; come scriverlo, analizzarlo, ecc. Ho pensato per un po 'che ricorrenza e ricorsione fossero la stessa cosa, ma alcuni problemi sui recenti compiti a casa e sui quiz mi fanno pensare che ci siano lievi differenze, che "recidiva" sia il modo di descrivere un programma o una funzione ricorsiva.

Questo è stato tutto molto greco per me fino a poco tempo fa, quando ho capito che c'è qualcosa chiamato "teorema master" usato per scrivere la "ricorrenza" di problemi o programmi. Ho letto la pagina di Wikipedia, ma, come al solito, le cose sono formulate in modo tale che non capisco veramente di cosa stia parlando. Imparo molto meglio con gli esempi.

Così, alcune domande: Diciamo che le venga somministrato questo ripetersi:

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

È questo, infatti, nella forma del teorema? Se è così, a parole, cosa sta dicendo? Se stessimo cercando di scrivere un piccolo programma o un albero di ricorsione basato su questa ricorrenza, come sarebbe? Dovrei semplicemente provare a sostituire i numeri, vedere un pattern, quindi scrivere pseudocodici che potrebbero creare ricorsivamente quel pattern, o, poiché questo potrebbe essere nella forma del teorema master, c'è un approccio matematico più diretto?

Ora, diciamo che è stato chiesto di trovare la ricorrenza, T (n), per il numero di aggiunte eseguite dal programma creato dalla ricorrenza precedente. Posso vedere che il caso base sarebbe probabilmente T (1) = T (2) = 0, ma non sono sicuro di dove andare da lì.

Fondamentalmente, sto chiedendo come passare da una data ricorrenza al codice, e viceversa. Dal momento che questo sembra il teorema principale, mi chiedo se c'è un modo semplice e matematico per farlo.

EDIT: Ok, ho esaminato alcuni dei miei incarichi passati per trovare un altro esempio di dove mi viene chiesto, 'per trovare la ricorrenza', che è la parte di questa domanda che sto avendo il problema del post con.

ricorrenza che descrive nel miglior modo il numero di operazioni di addizione nel seguente frammento di programma (quando chiamato con l == 1 ed r == n)

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

Answer 1

Alcuni anni fa, Mohamad Akra e Louay Bazzi hanno dimostrato un risultato che generalizza il metodo Master - è quasi sempre meglio. Davvero non dovrebbe usare il teorema più ...

Si veda, per esempio, questo documento intitolata: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

Fondamentalmente, ottenere il vostro recidiva a guardare come l'equazione 1 nella carta, pick off i coefficienti, e integrare l'espressione nel Teorema 1.

Answer 2

tuo metodo, scritto in codice utilizzando una funzione ricorsiva, sarebbe simile a questa:

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 
} 

io non sono su re quale "ricorrenza" è, ma una funzione ricorsiva è semplicemente quella che chiama se stessa.

funzioni ricorsive bisogno di una clausola escape (alcuni casi non ricorsiva - per esempio, "se n == 1 ritorno 1") per impedire un errore Stack Overflow (cioè, La funzione viene chiamata così tanto che l'interprete esaurisce la memoria o altre risorse)

Answer 3

Un semplice programma che avrebbe implementare che sarà simile:

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

Si sarebbe anche necessario assicurarsi che l'ingresso non causerà una ricorsione infinita, ad esempio se l'input all'inizio era inferiore a 1. Se questo non è un caso valido, restituire un errore, se è valido, quindi restituire il valore appropriato.

Answer 4

"io non sono esattamente sicuro di cosa è 'recidiva' sia"

la definizione di "recidiva relazione" è una sequenza di numeri ", il cui dominio è un insieme infinito di numeri interi e il cui intervallo è un insieme di numeri reali. " Con la condizione aggiuntiva che la funzione che descrive questa sequenza "definisce un membro della sequenza in termini di una precedente".

E, l'obiettivo di risolverli, penso, è passare da una definizione ricorsiva a una che non lo è. Di 'se hai T (0) = 2 e T (n) = 2 + T (n-1) per tutto n> 0, dovresti passare dall'espressione "T (n) = 2 + T (n -1) "a uno come" 2n + 2 ".

fonti: 1) "Matematica discreta con Teoria dei Grafi - Seconda Edizione", di Edgar G. Goodair e Michael M. Parmenter 2) "Computer Algoritmi C++," di Ellis Horowitz, Sartaj Sahni, e Sanguthevar Rajasekaran.

Answer 5

Zachary:

Diciamo che le venga somministrato questo ricorrenza:

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

E 'questo, infatti, il teorema del master ? Se è così, a parole, cosa sta dicendo ?

Penso che ciò che la vostra relazione di ricorrenza sta dicendo è che per la funzione di "r" con "n" come parametro (che rappresenta il numero totale di set di dati si sta inserendo), tutto ciò si ottiene a all'ennesima la posizione del set di dati è l'uscita della n-1 posizione più due volte qualunque sia il risultato della n-2 ° posizione, senza lavoro non ricorsivo. Quando cerchi di risolvere una relazione di ricorrenza, stai cercando di esprimerla in un modo che non implichi la ricorsione.

Tuttavia, non penso che sia nella forma corretta per il Metodo del Teorema Master. La tua affermazione è una "relazione di ricorrenza lineare di secondo ordine con coefficienti costanti". Apparentemente, secondo il mio vecchio manuale di matematica discreta, questo è il modulo che devi avere per risolvere la relazione di ricorrenza.

Ecco la forma che essi danno:

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

Per 'a' e 'b' sono alcune costanti e f (n) è una funzione di n. Nella tua affermazione, a = 1, b = 2 e f (n) = 0. Ogni volta che f (n) è uguale a zero la relazione di ricorrenza è conosciuta come "omogenea". Quindi la tua espressione è omogenea.

Non penso che sia possibile risolvere una relazione di ricorrenza omogenea usando il Metodo Master Theoerm perché f (n) = 0. Nessuno dei casi per il Teorema del Metodo Master lo consente perché n-to-the-power- di-qualsiasi cosa non può essere uguale a zero. Potrei sbagliarmi, perché non sono davvero un esperto in questo, ma non è che sia possibile risolvere una relazione di ricorrenza omogenea usando il Metodo Master.

io che che il modo per risolvere un relazione di ricorrenza omogenea è di andare da 5 fasi:

1) formano l'equazione caratteristica, che è una sorta di forma di:

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

Se 've ha ottenuto solo 2 casi ricorsivi nella vostra relazione di ricorrenza omogeneo, allora avete solo bisogno di cambiare l'equazione quadratica nella equazione dove

x^2 - a*x - b = 0 

Questo è bec ause una relazione di ricorrenza della forma di

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

può essere riscritta come

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

2) Dopo la relazione di ricorrenza viene riscritta come equazione caratteristica, la prossima trovare le radici (x [1] e x [2]) dell'equazione caratteristica.

3) Con le tue radici, la soluzione sarà ora una delle due forme:

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 

per quando n> 2. 4) Con la nuova forma della soluzione ricorsiva, è possibile utilizzare le condizioni iniziali (r (1) e R (2)) per trovare c [1] e c [2]

Andare in esempio qui di quello che otteniamo:

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

2) Risolvendo per x

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

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

3) Dal momento che x [1]! = x [2], i tuoi soluti su ha la forma:

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

4) Ora, utilizzare le condizioni iniziali per trovare le due costanti c [1] e c [2]:

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

Onestamente, io non sono sicuro di quello che le tue costanti sono in questa situazione, mi sono fermato a questo punto. Immagino che dovresti collegare i numeri fino a quando non avresti in qualche modo ottenuto un valore per c [1] e c [2], che entrambi soddisferebbero queste due espressioni.Uno che o eseguire la riduzione fila su una matrice C dove C è uguale a:

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

Zachary:

ricorrenza che descrive nel miglior modo il numero di operazioni di addizione nel seguente frammento di programma (quando chiamato con l == 1 ed r == n)

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

qui 's i valori di complessità di tempo per il codice data per quando 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)) 

Altrimenti, quando r == l allora T (r) = 2, perché il se-dichiarazione e il ritorno entrambi richiedono 1 step per esecuzione.