Diario di Marco Pagnin

Sui flussi

Posted by Marco Pagnin On Dicembre 27, 2016 Filed under Ricerca Operativa

...che poi i flussi, spogliati dei formalismi, non sono mica così difficili da capire.

La dico con parole mie, parole semplici.

Il problema del massimo flusso si applica a un grafo orientato (ciascun arco ha un verso) in cui esistono due nodi "speciali", detti sorgente e pozzo, in cui rispettivamente sono presenti solo archi uscenti (sorgente) e solo entranti (pozzo).
Formalmente:

Il grafo è denominato G(V,E). La denominazione è standard: G indica il grafo, V l'insieme dei vertici, E l'insieme degli archi.
Gli archi si chiamano s (sorgente), t (pozzo), poi gli altri sono numerati progressivamente
Un arco è indicato da due numeri tra parentesi separati da virgola; l'ordine determina il verso. Per esempio, (2,3) è l'arco che va dal nodo 2 al nodo 3.
(u,v) ∈ ω^-(v) indica l'insieme dei nodi che entrano in v
(v,k) ∈ ω⁺(v) indica l'insieme dei nodi che escono da v

Ogni arco è caratterizzato da una capacità e da un flusso, e il flusso non può mai eccedere la capacità. Si può immaginare un tubo in cui, senza cambiare la pressione, può passare una quantità massima di acqua; da zero al massimo, il flusso può prendere qualsiasi valore (anche se negli esercizi è sempre un valore intero).
La somma di tutti i flussi entranti in un nodo è uguale alla somma dei flussi uscenti. Mantenendo la metafora, tanta acqua entra, tanta acqua esce.
Formalmente:

0≤x_uv≤c_uv (x è il flusso, c è la capacità)
$\sum_{(u, v) \in ω^{-} (v)} x_{u v} - \sum_{(v, k) \in ω^{+} (v)} x_{u v} = 0$ ∀v∈V-{s, t}

Esempio di flusso

Questo flusso è ammissibile, perché esistono un nodo s con soli archi uscenti e un nodo t con soli archi entranti, il flusso di ogni arco è compreso tra zero e la capacità; inoltre la somma di tutti i flussi entranti è uguale a quella di tutti i flussi uscenti per ciascun nodo (tranne s, t):

entra 0, esce 0
entra 1, esce 1
entra 1, esce 1
entra 1, esce 1

Esempio di quali valori considerare per verificare i flussi entranti e uscenti per il nodo 2

Il problema del massimo flusso consiste nel determinare il flusso massimo che può transitare attraverso gli archi del grafo, con le seguenti semplici regole:

un flusso può transitare lungo il verso della freccia se il flusso è minore della capacità. In questo caso, è possibile incrementare il flusso fino ad arrivare alla capacità massima.
un flusso può "transitare" in verso opposto rispetto alla freccia, a patto che "scali" un flusso esistente. In questo caso, si parla di "cammino aumentante"

Nel caso dell'esempio, è possibile incrementare il percorso P₁ = {s, (s,2), 2, (2,3), 3, (3,t), t}, poiché tutti gli archi hanno un flusso minore della capienza. Il nuovo risultato è:

Ora (s,2) è diventato impraticabile, perché il flusso è pari alla capienza.

