Algoritmi e strutture dati

Appunti del corso di

Algoritmi e Strutture Dati

Vincenzo Acciaro

2

Per suggerimenti, commenti o segnalazione di errori scrivere a

acciaro@di.uniba.it

oppure a

m di leonardo@yahoo.it

Indice

1 Introduzione 9

1.1 Programmazione in piccolo ed in grande . . . . . . . . . . . . 9

1.2 Obiettivi del corso . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Motivazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.1 I limiti del calcolabile . . . . . . . . . . . . . . . . . . . 11

1.4 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.1 Specifiche del problema . . . . . . . . . . . . . . . . . . 13

1.4.2 Strumenti di formalizzazione . . . . . . . . . . . . . . . 14

1.4.3 Esempio di algoritmo . . . . . . . . . . . . . . . . . . . 14

1.4.4 L’algoritmo come funzione . . . . . . . . . . . . . . . . 15

1.4.5 Nota storica . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 Definizione formale di problema. . . . . . . . . . . . . . . . . . 16

1.6 Programma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.7 Costi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.7.1 Risorse di calcolo . . . . . . . . . . . . . . . . . . . . . 17

1.7.2 Efficienza. . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.7.3 Modello di calcolo . . . . . . . . . . . . . . . . . . . . . 18

1.7.4 Irrisolubilità . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.5 Intrattabilità . . . . . . . . . . . . . . . . . . . . . . . 19

2 La macchina di Turing 21

2.1 Definizione di Macchina di Turing . . . . . . . . . . . . . . . . 21

2.1.1 L’alfabeto esterno della M.d.T. . . . . . . . . . . . . . 22

2.1.2 Gli stati della M.d.T. . . . . . . . . . . . . . . . . . . . 22

2.1.3 Configurazione iniziale della MdT. . . . . . . . . . . . 22

2.1.4 Il programma nella M.d.T. . . . . . . . . . . . . . . . . 22

2.1.5 Il Programma come funzione . . . . . . . . . . . . . . . 23

2.1.6 Terminazione della computazione. . . . . . . . . . . . . 23

3

4 INDICE

2.2 Ipotesi fondamentale della teoria degli algoritmi . . . . . . . . 23

2.2.1 Irrisolubilità . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 La Random Access machine (RAM) 27

3.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2 Complessità computazionale di programmi RAM . . . . . . . . 28

4 Nozioni base di complessità 31

4.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.1.1 Obiettivi in fase di progetto. . . . . . . . . . . . . . . . 32

4.1.2 Ancora sulle risorse . . . . . . . . . . . . . . . . . . . . 33

4.2 Il tempo di esecuzione di un programma . . . . . . . . . . . . 33

4.2.1 Due misure apparentemente ragionevoli . . . . . . . . . 33

4.2.2 Dimensione del problema . . . . . . . . . . . . . . . . . 34

4.2.3 Misura della Dimensione . . . . . . . . . . . . . . . . . 34

4.3 Complessità temporale . . . . . . . . . . . . . . . . . . . . . . 34

4.4 Confronto di algoritmi . . . . . . . . . . . . . . . . . . . . . . 36

O

4.5 Definizione formale di . . . . . . . . . . . . . . . . . . . . . 39

4.5.1 Alcuni ordini di grandezza tipici . . . . . . . . . . . . 41

4.6 La notazione Ω . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.6.1 Definizione alternativa di Ω . . . . . . . . . . . . . . . 43

4.7 La notazione Θ . . . . . . . . . . . . . . . . . . . . . . . . . . 43

O,

4.8 Alcune proprietà di Ω, Θ . . . . . . . . . . . . . . . . . . . 44

4.8.1 Sulle notazioni asintotiche . . . . . . . . . . . . . . . . 44

4.9 Ricapitolando . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.10 Complessità di problemi . . . . . . . . . . . . . . . . . . . . . 45

O

4.10.1 La notazione applicata ai problemi . . . . . . . . . . 45

4.10.2 La notazione Ω applicata ai problemi. . . . . . . . . . . 46

4.11 Algoritmi ottimali . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.12 Funzioni limitate polinomialmente . . . . . . . . . . . . . . . . 47

4.13 Crescita moderatamente esponenziale . . . . . . . . . . . . . . 47

4.14 Crescita esponenziale . . . . . . . . . . . . . . . . . . . . . . . 47

4.15 Appendice: Notazione asintotica all’interno di eguaglianze . . 48

4.16 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

INDICE 5

5 Linguaggi per la descrizione di algoritmi 49

5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2 Valutazione della complessità di algoritmi scritti in pseudo-

codice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

O

