[Help] Esercizio di Algoritmi e Programmazione Avanzata

[Patryz]

Cdt, ho l'esame giovedì e non ho la più pallida idea di come si faccia questo esercizio, che da un anno a questa parte capita sempre ^^'

Si risolva la seguente equazione alle ricorrenze mediante sviluppo (unfolding):
T(n)=3T(n/2)+n^2 n>=2
T(1)=1

Non ho altre info perchè sugli appunti miei o del prof non c'è nessun accenno...
Vale solo due punti ma non vorrei bruciarmeli a priori, potrebbero servire :sneer:

Grazie..

[Hador]

che minchia è l'unfolding :sneer:

[Patryz]

Sono state le mie stesse parole quando l'ho visto :sneer:

Centra qualcosa con la teoria della ricorsione credo, ma sono al buio totale... Tra le altre cose in sto esame devo fare delle cose stupidissime, implementare algoritmi a mano disegnandoli e cazzate varie, più un programma decisamente bastardo SU CARTA e con la carta carbone per farne due copie, il tutto in 2 ore :shocked:

Se qualcuno ha qualche idea.. google e wikipedia non mi hanno aiutato molto

[Hador]

ma se è da implementare la formuletta si fa così (questo in java), il math.pow è la funzione per fare la potenza in java se devi fare pseudocodice mettici la potenza isi:


public double provaric(double ntmp) {
double n = ntmp;
if (n < 2) {
return 1;
} else
return (3 * provaric(n / 2) + Math.pow(n, 2));

}

[Patryz]

mmm potrebbe esere un'idea, mo provo a fare un po' di passi della ricorsione e vedere dove vado a finire :)

[Axet]

L'unico unfolding che conosco è riferito o alle reti di occorrenze o nelle dynamic bayesian network :O

[Hador]

mmm potrebbe esere un'idea, mo provo a fare un po' di passi della ricorsione e vedere dove vado a finire :)no ma giusto è giusto, non so se devi farci sopra dell'altro o se devi implementarlo in altro modo. (ho modificato solo la condizione base per farlo funzionare col double ma sono dettagli implementativi.)

[Patryz]

Son riuscito a trovarlo sul sito del politecnico di milano con la dicitura equazione alle ricorrenze, ma Dio Santissimo è possibile che ora devo pure andarmi a rivedere le serie per dare un esame di programmazione? -.-

Grazie dell'aiuto, se non ricorrevo non mi veniva in mente di mettere ricorrenze nella ricerca :)

Ps se interessa è questo
(ftp://ftp.elet.polimi.it/users/Luca.Breveglieri/Laurea/Fondamenti%20di%20Informatica%20II/2000-2001/EqRicor.pdf)

[Hador]

capit. Bhe in ogni caso se vuoi verificare il risultato il programmino funziona :sneer:

[Patryz]

Confermo, convertito in C e funziona :D

Peccato non doverlo implementare, sarebbe stato più semplice!
Grazie ancora, torno a studiare, devo ripassare come implementare un algoritmo di dijkstra su un foglio di carta :confused:

[Alkabar]

l'hai poi passato l'esame ?

[San Vegeta]

Io ho letto solo ora, pero' vorrei fare due appunti:

"Si risolva la seguente equazione alle ricorrenze mediante sviluppo (unfolding):"

ricorrenze = ricorsione
unfolding = non mi viene il termine italiano, cmq è l'azione di aprire qualcosa, tipo hai un foglio appallottolato e lo "apri"

Ora, uno fa informatica, e la ricorsione è uno degli strumenti principali di cui dispone.
Dove sta la difficoltà nel risolvere quell'esercizio?

T(n)=3T(n/2)+n^2 n>=2
T(1)=1

Ti sta dicendo che T(n=1) = 1

T(n) = 3T(n/2) + n^2 per qualunque valore di n >= 2

ste cose si facevano alle superiori con i sistemi di equazioni...

[Patryz]

l'hai poi passato l'esame ?

l'esame l'ho dato stamattina, ha pensato bene di cambiare le regole senza dirlo e non si poteva più tenere alcun materiale...
Alla fine la teoria andata (almeno 9/12) e la programmazione pure, chiedeva alla fine di implementare sul momento una pseudo libreria di un b tree 123


Io ho letto solo ora, pero' vorrei fare due appunti:
"Si risolva la seguente equazione alle ricorrenze mediante sviluppo (unfolding):"
ricorrenze = ricorsione
unfolding = non mi viene il termine italiano, cmq è l'azione di aprire qualcosa, tipo hai un foglio appallottolato e lo "apri"
Ora, uno fa informatica, e la ricorsione è uno degli strumenti principali di cui dispone.
Dove sta la difficoltà nel risolvere quell'esercizio?
T(n)=3T(n/2)+n^2 n>=2
T(1)=1
Ti sta dicendo che T(n=1) = 1
T(n) = 3T(n/2) + n^2 per qualunque valore di n >= 2
ste cose si facevano alle superiori con i sistemi di equazioni...

l'esercizio di per se è facile, e implementarne la ricorsione una cagata, il problema è esprimere l'equazione come serie e calcolarne i limiti superiore e inferiore, non lo facevo da analisi 2 e metodi di elaborazione dei segnali, infatti un punticino l'avrò perso li probabilmente :P


ps se mi ammette all'orale offro da bere a tutti voi che avete postato :banana:

[Hador]

Io ho letto solo ora, pero' vorrei fare due appunti:

"Si risolva la seguente equazione alle ricorrenze mediante sviluppo (unfolding):"

ricorrenze = ricorsione
unfolding = non mi viene il termine italiano, cmq è l'azione di aprire qualcosa, tipo hai un foglio appallottolato e lo "apri"

Ora, uno fa informatica, e la ricorsione è uno degli strumenti principali di cui dispone.
Dove sta la difficoltà nel risolvere quell'esercizio?

T(n)=3T(n/2)+n^2 n>=2
T(1)=1

Ti sta dicendo che T(n=1) = 1

T(n) = 3T(n/2) + n^2 per qualunque valore di n >= 2

ste cose si facevano alle superiori con i sistemi di equazioni...come no vege hai capito tutto :sneer:

[San Vegeta]

come no vege hai capito tutto :sneer:

bene, allora se non ho capito, erudiscimi pure :)

[Hador]

bene, allora se non ho capito, erudiscimi pure :)basta legger sopra :sneer:
Ps se interessa è questo (ftp://ftp.elet.polimi.it/users/Luca.Breveglieri/Laurea/Fondamenti%20di%20Informatica%20II/2000-2001/EqRicor.pdf)

[San Vegeta]

eh, e quello che hai fatto non è un programma con una funzione chiamata ricorsivamente?

[Hador]

vegeeee il quoteeeee, il "questo" è un link