Ricorrenze e domande
Ho un paio di domande, ho provato a risolvere questa ricorrenza:
[tex]T(n)=4T(n/5)+T(n/6)+n[/tex]
Ho pensato di provare per induzione che [tex]T(n)\leq cn[/tex]
Non so fare le dimostrazioni per induzione, vedendo gli appunti ci ho provato ma non sono convinto affatto.
Ho considerato [tex]n=(k/5)[/tex]
[tex]T(k/5)= ck/5[/tex]
Per n=k/6 [tex]T(k/6)=ck/6[/tex]
La ricorrenza è [tex]T(k)=4T(k/5)+T(k/6)+k[/tex] e diventa:
[tex]T(k)\leq 4ck/5+ck/6+k[/tex]
E continuando trovo [tex]T(k)\leq k(1+29c)[/tex]
E' scorretta? Si può concludere vera per ogni c>1?
In un' altra ricorrenza:
[tex]T(n)=T(n-1)+T(n-2)+n[/tex]
Ho provato a rappresentarla con l' albero di ricorsione e ottengo come costi:
n
2n-3
4n-12
.
.
.
Solo che per scriverla formalmente avrei [tex]2^in...[/tex] e non riesco a capire come rappresentare il secondo termine che non è una potenza di 2 ma un multiplo....
[tex]T(n)=4T(n/5)+T(n/6)+n[/tex]
Ho pensato di provare per induzione che [tex]T(n)\leq cn[/tex]
Non so fare le dimostrazioni per induzione, vedendo gli appunti ci ho provato ma non sono convinto affatto.
Ho considerato [tex]n=(k/5)[/tex]
[tex]T(k/5)= ck/5[/tex]
Per n=k/6 [tex]T(k/6)=ck/6[/tex]
La ricorrenza è [tex]T(k)=4T(k/5)+T(k/6)+k[/tex] e diventa:
[tex]T(k)\leq 4ck/5+ck/6+k[/tex]
E continuando trovo [tex]T(k)\leq k(1+29c)[/tex]
E' scorretta? Si può concludere vera per ogni c>1?
In un' altra ricorrenza:
[tex]T(n)=T(n-1)+T(n-2)+n[/tex]
Ho provato a rappresentarla con l' albero di ricorsione e ottengo come costi:
n
2n-3
4n-12
.
.
.
Solo che per scriverla formalmente avrei [tex]2^in...[/tex] e non riesco a capire come rappresentare il secondo termine che non è una potenza di 2 ma un multiplo....
Risposte
ben ritrovato Darèios89 
ok, ipotizzi che $T(n) in O(n)$ e lo vuoi dimostare.
eh? perchè queste strane sostituzione con un parametro $k$, che non cambia da $n$ (perchè è una lettera) ma non ne vedo il motivio.
sai cosa è una dimostrazione per induzione?
prima cosa devi far valere un "caso base", nel tuo post non ce ne è tracia,
poi passi a considerare i parametri di ricorsione $T(n/5)$ e $T(n/6)$ separatamente, e pechè mai? te ipoizzi che la ricorrenza ha limitazione di $O(n)$ che è tutta, non solo una parte. Perchè $T(k) <= 4ck/5+ck/6+k $ qua stai dicendo che vuoi dimostrare che $4ck/5+ck/6+k in O(4k/5+k/6+k)$
Poi secondo me è qualcosa di più alto di $O(n)$...
consiglio ($n$-esimo) in post passati più volte ti ho mostrato come si tratta una dimostrazione per induzione con le "equazioni di ricorrenza" prova a rivederle. Poi ne riparliamo...
sbagliato... ti ricordi come trattare queste equazioni con il "metodo dell'albero"?
stesso problema di questo. Non c'è UN solo ramo di ricorsione ma DUE. Rivedi il problema che pone il tutto.
Se non vuoi incorrere in questi dubbi, utilizza l'induzione (metodo per tentativi), appena ne avrai carpito la potenza del metodo...
[tex]T(n)=4T(n/5)+T(n/6)+n[/tex]
Ho pensato di provare per induzione che [tex]T(n)\leq cn[/tex]
ok, ipotizzi che $T(n) in O(n)$ e lo vuoi dimostare.
Ho considerato [tex]n=(k/5)[/tex]
[tex]T(k/5)= ck/5[/tex]
Per n=k/6 [tex]T(k/6)=ck/6[/tex]
La ricorrenza è [tex]T(k)=4T(k/5)+T(k/6)+k[/tex] e diventa:
[tex]T(k)\leq 4ck/5+ck/6+k[/tex]
E continuando trovo [tex]T(k)\leq k(1+29c)[/tex]
E' scorretta? Si può concludere vera per ogni c>1?
eh? perchè queste strane sostituzione con un parametro $k$, che non cambia da $n$ (perchè è una lettera) ma non ne vedo il motivio.
sai cosa è una dimostrazione per induzione?
prima cosa devi far valere un "caso base", nel tuo post non ce ne è tracia,
poi passi a considerare i parametri di ricorsione $T(n/5)$ e $T(n/6)$ separatamente, e pechè mai? te ipoizzi che la ricorrenza ha limitazione di $O(n)$ che è tutta, non solo una parte. Perchè $T(k) <= 4ck/5+ck/6+k $ qua stai dicendo che vuoi dimostrare che $4ck/5+ck/6+k in O(4k/5+k/6+k)$
Poi secondo me è qualcosa di più alto di $O(n)$...
consiglio ($n$-esimo) in post passati più volte ti ho mostrato come si tratta una dimostrazione per induzione con le "equazioni di ricorrenza" prova a rivederle. Poi ne riparliamo...
In un' altra ricorrenza:
[tex]T(n)=T(n-1)+T(n-2)+n[/tex]
Ho provato a rappresentarla con l' albero di ricorsione e ottengo come costi:
n
2n-3
4n-12
.
.
.
sbagliato... ti ricordi come trattare queste equazioni con il "metodo dell'albero"?
stesso problema di questo. Non c'è UN solo ramo di ricorsione ma DUE. Rivedi il problema che pone il tutto.
Se non vuoi incorrere in questi dubbi, utilizza l'induzione (metodo per tentativi), appena ne avrai carpito la potenza del metodo...
Questo corso è fatto malissimo, troppe cose, pensavo che le ricorrenze sarebbero state una possibilità in più per superare l' esame( magari per la gente comune lo sono) ma io proprio le sto odiando, troppo complicate.
Secondo quello che mi hai detto nei vecchi post( il problema è che a distanza di tempo, anche pochi giorni faccio la delete delle cose, non sono bravo in matematica) avrei la possibilità, per la seconda ricorrenza di scomporla in:
[tex]T(n)=2T(n-1)+n[/tex]
[tex]T(n)=2T(n-2)+n[/tex]
Dovrei trovare un limite superiore, in questo caso.....mi viene da dire che la prima sia quella con l' altezza maggiore, perchè essendoci [tex]n-1[/tex] dovrebbe essere più piccola di [tex]n-2[/tex] e quindi più lenta ad arrivare all' ultimo livello.
[tex]T(n)=2T(n-1)+n[/tex]
Saprei risolverla, se non ci fosse quel 2 davanti alla T......
Quanto alle dimostrazioni per induzione, ho cercato ma ho trovato altri post, non uno dove ci fosse una dimostrazione per induzione, che rimane un mistero anche per come la presenta il libro....credo che l' ipotesi induttiva la applichi ad input più piccoli. Se provassi a farla con l' albero potrei trovare due limitazioni, se non erro, scrivendo:
[tex]T(n)=5T(n/5)+n[/tex]
[tex]T(n)=5T(n/6)+n[/tex]
Considero per trovare una limitazione superiore:
[tex]T(n)=5T(n/5)+n[/tex] che con il teorema Master ha soluzione [tex]T(n)=n\log(n)[/tex]
Ora rimane da provarla per induzione, e qui proprio viene il bello
.
Io devo verificare che [tex]T(n)=O(n\log(n))[/tex] e quindi ho:
[tex]T(n)\leq 4(c(\frac{n}{5}\log(\frac{n}{5})))+c(\frac{n}{6}\log(\frac{n}{6}))+n[/tex]
[tex]T(n)\leq 4(c(\frac{n}{5}\log(n)-\frac{n}{5}\log(5))+c(\frac{n}{6}\log(n)-\frac{n}{6}\log(6))+n[/tex]
Spero che sia corretto, non riesco ad andare avanti, avrei pensato di poter semplificare un termine considerando la base del log come 5, ma in ogni caso non arrivo a più di tanto...
Secondo quello che mi hai detto nei vecchi post( il problema è che a distanza di tempo, anche pochi giorni faccio la delete delle cose, non sono bravo in matematica) avrei la possibilità, per la seconda ricorrenza di scomporla in:
[tex]T(n)=2T(n-1)+n[/tex]
[tex]T(n)=2T(n-2)+n[/tex]
Dovrei trovare un limite superiore, in questo caso.....mi viene da dire che la prima sia quella con l' altezza maggiore, perchè essendoci [tex]n-1[/tex] dovrebbe essere più piccola di [tex]n-2[/tex] e quindi più lenta ad arrivare all' ultimo livello.
[tex]T(n)=2T(n-1)+n[/tex]
Saprei risolverla, se non ci fosse quel 2 davanti alla T......
Quanto alle dimostrazioni per induzione, ho cercato ma ho trovato altri post, non uno dove ci fosse una dimostrazione per induzione, che rimane un mistero anche per come la presenta il libro....credo che l' ipotesi induttiva la applichi ad input più piccoli. Se provassi a farla con l' albero potrei trovare due limitazioni, se non erro, scrivendo:
[tex]T(n)=5T(n/5)+n[/tex]
[tex]T(n)=5T(n/6)+n[/tex]
Considero per trovare una limitazione superiore:
[tex]T(n)=5T(n/5)+n[/tex] che con il teorema Master ha soluzione [tex]T(n)=n\log(n)[/tex]
Ora rimane da provarla per induzione, e qui proprio viene il bello
.Io devo verificare che [tex]T(n)=O(n\log(n))[/tex] e quindi ho:
[tex]T(n)\leq 4(c(\frac{n}{5}\log(\frac{n}{5})))+c(\frac{n}{6}\log(\frac{n}{6}))+n[/tex]
[tex]T(n)\leq 4(c(\frac{n}{5}\log(n)-\frac{n}{5}\log(5))+c(\frac{n}{6}\log(n)-\frac{n}{6}\log(6))+n[/tex]
Spero che sia corretto, non riesco ad andare avanti, avrei pensato di poter semplificare un termine considerando la base del log come 5, ma in ogni caso non arrivo a più di tanto...
"Darèios89":
Per la seconda ricorrenza di scomporla in:
[tex]T(n)=2T(n-1)+n[/tex]
[tex]T(n)=2T(n-2)+n[/tex]
Dovrei trovare un limite superiore, in questo caso.....mi viene da dire che la prima sia quella con l' altezza maggiore, perchè essendoci [tex]n-1[/tex] dovrebbe essere più piccola di [tex]n-2[/tex] e quindi più lenta ad arrivare all' ultimo livello.
[tex]T(n)=2T(n-1)+n[/tex]
ok fin qua
Sì l'albero non è proprio il massimo, ma si può usare con alcuni accorgimenti.
Saprei risolverla, se non ci fosse quel 2 davanti alla T......anche scrivendola come [tex]T(n)=T(n-1)+T(n-1)+n[/tex] i costi mi diventano:
n
2n-2
4n-8
8n-32
Il primo termine è una potenza di 2, l' altro cresce in modo diverso e non lo so formalizzare....
semplice proprietà delle potenze. L'unica cosa particolare che è un albero con cammini radice-foglia estesi, cioè non sono logartimo il numero di nodi, ma sono esponenziali al numero di nodi...
perciò:
$n -> 2(n-1) -> 2*2(n-2) -> 2*2*2(n-3)= 2^3(n-3) -> ... -> 2^i(n-i) -> ... -> 2^(n-1)*(n-(n-1)) -> 2^nT(0)$
perciò considerando la serie geometrica (con un piccolo trucco che penso corretto):
$sum_{i=0}^{n-1} 2^i*(n-i) != sum_{k=1}^{n}2^kk = 2*sum_{k=1}^{n}2^(k-1)k = 2^(n+1)n-2^n + 2$
____________________
EDIT:
come scritto sotto, non ero sicuro di questa uguaglianza. $sum x^i(n-i) != sum x^ii$ è da calcolare con le normali proprietà della sommatoria, utilizzare la derivata invece è corretto, ed è il modo di risolvere la seconda parte della sommatoria completa.
____________________
summiamo il tutto con le foglie: $2^(n+1)n-2^n + 2 + O(2^n) in O(2^(n+1)n)$ ed ecco la limitazione.
Ora, non ho mai trattato una equazione del genere in questo modo di solito con sottrazioni lineari di ricorsione si utilizzano altri metodi, ma penso sia corretta questa limitazione (hai la soluzione?).
Quanto alle dimostrazioni per induzione, ho cercato ma ho trovato altri post
tipo questa (vedi gli ultimi messaggi): post467475.htm
credo che l' ipotesi induttiva la applichi ad input più piccoli, cioè l' ipotesi è:
[tex]T(n/5)\leq c\frac{n}{5}[/tex] e
[tex]T(n/6)\leq c\frac{n}{6}[/tex]
Perciò sostituendo nella ricorrenza di partenza (questo è lo schema del mio libro) ottengo:
[tex]T(n)\leq 4c\frac{n}{5}+c\frac{n}{6}+n[/tex]
E se non erro nel fare i calcoli:
[tex]T(n)\leq 29cn+n[/tex]
Però sul libro c' è scritto che è errata una cosa del genere perchè non risulta provata la forma esatta dell' ipotesi induttiva, cioè che [tex]T(n)\leq cn[/tex] quindi rimango perplesso....
mmm sì c'è qualcosa di corretto, ma il formalismo è totalmente sbagliato. Mi pare che si veda ad occhi che non può essere $O(n)$ prova $O(n^2)$ anche se non è stretto almeno vedi l'induzione in modo completo.
Fino alla sostituzione è ok. Per il resto vedi la dispensa che ti ho linkato, poi ne riparliamo
EDIT:
ok ho visto che hai modificato il messaggio.
Ad occhio vedo finalmente qualche sostituzione corretta (non ho controllato i calcoli). Per continuare scrivi in questo modo che è più chiaro ciò che vuoi dimostrare:
\( 4(c(\frac{n}{5}\log(n)-\frac{n}{5}\log(5))+c(\frac{n}{6}\log(n)-\frac{n}{6}\log(6))+n \leq cnlog(n)\)
a te la palla (non dimenticare che sono disequazioni e log(5)|log(6) sono costanti)
Si torna, la tua soluzione è quella corretta.....Alla fine non ho capito solo una cosa dopo che calcoli la sommatoria, hai [tex]2^{n+1}n-2^n+2[/tex]
Hai una serie geometrica che converge con somma [tex]2^k-1[/tex] quindi diventa [tex](2^k-1)k[/tex] considerando il 2 fuori dalla sommatoria avrei [tex](2^{n+1}-2)n[/tex] o sbaglio qualcosa o mi manca qualcosa...
P.S ma una cosa, a me non quadra il conto che hai fatto con le potenze all' ultimo livello che ho rappresentato, quello dove il primo termine è 8n mentre l' altro non è 24 come risulterebbe dalla tua formula, ma 32.
Per quanto riguarda l' altra, non riesco ad andare avanti, ho pensato che ad esempio [tex]\frac{n}{5}\log(5)[/tex] diventa [tex]\log(5^{\frac{n}{5}})[/tex] è esattamente [tex]\frac{n}{5}[/tex] supponendo che la base sia 5, ma per gli altri non so come fare, a parte la proprietà della differenza di logaritmi, non so, devo passare agli esponenziali?
"Darèios89":
:shock:
Si torna, la tua soluzione è quella corretta.....Alla fine non ho capito solo una cosa dopo che calcoli la sommatoria, hai [tex]2^{n+1}n-2^n+2[/tex]
Hai una serie geometrica che converge con somma [tex]2^k-1[/tex] quindi diventa [tex](2^k-1)k[/tex] considerando il 2 fuori dalla sommatoria avrei [tex](2^{n+1}-2)n[/tex] o sbaglio qualcosa o mi manca qualcosa...
perchè parli di convergenza?
io ho utilizzato la definizione di derivata della sommatoria (finita)
$2*D(sum_{k=1}^{n}2^k) = 2*sum_{k=1}^{n}k2^(k-1) rArr 2*D((2^(n+1)-1)/(2-1))$ che diviene dopo qualche conto $2*(2^n(n-1) + 1)$
nulla di fuori dal mondo...
P.S ma una cosa, a me non quadra il conto che hai fatto con le potenze all' ultimo livello che ho rappresentato, quello dove il primo termine è 8n mentre l' altro non è 24 come risulterebbe dalla tua formula, ma 32.
perchè 32?
Per quanto riguarda l' altra, non riesco ad andare avanti, ho pensato che ad esempio [tex]\frac{n}{5}\log(5)[/tex] diventa [tex]\log(5^{\frac{n}{5}})[/tex] è esattamente [tex]\frac{n}{5}[/tex] supponendo che la base sia 5, ma per gli altri non so come fare, a parte la proprietà della differenza di logaritmi, non so, devo passare agli esponenziali?
ma spiegami, come riesci a complicarti la vita così
allora, come detto $log(5)$ devi trattarlo come quello che è, una costante, un numero, perciò:
ipotesi induttiva: \(4T(\frac{n}{5}) + T(\frac{n}{6}) + n \in O(nlog(n))\)
passo induttivo:
\(4c\frac{n}{5}\log(\frac{n}{5}) + c\frac{n}{6}\log(\frac{n}{6}) + n \leq cnlog(n)\)
\(\frac{4}5cn(\log(n) - \log(5)) + \frac{1}6cn(\log(n) - \log(6)) + n = \)
\(\frac{4}5cn\log(n) - \frac{4\log(5)}5cn\log(5)\ + \frac{1}6cn\log(n) - \frac{\log(6)}6cn + n = \)
\(\frac{29}{30}cn\log(n) - (\frac{24\log(5)+5\log(6)}{30})cn + n \leq cnlog(n) \)
ora a te, devi calcolre $c$ e hai da dimostrare un caso base per cui valga la disequazione.
Se hai dubbi chiedi pure
perchè 32?
Hai ragione non è 32, ma è 36, il tuo invece dovrebbe risultare 24......
Quanto a quello che hai fatto nella sommatoria:
nulla di fuori dal mondo...
Se permetti...io a questo punto sono fuori dal mondo
Non ho capito allora perchè c' è un 2 fuori dalla sommatoria, a parte questo prima hai messo [tex]2^{k}k[/tex] perchè quel k che moltiplica? E soprattutto perchè dopo aver derivato rimane solo un k che moltiplica? Quella frazione poi, come la ottieni? Mi sembra la somma di una serie geometrica ma diversa.........non capisco e non ricordo molto sulle serie infatti guardo dagli appunti, e soprattutto, a questo punto mi chiedo come abbia fatto a darmi analisi...
Quella sui logaritmi....la guardo domani....grazie...hum
"Darèios89":
Non ho capito allora perchè c' è un 2 fuori dalla sommatoria, a parte questo prima hai messo [tex]2^{k}k[/tex] perchè quel k che moltiplica? E soprattutto perchè dopo aver derivato rimane solo un k che moltiplica? Quella frazione poi, come la ottieni? :
su wiki ti ho trovato pure lo stesso esempio (a conferma che ciò che ho fatto non è sbagliato): http://it.wikipedia.org/wiki/Serie_geometrica guarda l'ultimo esempio è identico a questo caso
ma tornando all'equazione non vedo dove sia il problema, io mi riconduco alla definizione (applicativa di calcolo) della derivata per poi applicarla al nostro caso.
Ricapitoliamo, forse con qualche passaqggio in più è meglio. Partiamo da qui:
$sum_{i=0}^{n-1} 2^i*(n-i) != sum_{k=1}^{n}2^kk$
questo è il solito trucco che penso sia corretto.
cioè che la sommatoria:
$sum_{i=0}^{n} (n-i) = sum_{i=0}^{n}i$
sono opposte, srotolando:
$(n-0) + (n-1) + .... + (n-(n-1)) + (n-n) = 0 + 1 + ... + (n-1) + n$ ok?
perciò applicando lo stesso trucco ad una sottoporzione non cambia (almeno spero) il senso della sommatoria:
____________
EDIT:
come scritto non sapevo se tale uguaglianza fosse corretta. Confermo che non lo è.
___________
Ora, ricorda queste proprietà delle serie geometriche:
$D(sum_{k=1}^{n}2^k) = sum_{k=1}^{n}k2^(k-1)$ (1)
e che la serie geometrica:
$sum_{k=1}^{n}2^k = (2^(n+1)-1)/(2-1)$ (2)
per sostituzione:
$sum_{k=1}^{n}k2^(k-1) = D(sum_{k=1}^{n}2^k) = D((2^(n+1)-1)/(2-1)) = ... = 2^n(n-1) + 1$ (3)
nel nostro caso cerchiamo di rincodurci ad un caso noto (1):
$sum_{i=0}^{n-1} 2^i*(n-i) = sum_{k=1}^{n}2^kk = 2*sum_{k=1}^{n}2^(k-1)k = $ che ancora per sostituzione con (3) $= 2*D(sum_{k=1}^{n}2^k) = ... = 2*(2^n(n-1) + 1)$
rivediti le varie sostituzioni se non ti sono chiare o guarda wiki, ma è piuttosto "banale" alla fine...
Ok, allora si, è che non sapevo alcune cose sulle serie geoemtriche, cavolo, quel cervello ti cammina davvero tanto, complimentoni Adesso dò un' occhiata a quella con l' induzione logaritmica.
EDIT:
Una cosa, nella penultima riga dell' aiuto sulla logaritmica, a me risulta [tex]-\frac{4\log(5)}{5}cn[/tex] senza [tex]\log(5)[/tex] che moltiplica [tex]cn[/tex]. Ora non so se è corretto perchè i logaritmi non mi sono mai stati lucidi, posso fare il minimo comune multiplo visto che c' è quel 30 a denominatore?
[tex]29cn\log(n)-(24\log(5)+5\log(6))cn+30n\leq 30cn\log(n)[/tex]
[tex]-24cn\log(5)-5cn\log(6)+30n\leq cn\log(n)[/tex]
[tex]c(-24n\log(5)-5n\log(6))+30n\leq cn\log(n)[/tex]
Non so come va.....devo mantenere quel termine a secondo membro per verificare l' uguaglianza vero?
Finora forse come dici nel tuo messaggio personale ho usato l' assurdo per dimostrare?
Adesso dò un' occhiata a quella con l' induzione logaritmica.EDIT:
Una cosa, nella penultima riga dell' aiuto sulla logaritmica, a me risulta [tex]-\frac{4\log(5)}{5}cn[/tex] senza [tex]\log(5)[/tex] che moltiplica [tex]cn[/tex]. Ora non so se è corretto perchè i logaritmi non mi sono mai stati lucidi, posso fare il minimo comune multiplo visto che c' è quel 30 a denominatore?
[tex]29cn\log(n)-(24\log(5)+5\log(6))cn+30n\leq 30cn\log(n)[/tex]
[tex]-24cn\log(5)-5cn\log(6)+30n\leq cn\log(n)[/tex]
[tex]c(-24n\log(5)-5n\log(6))+30n\leq cn\log(n)[/tex]
Non so come va.....devo mantenere quel termine a secondo membro per verificare l' uguaglianza vero?
Finora forse come dici nel tuo messaggio personale ho usato l' assurdo per dimostrare?
"Darèios89":
Ok, allora si, è che non sapevo alcune cose sulle serie geoemtriche, cavolo, quel cervello ti cammina davvero tanto, complimentoni
ti ringrazio.Ma magari servisse così poco per essere bravi (in informatica), alla fine questi sono frutto di un po' di esperienza (dove l'errore è sempre dietro l'angolo)
"Darèios89":
EDIT:
Una cosa, nella penultima riga dell' aiuto sulla logaritmica, a me risulta [tex]-\frac{4\log(5)}{5}cn[/tex] senza [tex]\log(5)[/tex] che moltiplica [tex]cn[/tex]
non capisco cosa intendi qua...
Ora non so se è corretto perchè i logaritmi non mi sono mai stati lucidi, posso fare il minimo comune multiplo visto che c' è quel 30 a denominatore?
[tex]29cn\log(n)-(24\log(5)+5\log(6))cn+30n\leq 30cn\log(n)[/tex]
[tex]-24cn\log(5)-5cn\log(6)+30n\leq cn\log(n)[/tex]
[tex]c(-24n\log(5)-5n\log(6))+30n\leq cn\log(n)[/tex]
Non so come va.....devo mantenere quel termine a secondo membro per verificare l' uguaglianza vero?
Finora forse come dici nel tuo messaggio personale ho usato l' assurdo per dimostrare?
mmm ti complichi troppo la vita così. Il mcm lo ho già fatto io sommando e separando le parti comuni, cioè $cnlogn$ e $cn$ con le costanti.
Il trucco sta nel raggiungere un punto dove tu possa vedere che $T(n) <= cnlogn$ in modo abbastanza liscio.
Il punto in cui ho interroto è proprio questo, cioè si raggiunge una forma:
$cnlogn - cn + n <= cnlogn$
come puoi notare $-cn + n$ si sottraggono ed eliminano per una certa costante che moltiplicata da $1$
detto ciò, quello che dovrai fare è:
\(\frac{29}{30}cn\log(n) - (\frac{24\log(5)+5\log(6)}{30})cn + n \leq cnlog(n) \)
estratte le costanti per eliminare $n$ e verificare la disuguaglianza per un certo $c$.
Il tutto lo puoi semplicemente separando il problem:
1. per quale costante elimini $n$? \(c \geq (\frac{30}{24\log(5)+5\log(6)})\)
2. per quale costante verifiche $29/30cnlogn <= cnlogn$? $c >= 30/29$
perciò se non ho sbagliato qualcosa, ora basta scegliere un $c$ e calcolare per un qualche $n>=m$.
Senza troppo complicarsi la vita sciegliamo il logaritmo naturale.
Facendo un conto veloce, con \(c \geq (\frac{30}{24\log(5)+5\log(6)})\) $~~ 0.63$ e $n>=2$ $T(n) in O(nln(n))$
manca un caso base...
Una delle cose che un informatico dovrebbe (deve) sapere fare è usare il principio di induzione, ma non lo capirò mai bene forse.
Quindi alla fine in quei due punti che hai indicato con 1. 2. così abbiamo trovato le costanti ed è provata. Dici che manca un caso base, io il principio di induzione lo applico in genere per altri problemi prima provando qualcosa per n=0 e poi per n+1. Ora non so che caso base dovrebbe mancare.....io avrei messo un punto. Scusa abbiamo trovato la costante c, se [tex]c\geq \frac{30}{29}[/tex] e per [tex]n\geq 2[/tex] la disuguaglianza è vera, non è un caso base? Perchè non possiamo concludere che la complessità è quella?
Quindi alla fine in quei due punti che hai indicato con 1. 2. così abbiamo trovato le costanti ed è provata. Dici che manca un caso base, io il principio di induzione lo applico in genere per altri problemi prima provando qualcosa per n=0 e poi per n+1. Ora non so che caso base dovrebbe mancare.....io avrei messo un punto. Scusa abbiamo trovato la costante c, se [tex]c\geq \frac{30}{29}[/tex] e per [tex]n\geq 2[/tex] la disuguaglianza è vera, non è un caso base? Perchè non possiamo concludere che la complessità è quella?
"Darèios89":
Una delle cose che un informatico dovrebbe (deve) sapere fare è usare il principio di induzione, ma non lo capirò mai bene forse.
prova a leggere la firma del mio profilo...
Quindi alla fine in quei due punti che hai indicato con 1. 2. così abbiamo trovato le costanti ed è provata.
Sì. Io ho scelto la 1. ma forse anche la 2. per un qualche $n$ è vera... ma essendo 1. <= 2. è sicuramente vera.
Dici che manca un caso base, io il principio di induzione lo applico in genere per altri problemi prima provando qualcosa per n=0 e poi per n+1.
certo è corretto ciò che dici, solo che il passo $n=0$ non lo abbiamo fatto...
sempliciemente metti (ipotizzando che a $n=1$ dia semplicemente $1$)
$T(1) = 1<=c1log(1)=0$ falso
$T(2) = 4T(1) + T(1) + 2 = 4 + 1 + 2 = 7 <= c2ln(2)$ falso
... non essendo vero per un T(n) possiamo scegliore noi da che $n>m$ partire perciò continiamo finche non lo troviamo:
$T(7) = 4T(1) + T(1) + 7 = 4 + 1 + 7 = 12 <= c7ln(7) ~~ 13$ vera per $c>= 12/13$ e $n>7$
Perciò: $T(n) in O(nln(n))$ per $c>=30/29$ (o una qualunque costante tra quelle scritte) $AAn>=7$
sarebbe un po' da riordinare il tutto, dato che è tutto messo in parecchi post, ma spero tu abbia capito il procedimento
Ah si ora ci sono, dimentico che per induzione si deve trovare una costante c positiva e un n naturale per cui valga la disequazione. Quindi io avrei dovuto trovare solo questo valore di n, questo mancava giusto?
Per quanto riguarda la costante, noi avevamo due c, per una si annullava sicuramente n, e con l' altra rendevamo l' uguaglianza nlogn minore del' altra giusto? Quindi tu hai dovuto scegliere quel c tale che entrambe queste condizioni fossero soddisfatte, giusto?
Per quanto riguarda la costante, noi avevamo due c, per una si annullava sicuramente n, e con l' altra rendevamo l' uguaglianza nlogn minore del' altra giusto? Quindi tu hai dovuto scegliere quel c tale che entrambe queste condizioni fossero soddisfatte, giusto?
come sempre ti ho fatto un discorso più lungo del necessario per farti comprender il perchè di certi passaggi.
Dato che $n$ e $c$ lo scegliamo noi, puoi basarti sui valori dell'equazione di ricorrenza per trovarne già una costante pronta da utilizzare (come ho fatto io), se vuoi puoi anche raggruppare in fattore le $c$ e sommarle per averne un'altra. Comunque basta provare che la $c$ trovatà è valida per ogni $n>=m$ ed è finita lì
Prendendo per buon quel discorso di prima di sottrarre $n$ e validare $cnlogn$, è per farti capire i passaggi mentali da fare.
Di solito si fa questo:
arrivati a questo punto validante della disequazione, arrivando ad un punto che ad occhio sembra che la disequazione è corretta,
\(\frac{29}{30}cn\log(n) - (\frac{24\log(5)+5\log(6)}{30})cn + n \leq cnlog(n) \)
si raggruppano le $c$ e si somma il tutto e si dice, che l'ultima disequazione sopra è valida per:
\(\frac{29}{30}c- (\frac{24\log(5)+5\log(6)}{30})c + 1 \leq c \)
\((1 + \frac{29}{30} - (\frac{24\log(5)+5\log(6)}{30}))c = (\frac{59 - (24\log(5)+5\log(6) \approx 11}{30}))c \geq 1 \)
$c \geq 30/11$
Se hai dubbi chiedi pure
Dato che $n$ e $c$ lo scegliamo noi, puoi basarti sui valori dell'equazione di ricorrenza per trovarne già una costante pronta da utilizzare (come ho fatto io), se vuoi puoi anche raggruppare in fattore le $c$ e sommarle per averne un'altra. Comunque basta provare che la $c$ trovatà è valida per ogni $n>=m$ ed è finita lì
Prendendo per buon quel discorso di prima di sottrarre $n$ e validare $cnlogn$, è per farti capire i passaggi mentali da fare.
Di solito si fa questo:
arrivati a questo punto validante della disequazione, arrivando ad un punto che ad occhio sembra che la disequazione è corretta,
\(\frac{29}{30}cn\log(n) - (\frac{24\log(5)+5\log(6)}{30})cn + n \leq cnlog(n) \)
si raggruppano le $c$ e si somma il tutto e si dice, che l'ultima disequazione sopra è valida per:
\(\frac{29}{30}c- (\frac{24\log(5)+5\log(6)}{30})c + 1 \leq c \)
\((1 + \frac{29}{30} - (\frac{24\log(5)+5\log(6)}{30}))c = (\frac{59 - (24\log(5)+5\log(6) \approx 11}{30}))c \geq 1 \)
$c \geq 30/11$
Se hai dubbi chiedi pure
Ah si infatti ricordo che nei tuoi appunti ho visto fare questo, mettere in evidenza la c. Solo una domanda, prima di mettere in evidenza la c hai scritto i termini senza i logaritmi per considerare la c solamente, perchè c' è [tex](\frac{......}{30})c+1\leq c[/tex]
Quell' 1 come mai? Non capisco a cosa si riferisce...
Quell' 1 come mai? Non capisco a cosa si riferisce...
l'1 è la costante di $n$.
Ma badi bene in questo caso puoi farlo, perchè il fattore $n$ viene eliminato da $n - cn$ per un qualche $c$, se avessi avuto solo $cnlogn + n$ non ci puoi fare niente, la disequazione non sarai mai vera per alcun $n$.
questo mi incuriosisce, dove la hai letta la dimostrazione, il Cormen?
Ma badi bene in questo caso puoi farlo, perchè il fattore $n$ viene eliminato da $n - cn$ per un qualche $c$, se avessi avuto solo $cnlogn + n$ non ci puoi fare niente, la disequazione non sarai mai vera per alcun $n$.
Mi è capitata una cosa simile se non erro nella dimostrazione dell' algoritmo Select(mediane), non capisco a cosa si riferisce...
questo mi incuriosisce, dove la hai letta la dimostrazione, il Cormen?
Si sul Cormen però è simile, cioè praticamente scrive questo:
[tex]T(n)\leq c\left \lceil n/5 \right \rceil+c(7n/10+6)+an[/tex]
[tex]cn/5+c+7cn/10+6c+an[/tex]
C' è una c che non mi spiego in più.....dopo n quinti.
Una curiosità allora, circa questa benedetta induzione, se io avessi, sto ipotizzando le fasi finali di una dimostrazione.
Voglio provare che [tex]T(n)\leq cn[/tex]
Se mi ritrovo [tex]cn +n[/tex]
Il testo dice errata perchè non è provata la forma esatta dell' induzione cioè che [tex][tex]T(n)\leq cn[/tex] anche se io da studente direi che la n dopo non mi dà fastidio visto che c è positiva e la ricorrenza sarà sempre ordine di O(n). Perchè non funziona?
Se per esempio invece dovessi provare che:
[tex]T(n)\leq cn^2[/tex]
E se arrivo a una cosa come
[tex]c2n^2+cn^2+n[/tex] a questo punte se faccio [tex]c(2n^2+n^2)+n[/tex] In teoria non dovrei trovarla la costante...
Se ho sbagliato ancora ti chiedo solo di farmi degli esempi di questo tipo per capire a fine dimostrazione come non sbagliare.
Sorry ormai non è più un forum, ma un supporto tecnico 24 ore su 24
[tex]T(n)\leq c\left \lceil n/5 \right \rceil+c(7n/10+6)+an[/tex]
[tex]cn/5+c+7cn/10+6c+an[/tex]
C' è una c che non mi spiego in più.....dopo n quinti.
Una curiosità allora, circa questa benedetta induzione, se io avessi, sto ipotizzando le fasi finali di una dimostrazione.
Voglio provare che [tex]T(n)\leq cn[/tex]
Se mi ritrovo [tex]cn +n[/tex]
Il testo dice errata perchè non è provata la forma esatta dell' induzione cioè che [tex][tex]T(n)\leq cn[/tex] anche se io da studente direi che la n dopo non mi dà fastidio visto che c è positiva e la ricorrenza sarà sempre ordine di O(n). Perchè non funziona?
Se per esempio invece dovessi provare che:
[tex]T(n)\leq cn^2[/tex]
E se arrivo a una cosa come
[tex]c2n^2+cn^2+n[/tex] a questo punte se faccio [tex]c(2n^2+n^2)+n[/tex] In teoria non dovrei trovarla la costante...
Se ho sbagliato ancora ti chiedo solo di farmi degli esempi di questo tipo per capire a fine dimostrazione come non sbagliare.
Sorry ormai non è più un forum, ma un supporto tecnico 24 ore su 24
Una qualsiasi dimostrazione per induzione è costituita da due fasi distinte. In un primo momento si dimostra la proposizione per un qualche valore costante. Questo caso è detto base dell'induzione. Nella seconda fase si suppone quindi che la proposizione sia vera per ogni \( c \le n \le k \) e si cerca di dimostrare la proposizione per \( n = k + 1 \). Questa seconda fare prende il nome di passo induttivo e nella dimostrazione si cerca solitamente di ridursi alla proposizione con \( n \le k \).
Esempio. Dimostriamo che la somma dei cubi dei primi \( n \) interi positivi è uguale al quadrato della somma degli stessi numeri interi. Cioè
\[ \sum_{i = 1}^n \, i^3 = \left( \sum_{i=1}^n \, i \right)^2 = \left( \frac{n(n+1)}{2} \right)^2. \]
Base dell'induzione \((n = 1)\). Questa parte della dimostrazione per induzione è spesso immediata e questo caso non fa eccezione, infatti
\[ 1^3 = 1^2. \]
Passo induttivo. Supponiamo che la proposizione sia vera per ogni \(1 \le n \le k\) e dimostriamola per \(n = k+1\). Per prima cosa si deve cercare di riportarsi ad un caso del quale si è già supposta la validità. In questo caso si può fare come segue:
\[ \sum_{i = 1}^{k+1} \, i^3 = \sum_{i=1}^k \, i^3 + (k+1)^3 = \left( \frac{k(k+1)}{2} \right)^2 + (k+1)^3. \]
A questo punto non rimane che dimostrare che
\[ (k+1)^3 = \left( \frac{(k+1)(k+2)}{2} \right)^2 - \left( \frac{k(k+1)}{2} \right)^2, \]
ma la parte destra dell'equazione può essere facilmente riscritta nel modo seguente dimostrando la proposizione:
\[ \left(\frac{k+1}{2}\right)^2 ( (k+2)^2 - k^2 ) = \left(\frac{k+1}{2}\right)^2 ( k^2 + 4k + 4 - k^2 ) = \frac{(k+1)^2}{4} (4k + 4) = (k+1)^2(k+1) = (k+1)^3. \]
In informatica la base dell'induzione sembra spesso ignorata.. ma questo è più o meno tutto quello che è necessario sapere sull'induzione matematica.
Stai confondendo due cose che devono rimanere separate. La complessità asintotica non può e non deve essere usata per verificare la validità di una proposizione. La relazione data dalla complessità asintotica è in effetti molto meno forte da quella imposta dalla proposizione che stai cercando di dimostrare. È infatti in generale diverso essere minori ad esempio di \( 3n \) o \( 4n \) ma asintoticamente le due funzioni sono uguali. Lo stesso vale per l'esempio successivo. Se hai bisogno che \( T(n) \) sia minore di \( c n^2 \) ed è invece minore di \( c2n^2 + cn^2 + n > cn^2 \) non hai ottenuto quello che volevi.
Esempio. Dimostriamo che la somma dei cubi dei primi \( n \) interi positivi è uguale al quadrato della somma degli stessi numeri interi. Cioè
\[ \sum_{i = 1}^n \, i^3 = \left( \sum_{i=1}^n \, i \right)^2 = \left( \frac{n(n+1)}{2} \right)^2. \]
Base dell'induzione \((n = 1)\). Questa parte della dimostrazione per induzione è spesso immediata e questo caso non fa eccezione, infatti
\[ 1^3 = 1^2. \]
Passo induttivo. Supponiamo che la proposizione sia vera per ogni \(1 \le n \le k\) e dimostriamola per \(n = k+1\). Per prima cosa si deve cercare di riportarsi ad un caso del quale si è già supposta la validità. In questo caso si può fare come segue:
\[ \sum_{i = 1}^{k+1} \, i^3 = \sum_{i=1}^k \, i^3 + (k+1)^3 = \left( \frac{k(k+1)}{2} \right)^2 + (k+1)^3. \]
A questo punto non rimane che dimostrare che
\[ (k+1)^3 = \left( \frac{(k+1)(k+2)}{2} \right)^2 - \left( \frac{k(k+1)}{2} \right)^2, \]
ma la parte destra dell'equazione può essere facilmente riscritta nel modo seguente dimostrando la proposizione:
\[ \left(\frac{k+1}{2}\right)^2 ( (k+2)^2 - k^2 ) = \left(\frac{k+1}{2}\right)^2 ( k^2 + 4k + 4 - k^2 ) = \frac{(k+1)^2}{4} (4k + 4) = (k+1)^2(k+1) = (k+1)^3. \]
In informatica la base dell'induzione sembra spesso ignorata.. ma questo è più o meno tutto quello che è necessario sapere sull'induzione matematica.Il testo dice errata perché non è provata la forma esatta dell'induzione cioè che \(T(n) \le cn\) anche se io da studente direi che la \( n \) dopo non mi dà fastidio visto che \( c \) è positiva e la ricorrenza sarà sempre ordine di \( O(n) \). Perché non funziona?
Stai confondendo due cose che devono rimanere separate. La complessità asintotica non può e non deve essere usata per verificare la validità di una proposizione. La relazione data dalla complessità asintotica è in effetti molto meno forte da quella imposta dalla proposizione che stai cercando di dimostrare. È infatti in generale diverso essere minori ad esempio di \( 3n \) o \( 4n \) ma asintoticamente le due funzioni sono uguali. Lo stesso vale per l'esempio successivo. Se hai bisogno che \( T(n) \) sia minore di \( c n^2 \) ed è invece minore di \( c2n^2 + cn^2 + n > cn^2 \) non hai ottenuto quello che volevi.
"Darèios89":
Si sul Cormen però è simile, cioè praticamente scrive questo:
[tex]T(n)\leq c\left \lceil n/5 \right \rceil+c(7n/10+6)+an[/tex]
[tex]cn/5+c+7cn/10+6c+an[/tex]
C' è una c che non mi spiego in più.....dopo n quinti.
ah questo è dovuto alla proprietà:
$n <= \lceil n \rceil < n + 1$
ti sei perso un $<=$ e sostituendo:
[tex]c\left \lceil n/5 \right \rceil+c(7n/10+6)+an \leq c(n/5 + 1) +7cn/10+6c+an = cn/5 + c +7cn/10+6c+an[/tex]
ok?
Ah ecco non la conoscevo, ora si, grazie
Grazie anche ad apatriarca, adesso rileggo il suo esempio.
Grazie anche ad apatriarca, adesso rileggo il suo esempio.
Quanto alle dimostrazioni per induzione, ho cercato ma ho trovato altri post
tipo questa (vedi gli ultimi messaggi): post467475.htm
credo che l' ipotesi induttiva la applichi ad input più piccoli, cioè l' ipotesi è:
[tex]T(n/5)\leq c\frac{n}{5}[/tex] e
[tex]T(n/6)\leq c\frac{n}{6}[/tex]
Perciò sostituendo nella ricorrenza di partenza (questo è lo schema del mio libro) ottengo:
[tex]T(n)\leq 4c\frac{n}{5}+c\frac{n}{6}+n[/tex]
E se non erro nel fare i calcoli:
[tex]T(n)\leq 29cn+n[/tex]
Però sul libro c' è scritto che è errata una cosa del genere perchè non risulta provata la forma esatta dell' ipotesi induttiva, cioè che [tex]T(n)\leq cn[/tex] quindi rimango perplesso....
mmm sì c'è qualcosa di corretto, ma il formalismo è totalmente sbagliato. Mi pare che si veda ad occhi che non può essere $O(n)$ prova $O(n^2)$ anche se non è stretto almeno vedi l'induzione in modo completo.
Fino alla sostituzione è ok. Per il resto vedi la dispensa che ti ho linkato, poi ne riparliamo
EDIT:
ok ho visto che hai modificato il messaggio.
Ad occhio vedo finalmente qualche sostituzione corretta (non ho controllato i calcoli). Per continuare scrivi in questo modo che è più chiaro ciò che vuoi dimostrare:
\( 4(c(\frac{n}{5}\log(n)-\frac{n}{5}\log(5))+c(\frac{n}{6}\log(n)-\frac{n}{6}\log(6))+n \leq cnlog(n)\)
a te la palla (non dimenticare che sono disequazioni e log(5)|log(6) sono costanti)
Forse dirò una cosa sbagliata..ma la soluzione di questa ricorrenza non è [tex]O(n)[/tex]??
Una curiosità, lo sviluppo l'albero, così come ho fatto sotto è giusto?
[tex]n[/tex]
[tex](\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{6})= \frac{29}{30}n[/tex]
[tex](\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{6})[/tex]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo