Appunti di Algoritmi e strutture dati

Ingegneria Informatica

Appunti di

ALGORITMI E

STRUTTURE DATI

A cura di Baldi F. e Sangeniti C.

2025-2026

Indice

1 Nozione di algoritmo 6

1.1 Algoritmo e programma . . . . . . . . . . . . . . . . . . . . 6

1.2 Concetti chiave . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Problema . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.2 Istanza . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.3 Modello di calcolo . . . . . . . . . . . . . . . . . . . 7

1.2.4 Efficienza . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.5 Correttezza . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Esempi storici di algoritmi . . . . . . . . . . . . . . . . . . . 7

1.3.1 Algoritmo di Euclide . . . . . . . . . . . . . . . . . . 7

1.3.2 Setaccio di Eratostene . . . . . . . . . . . . . . . . . 8

2 Complessità computazionale 11

2.1 Profiling VS complessità . . . . . . . . . . . . . . . . . . . . 11

2.2 Notazione di grande (limite asintotico superiore) . . . . . 11

O

2.2.1 Proprietà di grande . . . . . . . . . . . . . . . . . 12

O

2.2.2 Incommensurabilità . . . . . . . . . . . . . . . . . . . 13

2.2.3 Classi di complessità . . . . . . . . . . . . . . . . . . 13

2.3 Notazione grande (limite asintotico inferiore) . . . . . . . 14

Ω

2.4 Notazione grande (limite asintotico stretto) . . . . . . . . 15

Θ

2.5 Analisi della complessità temporale . . . . . . . . . . . . . . 16

2.6 Complessità dei programmi iterativi . . . . . . . . . . . . . . 17

2.6.1 Complessità delle espressioni . . . . . . . . . . . . . . 17

2.7 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.7.1 Analisi della complessità . . . . . . . . . . . . . . . . 19

2.8 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.8.1 Analisi della complessità . . . . . . . . . . . . . . . . 20

2.9 Moltiplicazione fra matrici . . . . . . . . . . . . . . . . . . . 21

2.10 Complessità dei programmi ricorsivi . . . . . . . . . . . . . . 22

2.10.1 Selection Sort ricorsivo . . . . . . . . . . . . . . . . . 23

2.10.2 Merge Sort ricorsivo . . . . . . . . . . . . . . . . . . 24

2.10.3 Quick Sort ricorsivo . . . . . . . . . . . . . . . . . . 27

2.10.4 Ricerca lineare ricorsiva . . . . . . . . . . . . . . . . 30

2.10.5 Ricerca binaria ricorsiva . . . . . . . . . . . . . . . . 30

2.10.6 Ricerca con divide et impera . . . . . . . . . . . . . . 31

2.10.7 Torre di Hanoi . . . . . . . . . . . . . . . . . . . . . 32

2.10.8 Serie di Fibonacci ricorsiva . . . . . . . . . . . . . . . 35

2.11 Metodo divide et impera . . . . . . . . . . . . . . . . . . . . 36

2.12 Algoritmo di Karatsuba . . . . . . . . . . . . . . . . . . . . 39

1

2.13 Relazioni di ricorrenza lineari . . . . . . . . . . . . . . . . . 41

3 Alberi 42

3.1 Alberi binari . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.1.1 Operazioni sugli alberi binari . . . . . . . . . . . . . 43

3.1.2 Complessità delle visite . . . . . . . . . . . . . . . . . 44

3.1.3 Memorizzazione in lista multipla . . . . . . . . . . . 44

3.1.4 Alberi binari bilanciati . . . . . . . . . . . . . . . . . 45

3.1.5 Alberi binari quasi bilanciati . . . . . . . . . . . . . . 45

3.1.6 Alberi pienamente binari . . . . . . . . . . . . . . . . 46

3.2 Alberi generici . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2.1 Albero binario VS Albero generico . . . . . . . . . . 46

