Formule notevoli

Poisson (discreta)

PX=k=λkk!e

Valore atteso: λ

Varianza: λ

Uniforme

Nell'intervallo (a,b) la funzione ha probabilità

fx=1b-a

Valore atteso: (a+b)/2

Varianza:

b-a212

Normale

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

Questa formula incasinata deriva dalla funzione di Gauss

e-x2

il cui integrale da -∞ a +∞ è π. Per questo al denominatore, per fare in modo che la derivata della normale sia uno e non kπ, c'è 1/√π.

Inoltre la funzione è più o meno "gonfia" a seconda di σ, e più o meno "spostata" dallo zero a seconda di μ.

Valore atteso: μ (la curva è simmetrica)

Varianza: σ2

Binomiale

La distribuzione binomiale mostra la distribuzione di n estrazioni da un campione di tipo bianco/nero (solo due scelte chiaramente distinte) con reinserimento.

I parametri sono:

  1. x/q/pp/nn: uno o più valori richiesti
  2. n: il numero di estrazioni
  3. p: la probabilità dell'evento

Nell'esempio di 17 studenti maschi, considerati "successo" nell'esempio, e 13 studentesse (totale: 30 studenti), per sapere la probabilità di ottenere esattamente 2 maschi su 3 estrazioni con reinserimento, si utilizza:

> dbinom(2, 3, 17/30)
[1] 0.4174444

 

Ipergeometrica

La distribuzione ipergeometrica mostra la distribuzione di n estrazioni da un campione di tipo bianco/nero (solo due scelte chiaramente distinte) senza reinserimento.

