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 visiten! )
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