Appunti Algoritmi e strutture dati

Algoritmi per l’intelligenza artificiale

Giuseppe Pio La Castellana

2025/2026

Indice

1 Algoritmo 5

1.1 Che cos’è un algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Fibonacci 5

2.1 Algoritmo numerico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Algoritmo Ricorsivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Algoritmo Iterativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Modelli di Calcolo 6

3.1 Macchina di Touring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 Macchina a Registri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 Notazione Asintotica 7

4.1 Notazione O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.2 Notazione Ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.3 Notazione Θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.4 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5 Analisi di algoritmi di ricerca 8

5.1 Ricerca sequenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5.2 Analisi Ricerca binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

6 Tecniche di Progettazione di un algoritmo 9

6.1 Divide et Impera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6.1.1 Ricorrenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6.1.2 Metodo di Sostituzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6.1.3 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6.1.4 Metodo con albero di ricorsione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6.1.5 Metodo principale (Master Theorem) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

7 Strutture dati elementari 14

7.1 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

7.1.1 Matrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

7.1.2 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7.1.3 Ottimizzazione di inserimento e cancellazione . . . . . . . . . . . . . . . . . . . . . . . . . 15

7.2 Liste concatenate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7.2.1 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

7.3 Pile e code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.3.1 Pseudocodice Pila con Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.3.2 Pseudocodice Code con Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

7.3.3 Concetti sullo pseudocodice di Pile e Code con Liste concatenate . . . . . . . . . . . . . . 18

7.4 Alberi Radicati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

7.4.1 Visite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

7.4.2 Visite albero binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1

8 Algoritmi di Ordinamento 19

8.1 Teorema del Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

8.2 Ordinamenti Incrementali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

8.2.1 Pseucodice e analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

8.3 Ordinamento a bolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

8.3.1 Pseudocodice e analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

8.4 Ordinamento Ricorsivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

8.4.1 Pseudocodice e analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

8.5 Ordinamento lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

9 Alberi Binari 25

9.1 Alberi binari di Ricerca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

9.1.1 Proprietà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

9.1.2 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

9.2 Alberi Rosso-Neri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

9.2.1 Dimostrazione altezza massima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

9.2.2 PseudoCodice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

10 Hashtable 28

10.1 Collisioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

10.1.1 Esempi funzioni hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.2 Metodo della divisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.3 Metodo della Moltiplicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.4 Gestione delle collisioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.5 Fattore di carico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.6 Analisi Temporale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.6.1 Caso peggiore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.6.2 Caso medio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10.6.3 Teorema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

10.6.4 Teorema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

10.7 Indirizzamento Aperto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

10.7.1 Hashing Lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

10.7.2 Hashing Doppio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

10.7.3 Analisi Ricerca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

10.8 Problema Hashing Statico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

10.8.1 Hashing Randomizzato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

11 Programmazione dinamica 36

11.1 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

12 Algoritmi Avidi 38

12.1 Prodotto tra Matrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

12.1.1 Definizione del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

12.1.2 Soluzione Esaustiva e Dinamica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12.1.3 Fasi di Risoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12.2 Sottosequenza Comune Massima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

12.2.1 Definizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

12.2.2 Analisi e Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

12.2.3 Algoritmo LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

12.2.4 Ottimizzazione: Eliminazione della Matrice . . . . . . . . . . . . . . . . . . . . . . . . . 44

b

13 Grafi 44

13.1 Rappresentazione dei Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

13.2 Visita in ampiezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

13.2.1 Cammini minimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

13.3 Visita in profondità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

14 Visita in profondità 50

14.1 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

14.1.1 Classificazione archi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

14.2 Ordinamento topologico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

14.3 Componenti fortemente connesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2

15 Albero di connessione minimo 58

16 L’Approccio Greedy: La Regola dei Colori 58

16.1 La Regola Blu (Blue-Rule) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

16.2 La Regola Rossa (Red-Rule) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

17 Fondamenti Teorici e Definizioni 58

17.1 Teorema dell’Arco Blu (Arco Sicuro) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

18 Algoritmo di Kruskal 59

