Laboratorio di Algoritmi e Strutture Dati

(1)

Laboratorio di Algoritmi e Strutture Dati

Marco Tarini

e-mail: marco.tarini@uninsubria.it

(2)

Argomenti del corso

Calcolo del tempo di computazione di un algoritmo:

I Esercizi di analisi formale: sommatorie, ricorrenze;

I Misurazione sperimentale dei tempi di calcolo;

Implementazione in C di alcuni algoritmi e strutture dati visti a lezione:

I Algoritmi di Ricerca e Ordinamento;

I Strutture: liste concatenate, alberi, BST, RB-alberi, Grafi;

I Algoritmi ricorsivi e iterativi;

I Programmazione dinamica.

Variazioni di implementazioni usate frequentemente.

Lezionifrontalie (secondo disponibilit`a delle aule) inlaboratorio.

(3)

Modalit` a d’esame

L’esame `e in comune con il Prof. Massazza (15 CFU totali).

Per poter fare l’orale bisogna preparare unprogetto in C:

I tre settimane a disposizione;

I si consegna indicativamente 7ggprima dell’orale (ladatavaria a seconda dell’appello);

I si discute nello stesso giorno dell’orale.

Tutte le informazioni sul sito del corso.

(4)

Materiale didattico

Materiale del corso (sul sito, a breve):

I file delle presentazioni;

I codice usato a lezione;

I calendario delle lezioni;

I avvisi di modifiche all’orario;

I avvisi per gliappelli;

I materiale aggiuntivo;

I links utili;

Per informazioni, contattatemi per posta elettronica.

e-mail: tarini@uninsubria.it

(5)

Testi di riferimento

Robert Sedgewick.

Algoritmi in C.

Addison-Wesley, Pearson Italia, 2002.

Brian W. Kernighan, Dennis M. Ritchie.

Linguaggio C (seconda edizione),

Nuova edizione italiana, Pearson, Italia, 2004.

Al Kelley, Ira Pohl.

C Didattica e Programmazione (A book on C, 4th edition).

Pearson, Italia, 2004.

(6)

Compilatore di riferimento

Useremo il compilatoregcc(GNU Compiler Collection).

Scaricatelo da

I per UNIX:

http://gcc.gnu.org/

I per Windows:

http://www.cs.colorado.edu/~main/cs1300/

Oppure un IDE qualunque

I es, DevCpp

(7)

Calcolo delle prestazioni degli algoritmi

Un algoritmo `e un insieme di istruzioni finalizzate a risolvere un problema.

I Ci possono essere pi`u algoritmi che risolvono lo stesso problema.

I (ma un algoritmo risolve un solo problema).

Per valutare quale siamiglioresi analizzano quante risorse impegano per resituire una soluzione:

I tempo (di calcolo)

← soprattutto questo

I spazio (di memoria)

I banda (di rete)

I eccetera

(8)

Calcolo delle prestazioni degli algoritmi

I tempo (di calcolo)

← soprattutto questo

I spazio(di memoria)

I banda (di rete)

I eccetera

(9)

Calcolo delle prestazioni degli algoritmi

I tempo (di calcolo) ← soprattutto questo

I spazio(di memoria)

I banda (di rete)

I eccetera

(10)

Calcolo delle prestazioni degli algoritmi (cont.)

Il tempo di esecuzione dipende da molti fattori. Lo stesso algoritmo impiega:

I tempo diverso su input diversi ⁽¹⁾;

I tempi diversi sullo stesso input, quando `e eseguito su computer diversi⁽²⁾.

(1) Chiediamo che il tempo di esecuzione sia stimato in relazione alla grandezza dell’input.

(2) L’analisi di complessit`a degli algoritmi cerca di stabilire il tempo di calcoloindipendentemente dalla macchina sulla quale `e

implementato il programma.

(11)

Calcolo delle prestazioni degli algoritmi (cont.)

(2) L’analisi di complessit`a degli algoritmi cerca di stabilire il tempo di calcoloindipendentementedalla macchina sulla quale `e

(12)

Calcolo delle prestazioni degli algoritmi (cont.)

(2) L’analisi di complessit`a degli algoritmi cerca di stabilire il tempo di calcoloindipendentementedalla macchina sulla quale `e

(13)

Esempio 1

Supponiamo che la stampa di un numero costi 1 secondo

e consideriamo un programma che legge un numero n e:

Caso A: stampa inumerida 0 a n − 1.

Caso B: stampa tutte lecoppie di numerida 0 a n − 1.

Caso C: stampa tutte lepotenze di 2 pi`u piccole di n.

(14)

Esempio 1 (cont.)

Tabella di esecuzione

Al variare di n indichiamo quanti secondi spende ogni algoritmo per la stampa:

n A B C

1

1 1 1

2

2 4 2

3

3 9 2

4

4 16 3

5

5 25 3

10

10 100 4

20

20 400 5

50

50 2500 6

100

100 10000 7

1000 1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(15)

Esempio 1 (cont.)

n A B C

1 1

2 2

4 2

3 3

9 2

4 4

16 3

5 5

25 3

10 10

100 4

20 20

400 5

50 50

2500 6

100 100

10000 7

1000 1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(16)

Esempio 1 (cont.)

n A B C

1 1 1

1

2 2 4

2

3 3 9

2

4 4 16

3

5 5 25

3

10 10 100

4

20 20 400

5

50 50 2500

6

100 100 10000

7 1000 1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(17)

Esempio 1 (cont.)

n A B C

1 1 1 1

2 2 4 2

3 3 9 2

4 4 16 3

5 5 25 3

10 10 100 4

20 20 400 5

50 50 2500 6

100 100 10000 7

1000 1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(18)

Esempio 1 (cont.)

n A B C

1 1 1 1

2 2 4 2

3 3 9 2

4 4 16 3

5 5 25 3

10 10 100 4

20 20 400 5

50 50 2500 6

100 100 10000 7

1000

1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(19)

Esempio 1 (cont.)

n A B C

1 1 1 1

2 2 4 2

3 3 9 2

4 4 16 3

5 5 25 3

10 10 100 4

20 20 400 5

50 50 2500 6

100 100 10000 7

1000 1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(20)

Esempio 1 (cont.)

n A B C

1 1 1 1

2 2 4 2

3 3 9 2

4 4 16 3

5 5 25 3

10 10 100 4

20 20 400 5

50 50 2500 6

100 100 10000 7

1000 1.000 1.000.000 10 10⁶

10⁶ 10¹² 20

(21)

Esempio 1 (cont.)

n A B C

1 1 1 1

2 2 4 2

3 3 9 2

4 4 16 3

5 5 25 3

10 10 100 4

20 20 400 5

50 50 2500 6

100 100 10000 7

1000 1.000 1.000.000 10

10⁶ 10⁶ 10¹² 20

(22)

Esempio 1 (cont.)

Ledifferenzetra il costo dei diversi algoritmi sono tanto più grandi quanto è più grande l’input.

Caso A se l’input raddoppia di grandezza, il costoraddoppia.

Caso B se l’input raddoppia di grandezza, il costoquadruplica.

Caso C se l’input raddoppia di grandezza, il costoaumenta di 1 sec.

25

15

5

0

4 5

3 2

1

n 10

20

(23)

Velocit` a di crescita delle funzioni

Lacomplessit`adi un algoritmo deve quindi essere funzione della dimensione dell’input.

Pervalori piccolidegli input, algoritmi con tempi di esecuzione diversipossono impiegare in realt`atempi molto simili.

Ma quando gli input hannodimensione maggiore, allora la differenza diventa rilevante.

(24)

Pseudo-codice

I Caso A:

for (i=0;i<n;i++) print(i);

I Caso B:

for (i=0;i<n;i++) for (j=0;j<n;j++)

print((i,j));

I Caso C:

for (i=1;i<n;i=2*i) print(i);

(25)

Esempio 1 (cont.)

Che succede se il costo passa da1 a50 secondiper operazione?

n A B C

1

50 50 50

2

100 200 100

3

150 450 100

4

200 800 150

5

250 1250 150

10

500 5000 200

50

2500 125000 300

100

5000 5000000 350

(26)

Esempio 1 (cont.)

n A B C

1 50

50 50

2 100

200 100

3 150

450 100

4 200

800 150

5 250

1250 150

10 500

5000 200

50 2500

125000 300

100 5000

5000000 350

(27)

Esempio 1 (cont.)

n A B C

1 50 50

50

2 100 200

100

3 150 450

100

4 200 800

150

5 250 1250

150

10 500 5000

200

50 2500 125000

300

100 5000 5000000

350

(28)

Esempio 1 (cont.)

n A B C

1 50 50 50

2 100 200 100

3 150 450 100

4 200 800 150

5 250 1250 150

10 500 5000 200

50 2500 125000 300 100 5000 5000000 350

(29)

Esempio 1 (cont.)

Al crescere dell’input, i comportamenti restano uguali:

Caso A se l’input raddoppia di grandezza, il costoraddoppia.

Caso B se l’input raddoppia di grandezza, il costoquadruplica.

Caso C²⁵ se l’input raddoppia, il costo aumenta di 50 sec.

15

5

0

4 5

3 2 1

n 10

20

0

n

2 4 5

1200

800

400

1 3

1000

600

200

(30)

Ecco perch` e...

L’analisi dei costi di un algoritmo:

1. si effettua in funzione della dimensione dell’input:

I caso peggiore(su input di dimensione n)

I caso ottimo(su input di dimensione n)

I caso medio(su input di dimensione n)

I ma: su che distribuzione degli input?;

2. si studia spesso in termini di comportamento asintotico:

I le costanti diventano importanti solo in situazioni particolari o aparit`a di costoasintotico;

I leequazioniche descrivono il costo diventanopi`u semplici.

(31)

Notazioni asintotiche

Ripasso delle definizioni

Def: siano f eg due funzioni da N in N.

I f (n) = O(g (n)) sse ∃c, n₀∈ N | ∀n > n₀,f (n) < cg (n);

I f (n) = Ω(g (n)) sse ∃c, n₀ ∈ N | ∀n > n₀,cf (n) > g (n);

I f (n) = Θ(g (n))sse f (n) = O(g (n)) e f (n) = Ω(g (n)).

(32)

Esercizio 1: analisi di complessit` a

Insertion Sort

void insertionSort( int a[], int length ) { int i, j, v;

for ( i = 1; i < length; i++ ) { j = i - 1;

v = a[i];

while ( ( j >= 0 ) && ( a[j] > v ) ) { a[j+1] = a[j];

j--;

}

a[j+1] = v;

} }

I Caso migliore: Θ(n);

I Caso peggiore: Θ(n²);

I Caso medio: Θ(n²);

(33)

Esempio.

La funzione f : n ∈ N 7→ 2n `e O(n).

Infatti per n > 1 si ha 2n ≤ 3n.

Esercizi:

I 5n²+ n = O(n²) ?

I log₂(8n) = O(n) ?

I n² = O(n) ?

(34)

Alcune propriet` a

O e Ω sono relazioni opposte.

I se g = O(f ) allora f = Ω(g )

Θ `e una relazione di equivalenza!

Per ogni funz f g h da naturali a naturali

I f = Θ(f ) (riflessiva)

I se f = Θ(g ) allora g = Θ(f ) (simmetrica)

I se f = Θ(g ) e g = Θ(h) allora f = Θ(h) (transitiva)

In quanto tale, Θ divide le funzioni in classi di equivalenza.

(35)

Alcune propriet` a

(36)

Alcune propriet` a

(37)

Funzioni di riferimento

Si usano alcune funzioni di riferimento per la notazione asintotica.

I f = Θ(1) : f ha andamentocostante

I f = Θ(log (N)) : f ha andamento logaritmico

I f = Θ(N) : f ha andamento lineare

I f = Θ(Nlog (N)) : f ha andamentopseudo-lineare

I f = Θ(N²) : f ha andamentoquadratico

I f = Θ(N³) : f ha andamentocubico...

I f = Θ(N^K) : f ha andamentopolinomiale(K costante)

I f = Θ(K^N) : f ha andamentoesponenziale(K costante) Sonoclassi di equivalenzaper Θ! (una per ogni K ).

(38)

A parole

Per N abbastanza grandi, e a meno di una costante moltiplicativia...

f = O(g ) significa “f vale meno di g ” f = Ω(g ) significa “f vale pi`u di g ”

f = Θ(g ) significa “f e g si comportano allo stesso modo”

f = O(N²) significa “f ha andamentoal pi`u quadratico”.

f = Ω(N²) significa “f ha andamento almenoquadratico”.

f = Θ(N²) significa “f ha andamento quadratico”.

(39)

Esercizio 2: Alberi

Quanti nodi ha un albero k-ario completo di altezza h?

I il livello 0 contiene 1 nodo (la radice);

I il livello 1 contiene k nodi;

I il livello 2 contiene k² nodi;

I il livello i contiene kⁱ nodi;

1 + k + k²+ · · · + k^(h−1)=

h−1

X

i =0

kⁱ = k^h− 1 k − 1

(40)

Esercizio 2: Alberi

1 + k + k²+ · · · + k^(h−1)=

h−1

X

i =0

kⁱ = k^h− 1 k − 1

(41)

Esercizio 2: Alberi

1 + k + k²+ · · · + k^(h−1)=

h−1

X

i =0

kⁱ = k^h− 1 k − 1

(42)

Esercizio 2: Alberi (cont.)

Quanti cammini diversi partono dalla radice?

I Esiste uno ed un solo cammino dalla radice ad ogni nodo: k^h− 1

k − 1 − 1

E quant’`e la lunghezza totale di questi cammini?

I (per i nodi a livello 1) ho k cammini di lunghezza 1;

I (per i nodi a livello 2) ho k² cammini di lunghezza 2;

I (per i nodi a livello i ) ho kⁱ cammini di lunghezza i ; k + 2k²+ · · · + (h − 1)k^h−1=

h−1

X

i =0

ikⁱ

= k(h − 1)k^h− hk^h−1+ 1 (k − 1)²

(43)

Esercizio 2: Alberi (cont.)

I Esiste uno ed un solo cammino dalla radice ad ogni nodo:

k^h− 1 k − 1 − 1 E quant’`e la lunghezza totale di questi cammini?

h−1

X

i =0

ikⁱ = k(h − 1)k^h− hk^h−1+ 1 (k − 1)²

(44)

Esercizio 2: Alberi (cont.)

I (per i nodi a livello i ) ho kⁱ cammini di lunghezza i ;

k + 2k²+ · · · + (h − 1)k^h−1=

h−1

X

i =0

ikⁱ = k(h − 1)k^h− hk^h−1+ 1 (k − 1)²

(45)

Esercizio 2: Alberi (cont.)

h−1

X

i =0

ikⁱ = k(h − 1)k^h− hk^h−1+ 1 (k − 1)²

(46)

Tipico problemino

Problema della ricerca suvettore ordinato.

“Dato un vettore ordinato a di valori e un valore v , capire se v `e presente in a e, se se lo `e, a quale posizione.”

Vediamo due possibili algoritmi per questo problema.

Algoritmo 1: Ricerca lineare (o esaustiva) Algoritmo 2: Ricerca binaria

(47)

Ricerca lineare

Implementazione:

int linearSearch( int a[], int length, int v ) { int i;

for (i=0; i<length; i++) {

if ( a[i] == v) return i; /* trovato! */

}

return -1; /* non l’ho trovato */

}

Complessit`a? Caso ottimo?

Caso pessimo?

E il caso medio?

(48)

Ricerca binaria

int binarySearch( int a[], int length, int v ) { int m, r = length - 1, l = 0;

while( r >= l ) { m = ( l + r ) / 2;

if ( v == a[m] ) return m;

if ( v < a[m] ) r = m - 1;

else l = m + 1;

}

return -1;

}

Complessit`a? Ogni test esclude met`a dell’array:

T (n) ≤ T (bn/2c) + 1(considero solo i confronti).

T (n) ≤ log₂n + 1 E il caso medio?