Algoritmi e Strutture Dati Laurea in Informatica
Calendario: 9 Marzo – 12 Giugno Aula: P200 (?)
Orario: Mer 12.30-14.15
Gio, Ven 14.30-16.15 Numero crediti = 9 (~ 72 ore)
~ 52 ore di teoria, ~20 ore di esercizi Docenti: Paolo Baldan (5 crediti)
Michele Scquizzato (4 crediti)
a. Prova intermedia
per l’assegnazione di un bonus fino a 3 punti (che si somma al voto dell’esame finale) [?]
b. Prova scritta
(5 appelli - indispensabile iscriversi nella lista di esame che verrà attivata su UNIWEB)
c. Registrazione, con possibile orale (su base volontaria). Indispensabile per conseguire la lode.
Modalità d’Esame
Testo: Introduzione agli Algoritmi e Strutture Dati (3°
ed). T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
McGraw-Hill.
Pagina del corso: www.math.unipd.it/~
baldan/Algoritmi
+ Moodle con altro materiale
Trad. di: Introduction to Algorithms and Data Structures (3° ed). T.H.Cormen, C.E.Leiserson, R.L.Rivest,
C.Stein. MIT Press.
Materiale didattico
Programma
Le prime 5 parti del testo (con qualche omissione):
I. Fondamenti: notazione per gli algoritmi e primi esempi di algoritmi e di analisi degli algoritmi II. Ordinamento e statistiche d’ordine
III. Strutture dati fondamentali
IV. Tecniche avanzate di progettazione ed analisi degli algoritmi
V. Strutture dati avanzate
I problemi computazionali, gli algoritmi che li risolvono e le tecniche per sviluppare tali
algoritmi
INTRODUZIONE
Esempio1: problema dell’ordinamento
Input: a1,a2,...,an
Output: a'1,a'2,...,a'n permutazione (riarrangiamento) di a1,a2,...,an tale che a'1 a'2 ... a'n
TECNICA
INCREMENTALE
Soluzione1: Algoritmo Insertion-Sort.
InsertionSort1 n
A
1 n
A
1 j n
A key
1 j n
A i
1 j n
A
j
1 n
A j
1 j n
A i
key
1 j n
Ai key
Insertion-Sort(A) n = A.length for j = 2 to n
key = A[j]
// inseriamo A[j] nella sequenza // ordinata A[1..j-1]
i = j - 1
while i > 0 and A[i] > key A[i+1] = A[i]
i = i – 1 A[i+1] = key
Insertion-Sort(A) n = A.length for j = 2 to n key = A[j]
// inseriamo A[j] nella // sequenza ordinata // A[1..j-1]
i = j – 1
while i > 0 and A[i] > key A[i+1] = A[i]
i = i – 1 A[i+1] = key
void Insertion-Sort(vector<T> A) {
int i, j, n = A.size(); T key;
for (j = 1; j < n; j++) {
key = A[j];
// inseriamo A[j] nella // sequenza ordinata // A[0..j-1]
i = j – 1;
while (i >= 0 && A[i] > key) {
A[i+1] = A[i];
i--;
}
A[i+1] = key;
} }
Insertion-Sort(A) n = A.length
for j = 2 to n
// inserisce A[j] nella // sequenza ordinata // A[1..j-1]
key = A[j]
i = j – 1
while i > 0 and A[i] > key A[i+1] = A[i]
i = i – 1 A[i+1] = key A
5 2 8 4 7 1 3 6
key
5 # 8 4 7 1 3 6 2
# 5 8 4 7 1 3 6 2 5 8 4 7 1 3 6
2 5 # 4 7 1 3 6 8
2 5 # 4 7 1 3 6 2 5 8 4 7 1 3 6
2 5 8 # 7 1 3 6 4
2 # 5 8 7 1 3 6 2 4 5 8 7 1 3 6
2 4 5 8 # 1 3 6 7
2 4 5 # 8 1 3 6 2 4 5 7 8 1 3 6
Insertion-Sort(A) n = A.lenght
for j = 2 to n
// inserisce A[j] nella // sequenza ordinata // A[1..j-1]
key = A[j]
i = j – 1
while i > 0 and A[i] > key A[i+1] = A[i]
i = i – 1 A[i+1] = key A
2 4 5 7 8 1 3 6
key
2 4 5 7 8 # 3 6 1
# 2 4 5 7 8 3 6 1 2 4 5 7 8 3 6
1 2 4 5 7 8 # 6 3
1 2 # 4 5 7 8 6 1 2 3 4 5 7 8 6
1 2 3 4 5 7 8 # 6
1 2 3 4 5 # 7 8 1 2 3 4 5 6 7 8
Insertion-Sort(A) n = A.length
for j = 2 to n key = A[j]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i – 1
A[i+1] = key
Analisi di Insertion-Sort: correttezza
Correttezza InsertionSort
1 j n
A
i
1 j n
A
1 j n
A
i
1 j n
Ai
1 j n
A
Analisi di Insertion-Sort: complessità Insertion-Sort(A) //
n = A.length //
for j = 2 to n //
key = A[j] //
i = j -1 //
while i > 0 and A[i] > key //
A[i+1] = A[i] //
i = i – 1 //
A[i+1] = key //
) 1
2(
5
n
j t j
c c0
n c2
) 1
3(n c
) 1
4(n c
nj t j
c6 2
nj tj
c7 2 ) 1
8(n c
j t j
0
c1
n
j j
n
j j
IS
t c
c t
c
n c
c c
n c c
c n
T
7 2 2 6
5
8 4
3 2
1 0
) (
) 1 (
) 1 )(
( )
(
caso migliore:
n j n
j IS
c c
c
n c
c c
n c c
c n
T
7 2 2 6
5
8 4
3 2
1 0
min
0 )
( 1
) 1 )(
( )
(
0
t j 0 tj j
a bn
c c
c c
c c
n c
c c
c c
n T IS
( ) ( )
)
( 2 3 4 5 8 0 1 3 4 5 8
min
caso peggiore: t
j j 1
' '
'
) (
2 ) 1 2
1 2
( 1
) 2 (
) 1 (
2
8 4
3 1
0
8 7
6 5
4 3
2
2 7
6 5
max
a n
b n
c
c c
c c
c
n c
c c
c c
c c
n c
c c
n T IS
j t
j
0
n j n
j IS
j c
c j
c
n c
c c
n c c
c n
T
7 2 2 6
5
8 4
3 2
1 0
max
) 1 (
) (
) 1 )(
( )
(
caso medio:
n j n j
j
j IS
c c
c
n c
c c
n c c
c n
T
2 2 7 1
2 2 6 5 1
8 4
3 2
1 0
med
) (
) 1 )(
( )
(
2
1
jt
j"
"
"
) (
4 ) 1 4
1 4
( 3
) 4 (
) 1 (
2
8 5
4 3
1
8 7
6 5
4 3
2
2 7
6 5
med
a n
b n
c
c c
c c
c
n c
c c
c c
c c
n c
c c
n T IS
j t
j
0
TECNICA
DIVIDE ET IMPERA
5 2 8 0 4 7 1 9 3 2 6
0 4 7 2
5
5 2 8
5 2 8 0 4 7
5 2 8 0 4 7 1 9 3 2 6
2 6 1 9 3
1 9 3 2 6
9 1
4 0
5 2 8 0 4 7 1 9 3 2 6
5 2 8 0 4 7 1 9 3 2 6
5 2 8 0 4 7 1 9 3 2 6
5 2 8 2
5
0 4 7 1 9 3
4
0 1 9
6 2
0 1 2 2 3 4 5 6 7 8 9 0 2 4 5 7 8
2 5 8 2 5
5 2
8
1 2 3 6 9
0 4 7 1 3 9 2 6
0 4 7 1 9 3
4
0 1 9
6 2
Soluzione2: Algoritmo Merge-Sort
Merge-Sort(A,p,r) if p < r
q = (p+r)/2
Merge-Sort(A,p,q) Merge-Sort(A,q+1,r) Merge(A,p,q,r)
L
0 2 4 5 7 8 1 2 3 6 9
0 2 4 5 7 8 R 1 2 3 6 9 A[p..q] A[q+1..r]
0
2 4 5 7 8 1 2 3 6 9
0 1
2 4 5 7 8 2 3 6 9
0 1 2
4 5 7 8 2 3 6 9 0 1 2 2
4 5 7 8 3 6 9 0 1 2 2 3
4 5 7 8 6 9 0 1 2 2 3 4
5 7 8 6 9 0 1 2 2 3 4 5
7 8 6 9 0 1 2 2 3 4 5 6
7 8 9 0 1 2 2 3 4 5 6 7
8 9 0 1 2 2 3 4 5 6 7 8
9 0 1 2 2 3 4 5 6 7 8 9
A[p..r]
Merge(A,p,q,r) n1 = q – p + 1 n2 = r – q
for i = 1 to n1
L[i] = A[p + i – 1]
for j = 1 to n2 R[j] = A[q + j]
L[n1 + 1] = R[n2 + 1] = i = j = 1
for k = p to r if L[i] R[j]
A[k] = L[i]
i = i + 1 else
A[k] = R[j]
j = j + 1
Merge-Sort(A,p,r)
if p < r // altrimenti A[p..r] è ordinato q = (p+r)/2
Merge-Sort(A,p,q) Merge-Sort(A,q+1,r)
Merge(A,p,q,r)
Analisi di Merge-Sort: correttezza
non ordinati
1 p r n
A
ordinati
1 p r n
A
ordinati
1 p ordinati r n
A q
Merge(A,p,q,r) n1 = q – p + 1 n2 = r – q
for i = 1 to n1
L[i] = A[p + i – 1]
for j = 1 to n2 R[j] = A[q + j]
L[n1 + 1] = R[n2 + 1] = i = j = 1
for k = p to r if L[i] R[j]
A[k] = L[i]
i = i + 1 else
A[k] = R[j]
j = j + 1
1 p q r n
A
1 p r n
A
L ∞ R ∞
1 n1 1 n2
1 p r n
A
L ∞ R ∞
1 n1 1 n2
k
i j
1 p r n
A
L ∞ R ∞
1 n1 1 n2
k
i j
Merge(A,p,q,r) // complessità//
n1 = q – p + 1 //
n2 = r – q //
for i = 1 to n1 //
L[i] = A[p + i – 1] //
for j = 1 to n2 //
R[j] = A[q + j] //
L[n1 + 1] = R[n2 + 1] = //
i = j = 1 //
for k = p to r //
if L[i] R[j] //
A[k] = L[i] //
i = i + 1 //
else
A[k] = R[j] //
j = j + 1 //
c1
c2
c3
1 1
4 n c
1 5n c4n2 1
c
2 5n c
c6
(p r)/2
q
2 11n c
c7
1
8 n c
1 11n c
n c9
1 10n c
2 10n c
1
r p n
/2
1 n
n
/ 2
2 n
n
2
1 n
n n
' '
2
) (
) (
8 7
6 4
3 2
1
11 10
9 8
5 4
b n a
c c
c c
c c
c
n c
c c
c c
c n
T M
Merge-Sort(A,p,r) //complessità //
if p < r //
q = (p+r)/2 //
Merge-Sort(A,p,q) //
Merge-Sort(A,q+1,r) //
Merge(A,p,q,r) //
c1
c2
c3
n1
T MS
n2
TMS
n a'n b'
TM
1
r p n
1 se
) ( )
( )
(
1 ) se
(
2 1
3 2
1
2 1
n n
T n
T n
T c
c c
n c
n c
T MS MS MS M
1 q p 1 n
q r n2
2
1 n
n n
1 se
) (
) (
1 ) se
(
2
1 T n n
n T
b an
n n c
T MS MS MS
n an
n
b n cnT MS log2 ( 1)
b
an1,1 an1,2 b an2,1 b an2,2 b
log2 n
c c c c c c c c c c c c
b an
b an 2
b an 4
cn
n can bT n1 T n2 sese nn 11
TMS MS MS
b an
n1
T MS T MS n2
b an1
n1,1
TMS TMS n1,2 TMS n2,an1 2 b TMS n2,2
n a'n log2 n b'n c'T MS
Dunque esiste N tale che per ogni n > N.
Qualunque siano i valori delle costanti a', b', c', a", b" e c"
l’algoritmo Merge-Sort è superiore a Insertion-Sort per array di dimensione sufficientemente grande.
lim ' "log " ' " ' 0lim 2 2
a n b n c
c n
b n
n a n
T
n T
IS n med
MS n
n T
nT MS medIS
n a'n log2 n b'n c'T MS
"
"
"
)
(n a n2 b n c TmedIS
Possiamo dire che “cresce come” n2 mentre “cresce come” n log2 n.
n n2 n log2 n
IS n2 ns
MS
n log2 n ns
10 100 33 0.1s 0.033s
100 10000 664 10s 0.664s
1000 106 9965 1ms 10s
10000 108 132877 0.1s 133s
106 1012 2·107 17m 20ms
109 1018 3·1010 30s
109 1018 3·1010 70anni 30s
nTmedIS
nT MS
dunque esiste N tale che per ogni n > N.
Qualunque siano i valori delle costanti a', b', c', a", b" l’algoritmo Insertion-Sort è superiore a Merge-Sort per array (quasi) ordinati e
sufficientemente grandi.
" "
' '
log lim '
lim 2
b n
a
c n
b n
n a n
T
n T
IS n min
MS n
n T
nT MS minIS
Insertion-Sort è anche superiore a Merge-Sort per array piccoli in quanto le costanti a', b', c' in sono generalmente molto maggiori delle costanti a", b" e c" in .
Questo suggerisce una modifica di Merge-Sort in cui le porzioni di array di dimensione minore di una certa costante k si ordinano con Insertion-Sort invece di usare ricorsivamente Merge-Sort.
nT MS
nTmaxIS
Soluzione3: Algoritmo Merge-Ins-Sort
Merge-Ins-Sort(A,p,r) if p < r
if r-p+1 < 32
InsertSort(A,p,r) else
q = (p+r)/2
Merge-Ins-Sort(A,p,q) Merge-Ins-Sort(A,q+1,r) Merge(A,p,q,r)
Complessità e Notazione Asintotica
Quando si confrontano algoritmi, determinare il tempo di esecuzione
- È complicato
- Contiene dettagli inutili che vorremmo ignorare
- Dipende da costanti non note
vogliamo darne una visione più astratta (tasso di crescita)
Paragonare tra loro algoritmi
Abbiamo una scala di complessità:
vogliamo inserire ogni algoritmo in questa scala
1 log
log ...
2 ...
2 3
n n n n
n n
n
Un algoritmo può richiedere tempi diversi per input della stessa taglia. Ad esempio il tempo per ordinare n oggetti può dipendere dal loro ordine iniziale.
complessità massima
complessità minima complessità media
1 log
log ...
2 ...
2 3
n n n n
n n
n
Nell’analizzare la complessità tempo di un algoritmo siamo interessati a come aumenta il tempo al crescere della taglia n dell’input.
Siccome per valori “piccoli” di n il tempo richiesto è comunque poco, ci interessa
soprattutto il comportamento per valori
“grandi” di n (il comportamento asintotico)
Inoltre, siccome la velocità del processore influisce sul tempo calcolo per una costante moltiplicativa noi valuteremo la complessità a meno di una tale costante.
Questo giustifica le seguenti definizioni:
Notazione asintotica O (limite superiore asintotico)
O(g(n))
} ogni
per )
( )
( 0
che tali
ed 0
esistono :
) ( { ))
( (
0 0
n n
n cg n
f
n c
n f
n g
) (n f
) (n cg
n0
Scriveremo f(n) = O(g(n)) per dire che f(n) è una delle funzioni dell’insieme O(g(n))
f(n) = O(g(n)) si legge:
f(n) è “o grande” di g(n)
Se f(n) = O(g(n)) rappresenta il tempo calcolo richiesto da un algoritmo diciamo che O(g(n)) è un limite superiore asintotico per la
complessità tempo di tale algoritmo.
esempi
infatti
per c = 4 ed n
0= 5
infatti
per c = 3 ed n
0= 1
Vedremo che in generale per a
2> 0
) (
5 5
2 )
(n n2 n O n2
f
2
2 5 5
2
0 n n cn
) 1 ( sin
2 )
( n n O
f
1 sin
2
0 n c
) (
)
( n a
2n
2a
1n a
0O n
2f
Notazione asintotica .
(limite inferiore asintotico)
} ogni
per 0
) ( )
(
che tali
ed 0 esistono
: ) ( { ))
( (
0 0
n n
n cg n
f
n c
n f n
g
) (n f
) (n cg
n0
Se f(n) = (g(n)) rappresenta il tempo
calcolo richiesto da un algoritmo diciamo che
(g(n)) è un limite inferiore asintotico per la complessità tempo di tale algoritmo.
Scriveremo f(n) = (g(n)) per dire che f(n) è una delle funzioni dell’insieme (g(n)).
f(n) = (g(n)) si legge:
f(n) è “omega” di g(n)
esempi
infatti
per c = 1 ed n
0= 10
infatti
per c = 1 ed n
0= 1
Vedremo che in generale se a
2> 0
) (
5 5
2 )
(n n2 n n2
f
5 5
2
0 cn2 n2 n
) 1 ( sin
2 )
(n n f
n c 1 2 sin 0
) (
)
(n a2n2 a1n a0 n2
f
Notazione asintotica .
(limite asintotico stretto)
)}
( )
( )
( 0
ogni per
che tali
ed 0
,
esistono :
) ( { ))
( ( ))
( ( ))
( (
2 1
0 0
2 1
n g c n
f n
g c
n n
n c
c
n f n
g n
g O n
g
) (n f
)
1g(n c
n0
)
2g(n c
Se f(n) = (g(n)) rappresenta il tempo calcolo richiesto da un algoritmo diciamo che (g(n)) è un limite asintotico stretto per la
complessità tempo di tale algoritmo.
Scriveremo f(n) = (g(n)) per dire che f(n) è una delle funzioni dell’insieme (g(n)).
f(n) = (g(n)) si legge:
f(n) è “theta” di g(n)
esempi
per c1 = 1, c2 = 4 ed n0 = 10 Dunque
Dunque
) (
5 5
2n2 n O n2 2n2 5n 5 (n2)
2 2 2
2
1 2 5 5
0 c n n n c n
) (
5 5
2n2 n n2
) 1 ( sin
2 n O 2 sin n (1)
) 1 ( sin
2 n
per ogni n n0 allora altrimenti
per ogni n n0. Assurdo!
per ogni n n0 allora altrimenti
per ogni n n0. Assurdo!
) (
5 5
2 )
(n n2 n n3
f
5 5
2
0 c1n3 n2 n
3 1 2
5 5
2
n n
c n
) ( 5
5 2
)
(n n2 n n
f
n c n
n2 5 5 2 2
0
n c n
n
2 2
5
2 5
Metodo del limite
Spesso è possibile determinare dei limiti
asintotici calcolando il limite di un rapporto.
Ad esempio se
allora per ogni > 0 esiste n0 tale che per n ≥ n0 Preso 0 < < k e posto c1 = k e c2 = k +
e quindi
0 )
( /
) (
lim
nf n g n k
f n g n k
k ( ) / ( )
) ( )
( )
(
21
g n f n c g n
c
)) (
( )
( n g n
f
Se diciamo che
Attenzione: quando il limite del rapporto non esiste questo metodo non si può usare.
ed in questo caso
Se diciamo che ed in questo caso
( )
) lim (
n g
n f
n f (n) (g(n))
)) (
( )
(
ma
)) (
( )
(n g n f n g n
f
) 0 (
) lim (
n g
n f
n
f ( n ) o ( g ( n ))
)) (
( )
(
ma
)) (
( )
(n O g n f n g n
f
In generale
per ogni funzione polinomiale di grado k con coefficiente ak > 0.
Inoltre
) (
...
)
(n aknk a1n a0 nk
f
b a
b
a
n
n
( ) ( ) per
b a
n
n b
a ) (log ) per ogni e (log
) (
) log
( n
kn n
k
h k
n
n
k
h
( ) ( ) per
n b
n a b
a log log
log
perché
Per 0 < h < k e 1 < a < b :
) (
) (
) log
(
) (
) (
) (log
n n
k
k h
b O
a O
n n
O
n O
n O
n O
) (
) (
) log
(
) (
) (
) (log
n n
k
k h
b a
n n
n n
n
Useremo le notazioni asintotiche anche all’interno delle formule.
In questo caso le notazioni O(f(n)), Ω(f(n)) e
ϴ(f(n)) stanno ad indicare una qualche funzione appartenente a tali insiemi e di cui non ci
interessa conoscere la forma esatta ma solo il comportamento asintotico.
Ad esempio T(n)=n2+O(n) significa che T(n) è la somma di n2 e di una funzione che cresce al più linearmente.
esiste un algoritmo che risolve il problema con questa complessità
limite superiore: O(n2)
Valutare la difficoltà dei problemi
1 log
log ...
2 ...
2 3
n n n n
n n
n
Valutare la difficoltà dei problemi
ogni algoritmo che risolve il problema ha complessità
maggiore o uguale di questa limite inferiore: (n)
1 log
log ...
2 ...
2 3
n n n n
n n
n
Un limite superiore per il problema dell’ordinamento
Abbiamo visto che Insert-Sort per ordinare n oggetti richiede O(n
2) operazioni
Quindi O(n
2) è un limite superiore
Vedremo in seguito che (n log n) è un limite stretto per il problema dell’ordinamento.
Per ora ci limitiamo a dimostrare che:
La complessità nel caso pessimo di ogni
algoritmo di ordinamento sul posto che confronta e scambia tra loro soltanto elementi consecutivi dell’array è (n2).
Quindi il problema di ordinare sul posto un array scambiando tra loro soltanto elementi consecutivi ha complessità (n2).
Se l’array è ordinato non ci sono inversioni.
Se l’array è ordinato in senso opposto e gli
elementi sono tutti distinti allora ogni coppia (i, j) di indici con i < j è una inversione e quindi ci
sono esattamente n(n-1)/2 inversioni.
Sia A[1..n] un array
Se i < j e A[i] > A[j] diciamo che la coppia di indici (i, j) è una inversione
8 3
i j
3
k
Come cambia il numero di inversioni quando facciamo uno scambio tra due elementi
consecutivi A[i] ed A[i+1] dell’array?
Consideriamo tutte le coppie di indici ( j, k) con j < k e vediamo quante e quali di esse
possono cambiare di stato da inversioni a non inversioni o viceversa quando scambiamo
A[i] con A[i+1].
x
i i+1
y
Se j e k sono entrambi diversi da i e i+1 la coppia ( j, k) non cambia di stato e quindi il numero di inversioni di questo tipo non cambia.
y x
i i+1
u v
k j
(i, k) è inversione dopo lo scambio se e solo se (i+1, k) lo era prima e (i+1, k) è inversione se e solo se (i, k) lo era prima.
y x
i i+1
v
k
x y
i i+1
v
k
Quindi le due coppie si scambiano gli stati ma il numero totale di inversioni non cambia.
Consideriamo le due coppie (i, k) e (i+1, k) con k > i+1 ossia