[Algoritmi]Equaz. di ricorrenza,met. iterativo, teor.esperto

[Skeggia1]

Ciao a tutti!
Ho ancora, bisogno del vostro aiuto devo risolvere la seguente relazione di ricorrenza con il metodo iterativo.Purtroppo, riesco ad arrivare sino ad un certo punto poi blocco.

$T(n)=2*T(n-2)+c*n$
Metodo iterativo:
$T(n-2)=2*T(n-4)+c*(n-2)$

$T(n)=2*[2*T(n-4)+c*(n-2)]+c*n=2^2*T(n-4)+2*c*(n-2)+c*n$

$T(n-4)=2*T(n-6)+c*(n-4)$

$T(n)=2^2*[2*T(n-6)+c*(n-4)]+2*c*(n-2)+c*n=2^3*T(n-6)+2^2*c*(n-4)+2*c*(n-2)+c*n$

Proseguendo in questo modo, per $k$ fissato ottengo:

$T(n)=2^k*T(n-2*k)+c*\sum_{j=1}^(k-1) 2^j*(n-2^j)+c*n$

E qui mi fermo, poiché non sono convinto che sia corretto l'utlimo passaggio...voi che dite?

[apatriarca]

Credo che dentro la sommatoria ci debba essere \( 2^j\,(n - 2\,j) \), ma sono un po' di fretta e non ci ho pensato più di tanto..

[hamming_burst]

"apatriarca":Credo che dentro la sommatoria ci debba essere \( 2^j\,(n - 2\,j) \), ma sono un po' di fretta e non ci ho pensato più di tanto..

hai visto giusto.

$sum_{j=0}^{k-1} 2^j(n-2j)$ si vede subito che $k=\lfloor n/2 \rfloor$ perchè l'iterazione si ferma quando $n-2j = 1$.

per il calcolo della sommatoria mi pare si debba passare per la derivazione.

EDIT: ovviamente sarebbe $k=\lfloor n/2 \rfloor - 1$ ma non cambia molto fermarsi in $T(0)$ od $T(1)$ è un caso base che non fa differenza.

[apatriarca]

Faccio solo osservare che il caso \( c\,n = c\,2^0\,\bigl(n - 2\,(0)\bigr) \) e può quindi essere considerato insieme al resto della sommatoria. Discorso simile vale anche per l'altro fattore. Per cui alla fine si ha semplicemente
\[ T(n) = c\,\sum_{j=0}^{\lfloor n/2 \rfloor} 2^j\,(n - 2\,j) = c\,\Bigl( n\,\sum_{j=0}^{\lfloor n/2 \rfloor} 2^j - \sum_{j=0}^{\lfloor n/2 \rfloor} 2^{j+1}\,j \Bigr). \]
La prima è a questo punto una serie geometrica e la seconda si può calcolare come derivata di una serie geometrica (moltiplicate per opportuni valori..).

[Skeggia1]

Ciao e grazie ad entrambi per le risposte.

Praticamente ponendo $k=n/2$ ottengo $T(n)=2^(n/2)*T(n-2*(n/2)) + c* sum_{j=0}^{\lfloor n/2 \rfloor} 2^j*(n - 2*j)$ quindi
$2^(n/2)*T(0) + c* sum_{j=0}^{\lfloor n/2 \rfloor} 2^j*(n - 2*j)$ che corrisponde a

"apatriarca":\[ T(n) = c\,\sum_{j=0}^{\lfloor n/2 \rfloor} 2^j\,(n - 2\,j) = c\,\Bigl( n\,\sum_{j=0}^{\lfloor n/2 \rfloor} 2^j - \sum_{j=0}^{\lfloor n/2 \rfloor} 2^{j+1}\,j \Bigr). \]
La prima è a questo punto una serie geometrica e la seconda si può calcolare come derivata di una serie geometrica (moltiplicate per opportuni valori..).

Mi confermate che i passaggi sono corretti?
Per risolvere la prima, posso applicare il ragionamento fatto in questo esempio?

