Analisi 1 PDF - Carlo La Bella

Analisi 1 Carlo La Bella Indice 1 Percorsi dei grafi 2 1.1 Caratteristiche................................ 2 1.2 Proprietà di connettività...................

Analisi 1 Carlo La Bella Indice 1 Percorsi dei grafi 2 1.1 Caratteristiche................................ 2 1.2 Proprietà di connettività........................... 3 1.2.1 Connettività.............................. 3 1.3 Componenti connessi............................ 3 1.3.1 Punti di articolazione......................... 3 1.3.2 Bridge................................. 4 1.4 Separeting set................................ 4 1.5 Connettività sui grafi orientati........................ 5 1.5.1 Componenti fortemente connessi.................. 5 1.6 Algoritmo di Dijkstra............................. 5 1.7 Ciclo Euleriano................................ 7 1.8 Ciclo Hamiltoniano.............................. 8 2 Calcolo combinatorio 9 2.1 Disposizioni semplici............................. 9 2.2 Permutazioni semplici............................ 9 2.3 Combinazioni semplici............................ 10 2.4 Distribuzione casuale............................ 11 2.4.1 Valore atteso............................. 11 2.4.2 Varianza................................ 12 2.5 Probabilità Condizionata........................... 13 2.5.1 Formula della Probabilità Condizionata.............. 13 2.5.2 Conclusione............................. 14 2.5.3 Calcolare l’intersezione....................... 14 3 Teorema di Bayes 15 1 Percorsi dei grafi Un percorso è un insieme di archi tale per cui ogni arco è adiacente al preceden- te. Figura 1: Un semplice percorso orientato con 3 nodi e 2 archi Figura 2: Un semplice percorso non orientato con 3 nodi e 2 archi Caratteristiche Un percorso si dice di lunghezza n se è formato da n nodi Figura 3: Il percorso dal nodo 1 al nodo 4 è lungo 3 Un percorso si dice circuito o ciclo se gli estremi sono collegati Figura 4: Il nodo 1 e il nodo 5 che sono gli estremi sono collegati Un percorso si dice semplice se non contiene archi multipli o selfloop Sia Figura 3 che Figura 4 sono grafi semplici Figura 5: Questo grafo non è semplice 2 Proprietà di connettività Connettività Definizione Un grafo non orientato si dice connesso se esiste per ogni coppia un cammino che li unisce Figura 6: Il grafo A1 è connesso, Il grafo A2 non è connesso Componenti connessi Dato un grafo A non orientato si dice componente connesso un sottografo con- nesso massimale (Il più grande sottografo connesso) Figura 7: Il grafo A è composto da 4 componenti connessi Possiamo dire che un grafo connesso possiede un solo componente connesso Figura 8: Il grafo A è composto da 1 solo componente connesso, quindi è un grafo connesso Punti di articolazione Un nodo che se rimosso sconnette un grafo viene detto punto di articolazione 3  Figura 9: Rimozione del nodo 9 Se al grafo rimuoviamo da a1 il nodo 9, il nodo 10 da solo costituirà un componente connesso, non ci sono altri nodi che se rimossi dal grafo A1 creano più componenti connessi. Bridge Sostanzialmente la stessa cosa ma adesso ci concentriamo sugli archi Un arco che se rimosso sconnette un grafo viene detto bridge Figura 10: Rimozione dell’arco 9 → 10 Separeting set Un gruppo di nodi viene chiamato separeting set, dove se rimossi sconnettono il grafo. Il separeting set è il minimo numero di nodi da rimuovere, possiamo quindi immaginare che più questo numero è alto più la rete è protetta e connessa. Figura 11: In A2 basta rimuovere un solo nodo. In B2 dobbiamo rimuovere due nodi Quindi il grafo B2 è più resistente ai guasti 4 Connettività sui grafi orientati Un grafo orientato fortemente connesso se per ogni coppia di nodi esiste un percorso orientato. Vale a dire che ci si piò arrivare seguendo la direzione dell’arco. Se c’è il percorso ma non è orientato, allora è debolmente connesso. Figura 12: A1 è fortemente connesso. A2 è debolmente connesso Ovviamente di base il grafo deve essere connesso. quindi deve avere solo un compo- nente connesso. Componenti fortemente connessi Si possono applicare gli stessi concetti anche ai componenti di un grafo se esso è foramto da più componenti. Figura 13: A1 è un componente fortemente connesso. A2 è un componente de- bolmente connesso Algoritmo di Dijkstra Partiamo da un grafico pesato e orientato 5  Figura 14: Lo scopo dell’algoritmo di Dijkstra è quello di trovare il cammino migliore per arrivare da un nodo ad un altro. Il miglior modo di spiegare questo algoritmo è quello di fare un esercizio. Sulla base del grafico in Figura 14. Lo scopo darà arrivare da A a C Iniziamo con scrivere una tabella e inserire i nodi disponibili nella prima riga. E nella prima cella della prima colonna mettere il nodo da cui partiamo. Ora lo scopo è quello di scrivere nelle celle della prima riga il peso che passa dal nodo all’altro, nel caso in cui non ci fosse nessun modo per raggiungere il nodo direttamente allora scriveremo INF A B C D E A 0A 20A INF INF 1A Ho evidenziato sottolineandolo la cella con scritto 1A perché escludendo il nodo di partenza è quella con peso minore. Ora riscrivo il nodo a cui arrivo (E), lo leggiamo dalla prima riga. Quindi scrivo E nella prima colonna e scrivo i pesi per tutti i nodi collegati a E. Ma adesso dobbiamo sommare il peso dell’arco nella cella evidenziata per la colonna successiva. Quindi E→B=19 ma dobbiamo sommare 1 poiché siamo partiti da A. Quindi A→E→B=20 A B C D E A 0A 20A INF INF 1A E INF 20B INF 7E 1A 7E è il minore escluso ovviamente 1A perché essendo riscritto dalla riga precedente, quindi lo evidenzio. E adesso continuiamo passando dal nodo D. E nella prossima riga riscriviamo 7E. A B C D E A 0A 20A INF INF 1A E INF 20B INF 7E 1A D INF 14D 32D 7E INF 6 Sottolineamo 14D perché è il minore e continuamo riscrivendolo nella riga successi- va. A B C D E A 0A 20A INF INF 1A E INF 20B INF 7E 1A D INF 14D 32D 7E Inf B INF 14D 19B INF INF Ora il minore è nella colonna c quindi siamo arrivati. A B C D E A 0A 20A INF INF 1A E INF 20B INF 7E 1A D INF 14D 32D 7E Inf B INF 14D 19B INF INF C 19B E dalla prima colonna possiamo ricavare il percorso A → E → D → B → C Ciclo Euleriano Un ciclo euleriano è un ciclo in un grafo che visita ogni arco esattamente una volta e termina nel nodo di partenza. Perché un grafo non orientato contenga un ciclo euleriano, devono essere soddisfatte le seguenti condizioni: Il grafo deve essere connesso. Ogni vertice deve avere un grado pari (cioè deve avere un numero pari di archi). Se un grafo contiene un ciclo euleriano, è detto grafo euleriano. Figura 15: Un grafo con un ciclo euleriano 7 Ciclo Hamiltoniano Un ciclo hamiltoniano, invece, è un ciclo che passa attraverso ogni nodo del grafo esattamente una volta, senza ripetere i nodi, e ritorna al nodo di partenza. Le condizio- ni per l’esistenza di un ciclo hamiltoniano non sono così semplici come quelle del ciclo euleriano, ma generalmente si possono osservare le seguenti caratteristiche: Non è necessario che il grado dei vertici sia pari. Un ciclo hamiltoniano può esistere anche in grafi dove alcuni archi non sono percorsi. Se un grafo contiene un ciclo hamiltoniano, è detto grafo hamiltoniano. Figura 16: Un grafo con un ciclo hamiltoniano 8 Calcolo combinatorio Disposizioni semplici Si chiamano disposizioni semplici di n elementi in classe h tutti i gruppi che si possono formare con h di n oggetti in modo che 2 gruppi siano considerati considerati distinti anche se variano solo per l’ordine Dhn {a, b, c, d} D42 = {(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (c, a), (c, b), (c, d), (d, a), (d, b), (d, c)} D43 = {(a, b, c), (a, b, d), (a, c, b), (a, c, d), (a, d, b), (a, d, c), (b, a, c), (b, a, d), (b, c, a), (b, c, d), (b, d, a), (b, d, c), (c, a, b), (c, a, d), (c, b, a), (c, b, d), (c, d, a), (c, d, b), (d, a, b), (d, a, c), (d, b, a), (d, b, c), (d, c, a), (d, c, b)} Ma come facciamo a capire quante sono i gruppi? D14 = 4 D24 = D14 · 3 D34 = D24 · 2 c’è un pattern, D24 = D41 · (4 − 3) D34 = D24 · (4 − 2) D3n = n · (n − 1) · (n − 2) Dhn = n · (n − 1) · n(−2) · n(−3)... (n − (h + 1)) È sostanzialmente un fattoriale che si può riscrivere come: n =n·(n−1)·n(−2)·n(−3)...(n−(h+1)) Dh n−h·(n−(h+1)) n! Che non è altro che (n−h)! Permutazioni semplici Le permutazioni semplici di un insieme di n elementi sono tutti i possibili ordinamenti di tali elementi. A differenza delle disposizioni semplici, in cui si sceglie solo un sot- toinsieme di elementi, nelle permutazioni si considerano tutti gli elementi dell’insieme, senza alcuna selezione. Infatti Dnn = Pn Ad esempio, per un insieme di 3 elementi {a, b, c}, le permutazioni sono tutti i modi in cui posso disporre questi elementi, cioè: P3 = {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)} Il numero totale di permutazioni di n elementi è dato dal prodotto di tutte le scelte possibili per ordinare questi elementi, ossia: Pn = n · (n − 1) · (n − 2) · · · · · 1 = n! 9 Combinazioni semplici A differenza delle disposizioni semplici Dhn dove due gruppi con gli stessi elementi erano considerati gruppi diversi, nelle combinazioni sempliciChn no, infatti: Le combinazioni sempliciChn sono tutti i gruppi che si possono formare con oggetti diversi in classe h. {a, b, c, d} C24 = {(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)} C34 = {(a, b, c), (a, b, d), (a, c, d), (b, c, d)} n Dh Per conoscere il numero di combinazioni semplici: Pn n! (n−h)·h! n! n! n! Lo chieda all’esame: Chn = (n−h)h! n ⇒ Cn−h = (n−(n−h))!·(n−h)! ⇒ h!·(n−h)! n ⇒ Cn−h 10 Distribuzione casuale Una distribuzione casuale descrive la probabilità di ogni possibile risultato per esempio quella del lancio di un dado x P 1 16 2 16 3 16 4 16 5 16 6 16 Tabella 1: Distribuzione di probabilità del lancio di un dado Valore atteso Il valore atteso rappresenta il valore medio ponderato in una distribuzione casua- le si calcola:γ = ni=1 xi · P (xi ) P calma calma calma, è comprensibile P è una sommatoria, quindi la somma di una serie di valori. Praticamente un for – i = 0 è l’indice della sommatoria – n è l’indice massimo a cui si può arrivare x1 è x con indice i, la troviamo nella Tabella 1 P1 è la probabilità con indice i e la troviamo nella Tabella 1 γ è la "variabile" con cui faremo riferimento per intendere il valore atteso, ci si può riferire al valore atteso anche con E(X) Calcoliamo il valore atteso del lancio del dado x_1cdotP (x_1) con i = 1 1 · 61 + x_2cdotP (x_2) con i = 2 2 · 16 + x_3cdotP (x_3) con i = 3 3 · 16 + x_4cdotP (x_4) con i = 4 4 · 16 + x_5cdotP (x_5) con i = 5 5 · 16 + 1 x_6cdotP (x_6) con i = 6 6· 6 1 · 61 + 2 · 16 + 3 · 16 + 4 · 61 + 5 · 16 + 6 · 1 6 = 21 6 = 3.5 γ = ni=1 xi · P (xi ) = 3.5 P 11 Varianza La varianza misura la dispersione dei valori di una distribuzione casuale rispetto al valore atteso. Si calcola come la media ponderata delle deviazioni quadrate rispetto al valore atteso, fornendo un’indicazione di quanto i risultati possano variare. La formula per calcolare la varianza σ 2 è: n X 2 σ = (xi − γ)2 · P (xi ) i=1 dove: σ 2 è la varianza. xi è il valore della variabile casuale con indice i. γ è il valore atteso della distribuzione, già calcolato. P (xi ) è la probabilità associata al valore xi. Calcoliamo la varianza del lancio del dado: (x1 − γ)2 · P (x1 ) con i = 1 (1 − 3.5)2 · 16 + (x2 − γ)2 · P (x2 ) con i = 2 (2 − 3.5)2 · 61 + (x3 − γ)2 · P (x3 ) con i = 3 (3 − 3.5)2 · 61 + (x4 − γ)2 · P (x4 ) con i = 4 (4 − 3.5)2 · 61 + (x5 − γ)2 · P (x5 ) con i = 5 (5 − 3.5)2 · 61 + 1 (x6 − γ)2 · P (x6 ) con i = 6 (6 − 3.5)2 · 6 6.25+2.25+0.25+0.25+2.25+6.25 17.5 σ2 = 6 = 6 ≈ 2.92 Quindi, la varianza del lancio di un dado è circa 2.92. Questo valore indica la mi- sura della dispersione dei risultati rispetto al valore atteso di 3.5. Una varianza più alta indica che i risultati sono più sparsi intorno alla media, mentre una varianza più bassa suggerisce che i risultati tendono ad essere più concentrati attorno al valore at- teso. In questo caso, la varianza suggerisce che, sebbene i risultati possano variare, la maggior parte delle volte i valori si trovano relativamente vicini al valore atteso di 3.5. DA FARE LA DIMOSTRAZIONE 12 Probabilità Condizionata La probabilità condizionata descrive la probabilità di un evento E dato che un altro evento F è già accaduto. Formula della Probabilità Condizionata La formula per calcolare la probabilità condizionata è la seguente: P (E ∩ F ) P (E|F ) = P (F ) dove: P (E|F ) è la probabilità dell’evento E dato che F è accaduto. P (E ∩ F ) è la probabilità che si verifichino entrambi gli eventi E e F. P (F ) è la probabilità dell’evento F. Consideriamo un mazzo di carte composto da 52 carte, di cui 26 sono rosse (cuori e quadri) e 26 sono nere (fiori e picche). Vogliamo calcolare la probabilità di pescare un asso (evento E) dato che abbiamo già pescato una carta rossa (evento F ). Identificazione degli Eventi - Evento E: pescare un asso. - Evento F : pescare una carta rossa. Probabilità di F La probabilità di pescare una carta rossa è: numero di carte rosse 26 1 P (F ) = = = numero totale di carte 52 2 Probabilità di E ∩ F Nel mazzo ci sono 2 assi rossi (cuori e quadri), quindi la probabilità di pescare un asso e che sia rosso è: numero di assi rossi 2 1 P (E ∩ F ) = = = numero totale di carte 52 26 Calcolo della Probabilità Condizionata Ora possiamo calcolare la probabilità con- dizionata utilizzando la formula: 1 P (E ∩ F ) 26 1 2 2 1 P (E|F ) = = 1 = · = = P (F ) 2 26 1 26 13 Interpretazione del Risultato La probabilità di pescare un asso, dato che si è già 1 pescata una carta rossa, è 13. Questo significa che, tra tutte le possibili carte rosse, la probabilità di scegliere un asso rosso è circa 7.69%. 13 Conclusione La probabilità condizionata è uno strumento potente che ci permette di aggiornare le nostre valutazioni probabilistiche basate su informazioni aggiuntive. Questo esempio illustra come la conoscenza dell’evento F (aver pescato una carta rossa) influisce sulla probabilità di un evento successivo E (pescare un asso). Calcolare l’intersezione DADO Immagina di lanciare due dadi e vogliamo calcolare la probabilità che il primo dado mostri un numero pari (evento E) e il secondo dado mostri un numero maggiore di 4 (evento F ). Passo 1: Definire gli Eventi Evento E: il primo dado è pari. Le possibilità sono 2, 4, 6. Evento F : il secondo dado è maggiore di 4. Le possibilità sono 5, 6. Passo 2: Calcolare le Probabilità La probabilità che il primo dado sia pari è: 3 1 P (E) = = 6 2 La probabilità che il secondo dado sia maggiore di 4 è: 2 1 P (F ) = = 6 3 Passo 3: Calcolare l’Intersezione L’intersezione P (E ∩ F ) corrisponde a quando il primo dado è pari e il secondo dado è maggiore di 4. Poiché i due dadi sono lanciati indipendentemente, la probabilità dell’intersezione è data dal prodotto delle probabilità individuali: 1 1 1 P (E ∩ F ) = P (E) · P (F ) = · = 2 3 6 CARTE Consideriamo un mazzo di 52 carte e vogliamo calcolare la probabilità di estrarre una carta che sia un cuore (evento E) e che sia anche un asso (evento F ). Passo 1: Definire gli Eventi Evento E: estrarre un cuore. Evento F : estrarre un asso. 14 Passo 2: Calcolare le Probabilità La probabilità di estrarre un cuore è: 13 1 P (E) = = 52 4 La probabilità di estrarre un asso è: 4 1 P (F ) = = 52 13 Passo 3: Calcolare l’Intersezione L’intersezione P (E∩F ) rappresenta la probabilità di estrarre un asso che è anche un cuore. Poiché c’è solo 1 asso di cuori nel mazzo, abbiamo: 1 P (E ∩ F ) = P (asso di cuori) = 52 Teorema di Bayes Il Teorema di Bayes permette di aggiornare le probabilità di un evento in base a nuove informazioni. Formalmente, il teorema esprime la probabilità condizionata di un evento A dato un altro evento B attraverso la formula: P (B|A) · P (A) P (A|B) = P (B) In questa espressione, P (A|B) è la probabilità di A dato che B è accaduto, P (B|A) è la probabilità di B dato che A è accaduto, P (A) è la probabilità a priori di A e P (B) è la probabilità totale di B. Il Teorema di Bayes è particolarmente utile in situazioni in cui è necessario fare inferenze su eventi rari o poco probabili, permettendo di migliorare le decisioni sulla base di dati e osservazioni precedenti. Questo teorema trova appli- cazione in vari campi, tra cui la statistica, l’inferenza causale, l’intelligenza artificiale e la medicina diagnostica. Esempio: Test per una Malattia Consideriamo un esempio in ambito medico. Supponiamo che esista un test per una malattia che ha le seguenti caratteristiche: - La malattia colpisce il 1% della popola- zione (P (A) = 0.01). - Se una persona ha la malattia, il test risulta positivo con una probabilità del 90% (P (B|A) = 0.9). - Se una persona non ha la malattia, il test risulta positivo con una probabilità del 5% (P (B|¬A) = 0.05). Per calcolare P (B), la probabilità totale che il test risulti positivo, utilizziamo la legge delle probabilità totali: P (B) = P (B|A) · P (A) + P (B|¬A) · P (¬A) Dove P (¬A) = 1 − P (A) = 0.99. Calcoliamo quindi P (B): 15  P (B) = (0.9 · 0.01) + (0.05 · 0.99) = 0.009 + 0.0495 = 0.0585 Ora possiamo applicare il Teorema di Bayes per trovare la probabilità che una persona abbia effettivamente la malattia dato che il test è risultato positivo (P (A|B)): P (B|A) · P (A) 0.9 · 0.01 P (A|B) = = ≈ 0.154 P (B) 0.0585 Interpretazione dei Risultati La probabilità che una persona abbia la malattia, dato che il test è risultato positivo, è circa 15.4%. Questo risultato potrebbe sorprendere, dato che il test è positivo. Tut- tavia, la bassa prevalenza della malattia nella popolazione e il tasso di falsi positivi influenzano notevolmente il risultato. Conclusione Il Teorema di Bayes è un potente strumento per la revisione delle probabilità in base a nuove evidenze e gioca un ruolo cruciale in molte applicazioni pratiche, dall’infe- renza statistica all’intelligenza artificiale. Comprendere come applicarlo consente di prendere decisioni più informate in presenza di incertezze. 16