3.2.2 Visite agli alberi generici . . . . . . . . . . . . . . . . 47

3.2.3 Memorizzazione figlio-fratello . . . . . . . . . . . . . 48

3.3 Funzioni su alberi . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.1 Conteggio dei nodi . . . . . . . . . . . . . . . . . . . 49

3.3.2 Conteggio delle foglie . . . . . . . . . . . . . . . . . . 49

3.3.3 Ricerca di un’etichetta . . . . . . . . . . . . . . . . . 50

3.3.4 Cancellare l’albero . . . . . . . . . . . . . . . . . . . 50

3.3.5 Inserimento di un nodo (albero binario) . . . . . . . 50

3.3.6 Inserimento di un nodo (albero generico) . . . . . . . 51

3.4 Classe BinTree . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.5 Alberi binari di ricerca . . . . . . . . . . . . . . . . . . . . . 52

3.5.1 Proprietà . . . . . . . . . . . . . . . . . . . . . . . . 53

3.5.2 Ricerca di un’etichetta . . . . . . . . . . . . . . . . . 53

3.5.3 Inserimento di un nodo . . . . . . . . . . . . . . . . . 54

3.5.4 Cancellazione di un nodo . . . . . . . . . . . . . . . . 54

3.6 Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.6.1 Memorizzazione in un array . . . . . . . . . . . . . . 58

3.6.2 Classe Heap . . . . . . . . . . . . . . . . . . . . . . . 58

3.6.3 Costruttore e distruttore . . . . . . . . . . . . . . . . 59

3.6.4 Inserimento . . . . . . . . . . . . . . . . . . . . . . . 59

3.6.5 Estrazione . . . . . . . . . . . . . . . . . . . . . . . . 61

3.6.6 Heap sort . . . . . . . . . . . . . . . . . . . . . . . . 63

4 Limiti inferiori 68

4.1 Alberi di decisione . . . . . . . . . . . . . . . . . . . . . . . 68

4.2 Counting sort . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.3 Radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5 Metodo hash 73

2

5.1 Accesso diretto . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.2 Indirizzamento aperto . . . . . . . . . . . . . . . . . . . . . 74

5.2.1 Scansioni . . . . . . . . . . . . . . . . . . . . . . . . 76

5.2.2 Tempo medio di ricerca . . . . . . . . . . . . . . . . 76

5.2.3 Numero medio di accessi . . . . . . . . . . . . . . . . 77

5.3 Metodo di concatenazione . . . . . . . . . . . . . . . . . . . 77

5.4 Hashing con le stringhe . . . . . . . . . . . . . . . . . . . . . 78

6 Programmazione dinamica 79

6.1 Più lunga sottosequenza comune . . . . . . . . . . . . . . . . 79

6.1.1 Soluzione ricorsiva . . . . . . . . . . . . . . . . . . . 80

6.1.2 Soluzione con programmazione dinamica . . . . . . . 80

6.1.3 Estrazione di una PLSC . . . . . . . . . . . . . . . . 82

7 Algoritmi greedy 83

7.1 Codici di compressione . . . . . . . . . . . . . . . . . . . . . 83

7.1.1 Rappresentazione codici prefissi . . . . . . . . . . . . 84

7.2 Algoritmo di Huffman . . . . . . . . . . . . . . . . . . . . . 85

8 Grafo 89

8.1 Grafo orientato . . . . . . . . . . . . . . . . . . . . . . . . . 89

8.1.1 Grado . . . . . . . . . . . . . . . . . . . . . . . . . . 89

8.1.2 Cammino e ciclo . . . . . . . . . . . . . . . . . . . . 90

8.1.3 Liste di adiacenza . . . . . . . . . . . . . . . . . . . . 90

8.1.4 Liste di adiacenza con etichette . . . . . . . . . . . . 90

8.1.5 Matrici di adiacenza . . . . . . . . . . . . . . . . . . 91

8.1.6 Matrici di adicenza con etichette . . . . . . . . . . . 92

