Appunti di Strutture dati e algoritmi

UNIVERSITÀ DEGLI STUDI DI MODENA E

REGGIO EMILIA

Dipartimento di Ingegneria “Enzo Ferrari”

Corso di Laurea in Ingegneria Informatica

Riassunto di

Strutture Dati e Algoritmi Giovanni Tassotti

Bolelli Federico, Vincini Maurizio

Basato sulle lezione di:

Indice

1 Ricorsione 4

1.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Caso base della ricorsione . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Validazione dell’input . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Ricorsione diretta e indiretta . . . . . . . . . . . . . . . . . . . . 5

1.5 Ricorsione di coda . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5.1 Trasformazioni in ricorsione di coda . . . . . . . . . . . . 7

2 Backtracking 8

2.1 Metodi per modellare il problema . . . . . . . . . . . . . . . . . . 9

3 Complessità computazionale degli algoritmi 10

3.1 Complessità temporale . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2 Differenza di complessità . . . . . . . . . . . . . . . . . . . . . . . 10

3.3 Notazione asintotica . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3.1 Notazione . . . . . . . . . . . . . . . . . . . . . . . . . 11

O

3.3.2 Notazione . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Ω

3.3.3 Notazione . . . . . . . . . . . . . . . . . . . . . . . . . 11

Θ

3.3.4 Proprietà . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3.5 Complessità in tempo di algoritmi e problemi . . . . . . . 12

4 Algoritmi greedy 14

4.1 Struttura degli algoritmi greedy . . . . . . . . . . . . . . . . . . . 14

5 Algoritmi di ordinamento 15

5.1 Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5.1.1 Analisi di insertion sort . . . . . . . . . . . . . . . . . . . 16

5.1.2 Valutazione complessità . . . . . . . . . . . . . . . . . . . 16

5.2 Merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.2.1 Il metodo divide et impera . . . . . . . . . . . . . . . . . 17

5.2.2 Analisi di merge sort . . . . . . . . . . . . . . . . . . . . . 17

5.2.3 Valutazione complessità . . . . . . . . . . . . . . . . . . . 19

5.3 Quick sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.3.1 Analisi di quick sort . . . . . . . . . . . . . . . . . . . . . 19

5.3.2 Valutazione complessità . . . . . . . . . . . . . . . . . . . 20

5.4 Analisi finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6 Liste 23

6.1 L’ADT (Abstract Data Type) Lista . . . . . . . . . . . . . . . . 23

6.2 Rappresentazione concreta di lista . . . . . . . . . . . . . . . . . 24

6.2.1 Statica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.2.2 Rappresentazione collegata . . . . . . . . . . . . . . . . . 24

6.2.3 Implementazione a vettori . . . . . . . . . . . . . . . . . . 25

6.3 Rappresentazione collegata mediante i puntatori . . . . . . . . . 25

6.3.1 Funzione IsMember . . . . . . . . . . . . . . . . . . . . . 27

6.3.2 Funzione Length . . . . . . . . . . . . . . . . . . . . . . . 28

6.3.3 Funzione Append . . . . . . . . . . . . . . . . . . . . . . . 28

6.4 Pila - Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.5 Coda - Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

7 Alberi 29

7.1 Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

7.1.1 Nomenclatura . . . . . . . . . . . . . . . . . . . . . . . . . 29

7.1.2 Proprietà delle relazioni . . . . . . . . . . . . . . . . . . . 29

7.1.3 Cammino di un grafo . . . . . . . . . . . . . . . . . . . . 29

7.2 Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

7.2.1 Alberi come strutture dati ricorsive . . . . . . . . . . . . . 30

7.2.2 Visita di alberi n-ari . . . . . . . . . . . . . . . . . . . . . 31

7.3 Alberi binari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

7.3.1 Visita di un albero binario . . . . . . . . . . . . . . . . . . 32

7.3.2 Visita in ampiezza . . . . . . . . . . . . . . . . . . . . . . 32

7.3.3 Proprietà . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

7.3.4 Curiosità: esempio di visite . . . . . . . . . . . . . . . . . 33

7.4 ADT Albero binario . . . . . . . . . . . . . . . . . . . . . . . . . 34

7.4.1 Rappresentazione di un albero binario . . . . . . . . . . . 34

7.4.2 Costruzione delle primitive . . . . . . . . . . . . . . . . . 34

7.5 Alberi binari di ricerca . . . . . . . . . . . . . . . . . . . . . . . . 37