5.3 Alcune regole per il calcolo di . . . . . . . . . . . . . . . . . 51

5.3.1 Applicazione: funzioni polinomiali . . . . . . . . . . . . 52

6 Algoritmi ricorsivi 53

6.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.2 Qualche mini esempio . . . . . . . . . . . . . . . . . . . . . . . 54

6.3 Linguaggi di programmazione che consentono la ricorsione . . 55

6.3.1 Visita di un albero binario . . . . . . . . . . . . . . . . 56

7 L’approccio Divide et Impera 57

7.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7.1.1 Esempio: il Mergesort . . . . . . . . . . . . . . . . . . 60

7.2 Bilanciamento . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.3 L’algoritmo di Strassen . . . . . . . . . . . . . . . . . . . . . . 62

8 Tecniche di analisi di algoritmi ricorsivi 65

8.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

8.1.1 Esempio: Visita di un albero binario . . . . . . . . . . 68

8.2 Soluzione delle equazioni di ricorrenza . . . . . . . . . . . . . . 69

8.3 Il caso Divide et Impera . . . . . . . . . . . . . . . . . . . . . 70

8.3.1 Dimostrazione del Teorema Principale . . . . . . . . . 72

8.3.2 Soluzione Particolare . . . . . . . . . . . . . . . . . . . 74

8.3.3 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

9 Liste, Pile e Code 77

10 Grafi e loro rappresentazione in memoria 79

11 Programmazione Dinamica 81

11.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

11.1.1 Un caso notevole . . . . . . . . . . . . . . . . . . . . . 81

11.1.2 Descrizione del metodo . . . . . . . . . . . . . . . . . . 82

11.1.3 Schema base dell’algoritmo . . . . . . . . . . . . . . . . 83

11.1.4 Versione definitiva dell’algoritmo . . . . . . . . . . . . 83

11.1.5 Un esempio svolto . . . . . . . . . . . . . . . . . . . . 84

6 INDICE

12 Dizionari 85

13 Alberi 87

14 Alberi di Ricerca Binari 89

15 Alberi AVL 91

16 2-3 Alberi e B-Alberi 93

17 Le heaps 95

17.1 Le code con priorità . . . . . . . . . . . . . . . . . . . . . . . 95

17.2 Le heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

17.3 Ricerca del minimo . . . . . . . . . . . . . . . . . . . . . . . . 97

17.4 Inserimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

17.5 Cancellazione del minimo . . . . . . . . . . . . . . . . . . . . . 98

17.6 Costruzione di una heap . . . . . . . . . . . . . . . . . . . . . 99

17.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

18 Heapsort 103

19 Tecniche Hash 105

19.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

19.2 Caratteristiche delle funzioni hash . . . . . . . . . . . . . . . . 108

19.3 Tecniche di scansione della tabella . . . . . . . . . . . . . . . . 109

19.3.1 Scansione uniforme . . . . . . . . . . . . . . . . . . . . 109

19.3.2 Scansione lineare . . . . . . . . . . . . . . . . . . . . . 109

19.3.3 Hashing doppio . . . . . . . . . . . . . . . . . . . . . . 110

19.3.4 Hashing quadratico . . . . . . . . . . . . . . . . . . . . 110

19.4 Hashing tramite concatenamento diretto . . . . . . . . . . . . 111

19.5 Hashing perfetto . . . . . . . . . . . . . . . . . . . . . . . . . 112

19.6 Implementazione pratica di uno schema ad indirizzamento aper-

to . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

19.7 Analisi di complessità . . . . . . . . . . . . . . . . . . . . . . . 115

19.7.1 Dimostrazione per le tecniche a concatenazione . . . . 116

19.8 Esercizi di ricapitolazione . . . . . . . . . . . . . . . . . . . . 117

19.9 Esercizi avanzati . . . . . . . . . . . . . . . . . . . . . . . . . 118

INDICE 7

20 Il BucketSort 121

20.1 Descrizione dell’algoritmo . . . . . . . . . . . . . . . . . . . . 121

20.1.1 Correttezza dell’algoritmo . . . . . . . . . . . . . . . . 122

20.1.2 Complessità nel caso medio . . . . . . . . . . . . . . . 123

20.1.3 Complessità nel caso pessimo . . . . . . . . . . . . . . 124

20.2 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

21 Complessitá del problema ordinamento 125

21.1 Alberi decisionali . . . . . . . . . . . . . . . . . . . . . . . . . 125

22 Selezione in tempo lineare 129

22.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

22.2 Un algoritmo ottimale . . . . . . . . . . . . . . . . . . . . . . 130

