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
Ma per T intendi una successione? Che senso ha allora n/4? Non capisco il problema.
Luca.
Luca.
Per T(n) si intende l'ennesimo elemento della successione
la relazione di ricorrenza per i numeri di Fibonacci ad esempio sarebbe scritta come
T(n) = T(n-1) + T(n-2)
l'elemento ennesimo è dato dala somma dei precedenti 2 {T(n-1), T(n-2)}
la relazione di ricorrenza per i numeri di Fibonacci ad esempio sarebbe scritta come
T(n) = T(n-1) + T(n-2)
l'elemento ennesimo è dato dala somma dei precedenti 2 {T(n-1), T(n-2)}
Do ragione a Luca77.Detto un po' alla buona,una
successione e' un'applicazione di N in R e non
vedo che significato possano avere T(n/4) e T(3n/4),
a meno di non considerare solo valori di n congrui a 0
modulo 4.Se questo fosse possibile, dovrei concludere
che molta acqua e' passata da quando ho lasciato
gli studi universitari.
karl.
successione e' un'applicazione di N in R e non
vedo che significato possano avere T(n/4) e T(3n/4),
a meno di non considerare solo valori di n congrui a 0
modulo 4.Se questo fosse possibile, dovrei concludere
che molta acqua e' passata da quando ho lasciato
gli studi universitari.
karl.
In riferimento alla corretta osservazione di Karl, continuo a non capire il problema.
Luca.
Luca.
Vorrei anch'io fare una domanda a Rael.
Nella mia tesi di laurea trovavo la soluzione ad una equazione differenziale lineare a coefficenti non costanti per mezzo di uno sviluppo in serie in cui la successione non era nota esplicitamente ma per mezzo di una relazione di ricorrenza simile, ma un tantino più complessa, a quelle che hai postato tu. Non mi ricordo più quanto tempo ho inutilmente passato a cercare di trasformare la mia relazione di ricorrenza in una relazione esplicita per il generico termine della successione.
Ora noto che tu hai fatto riferimento ad un certo Master Theorem di cui io non ho mai sentito parlare. Potresti darmi perfavore qualche dellaglio in più?
Grazie e ciao
Nella mia tesi di laurea trovavo la soluzione ad una equazione differenziale lineare a coefficenti non costanti per mezzo di uno sviluppo in serie in cui la successione non era nota esplicitamente ma per mezzo di una relazione di ricorrenza simile, ma un tantino più complessa, a quelle che hai postato tu. Non mi ricordo più quanto tempo ho inutilmente passato a cercare di trasformare la mia relazione di ricorrenza in una relazione esplicita per il generico termine della successione.
Ora noto che tu hai fatto riferimento ad un certo Master Theorem di cui io non ho mai sentito parlare. Potresti darmi perfavore qualche dellaglio in più?
Grazie e ciao
Il Master Theorem è anche noto come il teorema fondamentale delle ricorrenze, e consente di determinare il comportamento asintotico della formula esplicita della relazione di ricorrenza, e si usa nell'analisi degli algoritmi.
il Master theorem consente di evitare la risoluzione delle relazioni di ricorrenza del tipo T(n) = a*T(n/b) + f(n)
Chiarisco la cosa degli indici fratti : supponi di dover analizzare l'andamento di un algoritmo che usi la tecnica "Divide et Impera", suddividendo il problema iniziale, in "a" sottoproblemi più piccoli di dimensione "n/b" e che impieghi un tempo f(n) per ricombinare i risultati.
Es.
la relazione di ricorrenza relativa alla ricerca binaria su un array di n elementi è della forma :
T(n) = T(n/2) + k se n > 1
1 se n = 1
il Master theorem consente di evitare la risoluzione delle relazioni di ricorrenza del tipo T(n) = a*T(n/b) + f(n)
Chiarisco la cosa degli indici fratti : supponi di dover analizzare l'andamento di un algoritmo che usi la tecnica "Divide et Impera", suddividendo il problema iniziale, in "a" sottoproblemi più piccoli di dimensione "n/b" e che impieghi un tempo f(n) per ricombinare i risultati.
Es.
la relazione di ricorrenza relativa alla ricerca binaria su un array di n elementi è della forma :
T(n) = T(n/2) + k se n > 1
1 se n = 1
.
allora, ho capito il tuo problema...
mi ricorda cose fatte all'esame di algoritmi.
in pratica T(n) sta ad indicare il tempo necessario a "risolvere il problema" su n elementi.
T(n) = T(n/4)+ T(3n/4)
vuol dire che per n elementi il tempo necessario è quello necessario per lo stesso problema su n/4 elementi + quello per lo stesso problema su 3n/4 elementi.
il teorema master non credo sia applicabile in questo caso, metodi iterativi mi sembra che non portino a niente, forse ti conviene provare con qualche sostituzione e vedere se funziona.
cmq ti consiglio di dare un'occhiata al testo "introduzione agli algoritmi" di leiserson-cormen-rivest.
sinceramente a 2 anni di distanza non mi ricordo molto di più di quello che ho scritto...
mi ricorda cose fatte all'esame di algoritmi.
in pratica T(n) sta ad indicare il tempo necessario a "risolvere il problema" su n elementi.
T(n) = T(n/4)+ T(3n/4)
vuol dire che per n elementi il tempo necessario è quello necessario per lo stesso problema su n/4 elementi + quello per lo stesso problema su 3n/4 elementi.
il teorema master non credo sia applicabile in questo caso, metodi iterativi mi sembra che non portino a niente, forse ti conviene provare con qualche sostituzione e vedere se funziona.
cmq ti consiglio di dare un'occhiata al testo "introduzione agli algoritmi" di leiserson-cormen-rivest.
sinceramente a 2 anni di distanza non mi ricordo molto di più di quello che ho scritto...
Scusate, ma continuo a non capire: se T e' una successione, e n=5, che senso ha calcolare T(5/4)?
Luca.
Luca.
quote:
Originally posted by Luca77
Scusate, ma continuo a non capire: se T e' una successione, e n=5, che senso ha calcolare T(5/4)?
provo ad avanzare una ipotesi in attesa di conferma o di smentita da parte degli esperti.
se "an" è una successione con "n" appartenente ad "N", nulla ci vieta di definire la successione "bn" che si ottiene sostituendo al posto di "n" una qualunque funzione "f(n)".
Un esempio potrebbe essere il seguente:
an=x^n/n! (con x appartenente ad R)
f(n)=SQRT(n)=n^(1/2)
bn=x^f(n)/GAMMA(f(n)+1)
dove con GAMMA(x) ho indicato la nota funzione analitica interpolatrice del fattoriale.
In tal caso se T(n) è la successione "an" allora T(f(n)) sarebbe la successione "bn".
Ho capito bene oppure ho preso una cantonata?
Affinche' T(f(n)) sia ancora una successione e' necessario che f(n) sia naturale per ogni n; n/4 non e' naturale per ogni n.
Luca.
Luca.
quote:
Originally posted by Luca77
Affinche' T(f(n)) sia ancora una successione e' necessario che f(n) sia naturale per ogni n; n/4 non e' naturale per ogni n.
Si, su questo siamo d'accordo. Tra l'altro io non sono un esperto e forse sto parlando a sproposito. Tuttavia io mi chiedo:
La "bn" che ho definito precedentemente non è ancora una successione? Io credo di si dato che continua ad essere una applicazione tra N e un qualche altro corpo numerico (nel caso in esame sostituisco un numero naturale e la successione mi ritorna un numero reale).
A questo punto, come la vedo io, potrebbe essere solo un problema di definizione. Se "an" e "bn" sono due successioni tali che la seconda deriva dalla prima per la sostituzione di "n" con "f(n)" (se f(n)=n allora bn=an) non potrebbe darsi che si intenda T(n)=an e T(f(n))=bn?
Ripeto che potrei aver frainteso completamente tutta la vicenda. In tal caso mi scuso e taccio.
Ciao
Non capisco, se Rael non spiega meglio il suo problema: per come l'ha formulato nel primo post, T non puo' essere una successione.
Luca.
Luca.
Maverick pare che abbia colto il punto del problema, e anche l'ipotesi di gattomatto, è del tutto plausibile
infatti nulla mi vieta di definire una relazione di ricorrenza come segue :
T(n) = 2*T(sqrt(n)) + Log(n)
Es.
Sia T(n) = 4*T(n/2) + h(n)
pongo n = 2^m tale che T(f(n)) = T(g(m-1))
e definisco una seconda relazione di ricorrenza B(m) = B(g(m)) + ...
nel mio caso :
T(n) = 4*T(2^(m-1)) + h(2^m)
=> B(m) = 4*B(m-1) + h(2^m)
poi procedo a trovare la soluzione, non vedo cosa ci sia di strano negli indici fratti.
infatti nulla mi vieta di definire una relazione di ricorrenza come segue :
T(n) = 2*T(sqrt(n)) + Log(n)
Es.
Sia T(n) = 4*T(n/2) + h(n)
pongo n = 2^m tale che T(f(n)) = T(g(m-1))
e definisco una seconda relazione di ricorrenza B(m) = B(g(m)) + ...
nel mio caso :
T(n) = 4*T(2^(m-1)) + h(2^m)
=> B(m) = 4*B(m-1) + h(2^m)
poi procedo a trovare la soluzione, non vedo cosa ci sia di strano negli indici fratti.
Ascolta, non mi pare difficile: se T agisce su numeri naturali, cosa significa T(n/4)?
La tua relazione di ricorrenza la puoi definire, ma la soluzione non e' una successione.
Luca.
La tua relazione di ricorrenza la puoi definire, ma la soluzione non e' una successione.
Luca.
aspettate aspettate, c'è stato un fraintendimento generale. il problema postato da rael non è una successione vera e propria, ma il calcolo della complessità di un algoritmo che in generale non ha bisogno di essere "troppo preciso". si può arrotondare all'intero precedente o successivo se fa comodo, e di solito è anche uguale se si sggiungono o tolgono costanti.
rael, non è che la soluzione è sempre O(nlogn)?
le l'array fosse scomposto in 2T(n/2) funzionerebbe, così non sono sicuro ma vale la pena provare...
rael, non è che la soluzione è sempre O(nlogn)?
le l'array fosse scomposto in 2T(n/2) funzionerebbe, così non sono sicuro ma vale la pena provare...
Ok, se T non e' una successione, allora chiedo scusa per tutti i miei interventi.
Luca.
Luca.
baboomba come ti è stato detto sul forum non si fanno gare, quando qualcuno ha un problema ognuno cerca di apportare il suo contributo se può e come può. mi sembra che cmq vada lodato l'impegno di tutti a prescindere... e cmq luca77 col quale ce l'hai tanto non è proprio l'ultimo arrivato...
E se Rael avesse subito precisato che non si trattava di
successioni, facendolo invece credere col suo riferimento
alla successione di Fibonacci?
karl
successioni, facendolo invece credere col suo riferimento
alla successione di Fibonacci?
karl
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.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo