Costi di esecuzione (strutture dati) 27/05/2015

Posted by On Filed under Algoritmi e strutture dati, Tempi di esecuzione

Completare la seguente tabella indicando la complessità delle operazioni che si riferiscono a un dizionario di n elementi. Per l’operazione Successore si assuma di essere sull’elemento x a cui si applica l’operazione.

Ricerca Massimo Successore Minimo Costruzione
Albero binario di ricerca O(h) O(h) O(h) O(h) O(n)
Min-Heap O(log n) O(log n) O(log n) O(log n) O(n)

Nota: in un albero binario bilanciato, h è l'altezza dell'albero, che è uguale a log(n) per n compreso tra n^(h-1)+1 e n^h

I cinque algoritmi sui grafi da sapere

Posted by On Filed under Algoritmi e strutture dati

Kruskal, Prim, Dijkstra, Bellman-Ford, Floyd-Warshall

Kruskal

L'amico Kruskal vuole trovare l'albero (o gli alberi) che collega i vertici tramite gli archi più leggeri possibile.

Per fare questo, divide i vertici di un grafo in tanti sottoinsiemi quanti sono i vertici, poi ordina gli archi e considera le coppie di vertici partendo dall'arco più leggero: se i vertici appartengono allo stesso insieme, ignora l'arco; altrimenti aggiunge l'arco all'albero di copertura e unisce i due sottoinsiemi.

Il risultato è un albero di copertura minimo, il tempo di esecuzione è Θ(E log E).

_(, )
1.  ← ∅
2.  ℎ  ∈ []  //per [] intendiamo l’insieme dei vertici di 
3.   _() //abbiamo creato  insiemi, ognuno dei quali contiene un vertice
4.   ℎ        // tipico degli algoritmi Greedy
5.  ℎ (, ) ∈ []  //che sono ordinati
6.    _() ≠ _() ℎ
7.      ←  ∪ {(, )}
8.     (, )
9.

Prim

L'amico Prim vuole trovare l'albero (o gli alberi) che collega i vertici tramite gli archi più leggeri possibile.

Per fare questo, sceglie uno dei vertici e lo inserisce nell'albero, poi controlla quale tra gli archi adiacenti è il più leggero (o i più leggeri), aggiunge il vertice all'albero e gli attribuisce un peso pari all'arco. Se durante la visita un vertice è già stato visitato, ma ha un peso maggiore dell'arco corrente, si cambia l'arco connesso e si aggiorna il peso del vertice.

Il risultato è un albero di copertura minimo, il tempo di esecuzione è O(E V log V) a patto di utilizzare per l'archiviazione dell'elenco dei vertici uno heap di Fibonacci.

_(, , )
1.  ← [] //inizializziamo Q con tutti i vertici di G
2.  ℎ  ∈  
3.   [] = ∞
4. [] = 0
5. [] = 
6. ℎ  ≠ ∅ 
7.    ← _() //estrae il vertice con campo key minore
8.    ℎ  ∈ []  //per ogni vertice adiacente al vertice estratto
9.       ∈  && (, ) < [] ℎ
10.       [] ←  //u diventa il padre di v
11.       [] ← (, ) //aggiorna il valore di key e riorganizza l’heap
12.   = {(, []) |  ∈  \ {}}

Dijkstra

L'amico Dijkstra vuole raggiungere nel tempo/spazio minore un vertice partendo da un altro vertice.

Per fare questo, come l'amico Dijkstra, inizializza tutti i vertici con peso ∞ e parent = NIL, poi iniziando dal vertice sorgente imposta nei vertici adiacenti il peso degli archi. Se arriva a un vertice già esplorato, ma il peso del vertice è maggiore del vertice "nuovo padre" più l'arco che li congiunge, ne cambia il padre e aggiorna il peso del vertice (rilassamento).

Il risultato è un albero in cui ciascun vertice è collegato alla sorgente con il percorso più breve possibile. Il costo dipende dall'implementazione dell'elenco dei vertici, e segue questa tabella:

Grafo sparso Grafo denso
Array lineare O(n2) O(n2)
Heap binario O(n log n) O(n2 log n)

dove per "Grafo sparso" si intende un grafo in cui il numero di vertici e il numero di archi tende ad essere uguale E = Θ(V), mentre per "Grafo denso" si intende che E = Θ(V2).

NOTA: Dijkstra si incasina se ci sono archi con peso negativo.

__(, )
1.  ℎ  ∈ []
2.   [] ← +∞
3.   [] ← 
4. [] ← 0

(, , )
1.  [] > [] + (, ) ℎ
2.   [] ← [] + (, ) //aggiorna il peso del cammino da  a 
3.   [] ←  //aggiorna il predecessore

(, , )
1. __(, )
2.  ← ∅ //insieme dei vertici già estratti
3.  ← [] //vertici da estrarre
4. ℎ  ≠ ∅ 
5.    ← _()
6.    ←  ∪ {} // S si riempie
7.    ℎ  ∈ [] 
8.     (, , (, ))

Esempio