8.1.7 Visita in profondità . . . . . . . . . . . . . . . . . . . 93

8.1.8 Classe Graph . . . . . . . . . . . . . . . . . . . . . . 95

8.2 Grafi non orientati . . . . . . . . . . . . . . . . . . . . . . . 96

8.2.1 Cammino e ciclo . . . . . . . . . . . . . . . . . . . . 96

8.2.2 Grafo non orientato connesso . . . . . . . . . . . . . 96

8.2.3 Algoritmo di Kruskal . . . . . . . . . . . . . . . . . . 98

8.2.4 Rappresentazione in memoria . . . . . . . . . . . . . 99

8.3 Multi-grafi orientati/non orientati . . . . . . . . . . . . . . . 100

8.4 Algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . 100

8.5 Esempi di applicazione dei grafi . . . . . . . . . . . . . . . . 104

8.5.1 Graph coloring . . . . . . . . . . . . . . . . . . . . . 104

8.5.2 PageRank di Google . . . . . . . . . . . . . . . . . . 104

8.5.3 Graph databases . . . . . . . . . . . . . . . . . . . . 105

8.6 Ciclo Euleriano . . . . . . . . . . . . . . . . . . . . . . . . . 106

3

9 Problemi difficili 107

9.1 Cammino e ciclo Hamiltoniano . . . . . . . . . . . . . . . . 108

9.2 Soddisfattibilità di una formula logica . . . . . . . . . . . . . 108

9.3 Classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.3.1 Algoritmi non deterministici . . . . . . . . . . . . . . 110

9.3.2 Riducibilità . . . . . . . . . . . . . . . . . . . . . . . 112

9.3.3 NP-completezza . . . . . . . . . . . . . . . . . . . . . 112

9.4 Fattorizzazione . . . . . . . . . . . . . . . . . . . . . . . . . 113

10 Programmazione ad oggetti 115

10.1 Meta-Programmazione . . . . . . . . . . . . . . . . . . . . . 115

10.2 Costrutto template . . . . . . . . . . . . . . . . . . . . . . . 116

10.2.1 Funzioni modello con più parametri . . . . . . . . . . 119

10.2.2 Parametri non-tipo . . . . . . . . . . . . . . . . . . . 120

10.2.3 Funzioni modello con variabili statiche . . . . . . . . 121

10.2.4 Template in file esterno . . . . . . . . . . . . . . . . 121

10.2.5 Classi modello . . . . . . . . . . . . . . . . . . . . . . 122

10.2.6 Classi modello con parametri non-tipo . . . . . . . . 124

10.2.7 Classi modello con membri statici . . . . . . . . . . . 125

10.3 Derivazione semplice . . . . . . . . . . . . . . . . . . . . . . 126

10.3.1 Classi derivate . . . . . . . . . . . . . . . . . . . . . 127

10.3.2 Classi derivate: compatibilità fra tipi . . . . . . . . . 128

10.3.3 Classi derivate: risolutore di scope . . . . . . . . . . 130

10.3.4 Classi derivate: tipi di derivazione . . . . . . . . . . . 132

10.3.5 Costruzione degli oggetti . . . . . . . . . . . . . . . . 133

10.3.6 Distruzione degli oggetti . . . . . . . . . . . . . . . . 135

10.3.7 Classi derivate con membri statici . . . . . . . . . . . 136

10.3.8 Classi derivate con template . . . . . . . . . . . . . . 137

10.4 Funzioni virtuali . . . . . . . . . . . . . . . . . . . . . . . . 138

10.4.1 Funzione virtuale pura . . . . . . . . . . . . . . . . . 140

10.5 Distruttori virtuali . . . . . . . . . . . . . . . . . . . . . . . 140

10.6 Classi astratte . . . . . . . . . . . . . . . . . . . . . . . . . . 141

10.7 Gestione delle eccezioni . . . . . . . . . . . . . . . . . . . . . 143