18.1 Procedura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

18.2 Insiemi Disgiunti (Disjoint Sets) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

19 Algoritmo di Prim 59

19.1 Procedura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

19.2 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

20 Sintesi della Strategia Greedy 59

21 Cammini Minimi da Sorgente Unica 60

21.1 Varianti del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

21.2 Sottostruttura Ottima dei Cammini Minimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

21.3 Archi con Peso Negativo e Cicli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

22 Tecnica del Rilassamento 60

22.1 Proprietà dei Cammini Minimi e del Rilassamento . . . . . . . . . . . . . . . . . . . . . . . . . . 61

23 Algoritmo di Bellman-Ford 61

23.1 Analisi di Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

23.2 Correttezza dell’Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

24 Cammini Minimi nei Grafi Diretti Aciclici (DAG) 62

24.1 Analisi di Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

25 Algoritmo di Dijkstra 63

25.1 Teorema di Correttezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

25.2 Analisi delle Prestazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

26 NP-completezza 64

3

≤ −

SAT SAT

27 Dimostrazione: 65

P

3 − ≤

SAT CLIQU E

28 Dimostrazione: 66

P

≤ −

CLIQU E V ERT EX COV ER

29 Dimostrazione: 67

P

− ≤ −

V ERT EX COV ER HAM CY CLE

30 Dimostrazione: 68

P

− ≤

HAM CY CLE T SP

31 Dimostrazione: 69

P

32 Agente Risolutore di Problemi 71

32.1 Tipologie di Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

33 Formulazione di un Problema di Ricerca 71

34 Algoritmi e Alberi di Ricerca 72

34.1 Struttura dei Nodi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

34.2 Struttura Dati per la Frontiera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

35 Strategie di Ricerca 72

35.1 Ricerca Non Informata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

35.2 Ricerca Informata (Heuristic Search) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3

∗

A

36 Proprietà di ed Euristiche 72

36.1 Complessità e Potatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

37 Soluzioni Sub-ottime e Limiti di Memoria 73

38 Tecnica di Progettazione delle Euristiche 73

4

3 marzo 2026

1 Algoritmo

1.1 Che cos’è un algoritmo

Un algoritmo è un insieme di istruzioni definite passo per passo, così da poter essere eseguite meccanicamente

anche da uno scolaretto e tali da produrre un risultato. Si tratta di una sequenza finita di passi di calcolo che

ricevendo un input un valore restituisce un output con un altro valore. L’analisi di un algoritmo ci fornisce

garanzie matematiche sulle prestazioni dello stesso, per ogni tipo di input, in modo da decidere quale soluzione

possa essere più adeguata ai nostri obiettivi.

2 Fibonacci

Dobbiamo risolvere il problema per 1:

≥