7.5.1 Inserimento di un nuovo elemento . . . . . . . . . . . . . 37

7.5.2 Verifica della presenza di un elemento tramite ricerca binaria 38

7.5.3 Eliminazione di un nodo . . . . . . . . . . . . . . . . . . . 39

8 Heap 40

8.1 Coda di priorità . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

8.2 Applicazioni della coda di priorità . . . . . . . . . . . . . . . . . 40

8.3 Struttura dati Heap . . . . . . . . . . . . . . . . . . . . . . . . . 40

8.3.1 Proprietà . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

8.3.2 Operazioni fondamentali . . . . . . . . . . . . . . . . . . . 41

8.3.3 MoveUp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8.3.4 MoveDown . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8.3.5 FindMin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8.3.6 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8.3.7 Delete e DeleteMin . . . . . . . . . . . . . . . . . . . . . . 42

8.3.8 Increase . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8.3.9 Decrease . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

8.4 Heap binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

8.4.1 Implementazione delle procedure di supporto . . . . . . . 43

8.4.2 Costruzione heap binaria . . . . . . . . . . . . . . . . . . 44

8.4.3 Coda di priorità . . . . . . . . . . . . . . . . . . . . . . . 45

8.4.4 Algorimo HeapSort . . . . . . . . . . . . . . . . . . . . . . 45

2

9 Dizionari 46

9.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

9.2 Implementazione con una lista . . . . . . . . . . . . . . . . . . . 46

9.2.1 Implementazione con lista ordinata . . . . . . . . . . . . . 47

9.3 Implementazione con BST . . . . . . . . . . . . . . . . . . . . . . 47

9.4 Implementazione con Heap . . . . . . . . . . . . . . . . . . . . . 47

3

1 Ricorsione

1.1 Definizione

Nella logica matematica e nell’informatica, le sono una classe

funzioni ricorsive

di funzioni dai numeri naturali ai numeri naturali che sono attraverso

calcolabili

funzioni di base e regole costruttive che usano la funzione stessa. La base teorica

è il principio di induzione:

• una proprietà vale per un certo numero naturale , in altre

P (n) n = n 0

parole è vera;

P (n )

0

• supponendo che sia vera, ne consegue che è vera. Quindi

P (n) P (n + 1)

possiamo dire che P (n) =⇒ P (n + 1).

allora la proprietà vale .

∀n ≥

P (n) n 0

Dato un programma, una funzione si può definire ricorsiva se invoca sé stessa

direttamente o indirettamente (rispettivamente e

ricorsione diretta ricorsione

La ricorsione si definisce quando vi è una sola chiamata

indiretta). lineare

ricorsiva all’interno della definizione della funzione stessa, viceversa si definisce

ricorsione nel caso in cui le chiamate ricorsive siano più di una.

non lineare

1.2 Caso base della ricorsione

Una soluzione ricorsiva si pone come obiettivo quello di rappresentare il proble-

ma in termini di se stesso riducendo ad ogni ricorsione lo spazio delle soluzioni,

fino a quando non si verificano una o più condizioni (o casi) che ter-

di base

minano il processo ricorsivo. Se queste condizioni vengono definite in maniera

errata o affatto si genera una sequenza di chiamate ricorsive infinite che causerà

problemi di stack overflow.

Consideriamo il problema di calcolare il fattoriale dei primi numeri naturali.

n

Nella specifica ricorsiva il problema può essere visto come il prodotto di due

fattori: dove è noto e il fattoriale dei primi

∗ ∗ ∗ ∗ ∗ · · · ∗ −

(1 2 3 4 5 (n 1)), n

numeri è un sottoproblema di quello originale.

−

n 1

Il caso base si ha quando in quando il prodotto dei numeri naturali da

n = 1, 1

a vale proprio quindi:

1 1,

unsigned long long Fattoriale(int n) {

if (n == 1){

// Caso base

return 1;

}

// Ricorsione

return n * Fattoriale(n - 1);

} 4

1.3 Validazione dell’input

Oltre ad individuare i casi base è anche importante validare i valori di input.

Riprendendo l’esempio del fattoriale di per definizione di fattoriale possiamo

n:

calcolarlo solo per i numeri naturali (ovvero i numeri interi positivi), quindi solo

se Il caso va incluso all’interno del caso base (0! Per

n >= 0. n = 0 = 1).

gestire queste eventualità dobbiamo implementare una funzione ausiliaria (non

ricorsiva) che si occupa della validazione dell’input e che una volta verificato

