Ricorrenze
Salve a tutti.
Percaso qualcuno ha un idea su come si possa risolvere una relazione di ricorrenza del tipo:
T(n) = T(n/4)+ T(3n/4)
(ora se non ci fosse il secondo termine con 3n/4, non ci sono problemi, metto n = 4^n, e la riporto ad una ricorrenza di primo ordine omogenea, e poi risolvendo l'equazione caratteristica, tiro fuori la soluzione)
è possibile trovare una soluzione generale senza applicare il Master Theorem ? (nè sviluppare iterativamente, nè indovinare, nè tirando fuori sommatorie e funzioni generatrici ?)
e se invece che due termini con relazioni in n comunque simili, ho una roba del tipo T(f(n)) = T(h(n)) + T(g(n)) + ... + f(n)
(dove f(n), g(n), ed h(n) sono funzioni diverse ?)
Percaso qualcuno ha un idea su come si possa risolvere una relazione di ricorrenza del tipo:
T(n) = T(n/4)+ T(3n/4)
(ora se non ci fosse il secondo termine con 3n/4, non ci sono problemi, metto n = 4^n, e la riporto ad una ricorrenza di primo ordine omogenea, e poi risolvendo l'equazione caratteristica, tiro fuori la soluzione)
è possibile trovare una soluzione generale senza applicare il Master Theorem ? (nè sviluppare iterativamente, nè indovinare, nè tirando fuori sommatorie e funzioni generatrici ?)
e se invece che due termini con relazioni in n comunque simili, ho una roba del tipo T(f(n)) = T(h(n)) + T(g(n)) + ... + f(n)
(dove f(n), g(n), ed h(n) sono funzioni diverse ?)
Risposte
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ù...
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.
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 ^_^ !
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.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo