[ALGORITMI] - Risoluzione equazioni di ricorrenza

[Adva1]

Salve a tutti, sono nuovo di questo forum, colgo l'occasione per farvi i complimenti e salutarvi tutti.

Vorrei proporvi un'esercizio del corso di Algoritmi e strutture dati.

Traccia:

Per un problema sono noti due algoritmi ricorsivi, $A_1$ e $A_2$ le cui complessità temporali sono descritte dalle seguenti equazioni di ricorrenza:

$T_1(n) ={(T_1(n-1) + n^2),( T_1(1) = 1):}$

$T_2(n) ={(16T_2(n/2) + n^3sqrt(n) + nlog^2n),( T_2(1) = 1):}$

Risolvo la prima equazione con il metodo dell'iterazione:

$T_1(n) = T_1(n-1) + n^2 = 2n^2 + T_1(n-2) = ...etc$

dalla quale ricavo

$T_1(n) = i*n^2 + T_1(n-i)$

ora devo porre $n-i = 1$ ovvero $i = n+1$

sostituendo ottengo

$n^3+n^2+T_1(1)$ quindi la complessità asintotica è $T_1(n) = O(n^3)$

ammesso che ho svolto bene la prima equazione, ho grossi problemi con la seconda. Utilizzando sempre il metodo dell'iterazione arrivo a lunghi calcoli che(credo) non mi portano a niente.

A lezione il prof. ha illustrato altri 2 metodi:

1) Metodo della sostituzione: che consiste "nell' indovinare" la soluzione e poi dimostrarla per induzione.
2)Teorema Master:che divide il problema in più sottopreblemi di dimensione più piccola, li risolve ricorsivamente per poi ricombinare le soluzioni

Non riesco ad applicare questi due metodi, potreste indirizzarmi sulla giusta via de seguire?

Vi ringrazio in anticipo, ciao

Emanuele

[apatriarca]

Non ho tempo di mettermi a provare a risolvere il secondo caso, ma c'è un errore nel primo. Infatti,
\[ T_1(n) = n^2 + T_1(n-1) = n^2 + (n-1)^2 + T_1(n-2) = \sum_{k=1}^{n} k^2 = \frac{2\,n^3 + 3\,n^2 + n}{6}. \quad (*) \]
Il risultato è alla fine lo stesso, ma i passaggi intermedi erano tutti sbagliati. Non è infatti vero che \( T_1(n) = i\,n^2 + T_1(n-i) \), la relazione corretta è infatti \( T_1(n) = T_1(n-i) + \sum_{k=n}^{n-i+1} k^2 < T_1(n-i) + i\,n^2. \)

La seconda richiede certamente metodi più avanzati o comunque qualche idea brillante. Per prima cosa, mi pare abbastanza evidente che il termine \( n^{3.5} \) dominerà il termine \(n\,\log^2(n)\).

(*) La successione dei risultati della somma dei quadrati dei primi \(n\) interi consecutivi è abbastanza famosa e prendono il nome di numeri piramidali quadrati e fanno parte dei cosiddetti numeri figurati (insieme ad esempio ai numeri triangolari che sono la somma dei primi \(n\) interi).

[hamming_burst]

per la 1. non ho guardato, il buon apatriarca ha già parlato (interessante la disquisizione sui numeri piramidali quadrati)

per la 2. si potrebbe semplificarsi la vita e notare (come è stato fatto) che $n^3.5$ domina $nlog_{2}^{2](n)$ e calcolarsi una nuova ricorrenza riscritta:

$16T(n/2) + n^3sqrt(n) + nlog^2(n) >= 16T(n/2) + O(n^3sqrt(n))$