Grafo di test con sorgente = 1
  1. V(G) = {1};
    1. (1,2), π(2) = NIL → 1, d(2) = ∞ → 2;
    2. (1,3), π(3) = NIL → 1, d(3) = ∞ → 4
  2. V(G) = {1, 2, 3};
    1. i nodi esplorati sono:
      1. π(1) = NIL, d(1) = 0
      2. π(2) = 1, d(2) = 2
      3. π(3) = 1, d(3) = 4
    2. (2, 4), π(4) = NIL → 2, d(4) = ∞ → d(2) + 7 = 9
    3. (2, 3), π(3) = 1 → 2, d(3) = 4 → d(2) + 1 = 3
    4. (3, 5), π(5) = NIL → 3, d(5) = ∞ → d(3) + 3 = 6
  3. V(G) = {1, 2, 3, 4, 5}
    1. i nodi esplorati sono:
      1. π(1) = NIL, d(1) = 0
      2. π(2) = 1, d(2) = 2
      3. π(3) = 2, d(3) = 3
      4. π(4) = 2, d(4) = 9
      5. π(5) = 3, d(5) = 6
    2. (5, 4), π(4) = 2 → 5, d(5) = 9 → d(5) + 2 = 8
    3. (5, 6), π(6) = NIL → 5, d(6) = ∞ → d(5) + 5 = 11
    4. (4, 6), π(6) = 5 → 4, d(6) = ∞ → d(4) + 1 = 10

Bellman-Ford

Gli amici Bellman e Ford vogliono raggiungere nel tempo/spazio minore un vertice partendo da un altro vertice, ma in un grafo che può avere pesi negativi.

Uno dei motivi per cui i grafi con pesi negativi sono più incasinati di quelli con pesi solo positivi è che se c'è un ciclo e il suo bilancio è negativo (es. a→b = +2, b→a = -5) per ridurre il peso del cammino basta ciclare all'infinito il loop.

L'algoritmo è piuttosto semplice: per ogni vertice per ogni arco applica il rilassamento; poi controlla che per ogni arco il suo peso sia minore o uguale della somma del vertice più l'arco che li congiunge. In caso contrario è di fronte a un cappio con bilancio negativo e l'algoritmo si ferma restituendo falso.

Il costo dipende dal tipo di grafo, se sparso o denso:

Grafo sparso Grafo denso
Dijkstra - Array lineare O(n2) O(n2)
Dijkstra - Heap binario O(n log n) O(n2 log n)
Bellman-Ford O(n2) O(n3) 
_(, , )
1. __(, )
2.   = 1  |[]| − 1 
3.    ℎ (, ) ∈ [] 
4.     (, , (, ))
5.  ℎ (, ) ∈ [] 
6.    [] > [] + (, ) ℎ
7.      
8.

Floyd-Warshall

Gli amici Floyd e Warshall vogliono raggiungere nel tempo/spazio minore qualunque vertice partendo da un altro vertice qualunque, cioè vogliono calcolare tutti i percorsi minimi possibili.

In modo simile a una matrice M di adiacenza, creano una matrice n*n tale con w: E→R che per ogni cella i,j:

  • se i == j allora M[i, j] = 0
  • se i != j e (i, j) è un arco, allora M[i, j] = w(i, j)
  • se i != j e (i, j) non è un arco, allora M[i, j] = ∞

Per ogni vertice controllano se la somma di ciascun vertice entrante più ciascun vertice uscente ha un peso minore dell'arco diretto o del valore calcolato precedentemente.

Il costo spaziale di questo algoritmo è n2, perché abbiamo bisogno di iniziare con quella che - di fatto - è una matrice nxn di adiacenza. Il costo temporale dell'algoritmo è n3, perché per ogni arco (compresi quelli con valore ∞, cioè compresi gli archi "assenti", che quindi corrispondono a ogni coppia nxn) dobbiamo iterare ogni vertice.

Esempio

La matrice di partenza richiede che siano valorizzati tutti gli archi e che gli "auto-archi" siano impostati a zero.

A
DA 1 2 3 4
1 0 ∞ ∞ ∞
2 ∞ 0 ∞ ∞
3 ∞ ∞ 0 ∞
4 ∞ ∞ ∞ 0

Gli archi da nodo verso se stesso sono impostati a zero

1 2 3 4
1 0 3 ∞ 7
2 8 0 2 ∞
3 5 ∞ 0 1
4 2 ∞ ∞ 0

Gli altri archi sono riportati (senza calcoli). Gli archi rimanenti, che non esistono, sono impostati a infinito.

Passaggio vertice 1: si riportano gli zeri, tutta la riga 1 e tutta la colonna 1, poiché rappresentano archi diretti che non è neccessario calcolare.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 ∞ 7
2 8 0
3 5 0
4 2 0

Ora cerchiamo di calcolare il cammino da 2 a 3. L'arco diretto riporta il peso 2, dobbiamo capire se arrivare da 2 a 3 passando per 1 è più conveniente. (2,1) pesa 8, (1, 3) pesa infinito, 8+∞ = ∞, quindi ci conviene tenere l'arco diretto.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 ∞ 7
2 8 0 2
3 5 0
4 2 0

Ora cerchiamo di calcolare il cammino da 2 a 4. L'arco diretto riporta il peso ∞, dobbiamo capire se arrivare da 2 a 4 passando per 1 è più conveniente. (2,1) pesa 8, (1, 4) pesa 7, 8+7 = 15, quindi ci conviene passare per 1.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 ∞ 7
2 8 0 2 15
3 5 0
4 2 0

Da 3 a 2 l'arco diretto è ∞, mentre passando per 1 è 5+3 = 8, quindi cambiamo in 8.

