Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Jimmy93 on 21-09-2013, 10:12:24



Title: Complessità SelectionSort(Confronti)
Post by: Jimmy93 on 21-09-2013, 10:12:24
Non capisco questo passaggio:
\fs{4}\displaystyle\sum_{i=0}^{n-2}\left(1+\sum_{j=i+1}^{n-1}1 \right) = (n-1) + \sum_{i=0}^{n-2}(n-1-i)

Qualcuno può aiutarmi??  :-)|

EDIT del mod: questo forum supporta LaTeX. Usa questo invece di linkare siti esterni ;-)


Title: Re:Complessità SelectionSort(Confronti)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-09-2013, 11:24:45
\fs{4}\displaystyle\sum_{i=0}^{n-2}\left(1+\sum_{j=i+1}^{n-1}1 \right) =\sum_{\(A\)i=0}^{\(B\)n-2}{\({1}\)}+\sum_{i=0}^{n-2}{\({\sum_{\(C\)j=i+1}^{\(D\)n-1}{\({1}\)}}\)}\\=\overbrace{\({\({n-2}\)-0+1}\)}^ {B-A+1}+\sum_{i=0}^{n-2}\overbrace{\({\({n-1}\)-\({i+1}\)+1}\)}^{D-C+1}= \({n-1}\) + \sum_{i=0}^{n-2}\({n-1-i}\) :-OK


Title: Re:Complessità SelectionSort(Confronti)
Post by: Jimmy93 on 21-09-2013, 15:43:47
[latex] :-OK

Grazie ho capito, ma precisamente dove posso usare questa proprietà: \sum_{A}^{B}x = (B-A+x) ?? Sempre se è una proprietà XD


Title: Re:Complessità SelectionSort(Confronti)
Post by: Jimmy93 on 21-09-2013, 16:19:07
P.S Mentre aspetto risposta, il pasaggio successivo a quello che abbiamo visto sarebbe : \displaystyle(n-1)+(\sum_{i=0}^{n-2}n-\sum_{i=0}^{n-2}i-\sum_{i=0}^{n-2}(-1)) ??


Title: Re:Complessità SelectionSort(Confronti)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-09-2013, 18:44:01
[latex] :-OK

Grazie ho capito, ma precisamente dove posso usare questa proprietà: \sum_{A}^{B}x = (B-A+x) ?? Sempre se è una proprietà XD
La proprietà che ho usato non è quella che hai scritta tu, che non è nemmeno una proprietà visto che è falsa.

Ho sfruttato questa, piuttosto:
\fs{4}\displaystyle\sum_{i=A}^{i=B}\({k}\)=(B-A+1)\cdot\({k}\), ove \fs{3}k è una quantità che non dipende da \fs{3}i .nono. Nel tuo caso \fs{3}k=1 quindi non si vede nella moltiplicazione. Quel "+1" tra parentesi devi vederlo così:

se per esempio dovessi sommare un certo numero di termini tutti uguali a k, diciamo da i=1 a i=10 (inclusi), noteresti che ci sono esattamente 10 elementi uguali a k. Se sommassi da i=21 a i=25 (inclusi), noti che ci sono 5 elementi.
Ora, ovviamente il numero di oggetti compresi tra due indici ha certamente una relazione con la loro differenza (10-1 e 25-21) solo che se fai la semplice differenza, stai scartando anche il primo indice (il più basso, cioè 1 oppure 21), quindi devi aggiungere un "+1" alla differenza. Tutto ciò puoi dimostrarlo per induzione, ma a questo livello lo si dà per scontato...


Title: Re:Complessità SelectionSort(Confronti)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-09-2013, 18:49:52
P.S Mentre aspetto risposta, il pasaggio successivo a quello che abbiamo visto sarebbe : [latex]
No. Devi fare attenzione!

O lasci il generico addizionatore "+" tra le varie sommatorie, quando scomponi la sommatoria di un termine che è anch'esso una somma, e mantieni l'eventuale segno "-" dentro l'argomento della sommatoria scomposta, oppure lo fai uscire fuori dal segno di sommatoria, perché hai effettivamente fatto uscire un (-1) che moltiplicava l'argomento, e (-1), essendo costante, non dipende dalla variabile della sommatoria (i), e poteva uscire.

Diventerebbe, quindi:
\fs{4}\displaystyle(n-1)+\({\sum_{i=0}^{n-2}n+\sum_{i=0}^{n-2}\({-i}\)+\sum_{i=0}^{n-2}\({-1}\)}\)=(n-1)+\({\sum_{i=0}^{n-2}n-\sum_{i=0}^{n-2}i-\sum_{i=0}^{n-2}1}\)

Ora, le sommatorie sono tutte notevoli, quindi si semplificano facilmente. Ti anticipo che alla fine del processo di semplificazione otterrai un polinomio di secondo grado a coefficienti razionali a tre termini  :-OK.


Title: Re:Complessità SelectionSort(Confronti)
Post by: Jimmy93 on 22-09-2013, 10:10:05
Grazie, immaginavo che avrei detto un mucchio di cavolate  |-O
Comunque sono arrivato a questo: \left( n(n-1)-\frac{(n-2)(n-1)}{2} - (n-1) \right)
c'è scritto così anche nelle slide del prof, quindi penso sia così XD, sono arrivato a questo punto applicando la proprietà che mi hai fatto vedere alla prima e terza sommatoria e la formula(si chiama così?? XD) di Gauss alla seconda(proprio di questa non ne sono sicuro al 100%). Mi potresti dire se è giusta o sbagliata??  .rido


Title: Re:Complessità SelectionSort(Confronti)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-09-2013, 11:36:26
Ciò che hai scritto corrisponde a ciò che è dentro la parentesi con le 3 sommatorie, corretto .smile.

Non ricordo sinceramente se si chiamasse formula di Gau§ o altri nomi, io ero riusciuto a trovare la ricorrenza per la somma centrale già a scuola media/primo superiore mi pare, da solo :pray...


Title: Re:Complessità SelectionSort(Confronti)
Post by: Jimmy93 on 22-09-2013, 12:15:29
Ciò che hai scritto corrisponde a ciò che è dentro la parentesi con le 3 sommatorie, corretto .smile.

Non ricordo sinceramente se si chiamasse formula di Gau§ o altri nomi, io ero riusciuto a trovare la ricorrenza per la somma centrale già a scuola media/primo superiore mi pare, da solo :pray...
Si è il risultato delle tre sommatorie, praticamente una sommatoria che va da i=0 a n di i si calcola con n(n+1),
visto che n = n-1 allora dovrebbe essere n-1(n-1+1) quindi n(n-1).
P.s Mi dispiace ma Gauss ti ha anticipato, non so se lo conosci ma questo è il suo famoso aneddoto XD : http://mategame.blogspot.it/2008/08/famosissimo-aneddoto-su-gauss.html


Title: Re:Complessità SelectionSort(Confronti)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-09-2013, 09:36:34
Proprio come ho fatto io :pray...