23 Algoritmi su grafi 135

8 INDICE

Capitolo 1

Introduzione

1.1 Programmazione in piccolo ed in grande

Distinguiamo grossolanamente l’attività di programmazione in due aree di-

stinte:

1 La programmazione in grande;

2 La programmazione in piccolo.

La programmazione in grande si occupa della soluzione informatica di

problemi di grandi dimensioni (ad esempio l’informatizzazione della Regione

Puglia).

La programmazione in piccolo si preoccupa di trovare una buona soluzione

algoritmica a specifici problemi ben formalizzati (ad esempio, l’ordinamento

di una lista di elementi).

1.2 Obiettivi del corso

Il presente corso si preoccupa di fornire una introduzione alle nozioni di base

ed ai metodi della programmazione in piccolo. In particolare studieremo:

• Come organizzare e rappresentare l’informazione (le strutture dati) al

fine di ottenere una sua efficiente manipolazione (gli algoritmi);

• Come valutare la bontà di un programma (o meglio, di un algoritmo).

9

10 CAPITOLO 1. INTRODUZIONE

Testi di riferimento

I testi di riferimento sono indicati in bibliografia. Come libro di testo è

fortemente consigliato il volume di Lodi e Pacini [1].

Come libro di consultazione si consiglia il classico testo di Aho, Hopcroft

e Ullman [4]. Questo è un ”must” per gli addetti al settore, ovvero un volume

di cui non si può fare a meno.

Infine, la trattazione matematica del problema della complessità degli

algoritmi è molto rigorosa nel primo volume di Cormen, Leiserson e Rivest

[2].

1.3 Motivazioni

La potenza di calcolo che si trova su un personal computer di oggi, appena

qualche anno fa era disponibile solo sui mainframes (”grossi calcolatori”).

Disponendo di calcolatori più potenti, si cerca di risolvere problemi più

complessi, che a loro volta domandano maggiore potenza di calcolo... entran-

do cosi in un giro vizioso.

La volgarizzazione dell’informatica, se da una parte ha contribuito al

progresso economico, scientifico e tecnologico, ecc., dall’altra ha creato tanti

miti, uno dei quali é il seguente:

Mito (da sfatare): Se un problema é ben posto (formalizzato)

allora é possibile risolverlo se si disponga della adeguata potenza

di calcolo.

Ovvero: Se il calcolatore a nostra disposizione non é sufficiente per risolvere

un problema assegnato in tempo ragionevole, possiamo sempre risolvere il

problema utilizzando un calcolatore piú potente.

Nota bene 1 Nel linguaggio comune, la parola ”risolvere” giá implica ”in

tempo ragionevole”.

Ma, cosa si intende per ”tempo ragionevole”? Intuitivamente, un intervallo

di tempo é ”ragionevole” se é tale quando si rapporti alla durata media della

vita dell’uomo (1 minuto é ragionevole, 20 anni no!).

1.4. ALGORITMO 11

1.3.1 I limiti del calcolabile

Il seguente argomento, dovuto a L.J. Stockmeyer, di natura puramente fisica,

mostra efficacemente cosa si intenda per ”limiti del calcolabile”:

Il più potente calcolatore che si possa costruire non potrà mai es-

sere piú grande dell’universo (meno di 100 miliardi di anni luce

di diametro), nè potrà essere costituito da elementi più piccoli di

un protone (10-13 cm di diametro), nè potrà trasmettere infor-

mazioni ad una velocità superiore a quella della luce (300000 km

al secondo). 126

Quindi tale calcolatore non potrebbe avere più di 10 componen-

ti.

A.R. Meyer e L.J. Stockmeyer hanno dimostrato che tale calco-

latore impiegherebbe almeno 20 miliardi di anni per risolvere dei

problemi la cui risolubilità é nota in linea di principio. Poiché

presumibilmente l’universo non ha una età superiore ai 20 mil-

iardi di anni, ciò sembra sufficiente per affermare che questi

problemi sfidano l’analisi del calcolatore.

Alcuni obiettivi che ci poniamo:

1 Studio delle proprietà dei problemi computazionali, delle caratteristiche

che ne rendano facile o difficile la risoluzione automatica.

2 Studio delle tecniche basilari di analisi e progettazione di algoritmi.

3 Definizione e studio dei problemi computazionalmente intrattabili, ovvero

di quei problemi per cui si ritiene che non possa esistere alcun algoritmo

che risolva il problema in tempo ragionevole.

1.4 Algoritmo

Un algoritmo é un metodo di risoluzione di un problema, che presuppone

l’esistenza di:

1 un committente, ovvero colui che pone il problema e desidera conoscerne