Da 3 a 4 l'arco diretto è 1, mentre passando per 1 è 5+7 = 12, quindi teniamo 1.

Da 4 a 2 l'arco diretto è ∞, mentre passando per 1 è 2+3 = 5, quindi cambiamo in 5.

Da 4 a 3 l'arco diretto è ∞, mentre passando per 1 è 2+∞ = ∞, quindi lasciamo ∞.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 ∞ 7
2 8 0 2 15
3 5 8 0 1
4 2 5 ∞ 0

Partendo da questa tabella, si ripete per gli altri tre vertici.

_()
1.  ← [] //calcolo il numero di righe, ovvero il numero di vertici
2. 0 = 
3.   = 1  
4.     = 1   
5.       = 1   
6.       [,]() = min([,](−1) + [,](−1), [](−1))
7.

Alberi di copertura

Posted by On Filed under Algoritmi e strutture dati

Definizioni

Taglio

Un taglio è una suddivisione dell'insieme dei vertici V in due sottoinsiemi tali che V1∈G1 e V2∈G2, inoltre V1∩V2 = ∅ e V1∪V2 = V.

Attraversamento

Un arco E attraversa un taglio se E(u, v) con u∈G1 e v∈G2 cioè se i due vertici appartengono ciascuno a uno dei due insiemi determinati dal taglio.

Rispetto

Dato un sottoinsieme di vertici A ⊆ G si dice che un taglio rispetta l'insieme se nessuno dei suoi archi lo attraversa.

Arco leggero

Si dice leggero l'arco (o gli archi) che, dato un insieme di archi con una proprietà, ha il valore minimo per quella proprietà. Tipicamente si usa chiamare arco leggero quello con valore più basso tra quelli che attraversano un taglio.

Arco sicuro

Dato un grafo G con un taglio (S, V-S), un insieme A che sia rispettato dal taglio, un arco leggero che attraversa (S, V-S) è detto sicuro.

MST

Sta per Minimum Spanning Tree, o albero di copertura minimo. Rappresenta l'albero i cui archi sono quelli meno pesanti possibile.

Teorema fondamentale dei MTS

SIa G = (V, E) un grafo non orientato e connesso e sia w: E → R. Siano inoltre date le seguenti ipotesi:

  • A è un insieme di archi tale che A ⊆ E e che A ⊆ MST (che chiameremo T)
  • sia (S, V\S) un taglio che rispetta A, ovvero il taglio non attraversa alcun arco di A o viceversa;
  • sia (u,v) ∈ E, tale che sia leggero e che attraversa il taglio (S, V\S), ovvero che sia quello di peso minimo tra gli archi che attraversano il taglio

Allora l'arco (u,v) è sicuro per A.

Kruskal

L'algoritmo di Kruskal crea tanti alberi quanti sono i vertici, poi li unisce se non fanno parte della stessa foresta. L'unione avviene ordinando gli archi per peso dal più piccolo, così quando (se) avviene l'unione si memorizza l'arco sicuro di volta in volta.

  1. A = ∅; inizializza un insieme vuoto
  2. for each v in V, MAKE_SET(v); per ogni vertice nell'insieme dei vertici crea un albero (qui chiamato set)
  3. for E order by w; ordina gli elementi di E per peso (w = weight)
  4. for each e(u, v) in E
    1. if FIND_SET(u) ≠ FIND_SET(v); se non appartengono allo stesso albero
      1. A ← A ∪ {(u,v)}; si aggiunge l'arco all'insieme degli archi
      2. UNION(u, v); ora u e v fanno parte dello stesso albero
    2. ; se u e v appartengono allo stesso set non fa niente, perché appartengono già allo stesso albero

Domande

L'algoritmo converge? Sì, perché è composto solo da due cicli for, che per definizione convergono.

L'algoritmo è corretto? Sì, perché rispecchia quello che prescrive il teorema master degli MST.

Qual è la complessità dell'algoritmo?

1: O(1)

2: Θ(v) // inizializzazione

3: O(a log a) // ordinamento

4: O(a) // ciclo for

4.1: O(log a) // find set

4.2: O(1) // union

O(1) + O(v) + O(a log a) + O(a log a) + O(1) ⇒ O(a log a), dato che a domina su n e 1 è costante

Prim

L'algoritmo di Prim utilizza due strutture dati aggiuntive: per ogni vertice aggiunge un'informazione sul vertice "padre" π(v) e inserisce ogni vertice in un min-heap binario.

Inizializza tutti i vertici in modo che il loro peso sia ∞ e che i padri siano tutti NIL.
Poi estrae il vertice "root" e assegna 0 come peso.

A questo punto il vertice root non è più presente nell'heap (l'estrazione da un heap binario ha costo di Θ(n)).
A ogni vertice adiacente viene assegnato un peso pari all'arco che lo congiunge al nodo corrente, a meno che il vertice non abbia già un peso e che questo sia minore dell'arco.
Si estrae dall'heap l'elemento minore o - a parità di peso - uno a caso tra gli elementi minori.
Potrebbe succedere che lo stesso vertice sia visitato più volte, e che in una visita successiva l'arco abbia un peso minore di quello già attribuito al vertice. In questo caso, il vertice "cambia di padre" e gli viene assegnato il nuovo peso.
L'algoritmo di Prim è quindi

  1. Q ← V(G) // assegno all'heap i vertici di G
  2. foreach u ∈ Q, key(u) = ∞
  3. key(r) = 0