Si può procedere con P₂ = {s, (s,1), 1, (1,4), 4...

ma poi, arrivati a 4 si trova un flusso pari alla capienza, per arrivare a T. Per fortuna, è possibile "togliere 1" al flusso (3,4) e procedere poi con (3,t):

P₂ = {s, (s,1), 1, (1,4), 4, (3,4), 3, (3,t), t}

Nella notazione del cammino aumentante, l'arco percorso al contrario è rappresentato secondo il suo verso, quindi anche se si va da 4 a 3, l'arco è rappresentato come (3,4).

Il nuovo risultato è:

Ora il flusso uscente da s è 3, e qualunque strada porta o a un arco diretto saturo (es. (s,2)) o a un arco inverso vuoto (es. (1,2)).

Se, partendo da s, consideriamo tutti gli archi che avrebbero ancora capacità, dividendo il grafo in due otteniamo il cosiddetto taglio a capacità minima. In questo esempio, (s,2) è escluso; (s,1) è incluso; (1,2) è escluso; (1,4) è incluso; (2,3) è escluso; (3,4) è escluso; ovviamente gli archi connessi con t sono tutti esclusi (altrimenti si potrebbe aumentare il flusso). Il totale dei flussi che escono dal taglio minimo per entrare nell'insieme del pozzo è uguale al totale del flusso uscente da s.

Esempio di compito (08/01/2015)

Il grafo è ammissibile, poiché tutti i nodi hanno flusso positivo e non maggiore della capacità; inoltre la somma dei flussi entranti è pari alla somma dei flussi uscenti per tutti i nodi tranne s e t.

Il grafo ha valore 9 [(s,1) = 8, (s,2) = 1, (s,5) = 0, la somma è 9].

Il grafo può essere incrementato per il percorso P₁ = {s, (s,1), 1, (1,t), t} di 2.

La nuova situazione è (la prima coppia è l'arco; la seconda è flusso/capacità; sono colorati gli archi cambiati)

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (1,5)
(s,5) = (0,4)
(1,2) = (4,7)
(2,5) = (5,7)
(2,3) = (0,9)
(3,5) = (0,2)
(5,4) = (0,2)
(5,t) = (5,8)
(1,4) = (0,3)
(3,4) = (0,2)
(4,t) = (0,5)

Può essere ancora incrementato per il percorso P₂ = {s, (s,2), 2, (2,3), 3, (3,4), 4, (4,t), t} di 2.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (3,5)
(s,5) = (0,4)
(1,2) = (4,7)
(2,5) = (5,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (0,2)
(5,t) = (5,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (2,5)

Può essere ancora incrementato per il percorso P₃ = {s, (s,5), 5, (5, t), t} di 3.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (3,5)
(s,5) = (3,4)
(1,2) = (4,7)
(2,5) = (5,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (0,2)
(5,t) = (8,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (2,5)

Può essere ancora incrementato per il percorso P₄ = {s, (s,2), 2, (2,5), 5, (5,4), 4, (4,t), t} di 2.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (5,5)
(s,5) = (3,4)
(1,2) = (4,7)
(2,5) = (7,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (2,2)
(5,t) = (8,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (4,5)

A questo punto, apparentemente non c'è più niente, perché (s,1) e (s,2) sono impraticabili e (5,u) ha tutti gli archi uscenti saturi. Ma usando il cammino aumentato, c'è una "via d'uscita" in (2,5)!
Può essere quindi ancora incrementato per il percorso P₅ = {s, (s,5), 5, (2,5), 2, (1,2), 1, (1,t), t)} di 1.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (7,8)
(s,2) = (5,5)
(s,5) = (4,4)
(1,2) = (3,7)
(2,5) = (6,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (2,2)
(5,t) = (8,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (4,5)

A questo punto tutti gli archi uscenti da s sono saturi, quindi è immediatamente evidente che si è arrivati al flusso massimo, che corrisponde a 21.
Il taglio a capacità minima è costituito solo da s.

Distribuzione binomiale

Posted by Marco Pagnin On Dicembre 11, 2016 Dicembre 11, 2016 Filed under Probabilità & statistica

Quando si usa

Conosciamo la composizione della popolazione
Si può dividere in due nettamente la popolazione
C’è reinserimento

Esempi

Si consideri un'urna contenente quattro elementi, la cui probabilità di estrazione è

$X = {\frac{1}{2/7} \frac{2}{2/7} \frac{3}{2/7} \frac{4}{1/7}}$

in alternativa si possono considerare due biglie 1, due biglie 2, due biglie 3 e una sola biglia 4 (oppure 4, 4, 4, 2...).
Le biglie 1 e 2 sono bianche; le biglie 3, 4 sono rosse
Qual è la probabilità che si estragga una biglia bianca facendo 3 estrazioni?

Formula

n = numero di estrazioni
p = probabilità che si verifichi un successo
X˜B_p(n, p) = distribuzione binomiale (B) per n estrazioni con p probabilità
k = insieme di estrazioni, da 0 a n

$P (X = k) = (\binom{n}{k}) p^{k} {(1 - p)}^{n - k}$

Soluzione dell'esempio

p = 4/7 (la probabilità che esca il bianco)
n = 3 (il numero di estrazioni)

$P (S_{3} = 2) = (\binom{3}{2}) {(\frac{4}{7})}^{2} {(\frac{3}{7})}^{3 - 2} = 3 * \frac{16}{49} * \frac{3}{7} \approx 0,41982$

Distribuzione ipergeometrica

Posted by Marco Pagnin On Dicembre 11, 2016 Dicembre 19, 2016 Filed under Probabilità & statistica

Quando si usa

Conosciamo la composizione della popolazione
Si può dividere in due nettamente la popolazione
Non c'è reinserimento

Esempi

Un software consiste di 12 programmi, 5 dei quali necessitano di un upgrade. Se vengono scelti a caso 4 programmi per un test. Qual è la probabilità che almeno 2 di essi siano da aggiornare? Qual è il numero medio di programmi da aggiornare tra i 4 scelti?

Formula

X = Variabile aleatoria che conta il numero di successi
n = numero di estrazioni
N = numero di elementi
K = numero di elementi "successo" (successo significa che è vero per il criterio. Per es. se cerchiamo un bug in un programma, "successo" significa che è stato trovato)
X˜I_p(N, K, n) = distribuzione ipergeometrica (I) in N campioni di K successi per n estrazioni
k = ciascuno dei numeri compresi tra max{0, n-(N-K)} e min{n, K}.
max{0, n-(N-K)} significa che se faccio più estrazioni di quanti siano i casi di non-successo, sono sicuro di estrarre almeno un successo (es. bianco = successo, rosso = insuccesso; ho un'urna con 4 bianche e 5 rosse, faccio 6 estrazioni)
min{n, K} il ragionamento è analogo

$P (X = k) = \frac{(\binom{K}{k}) (\binom{N - K}{n - k})}{(\binom{N}{n})}$

Soluzione dell'esempio

N = 12 (il numero di programmi della popolazione)
n = 4 (il numero di estrazioni)
K = 5 (il numero di successi)
X ≥ 2 (almeno due casi di successo, richiede il maggiore/uguale)

P(X≥2) = P(X≤1) = 1 - (P(X=0) + P(X=1))

$1 - \frac{(\binom{5}{0}) (\binom{12 - 5}{4 - 0})}{(\binom{12}{4})} - \frac{(\binom{5}{1}) (\binom{12 - 5}{4 - 1})}{(\binom{12}{4})} = 1 - \frac{(\binom{7}{4})}{(\binom{12}{4})} - \frac{5 (\binom{7}{3})}{(\binom{12}{4})}$

Dal momento che un coefficiente binomiale si calcola così:

$(\binom{m}{n}) = \frac{m!}{n! (m - n)!}$

e che

$(\binom{m}{0}) = 1$

e che

$(\binom{m}{1}) = m$

otteniamo che

$(\binom{7}{4}) = 35$
$(\binom{7}{3}) = 35$
$(\binom{12}{4}) = 495$

Con qualche passaggio otteniamo:

$1 - \frac{35}{495} - \frac{5 * 35}{495} = \frac{19}{33}$

Variabili aleatorie continue

Posted by Marco Pagnin On Dicembre 11, 2016 Filed under Probabilità & statistica

Mentre le variabili discrete (in cui il campione può essere solo un numero intero, come il lancio di un dado o il numero di pecore) si possono studiare una ad una, anche se il numero può velocemente diventare immenso (es. la probabilità di vincere al lotto) e il campione può essere infinito, le variabili continue hanno un tipo di infinito legato a una proprietà dell'insieme ℚ che si estende a ℝ: c'è sempre un numero tra due numeri distinti.

Per questo, gli strumenti per affrontare il calcolo delle probabilità di un evento esprimibile in modo continuo (es. la distanza tra due auto) devono essere diversi.
Un ruolo chiave ha l'integrale: se alle elementari si spiega la statistica con torte e fette (che non sono altro che integrali in coordinate polari), all'università si rispolverano quegli integrali che - o perché la funzione ha un dominio limitato o perché l'integrale è improprio, arrivano comunque ad avere una superficie di 1.

Infatti nel calcolo della probabilità una delle caratteristiche dell'integrale è che non può mai avere valori negativi. Che senso avrebbe, infatti, una probabilità negativa? Per questo è possibile considerare un integrale alla stregua di un'area - cosa che in analisi non si può fare - in cui due punti distinti x₁ e x₂ appartenenti al dominio denotano un'area che rappresenta la probabilità che l'esito della variabile sia compreso tra x₁ e x₂. Questa superficie si chiama densità di probabilità.

La funzione di ripartizione P(x) indica la probabilità da 0 a x, con x ∈ [0, 1]. Dal momento che, come già detto, la funzione integranda non può assumere mai valori negativi, la funzione di ripartizione è sempre crescente e li limite di P(x) per x tendente a -∞ è 0 e il limite per x tendente a +∞ è 1. Infine, P(x) è continua a destra.

Varianza

Parliamo di varianza. La varianza è un indice di quanto gli esiti si differenzino dalla media. Per esempio, se lancio un dado tre volte e ottengo 2, 4, 6, poi ripeto l'esperimento e ottengo 4, 4, 4, la media in entrambi i casi è 4, ma la varianza è diversa. Se sommassi semplicemente gli scarti tra la media e ciascun esito, otterrei zero in entrambi i casi (-2 + 0 + 2 e 0 + 0 + 0).
La varianza si calcola facendo la differenza tra due elementi: il primo è la somma di tutti i quadrati dell'esito per la probabilità che possa verificarsi (nel nostro esempio, 2²*1/6 + 4²*1/6 + 6²*1/6, raccogliendo 1/6 si ottiene (2² + 4² + 6²) * 1/6, cioè 56/6 = ˜9,33333. L'altro elemento è il quadrato del valore atteso.
Il valore atteso è la somma degli esiti possibili per ciascuna probabilità: 1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6. In questo caso specifico, ogni esito ha una probabilità uguale a quella degli altri, quindi si può raccogliere 1/6 e scrivere (1+2+3+4+5+6)/6 = 3,5.
La varianza di questo caso è 9,33333 - 3,5 = 5,83333.

Nel caso di una variabile continua, occorre trovare la differenza tra due integrali, uno che rappresenta la superficie associata al quadrato della variabile e l'altro al quadrato di tutto l'integrale. Si ottiene questa formula:

$\int_{A} x^{2} f (x) dx - {(\int_{A} x f (x) dx)}^{2}$
dove A è lo spazio campionario.

Moda

La moda di una variabile aleatoria discreta è molto semplice da calcolare: è il valore (o i valori) più ricorrente.

La moda di una V.A. continua è data dal massimo assoluto (o dai massimi, se più di uno) della funzione.

Mediana e quantili

La mediana è il valore a metà dello spazio campionario. Se lo spazio è discreto ed è composto da un numero pari di elementi, se ne prende la media dei due centrali.

Esempio 1: un dado ha come esiti possibili 1, 2, 3, 4, 5, 6; la mediana è data dalla media di 3 e 4, cioè 3,5.
Esempio 2: le età dei colleghi dell'ufficio sono {24, 30, 33, 45, 55, 62, 65}. La mediana è il valore centrale (45)

Un quantile è il valore che si trova con una suddivisione diversa dalla metà. Per esempio, il percentile rappresenta ciascuno degli elementi che si trovano a cavallo tra 1/100 del campione e il campione successivo (es. il valore a metà tra 34/100 e 35/100)

Riflessioni sulla probabilità

Posted by Marco Pagnin On Dicembre 3, 2016 Filed under Probabilità & statistica

Quante probabilità ci sono di fare 6 lanciando un dado non truccato una volta?

Una su sei! Questo è ovvio. E quante probabilità ci sono di fare 6 lanciandolo due volte? Se lanciandolo una volta è 1/6, lanciandolo due volte sarà 1/6 + 1/6, cioè 2/6.

E invece no. Se lanciassimo un dado sei volte, infatti, ci sarebbero 6/6 probabilità di ottenere 6, e l'esperienza ci insegna che non è così. In realtà, la probabilità di ottenere un sei lanciando un dado sei volte è un po' meno di 2/6, così come lanciandolo tre volte è minore di 3/6 e così via. In questo modo si arriva a lanciare 6 volte un dado e a ottenere una probabilità alta, ma non certa, di ottenere un sei.

OK, questo corrisponde all'esperienza, ma allora qual è il ragionamento corretto da fare?
Facendo un rapido conteggio, le probabilità che esca sei con un lancio sono 1/6 (˜0,33333):

Ma se lancio due dadi le probabilità che venga fuori almeno un sei sono 11/36 (˜0,30555):

In pratica, considero un esito positivo solo la coppia di sei, che pesa per 1/36 sugli esiti.
Cosa succede se lancio un dado tre volte? E se lo lancio 1000 volte?
Se lo lancio tre volte posso ancora contare, su 216, il numero di esiti da "scartare", che sono quelli in cui il 6 compare due o più volte, da considerare come un esito solo: 1 6 1, 1 6 2, 1 6 3, ... , 6 6 6. Ma quanti sono? Il conto diventa un po' impegnativo.

Conviene invece contare gli esiti negativi e sottrarli da 1. Così nel caso di un lancio 1/6 deriva da 1-5/6, mentre il caso di 11/36 (numero un po' più "difficile") deriva da uno meno le probabilità che NON esca il sei: 5/6 * 5/6 = 25/36.
Con tre lanci, il numero di probabilità che NON esca 6 è di 5/6 * 5/6 * 5/6 = 125/216, quindi le probabilità che esca un sei sono 1-(125/216) = 91/216 = (˜0,42130).
Con mille lanci, la probabilità che non esca mai il sei è 1 - 5^1000 / 6^1000 = 6,58800 preceduto da 80 zeri (0,00000000000000000000000000000000000000000000000000000000000000000000000000000000658800).
Improbabile, ma non impossibile.

Concludo con una considerazione. Il lancio delle monete non ha memoria, per cui l'esito precedente non influenza in alcun modo quello successivo. Ma in questo ragionamento, il fatto che esca un sei al primo lancio influenza l'esito del lancio successivo: se esce sei, il secondo lancio è ininfluente!

1 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
2 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
3 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
4 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
5 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
6 => 1 di probabilità (100%) che tra il primo e il secondo esca almeno un 6

Formalismi e cavolate

Posted by Marco Pagnin On Novembre 18, 2016 Filed under Ricerca Operativa

Le matrici spaventano, questo da sempre.

Però se si fanno gli esempi giusti, tutto sommato (∑) non sono neanche impossibili.

Esercizi di probabilità

Posted by Marco Pagnin On Novembre 9, 2016 Novembre 9, 2016 Filed under Probabilità & statistica

Esercizi per il corso di Probabilità e Statistica

Foglio 1: Statistica descrittiva

Esercizio 1

Per ognuna delle seguenti variabili si dica se si tratta di una variabile quantitativa (discreta o continua) o qualitativa (nominale o ordinale):

l'età degli studenti in questo corso;
i programmi preferiti dalle studentesse di questo corso;
il numero degli studenti di questo corso che guardano la trasmissione "X Factor";
le spese di trasporto sostenute dagli studenti di questo corso;
il voto riportato all'esame di matematica;
l'aver superato l'esame di matematica.

Risposte

continua
nominale
discreta
discreta
discreta

Esercizio 2

Il docente di un corso universitario ha raccolto alcuni dati sugli studenti che hanno sostenuto il suo esame. La tabella riporta i dati relativi ai primi quattro studenti.

Voto	Anno di corso	Residenza	Diploma Sup. Frequentante
28	I	Treviso	Liceo S
21	IV	Venezia	Ist. Tecnico N
18	I	Verona	Ist. Comm. S
21	II	Padova	Ist. Prof. S

Qual è l'unità statistica? Qual è la popolazione di riferimento?
Quali caratteri (variabili) sono rilevati?
Quali sono le modalità rilevate del Diploma Superiore?
Quali sono le modalità rilevate del Voto e quali quelle possibili?

Risposte

L'unità statistica è lo studente e la popolazione è l'insieme degli studenti che hanno superato l'esame.
Sono rilevati il voto, l'anno di corso, la residenza e il diploma di scuola superiore
Le modalità rilevate del diploma superiore sono: Liceo S, Ist. Tecnico N, Ist. Comm. S, Ist. Prof. S...
Le modalità rilevate del voto sono ins, 18, 19, 20,... 30, 30L (non è specificato che l'esame sia superato)

Esercizio 3

In un gruppo di 20 persone sono state rilevate due variabili, il sesso e l'età

47 61 38 40 26 41 49 65 53 55
F  M  M  M  F  M  F  F  M  F
30 23 34 33 40 21 65 32 47 50
M  F  M  F  M  M  M  F  F  F

Si costruisca la distribuzione per classi dell'età (utilizzando le classi 19-29, 30-44, 45-59, 60 e oltre) e si calcolino le frequenze assolute, relative, percentuali, le cumulate e le densità di frequenza. Si disegni un opportuno istogramma.
Si rappresenti la funzione di ripartizione empirica e se ne calcoli il valore nel
punto 57.
Si disegni il diagramma a scatola con baffi, partendo dai dati originari.
Si calcolino media, varianza, scarto quadratico medio, campo di variazione,
scarto interquantile e coefficiente di variazione.
Si chiamino yi i valori originari e zi quelli standardizzati: si trovino media e
varianza degli zi attraverso le corrispondenti quantità degli yi.

Risposte

freq. ass f. rel. % ass. cum rel. cum dens.

19-29 3 0,15 15 3 0,15 0,3

30-44 8 0,4 40 11 0,55 ˜0,57

45-59 6 0,3 30 17 0,85 ˜0,43

60+ 3 0,15 15 20 1 0,6

Grafico:
Grafico della ripartizione empirica:

Ripartizione empirica = frequenza relativa di unità con valore ≤ x.
La ripartizione empirica di 57 è 0,85.
Grafico:
Dati A = l'insieme dei valori; n = il numero di elementi in A; A(i) l'i-esimo elemento di A (i ∈ ℕ):
- media
  $\frac{\sum_{i = 1}^{n} A (i)}{n}$ Usando R, si ottiene che mean(A) = 42,5
- varianza
  $\frac{\sum_{i = 1}^{n} {(A (i) - media (A))}^{2}}{n}$ La media dei quadrati è 1973,2, il quadrato della media è 1806,25, quindi la varianza è 166,95
- scarto quadratico medio (radice della varianza): ˜12,92
- campo di variazione: la differenza tra il valore più alto (65) e il più basso (21): 65-21 = 44
- scarto interquantile: differenza tra il terzo e il primo quartile. [21 23 26 30 32] [33 34 38 40 40] [41 47 47 49 50] [53 55 61 65 65] 50-32 = 18
- coefficiente di variazione ⇒?

	freq. ass	f. rel.	%	ass. cum	rel. cum	dens.
19-29	3	0,15	15	3	0,15	0,3
30-44	8	0,4	40	11	0,55	˜0,57
45-59	6	0,3	30	17	0,85	˜0,43
60+	3	0,15	15	20	1	0,6

Esercizio 4

L'assistenza tecnica di un rivenditore di computer ha registrato le richieste di intervento in un particolare giorno. Il risultato è stato:

H,H,M,S,H,M,M,S,H,S,S,M,H,M,M,S,M

dove H=problemi hardware, S=problemi software, M=guasto monitor.

Calcolare la distribuzione delle frequenze assolute e relative; disegnare il diagramma a barre;
calcolare un indice di posizione opportuno

Risposte

F. ass. F. rel

H 5 ˜0,29

S 5 ˜0,29

M 7 ˜0,41
L'indice di posizione opportuno è la moda, il cui valore è M (guasto al monitor)

	F. ass.	F. rel
H	5	˜0,29
S	5	˜0,29
M	7	˜0,41

Esercizio 5

Nella tabella sottostante sono riportati i consumi (in milioni di tonnellate) di risorse naturali impiegate nell'economia italiana nel quinquennio 2000-2004 e le importazioni delle medesime risorse nello stesso arco temporale.

             2000     2001     2002       2003     2004
Fabbisogno      2.357    2.295    2.214      2.077    2.184
Importazioni  329.028  330.035    334.807  343.784  360.282

Si rappresentino graficamente i dati;
si calcolino la covarianza e il coefficiente di correlazione e si dia un'interpretazione dei risultati.

Esercizio 6

Il responsabile della sicurezza di una grossa azienda ha rilevato il numero di tentativi di intrusione bloccati ogni giorno durante i primi 14 giorni del mese:

56 47 49 37 38 60 50 43 43 59 50 56 54 58

Dopo aver cambiato le impostazioni del firewall, le intrusioni bloccate nei 20 giorni
successivi sono state

53 21 32 49 45 38 44 33 32 43 53 46 36 48 39 35 37 36 39 45

Al fine di valutare l'efficacia delle nuove impostazioni, si confrontino il numero di tentativi di intrusione bloccati prima e dopo il cambio, calcolando il summary dei dati, tracciando i boxplot appaiati e commentando i risultati ottenuti.

Esercizio 7

I dati seguenti rappresentano il numero di registrazioni di nuovi account in dieci giorni consecutivi ad un sito di vendite online:

43 37 50 51 58 105 52 45 45 10

Calcolare media, mediana, quartili e deviazione standard.
Trovare gli outlier (osservazioni anomale) usando la regola 1:5Xdistanza interquartile.
Eliminare gli outlier trovati e calcolare nuovamente media, mediana, quartili e scarto quadratico medio.
Trarre delle conclusioni sull'influenza degli outlier sugli indici calcolati.

Esercizio 8

Un provider vuole valutare il carico della sua rete e registra il numero di utenti (in migliaia di persone) connessi contemporaneamente in 50 luoghi:

17.2 22.1 18.5 17.2 18.6 14.8 21.7 15.8 16.3 22.8
24.1 13.3 16.2 17.5 19.0 23.9 14.8 22.2 21.7 20.7
13.5 15.8 13.1 16.1 21.9 23.9 19.3 12.0 19.9 19.4
15.4 16.7 19.5 16.2 16.9 17.1 20.2 13.4 19.8 17.7
19.7 18.7 17.6 15.9 15.2 17.1 15.0 18.8 21.6 11.9

Calcolare la media campionaria, la varianza e lo scarto quadratico medio dei dati rilevati.
Calcolare il summary e costruire il boxplot.
Calcolare lo scarto interquantile. Sono presenti delgli outliers?
Tracciare un istogramma e commentare la simmetria della distribuzione.

Il gergo delle probabilità

Posted by Marco Pagnin On Novembre 6, 2016 Filed under Probabilità & statistica

Ω

Ω rappresenta l'insieme dei possibili risultati. La probabilità di tutti gli eventi che appartengono a Ω è 1.

ω

ω rappresenta un elemento dell'insieme Ω, cioè l'esito di un singolo evento.

$\overset{----}{Ω}$

$\overset{----}{Ω}$ è l'insieme complementare di Ω, cioè un evento impossibile. Qualunque insieme con una "barretta" sopra è l'insieme degli esiti diversi dall'insieme rappresentato. Si può rappresentare anche con 1 - P(A), cioè 1 meno la probabilità che si verifichi un evento di A

P(A)

P(A), con A ⊆ Ω è la probabilità che si verifichi uno degli eventi dell'insieme A.

P(A_i) è la probabilità che si verifichi l'i-esimo elemento dell'insieme A. A volte, senza tirare in ballo l'insieme A, si indica con p_i

Compitino ASD 20/01/2016 / 3

Posted by Marco Pagnin On Novembre 3, 2016 Novembre 3, 2016 Filed under Algoritmi e strutture dati

Si definiscano formalmente le relazioni O, Ω, Θ, o, ω e si dimostri la verità o la falsità di ciascuna delle seguenti affermazioni, giustificando formalmente le risposte:

Se P(n) è un polinomio di grado k, allora P(n) = Θ(n^k)
n = O(n log log n)
n log log n = O(n^1+ε), per ogni ε > 0
f(n) = O(g(n)) se e solo se g(n) = Ω(f(n))
ω(f(n)) ∩ O(g(n)) = ∅

Definizioni

O(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) ≤ cf(n) ∀ n ≥ n₀}

O(f(n)) significa che esiste una funzione g(n) tale che, data una costante c maggiore di zero e un parametro zero n₀maggiore o uguale a zero, g(n) è minore o uguale a f(n) per la costante per ogni n maggiore o uguale a n_0.

Ω(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) ≥ cf(n) ∀ n ≥ n₀}

Analogamente, o(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) < cf(n) ∀ n ≥ n₀} e ω(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) > cf(n) ∀ n ≥ n₀}

Θ(f(n)) = {g(n) : ∃ c₁ > 0, c₂ > 0, n₀ ≥ 0, c₁f(n) ≤ g(n) ≤ c₂f(n) ∀ n ≥ n₀}

ovvero, scelte due costanti diverse e maggiori di zero, per una costante vale O(f(n)) e per l'altra vale Ω(f(n)).

Se P(n) è un polinomio di grado k, allora P(n) = Θ(n^k)

Vero, poiché per la definizione di Θ, Θ(n^k) = {g(n) : ∃ c₁ > 0, c₂ > 0, n₀ ≥ 0, c₁f(n) ≤ g(n) ≤ c₂f(n) ∀ n ≥ n₀}.

Asintoticamente, i termini di grado inferiore a k si possono omettere, perché per ogni h < k, si ha che

$\lim_{n \to \infty} \frac{n^{k}}{n^{h}} = 0$

Dunque, in un polinomio nella forma c_in^k+c_iin^k-1+c_iiin^k-2+ ... + c_in, basta considerare il termine di grado più alto (c_in^k) e prendere un c₁ < c_ie un c₂ > c_i

n = O(n log log n)

L'uguaglianza è vera se, per la definizione di O(n), n ≤ n log log n; dividendo entrambi i termini per n, si ottiene che 1 ≤ log log n, che è vero per tutti gli n ≥ e^2

n log log n = O(n^1+ε), per ogni ε > 0

n^1+εsi può scrivere anche n * n^ε, in questo modo è possibile dividere per n entrambi i membri. L'uguaglianza è verificata se log log n ≤ n^εper ogni ε > 0.

L'uguaglianza si può dire verificata se è vero che:

$\lim_{n \to \infty} \frac{n^{ε}}{log log n} = 0$

Ma applicando de l'hôpital, vediamo che

$\lim_{n \to \infty} \frac{ε n^{ε - 1}}{\frac{1}{n log n}} = \lim_{n \to \infty} \frac{ε n^{ε - 1} * n log n}{1}$

che tende a +∞.

La risposta alla domanda è quindi che non è possibile generalizzare l'equivalenza per ogni ε > 0.

f(n) = O(g(n)) se e solo se g(n) = Ω(f(n))

Vero, è la proprietà della simmetria trasposta.

ω(f(n)) ∩ O(g(n)) = ∅

Falso.

Per definizione (condizioni al contorno omesse), ω(f(n)) = {g(n) > cf(n)} e O(g(n)) = {f(n) ≤ cg(n)}, quindi g(n) > cf(n) ∩ f(n) ≤ cg(n) ⇒ f(n) < cg(n), che è esattamente ω(f(n)).

RO: prova intermedia 2015-2016 / 1

Posted by Marco Pagnin On Ottobre 30, 2016 Filed under Ricerca Operativa

Tema

Con l'avvicinarsi delle festività natalizie la pasticceria Tànalo deve preparare cioccolate di 2 tipi (tipo I e tipo II). Inoltre ciascun tipo di cioccolata viene prodotto con 4 qualità diverse, a seconda della percentuale di burro di cacao presente. La produzione viene pianificata sulla base delle informazioni relative agli anni precedenti, riassunte come segue:

la quantità complessiva delle qualità 1 e 2 delle due cioccolate, deve essere non inferiore alla quantità complessiva delle qualità 3 e 4 delle due cioccolate;
la somma delle (quantità di) qualità 1 e 2 del cioccolato I, non può essere inferiore alla somma delle (quantità di) qualità 3 delle cioccolate I e II;
la quantità complessiva di cioccolato prodotta deve essere compresa tra i 600 Kg ed i 750 Kg;
in base a vincoli sulla disponibilità di materie prime, la pasticceria deve anche rispettare una ed una soltanto delle seguenti limitazioni:
- la quantità della qualità 1 per il cioccolato di tipo I, non può superare la quantità della qualità 1 del cioccolato di tipo II;
- la quantità della qualità 4 per il cioccolato di tipo I, non può superare la quantità della qualità 4 del cioccolato di tipo II;
se si produce la qualità j (j ∈ {1, 2, 3, 4}) del cioccolatino i (i ∈ {1, 2}), allora bisogna pagare un costo di acquisizione di un nuovo macchinario, pari a 260 Euro.

Sapendo che ogni Kg di cioccolatini del tipo I costa 9 Euro ed ogni Kg di cioccolatini del tipo II costa 10 Euro, formulare un modello di PL/PLI per la minimizzazione dei costi, dal quale si desuma la quantità di cioccolato di ciascun tipo e ciascuna qualità da produrre.

Svolgimento

La pasticceria produce due prodotti (Prod1, Prod2), ciascuno ha quattro percentuali di burro di cacao (Perc1, Perc2, Perc3, Perc4). I prodotti si possono indicare come x_{i, j}, in cui i indica il prodotto e j la percentuale di burro di cacao

	Perc1	Perc2	Perc3	Perc4
Prod1	x_{1, 1}	x_{1, 2}	x_{1, 3}	x_{1, 4}
Prod2	x_{2, 1}	x_{2, 2}	x_{2, 3}	x_{2, 4}

la quantità complessiva delle qualità 1 e 2 delle due cioccolate, deve essere non inferiore alla quantità complessiva delle qualità 3 e 4 delle due cioccolate:

	Perc1	Perc2	Perc3	Perc4
Prod1	x_{1, 1}	x_{1, 2}	x_{1, 3}	x_{1, 4}
Prod2	x_{2, 1}	x_{2, 2}	x_{2, 3}	x_{2, 4}

Il vincolo si esprime con x_{1, 1} + x_{1, 2} + x_{2, 1} + x_{2, 2} >= x_{1, 3} + x_{1, 4} + x_{2, 3} + x_{2, 4}

la somma delle (quantità di) qualità 1 e 2 del cioccolato I, non può essere inferiore alla somma delle (quantità di) qualità 3 delle cioccolate I e II;

	Perc1	Perc2	Perc3	Perc4
Prod1	x_{1, 1}	x_{1, 2}	x_{1, 3}	x_{1, 4}
Prod2	x_{2, 1}	x_{2, 2}	x_{2, 3}	x_{2, 4}

Il vincolo si esprime con x_{1, 1} + x_{1, 2} >= x_{1, 3} + x_{2, 3}

la quantità complessiva di cioccolato prodotta deve essere compresa tra i 600 Kg ed i 750 Kg

Il vincolo si esprime con 600 Kg <= Peso(x_{1, 1} + x_{1, 2} + x_{2, 1} + x_{2, 2} + x_{1, 3} + x_{1, 4} + x_{2, 3} + x_{2, 4}) <= 750 Kg

in base a vincoli sulla disponibilità di materie prime, la pasticceria deve anche rispettare una ed una soltanto delle seguenti limitazioni:

la quantità della qualità 1 per il cioccolato di tipo I, non può superare la quantità della qualità 1 del cioccolato di tipo II;
la quantità della qualità 4 per il cioccolato di tipo I, non può superare la quantità della qualità 4 del cioccolato di tipo II;

Il vincolo si esprime con ((x_{1, 1} < x_{1, 2}) ⋃ (x_{1, 4} < x_{2, 4})) ¬ ((x_{1, 1} < x_{1, 2}) ∩ (x_{1, 4} < x_{2, 4}))

se si produce la qualità j (j ∈ {1, 2, 3, 4}) del cioccolatino i (i ∈ {1, 2}), allora bisogna pagare un costo di acquisizione di un nuovo macchinario, pari a 260 Euro.

In questo caso creiamo una variabile on/off, che vale 1 se il prodotto è uno di quelli "nuovi" e 0 se non lo è:
y_{i, j}, dove anche in questo caso i è il tipo di prodotto e j la quantità di burro di cacao.

y_{i, j} vale 1 se i ∈ {1, 2} e j ∈ {1, 2, 3, 4}, zero altrimenti.

min 9(x_{1, 1} + x_{1, 2} + x_{1, 3} + x_{1, 4}) + 10(x_{2, 1} + x_{2, 2} + x_{2, 3} + x_{2, 4}) + 260(x_{1, 1} + x_{1, 2} + x_{2, 1} + x_{2, 2} + x_{1, 3} + x_{1, 4} + x_{2, 3} + x_{2, 4})

forma abbreviata:

$9 Σ_{j = 1}^{4} x_{1, j} + 10 Σ_{j = 1}^{4} x_{2, j} + 260 Σ_{i = 1}^{2} Σ_{j = 1}^{4} y_{i, j}$

From The Blog, Page 13

Esempio di flusso

Esempio di compito (08/01/2015)

Quando si usa

Esempi

Formula

Soluzione dell'esempio

Quando si usa

Esempi

Formula

Soluzione dell'esempio

Varianza

Moda

Mediana e quantili

Esercizi per il corso di Probabilità e Statistica

Foglio 1: Statistica descrittiva

Esercizio 1

Risposte

Esercizio 2

Risposte

Esercizio 3

Risposte

Esercizio 4

Risposte

Esercizio 5

Esercizio 6

Esercizio 7

Esercizio 8

Ω

ω

Ω----

P(A)

Definizioni

Se P(n) è un polinomio di grado k, allora P(n) = Θ(nk)

n = O(n log log n)

n log log n = O(n1+ε), per ogni ε > 0

f(n) = O(g(n)) se e solo se g(n) = Ω(f(n))

ω(f(n)) ∩ O(g(n)) = ∅

Tema

Svolgimento

$\overset{----}{Ω}$

Se P(n) è un polinomio di grado k, allora P(n) = Θ(n^k)

n log log n = O(n^1+ε), per ogni ε > 0