Appunti di algoritmi e strutture dati

UNIVERSITA DEGLI STUDI DI NAPOLI

“PARTHENOPE”

FACOLTA DI SCIENZE E TECNOLOGIE

CORSO DI LAUREA IN INFORMATICA

Algoritmi e Strutture Dati &

Laboratorio di Algoritmi e

Strutture Dati

Appunti a cura di

Giuseppe Liccardo

Indice

CAPITOLO 1. Analisi di algoritmi ............................................................................................................. 7

1.1 Introduzione .......................................................................................................................................................7

1.2 Tempo di esecuzione degli algoritmi ...................................................................................................................7

1.3 Notazione asintotica ...........................................................................................................................................8

1.4 Notazione O – Limite superiore asintotico – Caso peggiore.................................................................................8

1.4.1 Definizione formale .................................................................................................................................................................. 8

1.4.2 Definizione informale ............................................................................................................................................................... 8

1.4.3 Considerazione sulla notazione O ............................................................................................................................................ 9

1.5 Notazione Ω – Limite inferiore asintotico – Caso migliore ...................................................................................9

1.5.1 Definizione formale .................................................................................................................................................................. 9

1.5.2 Definizione informale ............................................................................................................................................................... 9

1.5.3 Considerazione sulla notazione Ω ............................................................................................................................................ 9

1.5.4 Regola della dualità .................................................................................................................................................................. 9

1.6 Notazione Θ – Limite asintotico stretto – Caso medio .......................................................................................10

1.6.1 Definizione formale ................................................................................................................................................................ 10

1.6.2 Definizione informale ............................................................................................................................................................. 10

1.6.3 Considerazioni sulla notazione Θ ........................................................................................................................................... 10

1.7 Ulteriori notazioni asintotiche ..........................................................................................................................10

1.7.1 Notazione o – Limite superiore asintotico non stretto .......................................................................................................... 10

1.7.2 Notazione ω – Limite inferiore asintotico non stretto........................................................................................................... 11

CAPITOLO 2. Algoritmi di ordinamento basati sul “Divide-et-Impera” .................................................... 12

2.1 Approccio Divide-et-Impera ..............................................................................................................................12

2.1.1 Paradigma generale di algoritmi basati sull’approccio Divide-et-Impera ........................................................................... 12

2.2 Algoritmo di ordinamento MergeSort ...............................................................................................................13

2.2.1 Richiamo: merge di array ordinati ......................................................................................................................................... 13

2.2.2 Idea dell’algoritmo ................................................................................................................................................................. 13

2.2.3 Pseudocodice .......................................................................................................................................................................... 14

2.2.4 Analisi complessità del MergeSort ......................................................................................................................................... 15

2.3 Algoritmo di ordinamento QuickSort ................................................................................................................15

2.3.1 Pseudocodice .......................................................................................................................................................................... 16

2.3.2 Idea dell’algoritmo ................................................................................................................................................................. 17

2.3.3 Casi estremi per la procedura “Partiziona” ........................................................................................................................... 17

2.3.4 Analisi complessità della procedura “Partiziona” ................................................................................................................. 18

2.3.5 Analisi complessità del QuickSort .......................................................................................................................................... 18

2.3.6 QuickSort con pivot random ................................................................................................................................................... 20

2.3.9 Analisi complessità del QuickSort con pivot random ............................................................................................................ 20

2.4 Albero di decisione ...........................................................................................................................................21

2.4.1 Il modello dell’albero di decisione .......................................................................................................................................... 21

2.5 Algoritmi di ordinamento non basati sui confronti ............................................................................................23

2.5.1 Algoritmo CountingSort .......................................................................................................................................................... 23

Pagina | 2

2.5.2 Pseudocodice CountingSort .................................................................................................................................................... 24

2.5.3 Algoritmo RadixSort ............................................................................................................................................................... 25

2.5.4 Pseudocodice RadixSort.......................................................................................................................................................... 25

2.5.5 Algoritmo BucketSort ............................................................................................................................................................. 26

2.5.6 Pseudocodice BucketSort ....................................................................................................................................................... 26

CAPITOLO 3. Programmazione Dinamica ............................................................................................... 27

3.1 Catena di montaggio .........................................................................................................................................27

3.1.1 Fase 1 – Caratterizzare la struttura di una soluzione ottima................................................................................................ 28

3.1.2 Fase 2 – Definire ricorsivamente il valore della soluzione ottima ........................................................................................ 28

3.1.3 Fase 3 – Calcolo del tempo minimo ....................................................................................................................................... 29

3.1.4 Fase 4 – Calcolo del percorso più rapido ............................................................................................................................... 29

3.2 Moltiplicazioni tra matrici .................................................................................................................................29