Visita di un grafo

Posted by On Filed under Algoritmi e strutture dati

Visita in ampiezza

La visita in ampiezza si basa sull'assegnazione a ogni vertice di un colore tra bianco, grigio e nero: il bianco indica che il vertice non è ancora stato visitato, il grigio indica che è stato visitato, ma non sono stati visitati tutti i suoi vertici adiacenti, il nero indica che è stato visitato il vertice e tutti i vertici adiacenti.

La visita in ampiezza sfrutta alcune strutture dati di appoggio:

  • il colore di un vertice è memorizzato in una lista in cui la chiave è il vertice e il valore è il colore: color[v]
  • il predecessore di un vertice è memorizzato in una lista in cui la chiave è il vertice e il valore è il predecessore: π[v]
  • la distanza dal vertice sorgente è memorizzata in una lista in cui la chiave è il vertice e il valore è un numero naturale: d[v]
  • l'elenco di vertici grigi è una coda FIFO: Q

L'algoritmo opera così:

  1. for each v in G inizializzazione dei vertici (tranne il sorgente)
    1. color[v] = white; imposto il colore bianco
    2. π[v] = NIL; il predecessore del vertice è vuoto
    3. d[v] = ∞; la distanza dalla sorgente è infinita
  2. inizializzazione del vertice sorgente
    1. color[s] = grey; imposto il colore grigio
    2. π[s] = NIL; il predecessore della sorgente è NIL (resterà così)
    3. d[s] = 0; la distanza dalla sorgente è zero (resterà così)
  3. Q ↞ s; aggiungo alla FIFO l'elemento sorgente
  4. while Q ≠ ∅, Q ↠ v; finché la coda Q non è vuota estraggo l'elemento in coda
      1. for each u = adj(v); per ogni vertice u adiacente a v
        1. if color[u] == white; se il colore di u è bianco
          1. color[u] = grey; imposta il colore grigio a u
          2. d[u] = d[v] + 1; la distanza di u è uno più di v
          3. π[u]= v; il predecessore di u è v
          4. Q ↞ u; accoda u all'elenco di vertici grigi
      2. color[v] = black; imposta il colore di v a nero

Il tempo di esecuzione di questo algoritmo è O(V+E), poiché ogni vertice e "toccato" una sola volta e ogni arco è "toccato" al massimo una volta.

Siccome se un nodo è già stato visitato non si visitano più i suoi archi, la visita in ampiezza crea, di fatto, un albero.

Visita in profondità

La visita in profondità inizia dal nodo sorgente e lo marca in grigio, poi non lo marca in nero finché non sono neri tutti i suoi successori, e così via ricorsivamente.

L'algoritmo ricorda il modo per uscire sempre da un labirinto (senza isole), che consiste nel procedere con una mano sempre appoggiata al lato (es. mano destra tocca sempre la parete destra).

L'algoritmo è composto da una parte di inizializzazione e lancio della parte ricorsiva e una seconda parte che richiama se stessa nei suoi sotto-vertici:

function DFS

  1. for each v in G inizializzazione dei vertici (tranne il sorgente)
    1. color[v] = white; imposto il colore bianco
    2. π[v] = NIL; il predecessore del vertice è vuoto
    3. time = 0; informazione sull'ordine di esecuzione
  2. for each v in adj(s) richiama la visita su ogni nodo adiacente
    1. if color[v] == white, DFG-visit(v)

function DFS-visit(v)

  1. color[v] = grey;
  2. time = time + 1;
  3. d[v] = time;
  4. for each u in adj(v)
    1. if color[u] == white
      1. π[u] = v;
      2. DFS-visit(u)
  5. color[v] = black;
  6. time = time + 1
  7. f[v] = time

Il tempo di esecuzione di questa funzione è Θ(V+E).

Una proprietà importante di questa visita è che l'ordine dei vertici visitati potrebbe ricalcare uno schema "a parentesi", cioè se apriamo una parentesi ogni volta che visitiamo un vertice e la chiudiamo ogni volta che finsice la visita, otteniamo una struttura a parentesi "ben formato".

Un'altra proprietà è che a seconda del colore che troviamo possiamo classificare gli archi:

  • se l'arco è collegato a un vertice white, abbiamo un arco dell'albero
  • se l'arco è collegato a un vertice grey, abbiamo un arco all'indietro
  • se l'arco(u, v) è collegato a un vertice black, abbiamo un arco in avanti (se d[u] < d[v]) o di attraversamento (se d[u] > d[v])

Topological sort

Utilizzando la DFS è possibile ordinare i vertici di un grafo in base all'ordine in cui sono disposti.

Grafici aciclici

Se una visita in profondità non incontra mai vertici grey, il grafo è aciclico.

 

I Grafi / introduzione

Posted by On Filed under Algoritmi e strutture dati

Grafi

Grafi e rappresentazioni

I grafi sono strutture dati caratterizzate dalla presenza di vertici e archi e sono solitamente rappresentati da G(V, E), in cui G è il grafico, V è l'insieme dei vertici e E - senza troppa fantasia - l'insieme degli archi.

I grafi solitamente sono rappresentati o da matrici o da liste. Se sono rappresentati da matrici, la memoria utilizzata è Θ(V2), perché ogni possibile arco è rappresentato, e il valore all'incrocio tra i due vertici è 1 se l'arco esiste, 0 altrimenti.

