[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

Grazie..

[Hador]

che minchia è l'unfolding

[Patryz]

Sono state le mie stesse parole quando l'ho visto

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

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

[Hador]

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

[Patryz]

Confermo, convertito in C e funziona

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

[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

[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

[San Vegeta]

come no vege hai capito tutto

bene, allora se non ho capito, erudiscimi pure