MATEMATICA E INFORMATICA - eventi.uniurb.it · Cosa ci serve per valutare la complessità di un...
141
MATEMATICA E INFORMATICA alessandro bogliolo http://codemooc.org/algomooc/ Urbino 2 febbraio 2018 La complessità nascosta degli algoritmi che ci semplificano la vita 1506 . UNIVERSITA DEGU STUDI DI URBINO CARLO BO
Transcript of MATEMATICA E INFORMATICA - eventi.uniurb.it · Cosa ci serve per valutare la complessità di un...
MATEMATICA E INFORMATICA
alessandro bogliolo
http://codemooc.org/algomooc/
Urbino 2 febbraio 2018
La complessità nascosta degli algoritmi che ci semplificano la vita
1506 . UNIVERSITA DEGU STUDI DI URBINO CARLO BO
MATEMATICA E INFORMATICA
eggi
o e
incr
emen
to3+
2 https://blockly-demo.appspot.com/static/demos/code/index.html
2 3
51 2 3 4
5 6 7
calcola 3 p i ù 2 : annulla i l risultato ripeti 3 volte
incrementa risulta t o ripeti 2 volte
incrementa ris u lta t o mostra risultato
ca lcola3piu2
Next i • 1 to 3
Done risulato = risuftato+1
Next i • 1 to2
Done risulato = risuftato+1
Output risultato
( End )
MATEMATICA E INFORMATICA
eggi
o e
incr
emen
toA+
B
1 2
3 4
5 6 7
somma A e B : annulla risultato ripeti A volte
incrementa risultato ripeti B volte
incrementa r isul t ato restituisci il risultato
somma (lnteger A, lnteger 6)
risultato• risulato+1
( Return lnteger risultato )
Output somma(3,2)
MATEMATICA E INFORMATICA
mo
l’ass
egna
men
toA+
B
1 somma A e B : 2 assegna A a r is u l t a t o 3 ripeti B volte 4 5
incrementa risultato restituisci il risul t ato
somma ( lnteger A , lnteger 6 )
y t,1ext
i = 1 toB
Done r isuttato • r isultato+1
Return lnteger r isultato
Output somma(3,2)
MATEMATICA E INFORMATICA
mo
il co
nfro
nto
A+B
1 somma A e B : 2 se A< B allora 3 assegna Ba risul t a t o 4 assegna A a inc 5 altrimenti 6 assegna A a risul t a t o 7 assegna Ba inc 8 ripeti inc volte 9 incrementa risul t a t o
10 restituisci risul t a t o
MATEMATICA E INFORMATICA
mo
cart
a e
penn
a 3 4 7 6 +5 8 3 1 =
7
+
passi
7
+
0
110
+
5+
3
1
13
+
4
+
99
48
1
3
1
5
1
4
15
1
1
1
1
1
1
6
Il Il
Il Il Il Il
MATEMATICA E INFORMATICA
oria
Cosa ci serve per valutare la complessità di un algoritmo?
Dimensione dei dati su cui opera
Numero di passi elementari espressi in funzione di n Funzione monotona crescente
MATEMATICA E INFORMATICA
ratic
a
! " = 2 + " ∗ 2 + 1 = " ∗ 2 + 3 ! " = )* + )+"( ) ( )
MATEMATICA E INFORMATICA
ratic
a
! " = 2 + &(") ∗ 2 + 1 = &(") ∗ 2 + 3 ! " = ,- + ,.&(")( ) ( )
MATEMATICA E INFORMATICA
posiz
ione
! " = 2 + " ∗ 1 + " ∗ 2 = 2 + 3 ∗ "
! " = )* + )+," + )+-"
( )
( )
MATEMATICA E INFORMATICA
posiz
ione
! " = 2 + " ∗ (" ∗ 1) ! " = *+ + " ∗ *, + " ∗ *- = *+ + *," + *-"-( ) ( ) ( ( ))
MATEMATICA E INFORMATICA
posiz
ione
! " = 2 + " ∗ " ∗ (2 + " ∗ 1 + 1)
! " = *+ + *," + *-"- + *.".
( )
( )
MATEMATICA E INFORMATICA
sem
pio
Operazione elementare: incremento unitarion = secondo addendo
1 somma A e B :
2 assegna A a ris u ltat o 3 ripeti B volte 4 incrementa risulta t o 5 restituisci il risultat o
MATEMATICA E INFORMATICA
rand
e
! "
# "
! " ∈ %(# " ) ( ) # "
"*
( ) ( )
=le > O, no E N: 'rin > no, lf(n) I < clg(n) I
( )
( )
( )
MATEMATICA E INFORMATICA
rand
e! " = 2 + " ∗ " ∗ (2 + " ∗ 1 + 1)
! " = 2 + " ∗ " ∗ 2 + " ∗ 1 + 1 = 2 + 3 ∗ "+ + ",./(",)
( )
( ) ( )
MATEMATICA E INFORMATICA
razi
oni e
lem
enta
ri o
no?
Incremento
Addizione a una cifra
Addizione a un numero limitato di cifre
Moltiplicazione a un numero limitato di cifre
MATEMATICA E INFORMATICA
Quando ti tocco la testaAppoggia la mano sinistra sulla spalla destra della persona davanti a te
Quando ti toccano la spalla destraAppoggia la mano destra sulla spalla destra della persona davanti a te
Quando ti tocco la testaAppoggia la mano sinistra sulla spalla sinistra della persona davanti a te
Quando hai un numero dispari di mani che ti toccanoAlza la mano sinistra
Quando hai più di una mano che ti tocca Con la mano destra tocca il braccio del vicino alla tua destra
MATEMATICA E INFORMATICA
nche
que
stio
ne d
i fo
rtun
a?
Caso ottimo
Caso medio
Caso pessimo
MATEMATICA E INFORMATICA
incr
emen
ti rip
etut
i 1 moltiplica A e B : 2 annulla ri s u lta t o 3 ripeti B volte 4 ripeti A volte 5 incrementa risultato 6 restituisci risultato
MATEMATICA E INFORMATICA
addi
zion
i rip
etut
e
1 moltiplica A e B : 2 annulla risultato 3 ripeti B volte 4 incrementa risultato di A 5 restituisci risultato
MATEMATICA E INFORMATICA
3 2 1 x2 3 =
x
Usia
mo
cart
a e
penn
a
3
passi
3
6
6
9
92
4
+
26
61
46383
1
7
xxxxx
+++ 3
8
13
7
1
2
3
1
2
2
18
1
2
4
1
1
1
1
1
1
1
10
1
1
1
1
lii lii lii lii
MATEMATICA E INFORMATICA
non
esag
eria
mo 3
321x23
21 2
33
831
6
7
3 2 1 x2 3 =
9 6 3 +6 4 2 _ =7 3 8 3
1
MATEMATICA E INFORMATICA
1 2 3 4 5 6 7 8 9 101 1 2 3 4 5 6 7 8 9 102 2 4 6 8 10 12 14 16 18 203 3 6 9 12 15 18 21 24 27 304 4 8 12 16 20 24 28 32 36 405 5 10 15 20 25 30 35 40 45 506 6 12 18 24 30 36 42 48 54 607 7 14 21 28 35 42 49 56 63 708 8 16 24 32 40 48 56 64 72 809 9 18 27 36 45 54 63 72 81 9010 10 20 30 40 50 60 70 80 90 100
L’im
port
anza
de
lle ta
belli
ne
MATEMATICA E INFORMATICA
port
anza
de
lle ta
belli
ne
1 2 3 4 5 6 7 8 9 101 1 2 3 4 5 6 7 8 9 102 2 4 6 8 10 12 14 16 18 203 3 6 9 12 15 18 21 24 27 304 4 8 12 16 20 24 28 32 36 405 5 10 15 20 25 30 35 40 45 506 6 12 18 24 30 36 42 48 54 607 7 14 21 28 35 42 49 56 63 708 8 16 24 32 40 48 56 64 72 809 9 18 27 36 45 54 63 72 81 9010 10 20 30 40 50 60 70 80 90 100I
MATEMATICA E INFORMATICA
0 1 2 3 4 5 6 7 8 9 100 0 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 9 102 0 2 4 6 8 10 12 14 16 18 203 0 3 6 9 12 15 18 21 24 27 304 0 4 8 12 16 20 24 28 32 36 405 0 5 10 15 20 25 30 35 40 45 506 0 6 12 18 24 30 36 42 48 54 607 0 7 14 21 28 35 42 49 56 63 708 0 8 16 24 32 40 48 56 64 72 809 0 9 18 27 36 45 54 63 72 81 9010 0 10 20 30 40 50 60 70 80 90 100
L’im
port
anza
de
lle ta
belli
ne-
I
I
MATEMATICA E INFORMATICA
0 1 2 3 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 92 0 2 4 6 8 10 12 14 16 183 0 3 6 9 12 15 18 21 24 274 0 4 8 12 16 20 24 28 32 365 0 5 10 15 20 25 30 35 40 456 0 6 12 18 24 30 36 42 48 547 0 7 14 21 28 35 42 49 56 638 0 8 16 24 32 40 48 56 64 729 0 9 18 27 36 45 54 63 72 81
L’im
port
anza
de
lle ta
belli
ne
MATEMATICA E INFORMATICA
0 1 2 3 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 92 0 2 4 6 8 10 12 14 16 183 0 3 6 9 12 15 18 21 24 274 0 4 8 12 16 20 24 28 32 365 0 5 10 15 20 25 30 35 40 456 0 6 12 18 24 30 36 42 48 547 0 7 14 21 28 35 42 49 56 638 0 8 16 24 32 40 48 56 64 729 0 9 18 27 36 45 54 63 72 81
L’im
port
anza
de
lle ta
belli
nepassi
3
6
9
2
4
6
61
3
8
13
7
1
2
3
1
2
2
18
1
2
4
1
1
1
1
1
1
1
10
1
1
1
1
moltip
licazione
addizio
ne
MATEMATICA E INFORMATICA
i in
fila
0 1 2 3 4 5 6
alunno[i]
altezza[i]
taglia[i]
peso[i]
175 165 110 180 150 100 170
MATEMATICA E INFORMATICA
175 165 110 180 150 100 170
0 1 2 3 4 5 6
Conc
entr
iam
oci
sui d
ati
indice
altezza
MATEMATICA E INFORMATICA
175 165 110 180 150 100 170
0 1 2 3 4 5 6
180
Cerc
hiam
o un
ele
men
to
dell’a
rray
indice
altezza
h
-1posizione
0i
n = numero di elementi
Complessità: O(n)
1 2 3 4 5 6 7
trova h in altezza : N = l u ng hezza di a l te zz a ; po si z i one = -1 ; per i da O a N- 1
se altezza [i] == h allora . . . po sizi one= i
restituisci p o sizi on e
MATEMATICA E INFORMATICA
175 165 110 180 150 180 170
0 1 2 3 4 5 6
180
Cerc
hiam
o un
ele
men
to
dell’a
rray
indice
altezza
h
-1posizione
0i
Quale posizione restituisce la funzione?
1 2 3 4 5 6 7
trova h in altezza : N = l u ng hezza di a l te zz a ; po si z i one = -1 ; per i da O a N- 1
se altezza [i] == h allora . . . po sizi one= i
restituisci p o sizi on e
MATEMATICA E INFORMATICA
175 165 110 180 150 100 170
0 1 2 3 4 5 6
180
Mod
ifich
iam
o l’a
lgor
itmo
indice
altezza
h
-1
0
posizione
i
n = numero di elementi
Complessità: O(n)
Caso ottimo: O(1)Caso medio: O(n/2) = O(n)Caso pessimo: O(n)
1 2 3 4 5 6 7 8 9
trova h in altezza : N = l u nghezza di altezza ; p o sizi o ne = - 1 ; i= O; finché i <N e p o sizi o ne== - 1
se altezza[i] == h allora . . . p o siz i one= i ;
i= i+l ; restituisci o sizi o ne
MATEMATICA E INFORMATICA
175 165 110 180 150 180 170
0 1 2 3 4 5 6
180
equi
vale
nte
al p
rece
ndet
e?
indice
altezza
h
-1
0
posizione
i
Quale posizione restituisce la funzione?
1 2 3 4 5 6 7 8 9
trova h in altezza : N = l u nghezza di altezza ; p o sizi o ne = - 1 ; i= O; finché i <N e p o sizi o ne== - 1
se altezza[i] == h allora . . . p o siz i one= i ;
i= i+l ; restituisci o sizi o ne
MATEMATICA E INFORMATICA
175 165 110 180 150 100 170
0 1 2 3 4 5 6
E se
cer
cass
imo
il m
ax? indice
altezza
-1
0
posizione
i1 trova massimo di altezz a : 2 N = l unghezz a di al tezz a ; 3 po si z i on e = O; 4 per i da O a N- 1 5 6 7
se altezza[ i] > a l tezza [pos i z i one] . . . pos i zione= i
restituisci po si z i one
MATEMATICA E INFORMATICA
100 110 150 165 170 175 180
0 1 2 3 4 5 6
165
E se
l’ar
ray
foss
e in
ord
ine?
indice
altezza
h
n = numero di elementi
Complessità: O(n)
Caso ottimo: O(1)Caso medio: O(n/2) = O(n)Caso pessimo: O(n)
1 trova h in altezza : 2 N = lunghezza di altezza ; 3 posizione= - 1 ; 4 i= O; 5 finché i <N e altezza[i]<=h 6 se altezza[i] == h allora 7 posizione= i ; 8 i= i+l ; 9 restituisci os izi one
MATEMATICA E INFORMATICA
100 110 150 165 165 175 180
0 1 2 3 4 5 6
165
E se
l’ar
ray
foss
e in
ord
ine?
indice
altezza
h
Quale posizione restituisce la funzione?
1 trova h in altezza : 2 N = lunghezza di altezza ; 3 posizione= - 1 ; 4 i= O; 5 finché i <N e altezza[i]<=h 6 se altezza[i] == h allora 7 posizione= i ; 8 i= i+l ; 9 restituisci os izi one
MATEMATICA E INFORMATICA
100 110 150 165 170 175 180
0 1 2 3 4 5 6
175
La ri
cerc
a di
coto
mic
a
indice
altezza
h
6
0
3
inizio
fine
mezzo
+1
1 trova h in altezza : 2 N = lunghezza di altezza; 3 i nizio = O; 4 f i ne= N-1 ; 5 finché inizi o< fine 6 mezzo= int ((inizio+ fine) /2) ; 7 se altezza[mezzo] >= h allora 8 fine = mezzo ; 9 altrimenti
10 inizi o = mezzo+l ; 11 se altezza[mezz o] = h allora 12 13 14 15
posizione - mezzo ; altrimenti
posizione - - 1 ; restituisci posizione
D D
MATEMATICA E INFORMATICA
100 110 150 165 170 175 180
0 1 2 3 4 5 6
175
La ri
cerc
a di
coto
mic
a
indice
altezza
h
6
4
5
inizio
fine
mezzo
1 trova h in altezza : 2 N = lunghezza di altezza ; 3 i nizio= O; 4 fine= N-1 ; 5 finché inizi o< f i ne 6 mezzo= int((inizi o+ fine)/2) ; 7 se altezza[mezzo] >= h allora 8 fine = mezzo ; 9 altrimenti
10 inizi o = mezzo+l ; 11 se altezza[mezzo] = h allora 12 posizione - mezzo ; 13 altrimenti 14 posizione - - 1; 15 restituisci posizione
MATEMATICA E INFORMATICA
100 110 150 165 170 175 180
0 1 2 3 4 5 6
175
La ri
cerc
a di
coto
mic
a
indice
altezza
h
5
4
4
inizio
fine
mezzo
+1
1 trova h in altezza : 2 N = lunghezza di altezza ; 3 i nizio= O; 4 fine= N-1 ; 5 finché inizi o< f i ne 6 mezzo= int((inizi o+ fine)/2) ; 7 se altezza[mezzo] >= h allora 8 fine = mezzo ; 9 altrimenti
10 inizi o = mezzo+l ; 11 se altezza[mezzo] = h allora 12 posizione - mezzo ; 13 altrimenti 14 posizione - - 1; 15 restituisci posizione
MATEMATICA E INFORMATICA
100 110 150 165 170 175 180
0 1 2 3 4 5 6
175
La ri
cerc
a di
coto
mic
a
indice
altezza
h
5
5
5
inizio
fine
mezzo
n = numero di elementi
Complessità: O(log(n))
1 trova h in altezza : 2 N = lunghezza di altezza ; 3 i nizio= O; 4 fine= N-1 ; 5 finché inizi o< f i ne 6 mezzo= int((inizi o+ fine)/2) ; 7 se altezza[mezzo] >= h allora 8 fine = mezzo ; 9 altrimenti
10 inizi o = mezzo+l ; 11 se altezza[mezzo] = h allora 12 posizione - mezzo ; 13 altrimenti 14 posizione - - 1; 15 restituisci posizione
MATEMATICA E INFORMATICA
100 110 150 165 170 175 180
0 1 2 3 4 5 6
175
Usia
mo
la ri
cors
ione
? indice
altezza
h
1 trova h in altezza: 2 N = l unghezza di al t ezza ; 3 se N > 1 allora 4 mezzo = i nt((N-1)/2) ; 5 se altezza[mezzo] >= h allora 6 pos i zione= trova h in a l tezza [ O, mezzo] ; 7 altrimenti 8 pos i z i one += trova h in a l tezza[mezzo + l , N-1 ]; 9 altrimenti
10 se altezza[O] - h allora 11 12 13 14
pos i z i on e - O; altrimenti
pos i zione -1 ; restituisci posizione
MATEMATICA E INFORMATICA
TU
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
TU
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
TU
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
seduto
alzato
MATEMATICA E INFORMATICA
0••••••••••••• ••••••• •••••• •••••••••••••• •• • •••• •••••• ••••••• ••••••
MATEMATICA E INFORMATICA
1••••••••••••• ••••••• •••••• • ••• •••••••••• • • • • ••• •••••• • ••• ••• ••••••
MATEMATICA E INFORMATICA
2••••••••••••• ••••• •• •••••• • ••• • ••••••••• • ••• • •• •••••• • ••• • •• ••••••
MATEMATICA E INFORMATICA
3•••••• ••••••• ••••• • • •••••• ••••• • •••••••• ••••• • • •••••• ••••• • • ••••••
MATEMATICA E INFORMATICA
4•••••• • •••••• •••••• • •••••• •••••• • ••••••• •••••• • •••••• •••••• • ••••••
MATEMATICA E INFORMATICA
5••••••••••••• ••••••• •••••• ••••••• • •••••• ••••••• •••••• ••••••• ••••••
MATEMATICA E INFORMATICA
6••••••••••••• ••••••• • ••••• •••••••• • ••••• ••••••• • ••••• ••••••• ••••••
MATEMATICA E INFORMATICA
7••••••• •• •••• ••••••• • • •••• ••••••••• • •••• ••••••• • • •••• ••••••• •• ••••
MATEMATICA E INFORMATICA
8••••••••• • ••• ••••••• •• • ••• •••••••••• • ••• ••••••• •• • ••• ••••••• •• • •••
MATEMATICA E INFORMATICA
9•••••••••• • •• ••••••• ••• • •• ••••••••••• • •• ••••••• ••• • •• ••••••• ••• • ••
MATEMATICA E INFORMATICA
10••••••••••• • • ••••••• •••• • • •••••••••••• • • ••••••• •••• • • ••••••• •••• • •
MATEMATICA E INFORMATICA
11•••••••••••• • ••••••• ••••• • ••••••••••••• • ••••••• ••••• • ••••••• ••••• •
MATEMATICA E INFORMATICA
11•••••••••••• • ••••••• ••••• • ••••••••••••• • ••••••• ••••• • ••••••• ••••• •
MATEMATICA E INFORMATICA
Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
TUTocca a te, ma…Quando dico «Via!»Se sei AnnaAlzatiFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto
MATEMATICA E INFORMATICA
TU
Quando un tuo vicino ti passa il suo messaggiopassa il messaggio al vicino di cui ricordi la posizione
MATEMATICA E INFORMATICA
••••••••••••• ••••••• •••••• ••••• ••• •••••• •• • •• •• •• •••• ••••••• •• • •••
MATEMATICA E INFORMATICA
[email protected]://informatica.uniurb.it/
http://codemooc.org/algomooc/
Gra
zie
per l
’att
enzi
one
![Università degli studi di Catania - INFORMATICA MATEMATICA ... · Università degli studi di Catania - INFORMATICA A.A. 2014-2015 MATEMATICA E INFORMATICA - Y70 INFORMATICA [X81]](https://static.fdocumenti.com/doc/165x107/5ed9a02a5139c40fce6755fb/universit-degli-studi-di-catania-informatica-matematica-universit-degli.jpg)