V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 1 0 0 0
V3 1 0 0 1 1
V4 0 0 1 0 0
V5 0 0 1 0 0

In questo esempio i vertici sono (V1, V2, V3, V4, V5) e gli archi sono ((V1, V2), (V2, V2), (V1, V3), (V3, V4), (V3, V5)).

Se il grafo è semplice, la matrice deve essere trasponibile senza che il risultato cambi; in altre parole, l'informazione di un "triangolo" di dati pari a V*(V-1)/2 è ridondante, perché l'arco (V1, V2) e (V2, V1) sono la stessa cosa:

V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 1 0 0
V3 1 0 0 1 1
V4 0 0 1 0 0
V5 0 0 1 0 0

Se invece gli archi hanno una direzione - come ad esempio le strade a senso unico, che vanno da V1 a V2 ma non viceversa - tutti gli archi sono importanti perché rappresentano un'informazione univoca.

La rappresentazione tramite liste di adiacenza invece contengono una lista di vertici, a ciascuno dei quali corrisponde una lista di altri vertici a cui sono collegati.
Il grafo riportato sopra sarebbe:

  • V1 → V2 → V3
  • V2 → V1 → V2
  • V3 → V1 → V4 → V5
  • V4 → V3
  • V5 → V3

Anche in questo caso, se il grafo non è orientato, alcune informazioni sono ridondanti (es. il collegamento tra V1 e V2 è rappresentato sia nella lista V1 sia nella V2), mentre nel caso di grafi orientati i due collegamenti rappresenterebbero entità diverse e non ci sarebbe ridondanza.

Visita del grafo

La visita del grafo permette, partendo da un vertice, di "toccare" tutti gli altri vertici collegati direttamente o indirettamente.

Si comincia da una sorgente, come nel problema dei flussi di Ricerca Operativa, e si visitano tutti i nodi collegati. Per fare questo, si colorano i nodi dapprima di bianco, poi in grigio, se sono stati visitati, e in nero se tutti i nodi adiacenti sono a loro volta stati visitati (sono in grigio o in nero).

Il seguito nel post Visita di un grafo.

 

Riflessioni sulla distribuzione normale

Posted by On Filed under Probabilità & statistica

fx=12πσe-12x-μσ2

Per oggi sono riuscito a scriverla. Riuscirò mai a capirla?

Distribuzione normale

Il senso sottostante a questa formula è che la distribuzione normale dipende dal valore medio e dalla varianza.

σ2 rappresenta la varianza. Più σ è grande e più c'è varianza, e quindi è più probabile trovare valori fuori dalla norma: la curva è quindi più piatta. Se invece σ è piccolo, la maggior parte dei valori sarà molto vicino alla media, e quindi la curva sarà più "appuntita". ±σ infatti sono i valori in cui stanno i due flessi della curva.

μ rappresenta il valore medio.

Il punto di partenza per comprendere questa funzione è e-x2 e il punto di partenza per questa è -x2: una parabola con il vertice in alto, che vale sempre meno di zero (tranne in 0,0). Elevare un valore per -x2 significa avere verso -∞ e +∞ valori sempre più piccoli in modo esponenziale, e avere 1 quando x=0. Abbiamo una curva a campana.

12πσ

è "solo" un fattore che riporta l'integrale improprio da -∞ e +∞ sempre a 1, sulla base della varianza: in pratica se la curva è più "piatta" per avere un integrale = 1 bisogna che sia più "alta".

 

Riflessioni sulla distribuzione di Poisson

Posted by On Filed under Senza (ancora) categoria

La distribuzione di Poisson si propone di risolvere problemi simili a quelli della distribuzione binomiale, ma con le due caratteristiche che il campione sia molto grande e che la probabilità sia molto piccola.

Per esempio, la probabilità che una persona abbia la sindrome di Krugen-Spassen è dello 0,003%, e la città di Mestre conta 250.000 persone. Quante probabilità ci sono che a Mestre ci sia qualcuno con la sindrome di Krugen-Spassen?

La risposta è 250.000 * 0,00003 = 7,5, cioè ci si può attendere che in tutta Mestre queste persone siano circa 7 o 8.

Applicando la "formulina" scopriamo quante probabilità ci sono che a Mestre ci siano esattamente tre persone con la sindrome:

λnn!e-λ

abbiamo λ = 7,5, n = 3

quindi λn = 7,5^3 = 421,875, e^-λ = 0,000553

e P(X) = 0,03888

In definitiva, abbiamo circa il 4% di probabilità che ci siano esattamente tre persone in tutta Mestre.

Riflessioni sulla distribuzione binomiale

Posted by On Filed under Probabilità & statistica

Il problema che la distribuzione binomiale si propone di risolvere riguarda la probabilità che in una popolazione divisibile in successi e insuccessi si ottengano k successi a fronte di n estrazioni con reinserimento.

Rispetto all'esempio della distribuzione ipergeometrica, in cui a fronte di una popolazione di 30 persone di cui 17 maschi e 13 femmine, vorrei sapere la probabilità di chiamare per un'interrogazione esattamente 2 maschi su 3 persone, nella distribuzione binomiale possiamo immaginare di chiamare una sola persona per materia, interrogando 3 volte.

Di conseguenza, lo stesso studente può essere chiamato più volte e tutto il conteggio diventa molto più semplice, mentre il ragionamento sottostante è praticamente uguale.