Mentre per la seconda parli di derivata di una serie geometrica... potresti farmi capire meglio?

Grazie mille e scusate il mio essere tonto

[hamming_burst]

per la prima parte: No, non puoi utilizzare questa approssimazione. Ma gurda che è una semplicissima serie geometrica troncata, basta che utilizzi la formula chiusa:

\[\sum_{j=0}^{\lfloor n/2 \rfloor} 2^j = \frac{2^{\lfloor \frac{n}2 \rfloor +1} - 1}{2-1}\]

per la seconda è un attiamo più macchinoso, ti riporto ad una diussione dove se ne parla: post557366.html#p557366 (nel resto di quel topic mi pare ci fosse un errore di calcolo, leggi solo il post linkato).
Se hai dubbi...

[Skeggia1]

Ok cercherò di capire, anche se non è molto semplice soprattutta la seconda.

Perdonatemi, se ne approfitto ma intanto ho fatto altri esercizi e vorrei avere la conferma da voi che li ho fatti bene. Poiché si tratta di ricavare equazioni di ricorrenza da algorimi e poi risolverle, evito di aprire un nuovo thread.


$T(n)=T(n/2)+Theta(sqrt(n))$
Dovrei risolverla in termini di $Theta$ quindi ho provato con il teorema dell'esperto ma non rientra in nessuno dei 3 casi. è così oppure mi sto sbagliando?


$T(n)=T(n/2)+c$
Con il teorema dell'esperto $T(n)=Theta(n)$


$T(n)=T(n/2)+c*n^3$
Applicando il teorema dell'esperto: $T(n)=O(n^3)$


$T(n)=2T(n/4)+c*sqrt(n)$
Applicando il teorema dell'esperto: $T(n)=O(sqrt(n)*log(n))$


Questa equazione va risolta in termini di $O$.
Su questa equazione ho un dubbio, posso scriverla come segue?
$T(n)=3T(n/4)+T(n/5)+O(n^2)+O(n)+O(log(n))=3T(n/4)+T(n/5)+O(n^2)$ Considero solo il termine additivo maggiore in ordine di grandezza. Se è giusto allora applico il teorema dell'esperto.

Infine, devo risolvere le seguenti equazioni è possibile applicare il teorema dell'esperto?Sareste così gentili da farmi capire come si applica?

$T(n)=T(n-1)+n$
$T(n)=T(sqrt(n))+1$

Spero di essere stato chiaro.
Vi ringrazio per la pazienza e disponibilità.

[Skeggia1]

Nessun riesci ad aiutarmi?Forse ho chiesto troppo?

[hamming_burst]

"Skeggia":Nessun riesci ad aiutarmi?Forse ho chiesto troppo?

un pochetto
vediamone un po' alla volta.

"Skeggia":
Infine, devo risolvere le seguenti equazioni è possibile applicare il teorema dell'esperto?Sareste così gentili da farmi capire come si applica?

$T(n)=T(n-1)+n$
$T(n)=T(sqrt(n))+1$

No. Non puoi applicare il master per alcune ovvie ragioni. Vedi la definizione e scrivi qui perchè secondo te non si può.

$T(n)=T(n-1)+n$

questa applica il metodo iterativo notando la linearità della ricorsione (lo step di sottrazione).

$T(n)=T(sqrt(n))+1$

qui prova ad applicare la sostituzione di variabili.

[hamming_burst]

"Skeggia":

$T(n)=T(n/2)+Theta(sqrt(n))$
Dovrei risolverla in termini di $Theta$ quindi ho provato con il teorema dell'esperto ma non rientra in nessuno dei 3 casi. è così oppure mi sto sbagliando?


$T(n)=T(n/2)+c$
Con il teorema dell'esperto $T(n)=Theta(n)$


$T(n)=T(n/2)+c*n^3$
Applicando il teorema dell'esperto: $T(n)=O(n^3)$
.

