pintu

User info:

Registered: Jul 2010
Posts: 248 (0.05 al dì)
Location: Novara
Corso: informatica
Anno:
Time Online: 2 Days, 0:46:30 [...]
Status: Offline

Post actions:

Qual'è l'enunciato del master theorem??

panzone

User info:

Registered: Sep 2010
Posts: 63 (0.01 al dì)
Location: Vigevano
Corso: Informatica
Anno: 2
Time Online: 16:10:18 [...]
Status: Offline

Post actions:

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.

Seoman

User info:

Registered: Jun 2012
Posts: 15 (0.00 al dì)
Location:
Corso: Informatica
Anno: II
Time Online: 7:43:52 [...]
Status: Offline

Post actions:

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

pintu

User info:

Registered: Jul 2010
Posts: 248 (0.05 al dì)
Location: Novara
Corso: informatica
Anno:
Time Online: 2 Days, 0:46:30 [...]
Status: Offline

Post actions:

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!

Seoman

User info:

Registered: Jun 2012
Posts: 15 (0.00 al dì)
Location:
Corso: Informatica
Anno: II
Time Online: 7:43:52 [...]
Status: Offline

Post actions:

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.