Ho 30 studenti, 17 maschi, 13 femmine, interrogo nella prima materia: ottengo 17/30 probabilità di avere un maschio K/N contro 13/30 di avere una femmina (1-K)/N

Per la seconda e la terza materia è uguale, perché lo studente chiamato torna a posto e ritorna disponibile per un'altra interrogazione. Si può dire che le tre materie siano commutative.

La probabilità di ottenere due maschi e una femmina è il prodotto di:

    • tre: il numero di casi in cui ho 2M e 1F: MMF, MFM, FMM, calcolato come coefficiente binomiale (2 3)
    • 17/30 ripetuto tante volte quante è richiesto un caso di successo: (17/30)2
    • 13/30 ripetuto tante volte quante è richiesto un caso di insuccesso: (13/30)1

La formula generale "scritta bene" è quindi:

(kn)KNkN-KNn-k

Scritta ancora meglio, se P = K/N, cioè P rappresenta la probabilità di successo:

(kn)Pk1-Pn-k

Riflessioni sulla distribuzione ipergeometrica

Posted by On Filed under Probabilità & statistica

Il problema che la distribuzione ipergeometrica si propone di risolvere riguarda la probabilità che uno o più successi (in statistica, il "successo" non porta necessariamente una connotazione positiva) accadano in un numero di eventi in seguito a un numero di rilevazioni.

Per esempio in una popolazione di 30 studenti, di cui 17 maschi e 13 femmine siano chiamate a essere interrogate tre persone di cui esattamente due maschi.

La popolazione è indicata con N, e corrisponde, nell'esempio, a 30.

I successi sono indicati con K, e corrispondono, nell'esempio, a 2 (ovviamente si poteva scegliere di considerare "successo" anche 1, ribaltando la domanda: quante probabilità di interrogare esattamente una femmina su tre interrogati).

Il numero di rilevazioni è indicato con n ed è 3.

Notiamo che chiamando 15 persone (tutte le femmine + due maschi) non è possibile arrivare a non interrogare esattamente due maschi in nessun caso: possiamo ottenere, seppure con probabilità scarsa, fino a 13 femmine e 0 maschi oppure 14 femmine e 1 maschio, ma all'estrazione successiva restano solo maschi.

P(n = (1-K)+k) = 1.

Notiamo anche che chiamando una sola persona non possiamo ottenere sicuramente due maschi.

P(n < k) = 0

Infine il numero di estrazioni deve essere minore o uguale al numero di elementi.

n ≤ N

Alla prima chiamata, possiamo ottenere un maschio oppure una femmina

Maschio P(1) = 17/30

Femmina 1-P(1) = (30-17)/30

La seconda chiamata dipende dall'esito della prima, e questo distingue la distribuzione ipergeometrica da molte altre distribuzioni: la distribuzione ipergeometrica "ha memoria".

La seconda estrazione si fa su un campione non più di 30, ma di 29 elementi, in quanto uno (maschio o femmina che sia) è stato estratto.

Per quanto riguarda i successi, il numero di possiblità cambia in base all'estrazione precedente: 17 successi se l'estrazione precedente è stata scelta una femmina; 16 viceversa.

La probabilità di estrarre un maschio è quindi "biforcata":

Se la prima estrazione è uscito un maschio, è di 16/29, se la prima è uscita una femmina è di 17/29; quindi la probabilità di avere due maschi è di 17/30*16/29 (˜31,2%).

Sommando la probabilità che alla seconda sia uscita una femmina 13/30*13/29 (˜25,4%) e la probabilità che alla prima estrazione sia uscita una femmina 13/30 (˜43,3%), si ottiene 1: infatti è sicuro che su due estrazioni sia uscita una femmina al primo turno oppure un maschio e uno tra maschio o femmina al secondo.

Le estrazioni possono essere rappresentate come un albero binario, in cui a ogni estrazione si sceglie di seguire il percorso di sinistra in caso di successo o destra in caso di insuccesso (anche questa è una convenzione, senza considerazioni di merito).

A ogni passo dell'albero, le informazioni che cambiano sono il numero di elementi del campione (decrementa a ogni livello dell'albero), il numero di successi (si decrementa solo nel ramo di sinistra), il cumulo di percentuale di probabilità, che moltiplica le probabilità precedenti fino alla radice.

Per il nostro problema, che è di trovare la probabilità che escano due elementi maschi su tre, ci viene in aiuto il coefficiente binomiale, che ci dice che le combinazioni utili sono 1, 3, 3, 1, ovvero 1 sequenza che porta a tre maschi, 3 che portano a due maschi e una femmina, 3 a due femmine e un maschio e 1 che porta a tre femmine (1: {MMM}; 3: {MMF, MFM, FMM}; 3: {FFM, FMF, MFF}; 1: {FFF}).

Le probabilità che ci interessa contare sono quelle del secondo gruppo: MMF, MFM, FMM.

MMF:

Alla prima estrazione abbiamo 30 elementi, 17 successi, una probabilità accumulata nulla, quindi la probabilità di successo è 17/30.
Alla seconda abbiamo 29 elementi, 16 successi, una probabilità accumulata di 17/30, quindi una probabilità di successo di 16/29 * 17/30 = 272/870.
Alla terza abbiamo 28 elementi, 15 successi, una probabilità accumulata di 272/870 e dobbiamo calcolare la probabilità che esca una femmina, che è di 13/28; la probabilità di successo è quindi di 3.536/24.360.