10.7.1 Corrispondenza fra throw e catch . . . . . . . . . . . 146

10.7.2 Eccezione con classe . . . . . . . . . . . . . . . . . . 148

11 Comandi Linux 152

11.1 Terminale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

11.2 Navigare tra la cartelle . . . . . . . . . . . . . . . . . . . . . 152

11.3 Comandi sui file e cartelle . . . . . . . . . . . . . . . . . . . 152

11.4 Aprire e modificare un file . . . . . . . . . . . . . . . . . . . 153

4

11.5 Aiuto sui comandi . . . . . . . . . . . . . . . . . . . . . . . 153

11.6 Compilazione ed esecuzione di un file . . . . . . . . . . . . . 153

11.7 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

11.8 Compiler flags . . . . . . . . . . . . . . . . . . . . . . . . . . 154

11.9 Input con un file . . . . . . . . . . . . . . . . . . . . . . . . 155

11.10 Confronto fra file . . . . . . . . . . . . . . . . . . . . . . . . 155

11.11 Tempo di esecuzione . . . . . . . . . . . . . . . . . . . . . . 156

12 Standard Template Library 157

12.1 Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

12.2 String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

12.3 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

12.3.1 Unordered map . . . . . . . . . . . . . . . . . . . . . 161

5

1 Nozione di algoritmo

Il termine deriva dal nome del matematico arabo Muhammad ibn

algoritmo

Musa al-Khwarizmi (IX secolo), noto per aver introdotto in Occidente la

notazione posizionale dei numeri e lo 0.

Il nome algoritmo con il significato attuale viene usato a partire dal XIX

secolo.

Definizione: Un algoritmo è un procedimento che descrive una sequenza

di passi ben definiti per risolvere un dato problema computazionale. Deve

possedere le seguenti caratteristiche essenziali:

• forniti dei dati in input, deve restituire un output;

• l’esecuzione deve terminare necessariamente dopo un numero finito di

passi e in un tempo finito;

• può usare una memoria per i risultati intermedi.

1.1 Algoritmo e programma

Definizione: Il programma rappresenta la di un algoritmo in un

codifica

linguaggio di programmazione specifico (come il C++).

Mentre l’algoritmo è un’entità logica astratta che fornisce il procedimento

per giungere alla soluzione di un dato problema di calcolo, il programma è

l’implementazione concreta che può essere eseguita da un elaboratore.

L’algoritmo è un concetto autonomo da quello di programma:

Algoritmo Programma

̸ =

1.2 Concetti chiave

1.2.1 Problema

Definizione: È una descrizione astratta di una relazione tra un insieme di

dati in ingresso (input) e un insieme di dati in uscita (output). Un problema

definisce "cosa" deve essere fatto, senza specificare "come".

6

1.2.2 Istanza

Definizione: È un caso specifico di un problema, con dati reali e definiti.

Se il problema è la domanda generale, l’istanza è la domanda con i numeri

inseriti.

La quantità di dati che compongono l’istanza è chiamata dimensione del-

l’istanza.

1.2.3 Modello di calcolo

Definizione: È un’astrazione matematica di un computer che definisce quali

operazioni sono permesse e quanto "costano" in termini di tempo o memoria.

1.2.4 Efficienza

Definizione: È la misura delle risorse consumate da un algoritmo per risol-

vere un problema.

1.2.5 Correttezza

Un algoritmo è considerato corretto se, per ogni possibile istanza del proble-

ma, termina in tempo finito e produce l’output desiderato.

1.3 Esempi storici di algoritmi

Gli algoritmi esistono fin dall’antichità sono indipendenti dal calcolatore

−→

Vediamone due esempi molto famosi: l’algoritmo di Euclide e il setaccio

di Eratostene.

1.3.1 Algoritmo di Euclide

Definizione: È un metodo iterativo efficiente per calcolare il Massimo Co-

