Ricorrenze

[Rael]

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 ?)

[Luca77]

Ma per T intendi una successione? Che senso ha allora n/4? Non capisco il problema.

Luca.

[Rael]

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)}

[karl]

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.

[Luca77]

In riferimento alla corretta osservazione di Karl, continuo a non capire il problema.

Luca.

[gattomatto]

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

[Rael]

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

[xxalenicxx]

.

[Maverick]

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

[Luca77]

Scusate, ma continuo a non capire: se T e' una successione, e n=5, che senso ha calcolare T(5/4)?

Luca.