che questo sia corretto, chiama la funzione ricorsiva. Le funzioni non possono

avere lo stesso nome, quindi quello che faremo è aggiungere il suffisso alla

Rec

effettiva implementazione ricorsiva:

static unsigned long long FattorialeRec(int n) {

// Caso base

if (n == 0 || n == 1) {

return 1;

}

// Ricorsione

return FattorialeRec(n - 1) * n;

}

unsigned long long Fattoriale(int n) {

// Validazione dell’input

if (n < 0) {

return 0;

}

// Implementazione ricorsiva

return FattorialeRec(n);

}

Il valore di ritorno della funzione viene dichiarato cosicché

FattorialeRec static

rimanga accessibile solo a quel blocco (così non corriamo il rischio che il valore

venga ritornato nella nostra funzione ).

main

1.4 Ricorsione diretta e indiretta

Data una funzione ricorsiva questa si definisce se invoca la funzione

diretta

FooA

direttamente all’interno del suo corpo.

FooA

//Ricorsione diretta

int FooA(){

//Fai qualcosa ...

FooA();

//Fai qualcosa ...

}

La funzione viene invece definita se invoca una seconda funzione

indiretta FooB

la qua a sua volta invoca , direttamente o indirettamente:

FooA

//Ricorsione indiretta

int FooA(){

//Fai qualcosa ...

FooB();

//Fai qualcosa ...

} 5

int FooB(){

//Fai qualcosa ...

FooA();

//Fai qualcosa ...

}

1.5 Ricorsione di coda

Una funzione ricorsiva si definisce (o ricorsione di coda) quando la

tail recursive

chiamata ricorsiva è l’ultima istruzione eseguita dalla funzione prima di termi-

nare; chiaramente solo la ricorsione lineare può essere tail. L’implementazione di

non è in quanto al termine della chiamata ricorsiva

tail recursive,

FattorialeRec

deve essere eseguito il prodotto tra il risultato ed .

n: FattorialeRec(n - 1)* n

Una funzione ricorsiva computa "all’indietro": al passo i-esimo non è

non-tail

disponibile nulla e il risultato viene sintetizzato mentre le chiamate si chiudo-

no. É quindi necessario conservare lo stato della computazione prima di fare

la chiamata ricorsiva, perché servirà il ritorno. Per farlo occorre aggiungere un

parametro ausiliario alla chiamata a funzione che tenga traccia del prodotto fino

al passo corrente.

static unsigned long long FattorialeRec(int n, int p) {

// Caso base

if (n == 0 || n == 1) {

return p + 1;

}

// Ricorsione

return FattorialeRec(n - 1, p * n);

}

unsigned long long Fattoriale(int n) {

// Validazione dell’input

if (n < 0) {

return 0;

}

// Implementazione ricorsiva

return FattorialeRec(n, 1);

}

É importante conoscere questo aspetto della ricorsione in quanto le funzione tail

possono essere facilmente ottimizzate dal compilatore: questo tipo di

recursive

ricorsione dà luogo a un processo computazionale di tipo iterativo (computa in

"avanti"), non richiede di conservare lo stato quindi può essere ottimizzarla e

resa efficiente come un ciclo (che a sua volta il compilatore convertirà in ).

goto

6

1.5.1 Trasformazioni in ricorsione di coda

Trasformare la soluzione ricorsiva non tail in ricorsione tail

Ricorsione non tail

unsigned long long FattorialeRec(int n) {

// Caso base

if (n == 0 || n == 1) {

return 1;

}

// Ricorsione

return FattorialeRec(n - 1) * n;

} Ricorsione tail

unsigned long long FattorialeRec(int n, int p) {

// Caso base

if (n == 0 || n == 1) {

return p + 1;

}

// Ricorsione

return FattorialeRec(n - 1, p * n);

} la condizione

Trasformare la soluzione ricorsiva tail in soluzione iterativa: if

diventa un ciclo e si toglie la chiamata ricorsiva (corpo e condizione di

while if

e del ciclo rimangono immutati)

Soluzione ricorsiva tail (trasformata)

unsigned long long FattorialeTail(int n, unsigned long long p, int

i) {

if (i <= n) {

p *= i;

i++;

return FattorialeTail(n, p, i);

}

return FattorialeTail(n - 1) * n;

} Soluzione iterativa

unsigned long long Fattoriale(int n) {

int i = 1;

unsigned long long p = 1;

while (i <= n) {

p *= i;

i++;

}

return p;

}