Ritenendo che hai calcolato le ricorrenza correttamente (non ho vogla guardare gli algoritmi) in questi casi devi fare queste considerazioni:

Fissiamo prima la definizione del master $aT(n/b) + f(n)\ |\ a>=1\ \wedge\ b > 1$

[*:1jr7ej9e]$T(n)=T(n/2)+Theta(sqrt(n))$
in questo caso:
$a = 1$
$b = 2$
$n^{log_2(1)} = n^0 \in O(1)$
l'unico caso applicabile in un seso lato è il terzo $sqrt(n)\ \in^{?}\ \Omega(n^{0+\epsilon})$ con $\epsilon = 1/2$ valido quando
$\sqrt(n/2) <= c*\sqrt(n)$ per $c>=1/\sqrt(2)$
perciò $T(n) \in \Theta(\sqrt(n))$

[/*:m:1jr7ej9e]
[*:1jr7ej9e]$T(n)=T(n/2)+c$
in questo caso:
$a = 1$
$b = 2$
$n^{log_2(1)} = n^0 \in O(1)$
vale il secondo caso: $c\ \in\ \Theta(1)$
perciò $T(n) \in \Theta(log(n))$ (la Binary Search... dice niente?)

[/*:m:1jr7ej9e]
[*:1jr7ej9e]$T(n)=T(n/2)+c*n^3$
in questo caso:
$a = 1$
$b = 2$
$n^{log_2(1)} = n^0 \in O(1)$
l'unico caso forse applicabile è il terzo $n^3\ \in^{?}\ \Omega(n^{0+\epsilon})$ con $\epsilon=3$, ma $\espsilon$ è definito come piccolo $0 < \epsilon <=1$, perciò il Master non ha senso di essere applicato in questo caso.[/*:m:1jr7ej9e][/list:u:1jr7ej9e]

In tutti e tre i casi siamo hai limiti di applicabilità, ricorda che il Master è uno strumento per avere un'idea immediata sulla complessità di una ricorrenza. Bisogna utilizzare altri strumenti per avere conferme su ciò che il master approssima, perchè è questo che fa.

[Skeggia1]

Ok, grazie mille per esserti prodigato.
Credo che comunque sarebbe stato meglio risolverle con il metodo iterativo...mentre questa qui $T(n)=T(sqrt(n))+1$ ho provato a svolgerla come mi hai suggerito ovvero con il metodo di sostituzione di variabili quindi ho posto $m=log n$ e quindi $T(2^m)=T(2^(m/2))+1$ ponendo poi $S(m)=T(2^m)$ abbiamo $S(m)=S(m/2)+1$ che applicando il metodo iterativo oppure il secondo caso del Master è uguale a $Theta(log n)$ esatto?

Ciao e grazie ancora.

[hamming_burst]

"Skeggia":Ok, grazie mille per esserti prodigato.
Credo che comunque sarebbe stato meglio risolverle con il metodo iterativo...

come detto, puoi utilizzare il master per dare un'idea della complessità, ma poi è meglio utilizzare altre tecniche per raffinare il tutto

mentre questa qui $T(n)=T(sqrt(n))+1$ ho provato a svolgerla come mi hai suggerito ovvero con il metodo di sostituzione di variabili quindi ho posto $m=log n$ e quindi $T(2^m)=T(2^(m/2))+1$ ponendo poi $S(m)=T(2^m)$ abbiamo $S(m)=S(m/2)+1$ che applicando il metodo iterativo oppure il secondo caso del Master è uguale a $Theta(log n)$ esatto?

Nì.
In parte è corretta la sostituzione, dove è una delle poche tecniche che ti semplifica davvero la vita in questi casi.
Ma ti dimentichi di tornare indietro nella sostituzione, tu hai dimostrato che $S(m) \in O(log(m))$ cosa ben diversa di $T(n)$ (la complessità reale non è lontanta cmq)

dai un occhio a questa discussione: ricorrenza-sostituzione-di-variabili-t95080.html e finire nel modo corretto.