MFM:

Prima: abbiamo 30 el, 17 succ, p.a. nulla, p(M) = 17/30.
Seconda: abbiamo 29 el, 16 succ, p.a. 17/30, ci interessa la probabilità che esca femmina, che è 13/29, il totale è 17/30*13/29 = 221/870.
Terza: abbiamo 28 el, 16 succ. p.a. 221/870, ci interessa la probabilità che esca maschio, che è 16/28, il totale è 221/870*16/28= 3.536/24.360

FMM:

Prima: abbiamo 30 el, 17 succ, p.a. nulla, p(F) = 13/30
Seconda: abbiamo 29 el, 17 succ, p.a. 13/30, P(M) = 17/29, p. tot = 221/870.
Terza: abbiamo 28 el, 16 succ. p.a. 221/870, ci interessa la probabilità che esca maschio, che è 16/28, il totale è 221/870*16/28= 3.536/24.360

Sommando tre volte 3.536 si ottiene 10.608, che diviso per 24.360 dà 0,43546...

Notiamo che la probabilità che si ottenga MMF, MFM o FMM è identica, perché anche se le percentuali di probabilità cambiano, alla fine abbiamo sempre 17, 16, 13 al numeratore e 30, 29, 28 al denominatore.

I dati che ci interessano per generalizzare la formula sono:

  • 30 * 29 * 28, che è N! / (N-n)!
  • 17 * 16 * 13, che è il prodotto di K! / (K-k)! e (N-K)! / (N-K-n+k)!
  • 3, che è il coefficiente binomiale di (2 3), cioè i casi di successo desiderati sulle estrazioni

Il risultato è dato dal prodotto di questi termini:

K!K-k!