la soluzione;

2 un esecutore, in grado di svolgere determinati compiti elementari.

12 CAPITOLO 1. INTRODUZIONE

Ricapitoliamo qui di seguito alcuni concetti fondamentali:

• All’inizio dell’esecuzione, l’esecutore riceve dal committente un insieme

di dati che rappresentano la descrizione della particolare istanza del

problema che si intende risolvere.

• I dati appartengono ad un insieme finito di simboli

{a, {14,

(ad esempio . . . , z} oppure 78, 98, 1} ).

• Deve essere definito un meccanismo con il quale l’esecutore comunica

al committente la soluzione del problema (il ”risultato”) al termine

dell’esecuzione.

• L’algoritmo é costituito da una sequenza di istruzioni che indicano in

modo non ambiguo le azioni che l’esecutore deve compiere.

• L’esecuzione avviene per passi discreti.

• L’esecuzione termina dopo un numero di passi finito, che é funzione

della particolare istanza del problema.

1 Attenzione

Occorre che sia ben chiara la distinzione tra problema, istanza del problema,

e descrizione dell’istanza.

Esempio 1 Un possibile problema è costituito dall’addizione di due numeri

interi. Chiameremo questo problema Addizione.

Una istanza del problema è la seguente:

Addizione

Somma i numeri interi 45 e 6

La descrizione di tale istanza è (i ”dati di input”):

I numeri interi 45 e 6

Il risultato (”output”) sarà costituito da:

Il numero intero 51

Esempio 2 Un possibile problema è costituito dall’ordinamento di un certa

sequenza di numeri interi. Chiameremo questo problema Ordinamento.

Una istanza del problema è la seguente:

Ordinamento

1.4. ALGORITMO 13

Ordina la sequenza 3,8,6,0,2

La descrizione di tale istanza è (i ”dati di input”):

La sequenza 3,8,6,0,2

Il risultato (”output”) sarà costituito da:

La sequenza 0,2,3,6,8

1.4.1 Specifiche del problema

Il precedente esempio Ordinamento è stato presentato in modo molto infor-

male (”discorsivo”).

Una descrizione informale del problema che si intende risolvere può essere

molto utile, in un primo momento, ad esempio per chiarirsi le idee.

Molto spesso sappiamo che c’è un problema, tuttavia non siamo in grado

di formalizzare esattamente tale problema.

Una descrizione informale del problema può essere sufficiente nel caso in

cui l’esecutore sia un essere dotato di capacità cognitiva simile alla nostra, e

che condivida con noi:

1 l’esperienza (ad esempio possiamo dire ad un nostro collaboratore ”sbriga-

mi la pratica del 3 dicembre”, ed il nostro collaboratore saprà esatta-

mente cosa fare) oppure

2 il senso comune (ad esempio uno sconosciuto: ”mi scusi, che ora è?”).

In attesa di costruire degli oggetti artificiali dotati della nostra esperienza

o del nostro senso comune (questo è uno degli obiettivi della Intelligenza

Artificiale), occorre specificare esattamente, in una prima fase, la natura del

problema da risolvere.

2 Attenzione

Non confondere la natura del problema da risolvere con la descrizione del

metodo di risoluzione del problema.

Esempio 3 Il problema Ordinamento può essere definito (”specificato”) nel

modo seguente:

14 CAPITOLO 1. INTRODUZIONE

• Dati: Un insieme di n chiavi a , . . . , a che è possibile confrontare

1 n

≤.

usando l’operatore Le chiavi sono numeri interi positivi più piccoli

di un limite prefissato (ad esempio 1000).

• Risultato: Una sequenza b , . . . , b che costituisce un riordinamento

1 n ≤

dell’insieme dato di chiavi e che soddisfa la relazione b b per ogni

i i+1

−

i = 1, 2, ..., n 1.

1.4.2 Strumenti di formalizzazione

La Matematica, ed in particolare la Logica Matematica, ci fornisce degli

strumenti eccellenti di formalizzazione, poichè ci permette di asserire in modo

non ambiguo:

• le relazioni che legano tra loro i dati di input (esempio: nel caso dell’Or-

dinamento, tutti i dati di input appartengono ad uno stesso insieme,

l’insieme delle chiavi);

• le relazioni che legano l’output all’input (i dati di output come ”fun-

zione” dei dati di input);

• le relazioni che dovranno legare tra loro i dati di output (esempio: nel

≤ −

caso dell’Ordinamento, la relazione b b per ogni i = 1, 2, . . . , n

i i+1

1).

1.4.3 Esempio di algoritmo

Uno degli algoritmi più elementari e