Importante - Calcolo Sommatoria

[Lordofnazgul]

ciao a tutti ragazzi! ho un esercizio di questo tipo: Siano ${ x_i } i=0, .. .. .. , 2n$ $ 2n+1$ punti distinti sulla sulla retta reale

definiamo ∑ 0 = $\sum_{i=0}^(2*n) |x_0 - x_i|$
∑ 1 = $\sum_{i=0}^(2*n) |x_1 - x_i|$

è possibile calcolare quanto è il risultato di queste due sommatorie? (non mi interessa la richiesta dopo dell'esercizio, mi interessa trovare quanto vengono queste due sommatorie)
io pensavo ad esempio di "spaccare" le due sommatorie in quattro sommatorie differenti dato che c'è una differenza, e poi applicare ad ognuna il doppio della sommatoria di Gauss (però non so se funziona dal momento che ho numeri reali e non interi) però dato che sto facendo il corso di laurea in informatica, sono un pò arrugginito con le sommatorie e chiedo aiuto a voi...che ne pensate?
grazie mille!

[gugo82]

Prova a dividere, che so, la prima sommatoria in due pezzi come segue:

[tex]$\sum_{i=0}^{2n} |x_0-x_i| =\sum_{i \text{ t.c. } x_i
elimina i valori assoluti, etc...


P.S.: Aggiungo che, essendo la somma indipendente dall'ordine degli addendi, puoi considerare di riordinare gli addendi e rinumerarli in modo che [tex]$x_0=x^\nu$[/tex] e che [tex]$\forall m<\nu,\ x^mriordinamento crescente di [tex]$\{ x_n\}$[/tex]), sicché la precedente diventa:

[tex]$\sum_{i=0}^{2n} |x_0-x_i| =\sum_{i=0}^{\nu -1} |x^\nu -x^i| +\sum_{i=\nu}^{2n} |x^\nu -x^i|$[/tex]

e si calcola facile.

[Lordofnazgul]

"gugo82":Prova a dividere, che so, la prima sommatoria in due pezzi come segue:

[tex]$\sum_{i=0}^{2n} |x_0-x_i| =\sum_{i \text{ t.c. } x_i
elimina i valori assoluti, etc...


P.S.: Aggiungo che, essendo la somma indipendente dall'ordine degli addendi, puoi considerare di riordinare gli addendi e rinumerarli in modo che [tex]$x_0=x^\nu$[/tex] e che [tex]$\forall m<\nu,\ x^mriordinamento crescente di [tex]$\{ x_n\}$[/tex]), sicché la precedente diventa:

[tex]$\sum_{i=0}^{2n} |x_0-x_i| =\sum_{i=0}^{\nu -1} |x^\nu -x^i| +\sum_{i=\nu}^{2n} |x^\nu -x^i|$[/tex]

e si calcola facile.

aiuto direi decisamente che mi sono perso sul secondo... io so calcolare numericamente quanto vale la sommatoria se l'esponente fosse al quadrato o al max al cubo, ma quando l'esponente diventa decisamente grande come faccio a trovare una formula adatta??

[gugo82]

Quelli non sono esponenti... Sono solo indici, messi in alto per distinguere il riordinamento crescente dalla sequenza originaria.

[Lordofnazgul]

"gugo82":Quelli non sono esponenti... Sono solo indici, messi in alto per distinguere il riordinamento crescente dalla sequenza originaria.

ah ok, mi ero già preso male... io intuitivamente "spezzerei" tutte le sommatorie e le risolverei appunto come il doppio della somma di gauss, come risultato quindi avrei $n(n + 1)$ però il problema è che mi si annullano tutte... cioè tipo verrebbe: $n(n+1) - n(n+1) .....$ e così mi esce 0 dov'è che sbaglio??

[gugo82]

Cosa c'entra Gauss se gli [tex]$x_n$[/tex] non sono naturali?
Quel risultato è valido per la somma [tex]$\sum_{i=0}^N i$[/tex] (in cui, nota bene, gli addendi sono i primi [tex]$N+1$[/tex] numeri naturali consecutivi), quindi non vedo come potresti applicarlo qui.

Ad ogni modo, la soluzione è molto più semplice di quanto immagini: davvero, basta riordinare ed eliminare i valori assoluti.

Ad esempio, suopponi che l'insieme [tex]$\{ x_n\}$[/tex] sia fatto in modo che [tex]$x_0\leq x_1\leq \ldots \leq x_i\leq x_{i+1} \leq \ldots \leq x_{2n}$[/tex]: in tal caso sai dire quanto vale la somma [tex]$\sum_{i=0}^{2n} |x_0-x_i|$[/tex]?

[Lordofnazgul]

"gugo82":Cosa c'entra Gauss se gli [tex]$x_n$[/tex] non sono naturali?
Quel risultato è valido per la somma [tex]$\sum_{i=0}^N i$[/tex] (in cui, nota bene, gli addendi sono i primi [tex]$N+1$[/tex] numeri naturali consecutivi), quindi non vedo come potresti applicarlo qui.

Ad ogni modo, la soluzione è molto più semplice di quanto immagini: davvero, basta riordinare ed eliminare i valori assoluti.

Ad esempio, suopponi che l'insieme [tex]$\{ x_n\}$[/tex] sia fatto in modo che [tex]$x_0\leq x_1\leq \ldots \leq x_i\leq x_{i+1} \leq \ldots \leq x_{2n}$[/tex]: in tal caso sai dire quanto vale la somma [tex]$\sum_{i=0}^{2n} |x_0-x_i|$[/tex]?

uhm, non sarebbe come dire qualcosa di questo tipo: $x_0 - (x_0 + x_1 + x_2 + ........ + x_i)$ ? quindi $x_0$ si dovrebbe eliminare, e rimangono tutti i valori che vanno da $x_1$ a $x_i$...
il problema è che non riesco a capire come potrei scrivere il tutto come un risultato esplicito...
Scusa se magari sembro un pò niubbo, ma sono decisamente arrugginito riguardo queste cose...

[gugo82]

Immaginiamo di avere [tex]$x_0\leq \ldots \leq x_{i+1} \leq \ldots \leq x_{2n}$[/tex]: allora [tex]$|x_0-x_i|=x_i-x_0$[/tex] per [tex]$i=1,\ldots ,2n$[/tex] ed [tex]$|x_0-x_i|=0$[/tex] per [tex]$i=0$[/tex] sicché:

[tex]$\sum_{i=0}^{2n} |x_0-x_i| =\sum_{i=1}^{2n} x_i-x_0 = \sum_{i=1}^{2n} x_i -\sum_{i=1}^{2n} x_0 =\left\{ \sum_{i=1}^{2n} x_i \right\} -2n\ x_0$[/tex].

Ti convince?

[Lordofnazgul]

"gugo82":Immaginiamo di avere [tex]$x_0\leq \ldots \leq x_{i+1} \leq \ldots \leq x_{2n}$[/tex]: allora [tex]$|x_0-x_i|=x_i-x_0$[/tex] per [tex]$i=1,\ldots ,2n$[/tex] ed [tex]$|x_0-x_i|=0$[/tex] per [tex]$i=0$[/tex] sicché:

[tex]$\sum_{i=0}^{2n} |x_0-x_i| =\sum_{i=1}^{2n} x_i-x_0 = \sum_{i=1}^{2n} x_i -\sum_{i=1}^{2n} x_0 =\left\{ \sum_{i=1}^{2n} x_i \right\} -2n\ x_0$[/tex].

Ti convince?

ok, questo mi convince! c'è qualche teorema che posso applicare per calcolare la sommatoria riguardante $x_i$ dal momento che non siamo nei naturali???

[gugo82]

"Lordofnazgul":c'è qualche teorema che posso applicare per calcolare la sommatoria riguardante $x_i$ dal momento che non siamo nei naturali???

No.
Se non hai altre ipotesi su [tex]$x_1,\ldots ,x_{2n}$[/tex], la devi necessariamente tenere com'è.

[Lordofnazgul]

"gugo82":[quote="Lordofnazgul"]c'è qualche teorema che posso applicare per calcolare la sommatoria riguardante $x_i$ dal momento che non siamo nei naturali???

No.
Se non hai altre ipotesi su [tex]$x_1,\ldots ,x_{2n}$[/tex], la devi necessariamente tenere com'è.[/quote]


ah ok, quindi non posso andare oltre nei calcoli??
l'esercizio iniziale era questo:

Siano ${ x_i } i=0, .. .. .. , 2n$ $ 2n+1$ punti distinti sulla sulla retta reale

definiamo ∑ 0 = $\sum_{i=0}^(2*n) |x_0 - x_i|$
∑ 1 = $\sum_{i=0}^(2*n) |x_1 - x_i|$


Provare che esiste un algoritmo lineare che trova $\sum_{min}$ = {$\sum_{i}$ $| i:0,.. .. .. ,2n}


io l'algoritmo l'ho scritto, solo che una volta trovata la complessità del mio algoritmo pensavo di confrontarla con il risultato delle sommatorie per verificare che l'algoritmo che ho scritto funzionava...dici che forse ho sbagliato idea?

[gugo82]

Vediamo se ho capito il problema: scelti [tex]$2n+1$[/tex] numeri a caso [tex]$x_0,\ldots ,x_{2n} \in \mathbb{R}$[/tex], poni:

[tex]$S_k:=\sum_{i=0}^{2n} |x_k-x_i|$[/tex] per [tex]$k=0,\ldots ,2n$[/tex]

e vuoi determinare il valore [tex]$S:=\min \{S_k\}_{k=0,\ldots ,2n}$[/tex]. Giusto?

La sommatoria cui pervieni nel caso che abbiamo trattato in precedenza non si può esprimere in forma chiusa; pertanto non puoi trovare una formula che copra tutti i casi possibili. In questo caso o devi fare i conti "a mano" per la verifica su un esempio test oppure ti fai stampare tutti gli [tex]$S_k$[/tex] e controlli che il tuo output [tex]$S$[/tex] sia effettivamente il minimo.

Poi, che significa confrontare la complessità col risultato dell'algoritmo? Sono due cose differenti!
È un po' come confrontare le mele con le pere, quando ti insegnano dalle elementari che questo non si fa!

[Lordofnazgul]

"gugo82":Vediamo se ho capito il problema: scelti [tex]$2n+1$[/tex] numeri a caso [tex]$x_0,\ldots ,x_{2n} \in \mathbb{R}$[/tex], poni:

[tex]$S_k:=\sum_{i=0}^{2n} |x_k-x_i|$[/tex] per [tex]$k=0,\ldots ,2n$[/tex]

e vuoi determinare il valore [tex]$S:=\min \{S_k\}_{k=0,\ldots ,2n}$[/tex]. Giusto?

La sommatoria cui pervieni nel caso che abbiamo trattato in precedenza non si può esprimere in forma chiusa; pertanto non puoi trovare una formula che copra tutti i casi possibili. In questo caso o devi fare i conti "a mano" per la verifica su un esempio test oppure ti fai stampare tutti gli [tex]$S_k$[/tex] e controlli che il tuo output [tex]$S$[/tex] sia effettivamente il minimo.

Poi, che significa confrontare la complessità col risultato dell'algoritmo? Sono due cose differenti!
È un po' come confrontare le mele con le pere, quando ti insegnano dalle elementari che questo non si fa!

eh lo so ma il problema è che della parte matematica non ci capisco tanto cioè sostanzialmente io ho pensato di scrivere un algoritmo che mi calcola la media di quei numeri e mi stampa a video l'elemento più vicino alla media (cioè che minimizza A - media) il problema mio è che non riesco a capire come fare a dimostrare che funziona... cioè l'algoritmo che ho scritto è lineare, è il tempo peggiore di esecuzione è $O(n)$
come faccio a dimostrare che il mio algoritmo effettivamente funziona??? io pensavo appunto di trovare la complessità dell'algoritmo, esaminare i dati che avevo all'inizio, e pensavo che mi spuntasse fuori qualcosa nell'ordine di n, invece mi sa di no vero???