I parametri sono:

  1. x/q/p/nn: uno o più valori richiesti
  2. w: il numero di casi di successo (palline bianche nell'urna)
  3. b: il numero di casi di non successo (palline nere nell'urna)
  4. n: il numero di estrazioni

Nell'esempio di 17 studenti maschi, considerati "successo" nell'esempio, e 13 studentesse (totale: 30 studenti), per sapere la probabilità di ottenere esattamente 2 maschi su 3 estrazioni, si utilizza:

> dhyper(2, 17, 13, 3)
[1] 0.435468

Le distribuzioni - probabilità, quantile, densità, valore casuale

In R le distribuzioni riportano un prefisso che può essere una lettera tra p, q, d, r.

  • p significa "probabilità" della distribuzione
  • q significa "quantile"
  • d significa "densità"
  • r significa "randon", cioè valore casuale

Gli esempi seguenti si basano sulla distribuzione normale con μ=100 e σ=30 da 1 a 200.

pnorm rappresenta la funzione di ripartizione, che - come previsto - inizia a zero e tende a 1; dnorm rappresenta la probabilità e disegnando la probabilità di ciascun punto da 1 a 200 si ottiene la classica gaussiana:

qnorm rappresenta il valore che si trova al quantile, quindi il primo parametro che prende è un valore da 0 a 1. Per esempio, la mediana si ottiene passando come primo parametro 0.5:

> qnorm(0.5, 100, 30)
[1] 100

Volendo rappresentare con un grafico l'andamento dei quartili si può utilizzare la funzione qnorm(seq(0, 1, 0.01), 100, 30), che produce questo grafico:

rnorm restituisce una certa quantità (primo parametro) di valori casuali con la distribuzione scelta.

plot

La funzione plot prende come parametri:

  1. un vettore di valori da posizionare nell'asse x
  2. un vettore di valori da posizionare nel grafico, che dovrebbe essere di dimensione uguale al primo
  3. un tipo:
    • p => points
    • l => lines
    • h => histogram
    • s => steps
    • altri meno interessanti
  4. main = intestazione del grafico
  5. sub = piè di pagina del grafico
  6. xlab / ylab = etichette degli assi
  7. asp = proporzione y/x

Lezione 2, Esercizio 2

Un dado non truccato viene lanciato 6 volte.
b) Si calcoli la cardinalità dell'evento "si ottengono tre diversi valori, ciascuno due volte".

Su sei lanci è possibile ottenere valori a coppie uguali in

63

modi diversi (U = uguale, D = diverso)

U U D D D D
U D U D D D
U D D U D D
U D D D U D
U D D D D U
D U U D D D
D U D U D D
D U D D U D
D U D D D U
D D U U D D
D D U D U D
D D U D D U
D D D U U D
D D D U D U
D D D D U U

In quanti modi è possibile ottenere una coppia di numeri scelti tra sei lanciando un dado due volte?
62

In quanti modi è possibile ottenere una coppia di numeri scelti tra quattro lanciando un dado due volte?
42

In quanti modi è possibile ottenere una coppia di numeri scelti tra due lanciando un dado due volte?
22

La probabilità condizionata

La probabilità condizionata è la probabilità che avvenga un evento dopo che ne è avvenuto un altro non certo.

Per esempio, qual è la probabilità che un pacco contenga il premio pià grande dopo che si è aperto un altro pacco.

L'intuizione in questo caso gioca brutti scherzi: la probabilità infatti non è la stessa che ci sarebbe iniziando direttamente con la premessa già verificata!

Per esempio, quante probabilità ci sono di fare almeno un sei lanciando un dado due volte? E lanciandoli assieme? Se faccio sei al primo lancio, non lancerò il dado una seconda volta, quindi la probabilità lanciandoli assieme è 12/36 (=2/6), mentre lanciandoli di seguito è 1/6 + 5/36 = 11/36. La differenza è che lanciandoli assieme contemplo un caso in più, il 6-6, che non avrei se lanciassi i dadi di seguito.

La probabilità condizionata si indica con P(A|B), che significa "probabilità che si verifichi A dato per certo B".

La formula è

PA|B=PAPBPB

NP completezza

  • Problemi Decidibili
    • Trattabili (complessità polinomiale)
    • Intrattabili (complessità esponenziale)
  • Problemi Indecidibili

 

  • Problemi decisionali (sì/no)
  • Ottimizzazioni (il migliore è n)

ma a ogni problema di ottimizzazione può essere associato un problema decisionale

 

  • Classe P: problemi risolvibili in tempo polinomiale O(nk)
  • Classe NP: problemi verificabili in tempo polinomiale O(nk)

P ⊆ NP

NPC???

Lista degli argomenti relativi ai grafi (per esame ASD)

  • definizione di grafo
  • grafo orientato e non orientato
  • sottografi
  • grafi aciclici
  • cammino
  • ciclo
  • cammino semplice
  • cappi
  • grado di un vertice
    • lemma della stretta di mano
  • grafi regolari
    • 2-reg: |V| = |E|
    • 3-reg: |V| pari
    • 4-reg: |E| pari
    • 6-reg: |V| pari ⇒ |E| pari, |V| dispari ⇒ |E| dispari
  • rappresentazione di grafi con matrici di adiacenza
    • indici di colonna = da, di riga = a
  • rappresentazione di grafi con liste di adiacenza
  • densità di un grafo (denso/sparso)
    • orientato:
      δ=mn2
    • non orientato:
      δ=mnn-12
  • prodotto di matrici di adiacenza
    • diagonale del risultato come grado del vertice
    • altri valori come numero di cicli con grado k (k = numero di volte che si moltiplica la matrice)
  • grafo pesato
  • isomorfismo di grafi
  • grafo complementare
  • grafo aciclico
  • grafi connessi
  • albero
  • grafo completo
  • grafo vuoto
  • grafo bipartito
  • albero di copertura minimo (MST)
  • taglio
  • arco leggero
  • teorema fondamentale degli MST
    1. A ⊆ E, A ⊆ MST
    2. t = (S, S/V) un taglio che rispetta A
    3. l'arco a che attraversa t è leggero
    4. → l'arco a è sicuro per A
  • taglia e cuci
    1. abbiamo un albero
    2. aggiungiamo un arco leggero
    3. otteniamo sicuramente un ciclo
    4. siccome l'arco precedente è più pesante di quello appena aggiunto se lo rimuovo ottengo un MST
  • corollario del teorema fondamentale degli MST
    1. A ⊆ E, A ⊆ MST
    2. C è una componente connessa di A
    3. l'arco a che collega C a un'altra componente connessa di A è leggero
    4. → l'arco a è sicuro per A
  • Kruskal O(m logm)
    • implementazione di MAKE_SET(x)
    • implementazione di UNION(x, y)
    • implementazione di FIND_SET(x)
  • Prim O(m logn)
    • implementazione della coda di vertici e della funzione EXTRACT_MIN
  • Funzioni INIT_SINGLE_SOURCE e RELAX
  • Dijkstra
    • con array O(n2) / O(n2)
    • con heap binario O(m log n) ⇒ O(n log n) / O(n2 log n)
    • Dijkstra per problemi di massimizzazione
  • Bellman-Ford O(n2) / O(n3)
    • verifica di proprietà di cicli, per esempio
      Πi=1qwxi-1xi<1
  • Floyd-Warshall O(n3)
  • Clique