mun Divisore (MCD) tra due numeri naturali.

Questo algoritmo si basa sul seguente teorema: il MCD fra due numeri è

uguale al MCD fra il più piccolo e la differenza fra i due.

7

Osserviamo il codice C++ di questo algoritmo:

ESEMPIO

Calcoliamo MCD(30,21):

int MCD ( int x , int y ) {

while ( x != y ) { x = 30, y = 21

if ( x < y ) y =y - x ; x = 9, y = 21

else x =x - y ; x = 9, y = 12

} x = 9, y =3

return x ;

} x = 6, y =3

x = 3, y=3

Esiste anche un altro algoritmo, basato sul seguente teorema: il MCD fra

due numeri e è uguale al MCD fra e il resto della divisione fra e

x y y x y.

Osserviamo il codice C++ di quest’ultimo algoritmo:

ESEMPIO

int MCD ( int x , int y ) { Calcoliamo MCD(30,21):

while ( y != 0) {

int k = x ; x = 30, y = 21

x=y;

y=k%y; x = 21, y =9

} x = 9, y =3

return x ; x = 3, y =0

}

Notiamo che, sebbene i due algoritmi trovino lo stesso risultato, il secondo

algoritmo utilizza meno operazioni rispetto al primo.

1.3.2 Setaccio di Eratostene

Definizione: È un procedimento meccanico per individuare tutti i numeri

primi fino a un limite prefissato, eliminando progressivamente i multipli dei

numeri già identificati come primi.

È un approccio molto più efficiente rispetto a controllare quali sono i divisori

di ogni numero e selezionare solo quelli che hanno come divisore e se stessi.

1

8

Osserviamo il codice C++ di questo algoritmo:

void setaccio ( int n ) {

bool primi [ n ]; primi [0] = primi [1] = false ;

for ( int i = 2; i < n ; i ++)

primi [ i ] = true ; // inizializza

int i = 1;

for ( i ++; i * i < n ; i ++) { // scorri i numeri successivi a

partire da i * i

while (! primi [ i ]) i ++; // cerca il prossimo primo

for ( int k = i * i ; k < n ; k += i )

primi [ k ]= false ; // cancella multipli di i

}

for ( int j = 2; j < n ; j ++)

if ( primi [ j ]) cout <<j < < endl ; // stampa tutti primi

} ESEMPIO

Ipotizziamo cioè cerchiamo i numeri primi ≤

n = 50, 50:

Cancellazione multipli di 2:

2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Cancellazione multipli di 3:

2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

9

Cancellazione multipli di 5:

2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Cancellazione multipli di 7:

2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

10

2 Complessità computazionale

Definizione: La complessità di un algoritmo è una funzione (sempre posi-

tiva) che associa alla dimensione del problema il costo della sua risoluzione.

Conoscere la complessità di un algoritmo permette di con altri

confrontarlo

algoritmi, aventi lo stesso scopo, per determinare quale sia più efficiente.

Per quanto riguarda la complessità degli algoritmi, è necessario trovare un

metodo di calcolo della complessità che misuri l’efficienza come proprietà

dell’algoritmo, cioè astragga:

• dal su cui l’algoritmo è eseguito;

computer

• dal in cui l’algoritmo è scritto.

linguaggio

È inoltre fondamentale misurare l’efficienza indipendentemente dalla dimen-

infatti la funzione della complessità deve essere analizzata

sione dei dati,

nel suo comportamento asintotico.

Le due metriche principali sono:

• complessità temporale: il tempo richiesto per l’esecuzione, misura-

to come numero di operazioni elementari in funzione della dimensione

dell’input n;

• complessità spaziale: la quantità di memoria aggiuntiva necessaria

durante l’elaborazione.

2.1 Profiling VS complessità

Definizione di profiling: Il profiling è una tecnica di analisi basata sull’u-

tilizzo di uno strumento software (chiamato profiler) per misurare gli indici