e calcolarla con un qualche metodo, ricordandosi le costanti nascoste.
Per trovare una limiazione più stretta (all'originale) l'unico metodo che da qualche speranza pratica è il metodo dell'albero. Anche con l'iterazione si può fare ma è troppo ingarbugliato, con la sostituzione si potrebbe tentare con una complessità trovata tipo con il Master e poi sostituire, di sicuro il metodo più veloce (non lo ho provato).

Visto che avevo un po' di voglia ho fatto qualche calcolo con l'albero (è equivalente all'iterazione).

profondità albero: $log_2(n)$

$n^3sqrt(n) + nlog^2(n) = n^3.5 + nlog^2(n) -> 16*(n^3.5/2^3.5 + n/2log_2^2(n/2)) -> $
$16^2*(n^3.5/(2^3.5)^2 + n/(2^2)log_2^2(n/2^2)) -> ... $
$-> 16^i*(n^3.5/(2^3.5)^i + n/(2^i)log_2^2(n/2^i)) ->$ fino a profondità $log_2(n)-1$

semplificando il passo $i-$esimo:

$16^i*(n^3.5/(2^3.5)^i + n/(2^i)log_2^2(n/2^i)) = 2^(4i)/(2^(3.5i))n^3.5 + 2^(4i)/(2^i)n(log^2(n)-i^2)$

calcoliamo in nodi interni con le sommatorie dei vari livelli:

$sum_{i=0}^{log_2(n)-1}2^(4i)/(2^(3.5i))n^3.5 + 2^(4i)/(2^i)n(log^2(n)-i^2) =$

$sum_{i=0}^{log_2(n)-1}2^(4i)/(2^(3.5i))n^3.5 + sum_{i=0}^{log_2(n)-1}2^(4i)/(2^i)n(log^2(n)-i^2)$

calcoliamo le sommatorie separatamente:
$sum_{i=0}^{log_2(n)-1}2^(4i)/(2^(3.5i))n^3.5 = n^3.5sum_{i=0}^{log_2(n)-1}sqrt(2)^i =$

$n^3.5(sqrt(2)^{log_2(n)-1+1}-1)/(sqrt(2)-1) = n^1.75/(sqrt(2)-1) - n^3.5/(sqrt(2)-1)$
____

$sum_{i=0}^{log_2(n)-1}2^(4i)/(2^i)n(log^2(n)-i^2) = $

$sum_{i=0}^{log_2(n)-1}2^(3i)nlog^2(n) - sum_{i=0}^{log_2(n)-1}2^(3i)ni^2 =$ le calcolo separatamente:

la prima:
$sum_{i=0}^{log_2(n)-1}2^(3i)nlog^2(n) = nlog^2(n)sum_{i=0}^{log_2(n)-1}2^(3i) = $

$n/7log^2(n)(8^log_2(n)-1) = n^4/7log^2(n) - n/7log^2(n)$

la seconda:
$ - sum_{i=0}^{log_2(n)-1}2^(3i)ni^2 = -nsum_{i=0}^{log_2(n)-1}2^(3i)i^2$

si applica il ragionamento che si fa con le serie geometriche e le derivata; ora non riesco a ricordare come ci si comporta quando c'è $i^2$ sarà qualche trasformazione algebrica (apatriarca te lo sai?), comunque il comodo wolframAlpha ci dice che è uguale a:

$-n(1/343 (-72+8^{log_2(n)-1} (72+7(log_2(n)-1) (-16+7(log_2(n)-1)))))=$

$72n/(2744) + 112/2744n^4log_{2}(n) + 7/2744n^4log_{2}^{2}(n) - (63)/(2744)n $

sommando il tutto con il resto delle sommatorie di prima (per essere mega-pignolik si dovrebbe riportare le costante ma non ne ho voglia):

prima: $n^1.75 - n^3.5 +$

seconda parte 1: $n^4log^2(n) - nlog^2(n) +$

seconda parte 2: $n + n^4log_{2}(n) + n^4log_{2}^{2}(n) - n $

dove vediamo che $n^4log_{2}^{2}(n)$ sovrasta tutto il resto percio $in O(n^4log_{2}^{2}(n))$
ora calcoliamo le foglie di questo albero che sono, dove il costo dalla definizione di $T_2(n)$ quando $n=1$ è $O(1)$, perciò:

$16^(log_2(n))*O(1) = n^4*O(1) in O(n^4)$

valutiamo il tutto con i nodi interni e le foglie:

$O(n^4log_{2}^{2}(n)) + O(n^4) in O(n^4log_{2}^{2}(n))$

perciò la complessità di $T_2(n) in O(n^4log_{2}^{2}(n))$.

consiglio: prova a calcolare la versione riscritta e valuta se ci sono differenze asintotiche oppure utilizza questa limitazione e praticalo al metodo della sostituzione per verificarla (penso sia un esercizio interessante).

se hai dubbi chiedi pure

[apatriarca]

Per quanto riguarda la seconda ricorrenza, avrei prima di tutto definito \( f(n) = n^3\,\sqrt{\,n} + n\,\log^2\,n \; \) e riscritto la ricorrenza nella forma \( T\,(n) = 16\,T\,(n/2) + f(n). \; \) In questo modo avrei ottenuto
\[ T\,(n) = \sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{4i} f\bigl(n/2^i\bigr) = \sum_{i=0}^{\lfloor \log \, n \rfloor} \Bigl( 2^{i/2}\,n^{7/2} + 2^{3i} \, n \, (\log \, n - i)^2 \Bigr). \]
Osservo che \( T\,(1) = f(1) = 1 \) per cui posso in effetti fare la somma fino all'ultimo termine. Sfrutto quindi la linearità della sommatoria e inizio a calcolare la serie geometrica seguente:
\[ \sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{i/2} \,n^{7/2} = n^{7/2}\,\frac{1 - \sqrt{2}^{\lfloor \log \, n \rfloor - 1}}{1 - \sqrt{2}} \sim \frac{n^4}{\sqrt{2} - 1}. \]
Passiamo quindi alla seconda parte della sommatoria. Abbiamo che
\[ \sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{3i} \, n \, (\log\,n - i)^2 = n \, \sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{3i} (\log^2\,n - 2i\,\log\,n + i^2). \]
Consideriamo quindi separatamente le 3 sommatorie ottenute per linearità
\[ \begin{align*}
n\,\log^2\,n\,\sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{3i} &= n\,\log^2\,n\,\frac{2^{3(\lfloor \log \, n \rfloor-1)} - 1}{7} \sim \frac{n^4\,\log^2\,n}{7}, \\
- 2\,n\,\log\,n\,\sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{3i}i &= - 2\,n\,\log\,n\,\frac{\bigl(\lfloor \log \, n \rfloor - 2\bigr)2^{3(\lfloor \log \, n \rfloor-1)} - \bigl(\lfloor \log \, n \rfloor - 1\bigr)2^{3(\lfloor \log \, n \rfloor - 2)} + 1}{49} \sim -\frac{2\,n^4\,\log^2\,n}{49}, \\
n \, \sum_{i=0}^{\lfloor \log \, n \rfloor} 2^{3i} i^2 &\sim \frac{n\,(49\,n^3\,\log^2\,n + 9\,n^3 - 9)}{343}.
\end{align*}\]
L'ultima serie non l'ho calcolata a mano (ma ho usato un programma). A quanto pare il risultato di hamming_burst sembra corretto (in quanto ho ottenuto la stessa complessità con un metodo differente). Sono convinto ci debba essere un qualche metodo migliore.

[hamming_burst]

"apatriarca":Sono convinto ci debba essere un qualche metodo migliore.

migliore nel senso di veloce?
per "esattezza" della complessità penso che meglio di quanto è stato fatto non si riesca...
Se si vuole una conferma si va per induzione, ed è questo un metodo veloce.
Il master theorem non può essere applicato con due funzioni libere, si può solo applicare con una riscrittura ed in questo caso nessuno ci vieta di farlo.

Un altro metodo (per rimanere con la funzione originale) potrebbe essere la sostituzione di variabili. Ma ora non mi viene in mente una sostituzione accettabile perchè è la funzione libera il problema non la ricorsione, di solito si utilizza $n=2^k$ ma non ha senso in questa, ma proviamo:

$16T((2^k)/2)+ (2^k)^3sqrt(2^k) + 2^klog^2(2^k) = 16T(2^k/2) + 2^(3)k2^(k/2) + 2^kk = 16T(2^k/2) + 2^(7k/2) + 2^kk=$

al momento non oso continuare.

[apatriarca]

Intendevo dire con meno calcoli, possibilmente anche più semplici. La sostituzione che hai scritto sembra abbastanza utile (sono andato un po' avanti nei calcoli ma non li ho conclusi per cui faccio a meno di scriverli).

[hamming_burst]

rissumendo per \(16T(\frac{n}2) + n^{\frac{7}2} + nlog_{2}^{2}(n)\)

- metodo iterativo (o con albero, che è la stessa tecnica) si trova la limitazione superiore: \(O(n^4log_{2}^{2}(n))\)
- metodo con Master Theorem:

si può vedere in diversi modi ma ci si porta sempre alla stessa complessità:

\(n^{log_2(16)} = n^4\)
\(n^{\frac{7}2} + nlog_{2}^{2}(n) \in O(n^{4-\epsilon})\) con \(\epsilon=\frac{1}2\)

perciò si trova la complessità: \(T(n) \in \Theta(n^{4})\)
In questo metodo si cerca di approssimare l'andamento e vedere cosa accade asintoticamente, non da quasi mai la limitazione algebricamente esatta in ricorrenze particolari. Si può vedere come un metodo che "smussa" cose in eccesso per arrotondare la complessità ad una effettivamente calcolabile in modo veloce.

- metodo della sostituzione (o per tentativi):
si può utilizzare la complessità trovata con il Master e provare a dimostrarla per induzione. Il problema di questa tecnica è l'approccio induttivo su questa particolare equazione, è meglio semplificarla riscrivendola. Come si è visto nell'albero o nell'iterazione $n^(7/2)$ è la funzione dominante rispetto a $nlog^2(n)$ perciò utilizziamo:

\(T'(n) = 16T(\frac{n}2) + O(n^{\frac{7}2})\) per dimostrare che $T'(n) in O(n^4)$. Se si va brutalmente a sostituire non si raggiunge una dimostrazione favorevole (ricordandosi delle costanti nascoste):

\(16c(\frac{n}2)^4 + d(n^{\frac{7}2}) = \frac{16}{16}cn^4 + dn^{\frac{7}2} = cn^4 + dn^{\frac{7}2} \not\leq cn^4\) per nessun $c$ ed $n$.

per dimostrare allora la complessità, bisogna utilizzare una ipotesti induttiva più forte: $T'(n) <= c(n^4 - n^(7/2))$
proviamo:

\(16c*((\frac{n}2)^4 - (\frac{n}2)^{\frac{7}2}) + d*(n^{\frac{7}2}) = cn^4 - \sqrt{2}t*n^{\frac{7}2} + d*n^{\frac{7}2}\)

\(c*n^4 - \sqrt{2}t*n^{\frac{7}2} + d*n^{\frac{7}2} \leq c*n^4 - t*n^{\frac{7}2}\)

\(-\sqrt{2}t*n^{\frac{7}2} + d*n^{\frac{7}2} \leq - t*n^{\frac{7}2}\)

essendo $c,d,t > 0$ la disequazione è vera per:

\(t \geq \frac{d}{\sqrt{2} -1}\) e $n>0$

ci sarebbero i casi base, ma non importa.

perciò (se non ho commesso errori): $T'(n) in O(n^4)$.
Per dimostrare che anche $T_2(n) \in O(n^4)$ la tecnica è simile a quella discussa sopra.

EDIT:
ho corretto alcune cose.
La ricorrenza $T_2(n)$ la si può considerare come la ricorrenza di un algoritmo divede&impera (divide&combina), dove:
- $n^(7/2)$ è la parte divide
- $nlog^2(n)$ è la parte combina
nelle ricorrenze classiche come il merge-sort tale suddivisione non è esplicitata (dove divide $in O(1)$ e combina $in O(n)$) ma solamente viene messa la complessità dominante $\Theta(n)$, come ho proposto io.
Si può notare, anche, che si sono trovate due limitazioni: sono entrambe corrette. Il metodo dell'iterazione e dell'albero danno sempre una limitazione superiore (considerando i diversi ordini di grandezza sottratti nei calcoli), per trovarne di più strette esistono altre tecniche, come quella per sostituzione.