3.2.1 Fase 1 – Caratterizzare la struttura di una soluzione ottima................................................................................................ 30

3.2.2 Fase 2 – Definire ricorsivamente il valore della soluzione ottima ........................................................................................ 30

3.2.3 Fase 3 – Calcolo dei costi ottimi ............................................................................................................................................. 31

3.3 LCS – Longest Common Sequence .....................................................................................................................32

3.3.1 Fase 1 – Caratterizzare la struttura di una soluzione ottima................................................................................................ 33

3.3.2 Fase 2 – Definire ricorsivamente il valore della soluzione ottima ........................................................................................ 33

3.3.3 Fase 3 – Calcolo della lunghezza di una LCS .......................................................................................................................... 33

3.3.4 Fase 4 – Costruzione della soluzione ottima.......................................................................................................................... 34

3.4 Problema dello zaino 0-1 ..................................................................................................................................35

3.4.1 Approfondimenti sulla soluzione Zaino(n,W) con programmazione dinamica .................................................................... 35

3.5 Cambio monete ................................................................................................................................................37

CAPITOLO 4. Algoritmi Greedy .............................................................................................................. 39

4.1 Approccio Greedy VS Programmazione Dinamica .............................................................................................39

4.1.1 Proprietà della scelta ottima .................................................................................................................................................. 40

4.2 Selezione di attività (scheduling) .......................................................................................................................40

4.3 Problema dello zaino frazionario ......................................................................................................................41

4.4 Algoritmo di Huffman .......................................................................................................................................43

4.4.1 Huffman in breve .................................................................................................................................................................... 43

4.4.2 Codici prefissi .......................................................................................................................................................................... 44

4.4.3 Rappresentazione dei codici prefissi ...................................................................................................................................... 45

4.4.4 Costruzione del codice di Huffman......................................................................................................................................... 45

4.4.5 Analisi dell’algoritmo di Huffman .......................................................................................................................................... 46

CAPITOLO 5. Algoritmi di ricerca esaustiva ............................................................................................ 48

5.1 Backtracking .....................................................................................................................................................48

5.1.1 Problemi di soddisfacimento dei vincoli (CSP) ....................................................................................................................... 48

5.1.2 Ricerca in problemi CSP .......................................................................................................................................................... 49

5.1.3 Ricerca con backtracking per CSP .......................................................................................................................................... 49

5.1.4 Euristiche ................................................................................................................................................................................. 50

Appunti a cura di Liccardo Giuseppe – Università degli Studi di Napoli Parthenope

Pagina | 3

5.2 Branch & Bound................................................................................................................................................52

5.2.1 Schema generale .................................................................................................................................................................... 52

5.2.2 Componenti principali ............................................................................................................................................................ 53

5.2.3 Problema dello zaino 0-1 con B&B ......................................................................................................................................... 54

5.2.4 Considerazioni finali ............................................................................................................................................................... 54

CAPITOLO 6. Heap e HeapSort .............................................................................................................. 55

6.1 Heap .................................................................................................................................................................55

6.1.1 Memorizzazione di un Heap ................................................................................................................................................... 55

6.1.2 Max-Heap: da albero ad array ............................................................................................................................................... 56

6.1.3 Operazioni elementari su un Heap......................................................................................................................................... 57

6.1.4 Max-Heapify ........................................................................................................................................................................... 57

6.1.5 Complessità di Max-Heapify .................................................................................................................................................. 59

6.1.6 Osservazioni sull’Heap ............................................................................................................................................................ 60

6.2 Code con priorità ..............................................................................................................................................60

6.2.1 Heap-Maximum ...................................................................................................................................................................... 61

6.2.2 Heap-Extract-Max .................................................................................................................................................................. 61

6.2.3 Heap-Increase-Key .................................................................................................................................................................. 61

6.2.4 Max-Heap-Insert ..................................................................................................................................................................... 61

6.3 Costruzione di un Heap .....................................................................................................................................62

6.3.1 Complessità di Costruisci-Heap .............................................................................................................................................. 64

6.3 HeapSort ..........................................................................................................................................................64

6.3.1 Complessità di HeapSort ........................................................................................................................................................ 67

CAPITOLO 7. Strutture dati per insiemi disgiunti ................................................................................... 68

7.1 Operazioni su insiemi disgiunti .........................................................................................................................68

7.2 Rappresentazione di insiemi disgiunti mediante liste concatenate ...................................................................68

7.2.1 Complessità delle operazioni usando le liste concatenate ................................................................................................... 69

7.2.2 Osservazioni ............................................................................................................................................................................ 69

7.3 Rappresentazione di insiemi disgiunti mediante alberi ............................