Ricorrenze

[Rael]

Ok raga, scusate, magari non sono stato particolarmente preciso, ma dal momento che pensavo che l'argomento fosse di comune conoscenza, avevo dato per scontato alcune cose.

Rispondeno a Maverick, Infatti il teorema master non è applicabile, in questo caso, ci sono due termini con indice fratto (fosse 1 ok), Ed ahimè la soluzione della ricorrenza inizialmente postata non è O(xLog(x)), si aggira circa intorno a x forse, o x alla qualcosa di molto prossimo ad 1, in ogni modo davvero non esiste un modo per tirare fuori una soluzione precisa ?
Per gli algoritmi divide et impera semplici del tipo aT(n/b) + f(n) è possibile tirare fuori la soluzione esplicita, senza approssimazioni, mi kiedevo soltanto se fosse possibile fare altrettanto con relazioni di ricorrenza più complesse.

[Maverick]

rael devi scusarli, sono dei matematici puri, non degli ingegneri. per fortuna ora ci siamo noi ing matematici... [;)]

mi sono ripreso in mano il libro sul quale ho studiato. nelle 20 pagine che dedica all'argomento dice sostanzialmente che dove non è applicabile il teorema master o tiri a indovinare e poi dimostri per induzione, oppure fai qualcosa con gli alberi di ricorsione (metodo iterativo).

penso che un metodo generale non ci sia. purtroppo non ti so aiutare di più...

[Anto]

Scusa Maverick, a quale libro ti riferisci? Anch'io devo preparare l'esame di Algoritmi e non sono riuscito a trovare dei testi in merito. Le poche cose che si trovano sono o vecchi appunti di altri studenti o dei testi troppo approfonditi.
Ciò rende l'esame alquanto complicato per chi è quasi un autodidatta come me ....

Ciao e grazie.

[Rael]

Daccordo .. mi sa che dovrò cercare altrove.


P.s.
Strano che dei "matematici puri" non abbiano mai visto una relazione di ricorrenza (che è argomento di matematica discreta) ^_^
dai raga scherzo, evidentemente è un argomento troppo specifico ^_^
Grazie cmq di tutto, a tutti ^_^ !

[Rael]

Maverick, però le ricorrenze non lineari, è possibile risolverle (alcune) in modo analitico, come anche tutte le ricorrenze lineari omogenee(e non), senza usare il teorema master, nè tirando ad indovinare. Il punto è che le ricorrenze con indici un po' "particolari" sembrano essere un argomento troppo "matematico" per gli informatici, e troppo "informatico e poco preciso" per i matematici ... ergo nessuna delle due "parti" sa rispondere ^_^.

[BABOOMBA]

Karl non farci caso, agli ingegneri basta applicare la regola e si sentono arrivati nella vita, contenti loro.

[Maverick]

per anto: "introduzione agli algoritmi" di leiserson-cormen-rivest della Jackson libri. è la traduzione italiana del testo "introduction to algorithms"

[xxalenicxx]

ANDATE A VEDERE IL TEOREMA DI AKRA-BAZZI.

[kewl]

Salve,
la relazione di ricorrenza T(n) = T(n/4)+ T(3n/4) e' una relazione del tipo:
T(n)<= c*n + T(a*n) + T(b*n) con a + b < 1 ed ha come soluzione T(n) <= c/(1 - a - b) * n

Infatti disegnando l'albero delle chiamate ricorsive e riportanfdo le dimensioni dei problemi di ogni chiamata ricorsiva si ha che al primo livello (a + b)n, al secondo (a + b)^2 * n e cosi via. Quindi:
T(n) <= c*n(1 + (a + b) + (a + b)^2 + (a + b)^3 + ... <= c*n Somatoria(a + b)^i con i che va da 0 a infinito ha come soluzione c/(1 - a - b) * n.

Lorenzo.