CONOSCERE CONOSCERSI COMUNICARE PROBLEMI • Pianificare un concerto. (Vai) • Cinque amici si ritrovano dopo molti anni. Tutti si salutano con una stretta di mano. Quante strette di mano ci sono state? E se gli amici fossero stati 8? 100?….. (Vai) • Giulio vuole andare a trovare i suoi 20 amici incontrati in vacanza. Ognuno di loro abita in una città diversa. Come programma il viaggio se vuole fare il minor numero di chilometri? Quanti sono i possibili itinerari? (Vai) Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 2 Pianificare un concerto. Tener conto di: • luogo e tema • scelta brani • scelta strumenti • montaggio palco • allestimento impianto elettrico • prova strumenti • prove generali Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 3 Grafo concerto 1. 2. 3. 4. 5. 6. 7. luogo e tema scelta brani scelta strumenti montaggio palco impianto elettrico prova strumenti prove generali 1 2 4 3 5 6 7 Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 4 Cinque amici si ritrovano dopo molti anni. Tutti si salutano con una stretta di mano…. Schema: 5 amici …. (alla lavagna)…10 strette 8 amici ……………………24 100 amici ……………..100(99)/2 ……. ……. n(n 1) n 2 n n2 n amici ….. 2 Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 2 5 Giulio vuole andare a trovare i suoi 20 amici incontrati in vacanza…. Possibile strategia: • trovare tutti i possibili itinerari • calcolare la lunghezza di ciascuno • scegliere il più corto Domande: E’ trattabile questo problema? E’ possibile eseguire la ricerca in un tempo ragionevole? Quanti sono i cammini possibili? (Alla lavagna per trovare il numero dei cammini) Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 6 Tabella itinerari amici • Costruire con Excel una tabella che calcoli il numero di tutti i cammini con il numero dei vertici da 1 a 20. • Se una macchina può esaminare 1 milione di cammini al secondo calcolare il tempo necessario per valutare tutti i cammini. Esprimere il tempo in una opportuna unità di misura. Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 7 Tabella cammini • • • • • • • • • • • • • • • • • • • • • n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 n! sec 1 0,000001 2 0,000002 6 0,000006 24 0,000024 120 0,00012 720 0,00072 5.040 0,00504 40.320 0,04032 362.880 0,36288 3.628.800 3,6288 39.916.800 39,9168 479.001.600 479,0016 6.227.020.800 6.227 giorni 87.178.291.200 87.178 1 1.307.674.368.000 1.307.674 15 20.922.789.888.000 20.922.790 242 anni 355.687.428.096.000 355.687.428 4.117 11 6.402.373.705.728.000 6.402.373.706 74.102 203 121.645.100.408.832.000 121.645.100.409 1.407.929 3857 2.432.902.008.176.640.000 2.432.902.008.177 28.158.588 77147 (collegamento ad excel tabella Tempi.xls) Non c’è speranza! E’ sempre così? Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 8 Complessità Non tutti i problemi hanno la stessa complessità ( mani n2 visiten! ) Non tutti gli algoritmi che risolvono lo stesso problema hanno la stessa complessità (divisione classica divisione per sottrazioni successive) Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 9 Esempio Calcolare la seguente divisione: 132:12 con due procedimenti diversi: • metodo in colonna • metodo sottrazioni successive Soluzione Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 10 Metodo in colonna 132 12 12 11 0 4 operazioni elementari Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 11 Metodo sottrazioni successive 132-12=120 132:12=11 120-12=108 108-12=96 96-12=84 84-12=72 72-12=60 60-12=48 48-12=36 36-12=24 24-12=12 12-12=0 operazioni elementari 11 Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 12 Conclusione Lo stesso problema è stato risolto con due algoritmi con diversa complessità Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 13 Confronto complessità Parte Seconda n n! 2n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 6 24 120 720 5.040 40.320 362.880 3.628.800 39.916.800 479.001.600 6.227.020.800 87.178.291.200 1.307.674.368.000 20.922.789.888.000 355.687.428.096.000 6.402.373.705.728.000 121.645.100.408.832.000 2.432.902.008.176.640.000 2 4 8 16 32 64 128 256 512 1.024 2.048 4.096 8.192 16.384 32.768 65.536 131.072 262.144 524.288 1.048.576 Conoscere - Conoscersi - Comunicare Sonia Fiori n2 log(n) 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 0 0,69 1,10 1,39 1,61 1,79 1,95 2,08 2,20 2,30 2,40 2,48 2,56 2,64 2,71 2,77 2,83 2,89 2,94 3,00 14 Conclusione: • Esistono algoritmi efficienti, cioè quando si ottiene una risposta in un tempo T accettabile, TEMPO POLINOMIALE = P, del tipo nk , allora il problema si dice TRATTABILE. • Esistono algoritmi non efficienti, TEMPI NON POLINOMIALI = NP, quindi problemi INTRATTABILI. Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 15 PROBLEMA Cercare un numero S tra i 100 di una lista ordinata. Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 16 Ricerca lineare Si confronta il numero da cercare S con tutti gli elementi della lista iniziando dal primo. Ricerca binaria Si divide la lista a metà, si controlla se il numero S sta nella prima o nella seconda metà, si ripete finché non si trova S Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 17 Confronto tra i due algoritmi • Nel caso peggiore, • Nel caso peggiore, cioè S è l’ultimo della cioè S è l’ultimo della lista, si devono lista, si devono fare 7 effettuare 100 controlli controlli • Complessità O(n) • Complessità O(logn) Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 18 Parole chiave • Complessità • Problemi trattabili P • Problemi intrattabili NP Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 19 Fine seconda parte Parte Seconda Conoscere - Conoscersi - Comunicare Sonia Fiori 20