n ( + se 3

≥

F F n

n−1 n−2 (1)

1 se = 1, 2

n

Questa prende il nome di Analizziamo 3 metodi per risolverlo:

relazione di ricorrenza.

1. Algoritmo numerico

2. Algoritmo ricorsivo

3. Algoritmo iterativo

2.1 Algoritmo numerico

Per ottenere un algoritmo cerchiamo una formula chiusa che calcoli direttamente i numeri di Fibonacci. Sup-

poniamo che sia soluzione di = + con = 0, sostituendo otteniamo:

n ̸

a F F F a

n n−1 n−2

= + (2)

n n−1 n−2

a a a

portando tutto a primo membro: = 0 (3)

n n−1 n−2

− −

a a a

raccogliamo a fattor comune, il termine più piccolo : n−2

a

(a 1) = 0 (4)

n−2 2

· − −

a a

= 0 per ipotesi, quindi le soluzioni da ricercare sono in:

n−2 ̸

a 1 = 0 (5)

2 − −

a a

Le soluzioni si ottengono con la formula del ∆: √

1+ 5

= 1, 618 (6)

≈

ϕ 2

√

1 5

−

= 618 (7)

≈ −0,

ϕ̄ 2

La soluzione sarà del tipo: ( + = 1 per (1) = 1

· ·

c ϕ c ϕ̄ F

1 2 (8)

¯

+ = 1 per (2) = 1

2 2

· ·

c ϕ c ϕ F

1 2

Risolvendo il sistema avremo: ( = 1

c √

1 (9)

5

= 1

−

c √

2 5 ¯

Quindi la soluzione della relazione di ricorrenza si avrà sostituendo i valori di e a (n) = +

n n

· ·

c c F c ϕ c ϕ

1 2 1 2

ottenendo (mettendo in evidenza )

1

√ 5 1 1 1

(n) = = (ϕ ) (10)

n n n n

√ √ √

· − · · −

F ϕ ϕ̄ ϕ̄

5 5 5

Il vantaggio di questo algoritmo è nel costo computazionale costante, tuttavia lo svantaggio sta nell’infinità della

rappresentazione dei numeri reali che porta la macchina che esegue l’algoritmo a lavorare con approssimazioni,

il che non lo rende preciso. 5

2.2 Algoritmo Ricorsivo

La natura della è ricorsiva, perché per trovare il valore, richiama sé stessa su input di

sequenza di Fibonacci

taglia più piccola. Lo pseudocodice di questo algoritmo è il seguente:

PROCEDURE FibRic(n):

IF 2:

≤

n

return 1

ELSE:

return FibRic(n-1) + FibRic(n-2)

def FibRic ( n ) :

1 return 1 if n <=2 else FibRic (n -1) + FibRic (n -2)

2 Analizzando quante linee richiede l’algoritmo, notiamo che ogni chiamata alla funzione coinvolge una o due linee

di codice:

• Se 2, viene eseguita solo una riga di codice, in particolare l’istruzione dentro l’IF

≤

n

• Se n = 3 vengono eseguite due linee di codice perla chiamata FibRic(3), più una per FibRic(2) e una per

FibRic(1), per un totale di quattro righe

• Se n = 4 vengono eseguite due linee di codice per FibRic(4) più quattro righe per FibRic(3) ed una per

FibRic(2) per un totale di 7 righe di codice.

Quindi oltre alle due linee per ogni chiamata, il numero delle linee mandate in esecuzione in occasione di una

chiamata alla funzione FIbRic(n) è dato dalla somma delle linee di codice mandate in esecuzione dalle due

chiamate ricorsive: (n) = 2 + (n 1) + (n 2) (11)

− −

T T T

Si dimostra che vengono mandate in esecuzione: 3 (n) 2 (12)

· −

F

linee di codice. Quindi per n = 45 avremmo sostanzialmente più di tre miliardi di linee di codice. Il che non è

efficiente.

2.3 Algoritmo Iterativo

L’algoritmo ricorsivo è lento perché continua a ricalcolare ripetutamente la soluzione dello stesso sottoproblema.

Quindi la soluzione sarebbe risolvere un sottoproblema solo una volta e memorizzarla invece di ricalcolarla.

Questa idea è alla base di una tecnica algoritmica detta PROCEDURE FibIt(n)

programmazione dinamica.

= ARRAY DIM N

F

b = = 1

F F

b[0] b[1]

FOR i = 2 to n

= +

F F F

b[i] b[i−1] b[i−2]

return F b[n]

def FibIt ( n ) :

1 f = [ x for x in range ( n +1) ]

2 f [0]= f [1] = 1

3 for i in range (2 , n +1) :

4 f [ i ] = f [i -1] + f [i -2]

5 return f [ -1]

6 In questo caso tralasciando la creazione dell’array, vengono eseguite sempre la seconda e la quinta riga, la

terza riga (quella con il ciclo) viene eseguita n-2 volte + 1 (quindi n-1) dove 1 serve per arrivare ad n, mentre

alla quarta viene eseguira n-2 volte, per cui avremo:

(n) = 1 + 2 + 1 + 1 = 2n 1 (13)

− − −

T n n

Quindi per n= 45 ci vogliono 90 passi, a differenza dei tre miliardi dell’algoritmo ricorsivo.

3 Modelli di Calcolo 4 Marzo 2026

3.1 Macchina di Touring

Per analizzare un algoritmo ci serve un modello ideale che possa simulare in maniera teorica il