Equazione di ricorrenza
[tex]T(n)=4T(n/2)+n^2\log^2(n)[/tex]
Ho pensato di risolverla con il teorema master ma non riesco ad arrivare ad una soluzione, prendo [tex]f(n)=n^2\log^2(n)[/tex] e [tex]n^{\log_b(a)}=n^2[/tex]
Se considero [tex]n^{\log_b(a)+\epsilon}[/tex] oppure [tex]n^{\log_b(a)-\epsilon}[/tex] non trovo una limitazione.....non so.
Ho pensato di risolverla con il teorema master ma non riesco ad arrivare ad una soluzione, prendo [tex]f(n)=n^2\log^2(n)[/tex] e [tex]n^{\log_b(a)}=n^2[/tex]
Se considero [tex]n^{\log_b(a)+\epsilon}[/tex] oppure [tex]n^{\log_b(a)-\epsilon}[/tex] non trovo una limitazione.....non so.
Risposte
Ciao,
ovviamente non puoi dimostrare una limitazione superiore per qualsiasi \(\epsilon>0\) tu scelga \(n^2log^2(n) \notin O(n^{2-\epsilon})\)
Puoi invece provare con una limitazione inferiore prova con \(\epsilon=1\) ricordati che nel master \(0<\epsilon <= 1\)
Ricordati anche le condizione perchè la limitazione inferiore valga nel master...
Se hai dubbi chiedi pure, come esercizio ti consiglio di trovare anche la limitazione superiore con altri metodi
ovviamente non puoi dimostrare una limitazione superiore per qualsiasi \(\epsilon>0\) tu scelga \(n^2log^2(n) \notin O(n^{2-\epsilon})\)
Puoi invece provare con una limitazione inferiore prova con \(\epsilon=1\) ricordati che nel master \(0<\epsilon <= 1\)
Ricordati anche le condizione perchè la limitazione inferiore valga nel master...
Se hai dubbi chiedi pure, come esercizio ti consiglio di trovare anche la limitazione superiore con altri metodi
Ciao ham_burst vecchio amico come te la passi? 
Finalmente ho dato Matematica discreta che mi bloccava questa materia, adesso sto iniziando a studiare seriamente algoritmi.....
Allora si hai ragione non ci avevo pensato, mi quadra, solo una cosa, dovrei verificare la condizione di regolarità, cioè che: [tex]af(n/b)\leq cf(n)[/tex]
Ma non mi torna.....avrei:
[tex]4(\frac{n^2\log^2(n)}{2})\leq c(n^2\log^2(n))[/tex]
Ma non mi risulta verificata per [tex]c<1[/tex]
Finalmente ho dato Matematica discreta che mi bloccava questa materia, adesso sto iniziando a studiare seriamente algoritmi.....Allora si hai ragione non ci avevo pensato, mi quadra, solo una cosa, dovrei verificare la condizione di regolarità, cioè che: [tex]af(n/b)\leq cf(n)[/tex]
Ma non mi torna.....avrei:
[tex]4(\frac{n^2\log^2(n)}{2})\leq c(n^2\log^2(n))[/tex]
Ma non mi risulta verificata per [tex]c<1[/tex]
"Darèios89":
Ciao ham_burst vecchio amico come te la passi?
ciao, vecchio compagno di ricorrenze
Finalmente ho dato Matematica discreta che mi bloccava questa materia, adesso sto iniziando a studiare seriamente algoritmi.....
ottima cosa, così ti concentri solo su un corso, per esperienza personale se si hanno più esami da preparare e non si pianifica bene, non si combina un tupo (magari fossimo multithreading)
dovrei verificare la condizione di regolarità, cioè che: [tex]af(n/b)\leq cf(n)[/tex]
Ma non mi torna.....avrei:
[tex]4(\frac{n^2\log^2(n)}{2})\leq c(n^2\log^2(n))[/tex]
Ma non mi risulta verificata per [tex]c<1[/tex]
si la condizione è quella, ma ieri sera non ho guardato se fosse valida o meno.
E poi con \(\epsilon=1\) si ha un valore non polinomialmente inferiore ad $f(n)$ un errore non da poco, con qualche \(\epsilon\approx 0.\text{pippo}\) se vuoi provare a calcolarlo esattamente, devi utilizzare gli infinitesimi...
Scusa l'ora non ha giovato a dirti cose corrette...
comunque mettiamo che abbiamo trovato un $\epsilon$ valido, per la condizione puoi vederla anche in questo modo equivalente, ma attento che te hai sostituito in modo sbagliato non è \(a*\frac{f(n)}b\) ma \(a*f(\frac{n}b)\) cosa ben diversa...
\( \exists 0\leq c<1,m\geq0 : af(\frac{n}b) = cf(n), \forall n\geq m\)
cioè basta trovare un $c$ che faccia valere la condizione che hai riportato te.
perciò: \(a=4\ ,\ b=2\)
\(4(\frac{n}2)^2\log^2(\frac{n}2) = cn^2log^2(n)\)
\(n^2(log^2(n)-log^2(2)) = n^2(log^2(n)-log^2(2)) = n^2(log^2(n)-1) \)
\(n^2log^2(n)-n^2 \ne cn^2log^2(n)\ \forall m\ \land\not\ \exists c<1\) EDIT: qua mi fai venire un dubbio, sarebbe da provare con qualche caso base, ma ora non posso...
perciò bisogna utilizzare altri metodi $rArr$ metodo dell'albero o secondo me prova con sistituzione con $O(n^3)$
"ham_burst":
\(n^2log^2(n)-n^2 \ne cn^2log^2(n)\ \forall m\ \land\not\ \exists c<1\) EDIT: qua mi fai venire un dubbio, sarebbe da provare con qualche caso base, ma ora non posso...
come detto avevo un dubbio se era vera l'uguaglianza.
Provando con qualche caso base si può scoprire che:
\(n^2log^2(n)-n^2 = cn^2log^2(n)\)
$c = 1 - 1/(log^2(n))$
con $n=3\,\ c~~0.601928$
perciò l'uguaglianza è verificata con $m=3$ ma non è vera $\forall n>=m$ (si fa presto a calcolarlo).
Questo ovviamene perchè essendo $c$ funzione di $n$ non sarà mai vera $\forall n$
In pratica, il Master Theorem non può essere utilizzato con questa equazione, bisogna utilizzare altri metodi (come suggerito sopra)
AH infatti, mi hai tolto un grosso peso di dosso
Come primo passaggio direi che puoi osservare che:
\[T(n) = 4 \, T(n/2) + n^2 \log^2 n = 16 \, T(n/4) + n^2 ( \log^2 (n/2) + \log^2 n) = 64 \, T(n/8) + n^2( \log^2 (n/4) + \log^2 (n/2) + \log^2 n) = \dots \]
Per cui dovrebbe valere il seguente (ci vorrebbe una dimostrazione più rigorosa):
\[ T(n) = n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \sum_{i=0}^{\lfloor \log n \rfloor} \log 2^i \right) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \log 2 \sum_{i=0}^{\lfloor \log n \rfloor} i \right) + C \]
dove \( C \) è una qualche costante. A questo punto dovrebbe essere possibile dimostrare che \( T \in O(n^2 \log^3 n) \) senza troppi problemi. A meno di aver preso un abbaglio ovviamente vista l'ora e la completa mancanza di dimostrazioni..
\[T(n) = 4 \, T(n/2) + n^2 \log^2 n = 16 \, T(n/4) + n^2 ( \log^2 (n/2) + \log^2 n) = 64 \, T(n/8) + n^2( \log^2 (n/4) + \log^2 (n/2) + \log^2 n) = \dots \]
Per cui dovrebbe valere il seguente (ci vorrebbe una dimostrazione più rigorosa):
\[ T(n) = n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \sum_{i=0}^{\lfloor \log n \rfloor} \log 2^i \right) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \log 2 \sum_{i=0}^{\lfloor \log n \rfloor} i \right) + C \]
dove \( C \) è una qualche costante. A questo punto dovrebbe essere possibile dimostrare che \( T \in O(n^2 \log^3 n) \) senza troppi problemi. A meno di aver preso un abbaglio ovviamente vista l'ora e la completa mancanza di dimostrazioni..
"apatriarca":
Come primo passaggio direi che puoi osservare che:
\[T(n) = 4 \, T(n/2) + n^2 \log^2 n = 16 \, T(n/4) + n^2 ( \log^2 (n/2) + \log^2 n) = 64 \, T(n/8) + n^2( \log^2 (n/4) + \log^2 (n/2) + \log^2 n) = \dots \]
Per cui dovrebbe valere il seguente (ci vorrebbe una dimostrazione più rigorosa):
\[ T(n) = n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \sum_{i=0}^{\lfloor \log n \rfloor} \log 2^i \right) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \log 2 \sum_{i=0}^{\lfloor \log n \rfloor} i \right) + C \]
dove \( C \) è una qualche costante. A questo punto dovrebbe essere possibile dimostrare che \( T \in O(n^2 \log^3 n) \) senza troppi problemi. A meno di aver preso un abbaglio ovviamente vista l'ora e la completa mancanza di dimostrazioni..
ho fatto due conti veloci è corretta l'appartenenza $T(n) in O(n^2 \log^3 n)$
ma come mai la Sommatoria la fai arrivare a $\lfloor \log n \rfloor$? non cambia quasi nulla comunque, ma volevo sapere quale è stato il tuo ragionamento, per curiosità di calcolo
Se si vuole essere pignoli, mettendo la base al logaritmo la sommatoria risulta così: $n^2(log_{2}^{3}(n) - log_{2}^{2}(sqrt(n)) - log_{2}(sqrt(n))) + O(n^2)\ in\ O(n^2log_{2}^{3}(n))$
EDIT:
corretto errore sommatoria.
"ham_burst":
ma come mai la Sommatoria la fai arrivare a $\lfloor \log n \rfloor$? non cambia quasi nulla comunque, ma volevo sapere quale è stato il tuo ragionamento, per curiosità di calcolo
Che cosa avresti messo tu? Ho dato per scontato che fosse \(T(n \le 1) = C\) e \( n / 2^{\lceil \log n \rceil} \le 1 \).
Mi sono però accorto di aver sbagliato.. Il seguente passaggio è sbagliato:
\[ n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \sum_{i=0}^{\lfloor \log n \rfloor} \log 2^i \right) + C \]
Il logaritmo nella sommatoria era infatti al quadrato.. Quindi doveva essere:
\[ n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} (\log n - i \log 2)^2 + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - 2 \log 2 \log n \sum_{i=0}^{\lfloor \log n \rfloor} i + \log^2 2 \sum_{i=0}^{\lfloor \log n \rfloor} i^2 \right) + C \]
Ma il risultato dovrebbe comunque essere lo stesso. La sommatoria dei primi \(k\) interi consecutivi è infatti più o meno equivalente a \(k^2\) mentre quella dei primi \(k\) quadrati consecutivi è più o meno equivalente a \(k^3\).
\[ n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - \sum_{i=0}^{\lfloor \log n \rfloor} \log 2^i \right) + C \]
Il logaritmo nella sommatoria era infatti al quadrato.. Quindi doveva essere:
\[ n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} \log^2 (n/2^i) + C = n^2 \sum_{i = 0}^{\lfloor \log n \rfloor} (\log n - i \log 2)^2 + C = n^2 \left( \lfloor \log n + 1 \rfloor \log^2 n - 2 \log 2 \log n \sum_{i=0}^{\lfloor \log n \rfloor} i + \log^2 2 \sum_{i=0}^{\lfloor \log n \rfloor} i^2 \right) + C \]
Ma il risultato dovrebbe comunque essere lo stesso. La sommatoria dei primi \(k\) interi consecutivi è infatti più o meno equivalente a \(k^2\) mentre quella dei primi \(k\) quadrati consecutivi è più o meno equivalente a \(k^3\).
"apatriarca":
[quote="ham_burst"]ma come mai la Sommatoria la fai arrivare a $\lfloor \log n \rfloor$? non cambia quasi nulla comunque, ma volevo sapere quale è stato il tuo ragionamento, per curiosità di calcolo
Che cosa avresti messo tu? Ho dato per scontato che fosse \(T(n \le 1) = C\) e \( n / 2^{\lceil \log n \rceil} \le 1 \).[/quote]
E' corretto ciò che hai fatto te, come detto non cambia il risultato.
Alle volte nelle equazioni di ricorrenza ci sono delle condizioni per alcuni $n$ che te hai sostituito con $C$, sei rimasto generale.
Io per ovviare a ciò di solito (con questa tipologia di equazioni generali) mi fermo a valori di $n=2$ cioè al $log(n)-1$, considerando a parte $n=1|n=0$.
in questo caso:
\(T(n\geq 2) :=\ \sum_{i=0}^{log_2(n)-1} ...\)
\(T(n=1) :=\ 4^{log_2(n)} = n^2\ \in\ O(n^2)\)
è solo una derivazione del metodo algebrico che hai applicato te
Wow.....impressionante, ricorrenza davvero tosta 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo