.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Master theorem (http://www.dsy.it/forum/showthread.php?threadid=42713)

Master theorem

Qual'è l'enunciato del master theorem??

Un' equazione generatrice del tipo:

T(n) = a T(n/b) + xn^c

può essere asintotica a:
T(n) = Teta(n^c) se a< b^c
T(n) = Teta( n^ c log n ) se a = b^c
T(n) = Teta( n^ log base b di a ) se a > b^c

Ovvero, messa giù in termini umani: visto che l' equazione di ricorrenza sopra rappresenta un generico calcolo del tempo di una procedura dividi et impera, questo valore è asintotico a quale tra la fase di suddivisione del problema ( aT(n/b) ) e la fase di ricostruzione del risultato ( xn^c ) è dominante. L' esempio perfetto è mergesort. Difatti:

T(n) = 2T(n/2) + n-1

n-1 è asintotico ad n, ergo posso vederla come

T(n) = 2T(n/2) + n

Intuitivamente, dividere il problema in due parti uguali ( T(n/2) ) e calcolare le singole parti ha un costo uguale ad n, ovvero la fase di ricostruzione. Ergo la fase di suddivisione e di riunione del problema son di stessa dimensione ergo è il caso centrale, ovvero Teta(n log n ). Ma se vogliamo fare le cose bene:

a= 2 b=2 c=1

ergo 2=2^1 ergo vale Teta(n^1 log n).

La dimostrazione passa per il calcolo della funzione generatrice.

Scusate l'intrusione, ma giusto in merito al Master Theorem: io al tempo me lo ero studiato per i fatti miei, 'a parte' dalle dispense (anche perché non credo sia nemmeno presente ..)

Adesso che ho ripreso in mano il malloppo da ripassare\ristudiare per l'orale non riesco a trovare una corrispondenza di argomenti, e la mia domanda è:
i capitoli sulle equazioni di ricorrenza e sulle funzioni generatrici sono da fare giusto per capire l'analisi della ricorsione e le dimostrazioni dei tre casi del Theorem oppure vengono chiesti 'specificatamente' all'esame ?
GRazie

Non vengono richiesti direttamente all'esame però bisogna sapere risolvere le equazioni di ricorrenza dei tempi di calcolo degli algoritmi principali. A me all'orale aveva messo davanti l'equazione di ricorrenza di Mergesort e mi aveva chiesto di risolverla..Cerca di studiare i casi specifici.. Per quanto riguarda il capitolo sulle funzioni generatrici io non lo avevo fatto!

GRazie per la risposta, era più o meno quello che avevo in mente; anche perché le dimostrazioni dei tempi di calcolo degli algoritmi fondamentali sono abbastanza rigide, se viene implementata la ricorsione c'è anche l'equazione di ricorrenza associata.