In conclusione possiamo dire che conviene utilizzare una soluzione ricorsiva

per rendere il codice più espressivo e più compatto rispetto ad una soluzione

iterativa. 7

2 Backtracking

Gli algoritmi di vengono utilizzati per risolvere delle classi di pro-

backtracking

blemi (decisionali, di ricerca, di ottimizzazione) che si basano sul concetto di

ovvero una soluzione che soddisfa un certo insieme di

soluzione ammissibile,

criteri; per esempio: contare le soluzioni ammissibili, costruire una o tutte le so-

luzioni ammissibili o trovare le soluzioni ammissibili "più grandi", "più piccole"

o in generale "ottimali" (esempi concreti possono essere le possibili permutazioni

di un insieme generico o i suoi possibili sottoinsiemi).

Quindi dato un problema , definiamo e rappresentiamo una sua

P soluzione

come un vettore di scelte dove ogni elemento è

S[x , x , . . . , x ] S[i]

potenziale 1 2 n

preso da un insieme di che dipende da . Se una

C, P

scelte possibili soluzione

rispetta gli eventuali vincoli che il problema impone tra gli elementi

potenziale

del vettore allora questa è una per P.

S, soluzione

L’insieme di tutte le viene indicato come

soluzioni potenziali spazio di ricerca

delle soluzioni o e il procedimento risolutivo è denominato

spazio delle soluzioni

dello spazio di ricerca.

esplorazione

Il deve, personalizzando l’algoritmo in base alle condizioni di

backtracking

ogni singola applicazione individuale, esplorare in modo sistematico tutte le

possibili istanze di uno spazio di ricerca (tramite una visita in profondità) e

utilizzando la ricorsione memorizzare le scelte fatte fino ad un certo punto.

In generale per risolvere un problema attraverso un algoritmo di backtracking,

occorre sempre:

1. Definire la lunghezza massima della sequenza che rappresenta una solu-

zione, di solito viene indicata con n.

2. Definire il dominio dei valori ammissibili per gli elementi della sequenza,

C

di solito la cardinalità di viene indicata con

C k.

3. Definire, per ogni posizione della sequenza risolutiva, le eventuali regole

matematiche che la soluzione parziale deve soddisfare. In altre parole,

occorre definire i vincoli che sussistono tra gli elementi della sequenza

risolutiva.

4. Rappresentare lo spazio delle soluzioni che la funzione deve esplorare per

individuare i vettori soluzione. 8

2.1 Metodi per modellare il problema

Variabile Descrizione Albero delle Soluzioni

Lunghezza (massima) del vet- L’albero delle soluzioni sarà

n tore soluzione alto n

Cardinalità del dominio dei Numero massimo di figli che

k valori ammissibili ogni nodo dell’albero può avere

C

Numero intero che rappresenta Livello dell’albero che stiamo

i l’indice della scelta corrente esplorando

Vettore di scelte (S) corrispon-

vcurr dente alla soluzione parziale

corrente.

Vettore di scelte corrisponden-

vbest te alla soluzione migliore fino

ad ora trovata.

Valore intero che indica il

nsol numero di soluzioni trovate.

9

3 Complessità computazionale degli algoritmi

Per risolvere un problema possiamo ricorrere a diversi algoritmi; è quindi neces-

sario trovare un modo per confrontare la loro "bontà", ovvero la loro comples-

(il costo di un algoritmo in termini di quantità di risorsa

sità computazionale

richiesta per il calcolo).

Quali sono queste risorse?

• il numero in unità di tempo che il mio algorit-

Complessità temporale:

mo impiega per risolvere il problema (sarà l’unità computazionale di cui

ci occuperemo);

• spazio fisico di un elaboratore (memoria centra-

Complessità spaziale:

le);

• il tempo di accesso alla periferiche.

Complessità di Input/Output:

3.1 Complessità temporale

La è il costo di un algoritmo in termini di quantità di

complessità temporale

tempo richiesto per il calcolo. I fattori che influenzano il tempo sono:

• la dimensione dell’input (che coincide con la grandezza dei numeri che

andiamo a misurare);

• la configurazione dell’input;

• la velocità della macchina usata (di cui non terremo conto);

• il linguaggio di programmazione (perché ci sono linguaggi compilati, per

esempio il C, che sono molto più veloci di linguaggi semi-interpretati, per

esempio Java; anche di questo fattore non terremo conto)

Per il calcolo d