rappresenta il numero di esiti positivi che vogliamo ottenere (nell'esempio, 17*16)

N-K!N-K-n+k!

rappresenta il numero di esiti negativi utili a completare il numero di estrazioni (nell'esempio, 13, ma se fossero state più estrazioni sarebbero 13*12*11...)

n!k!n-k!

è rappresentabile anche come

(kn)

è il numero di risultati corrispondenti al nostro requisito (2 maschi su 3 persone).
Da notare che il numero di femmine (1 femmina su 3 persone), cioè

(13)

dà lo stesso risultato; in generale, portando il concetto in formula:

(kn)=(n-kn)

N-n!N!

è l'inverso - poiché sta al denominatore - del numero totale di esiti possibili (nel nostro esempio 1/(30*29*28)).

Moltiplicando tutto, si ottiene

K!K-k!N-K!N-K-n+k!n!k!n-k!N-n!N!

La formula è già incasinata così come sta, ma è necessario porre un'ulteriore limitazione:

K!K-k!N-K!max0,N-K-n+k!n!k!n-k!N-n!N!

che rappresenta il fatto che, se estraiamo 14 persone, sicuramente estraiamo almeno un maschio, N-K-n+k potrebbe essere un valore negativo.

Formula semplificata

Dopo aver "sbattuto" contro questa formula, la formula "semplificata" sembrerà quasi abbordabile, pur essendo costituita da ben tre coefficienti binomiali:

(Kk)(N-Kn-k)(Nn)

Basta riscrivere la formula a coefficienti binomiali come formula con i fattoriali, secondo l'equivalenza

(kn)=n!k!n-k!

per ottenere praticamente la funzione da cui siamo partiti.

Excel

Di seguito, uno screenshot di un foglio excel in cui è riportato tutto il ragionamento sotto forma di formule

Calcolare velocemente distribuzioni ipergeometriche semplici

Quando un problema è posto come

c'è una popolazione di N elementi, di cui K sono successi: quante probabilità ho di ottenere k successi su n estrazioni?

sono di fronte a un problema risolvibile con la distibuzione ipergeometrica. Purtroppo il calcolo di un coefficiente binomiale come quello dell'esempio richiede di calcolare 30! e 27!, che sono numeri enormi.

È possibile calcolare il risultato di un problema abbastanza semplice ragionando in questo modo:

  1. Al numeratore metto una serie discendente di numeri che rappresentano le probabilità di successo (nell'esempio 2 probabilità di successo = 17*16) e le moltiplico per la serie discendente di insuccessi, fino ad avere un prodotto di n numeri, dove n è il numero di estrazioni (nell'esempio, 17*16*13)
  2. Al denominatore metto una serie discendente di popolazione, da 1 a n (nell'esempio, 30*29*28).
  3. Ottengo due serie di prodotti con lo stesso numero di termini (nell'esempio, 3 termini al numeratore e 3 al denominatore: 17*16*15 / 30*29*28).
  4. Moltiplico per il coefficiente binomiale, ma - se i numeri sono piccoli - posso arrivarci anche ragionando: ho 8 possibilità diverse (MMM, MMF, MFM, MFF, FMM, FMF, FFM, FFF), di cui 3 di ottenere esattamente 2 maschi e una femmina.

(quello che ho capito di) variabili aleatorie

Posted by On Filed under Probabilità & statistica

Variabile aleatoria

Una variabile aleatoria è una variabile il cui valore non è conosciuto a priori.

Le V.A. possono essere discrete (praticamente ℕ) o continue (praticamente ℝ+).

Ciascun esito può prendere un valore compreso tra 0 e 1, e la somma di tutti gli esiti fa 1. 0 = evento impossibile; 1 = evento certo. P.E. gli esiti di una moneta non truccata sono: 1/2 testa, 1/2 croce.

Spazio campionario

uno spazio campionario è un insieme di valori associati a un esito. Per es. testa = milan, croce = inter ==> milan e inter sono lo spazio campionario.

Reinserimento

Una delle caratteristiche più importanti è se ogni evento è seguito da un reinserimento oppure no.

Per esempio, il lancio di un dado genera un evento (l'uscita di un numero), ma questo non preclude che al lancio successivo possa uscire di nuovo lo stesso numero: in linea di principio potremmo avere n lanci ciascuno sempre con lo stesso numero.

L'estrazione dei numeri di una tombola, viceversa, esclude che l'evento si ripeta.

Le probabilità cambiano completamente, perché nel primo caso la probabilità per ogni evento che esca un numero è 1/6, poi al secondo evento 1/6, poi 1/6 e così via; per il secondo evento la probabilità è 1/90, poi al secondo 1/89 e così via. Quando si arriva ad avere un solo numero nel sacchetto, la probabilità che esca quel numero arriva a 1/1.

V.A. continua

Una V.A. continua è una variabile rappresentabile da un numero reale. In questo caso la probabilità è rappresentata dall'area sottostante il grafico della funzione. A differenza di una funzione generica, una funzione che esprime una probabilità è sempre non negativa; questo significa che possiamo considerare l'integrale sottostante alla stregua di una vera e propria area. Inoltre l'integrale della funzione su tutto il suo dominio ha valore 1: in altre parole, sommando tutti i valori (infiniti) che può prendere la funzione, la probabilità che un evento abbia uno di quei valori è 1 (certezza).

Può capitare che una V.A. continua sia rappresentata da una funzione che ha un certo valore k quando tende a zero, rappresentato da

limx→0fx=k

e poi la funzione decresca sempre di più, in modo che

limx→∞fx=0

ma abbia come dominio ℝ+, e quindi "prosegua all'infinito". In questo caso dobbiamo utilizzare un integrale improprio, poiché il dominio non è limitato superiormente. Per esempio la funzione 1/x2 ha integrale da 1 a infinito = 1 e il suo valore è sempre positivo.

Mentre la probabilità di un singolo evento è nulla, poiché ci sono infiniti eventi, la probabilità che un evento ricada tra due numeri diversi è calcolabile come area sottostante, sempre tramite l'integrale.

Per esempio, se la funzione di probabilità è rappresentata da 1/x2, la probabilità che un evento accada tra x = 1 e x = 2 è data da

∫121x2dx=-12--1=12

Funzione di ripartizione

La funzione di ripartizione restituisce la probabilità che si verifichi un evento minore o uguale a un valore dato.

Il valore cresce continuamente, perché in ogni momento la probabilità che si verifichi un evento si somma a tutte le probabilità precedenti.

Per es. la probabilità che esca un numero minore o uguale a 23 alla tombola è 23/90 (1/90 per il numero 1 + 1/90 per il numero 2 + 1/90 per il numero 3 ... + 1/90 per il numero 23).

Nel caso di una funzione continua, la funzione di ripartizione è data dall'integrale da meno infinito a x della funzione.

Valore atteso

Il valore atteso equivale alla media aritmetica.

Varianza

La varianza è un indice (un valore numerico) che indica quanto lontani sono i valori di una V.A. uno dall'altro.

Si calcola facendo la differenza tra la media dei quadrati e i quadrati della media. Una caratteristica della media dei quadrati è che è sempre maggiore del quadrato della media, quindi sottraendo la prima al secondo si ottiene un valore sempre non negativo.

La varianza è un valore che cresce esponenzialmente: quindi la differenza tra la varianza tra due valori vicini e tra due valori lontani cresce in maniera molto veloce.

P.E. la differenza tra la varianza tra 35 e 43 (media: 39, varianza: 16) e tra 34 e 44 (media: 39, varianza: 25) è minore della differenza tra la varianza tra 28 e 50 (media: 39, varianza: 121) e tra 27 e 51(media: 39, varianza: 144)

La formula per la varianza di una variabile aleatoria continua è omologa a quella discreta, ma fa uso di un integrale:

∫Rx2fxdx-AVGx2

Moda

La moda è il valore più ricorrente in una V.A. discreta.

Nel caso di una V.A. continua, la moda è data dal punto (o dai punti) di massimo della funzione.

Mediana

La mediana è data dal valore intermedio in uno spazio campionario ordinato.

P.E. se lo spazio campionario è [3, 19, 32, 12, 15, 22, 7, 29, 24]

lo spazio campionario con i valori ordinati è [3, 7, 12, 15, 19, 22, 24, 29, 32]

la mediana è il valore centrale dell'elenco: 19.

Se lo spazio campionario ha un numero pari di elementi, la mediana è la media degli elementi centrali.

La mediana può essere ricavata tramite la funzione di ripartizione, ed è il minimo elemento in cui la funzione è ≥ ½.

La mediana di una V.A. continua è il punto in cui la sua funzione di ripartizione vale ½:

∫Rfxdx=12

Quantili

Lo stesso discorso della mediana vale per i quantili, che rappresentano altre suddivisioni dello spazio campionario: i quartili indicano una suddivisione in quattro, i centili in cento e così via.