Matematicamente.it

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.

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ù...

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.

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 ^_^ !

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 ^_^.

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

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

ANDATE A VEDERE IL TEOREMA DI AKRA-BAZZI.

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.