Appunti di Dati e Algoritmi 1

Appunti di Dati e

Algoritmi 1

Corso L.T. Ingegneria Informatica, Prof. Vandin

UniPD, 1° semestre A.A. 2017/2018

Indice

Indice............................................................................................................................................................................... 1

Nozioni fondamentali ................................................................................................................................................ 3

Problema computazionale ..................................................................................................................................................... 3

Algoritmo e modello di calcolo ............................................................................................................................................ 3

Strutture dati ............................................................................................................................................................................... 3

Analisi degli algoritmi: Time Complexity ........................................................................................................................ 4

Ordini di grandezza .................................................................................................................................................................. 6

Efficienza asintotica degli algoritmi .................................................................................................................................. 9

Tecniche di dimostrazione .................................................................................................................................................... 9

Analisi degli algoritmi: Correttezza ................................................................................................................................ 11

Ricorsione .................................................................................................................................................................................. 12

Riepilogo .................................................................................................................................................................................... 16

Text Processing ......................................................................................................................................................... 17

Pattern Matching Problem .................................................................................................................................................. 17

Riepilogo .................................................................................................................................................................................... 23

Ripasso di Java ........................................................................................................................................................... 23

Calcolo dell’n-esimo numero di Fibonacci ................................................................................................................... 23

Caratteristiche di Java ed approccio O-O ...................................................................................................................... 24

Liste .............................................................................................................................................................................................. 26

Pile e Code ................................................................................................................................................................................. 31

Iteratori ...................................................................................................................................................................................... 32

Esempi di domande ............................................................................................................................................................... 32

Alberi ............................................................................................................................................................................. 33

Definizione informale ........................................................................................................................................................... 33

Albero radicato ........................................................................................................................................................................ 33

Implementazione di un albero generale ....................................................................................................................... 33

Visite di alberi .......................................................................................................................................................................... 35

Albero binario .......................................................................................................................................................................... 36

Riepilogo .................................................................................................................................................................................... 41

Priority Queue e Heap ............................................................................................................................................. 42

Entry ............................................................................................................................................................................................ 42

Definizione ................................................................................................................................................................................ 42

Priority Queue tramite liste (riepilogo) ........................................................................................................................ 42

Heap ............................................................................................................................................................................................. 42

Priority Queue tramite heap .............................................................................................................................................. 44

Costruzione di uno heap a partire da entry date ....................................................................................................... 45

- 1 -

Sorting tramite Priority Queue ......................................................................................................................................... 46

Riepilogo .................................................................................................................................................................................... 47

Mappa e Dizionario .................................................................................................................................................. 48

Definizione generale ............................................................................................................................................................. 48

Mappa - Definizione ............................................................................................................................................................... 48

Implementazione con Doubly Linked List ................................................................................................................... 48

Implementazione con Tabella Hash ................................................................................................................................ 48

Implementazione con Alberi .............................................................................................................................................. 50

Dizionario (Multimap) .......................................................................................................................................................... 52

Riepilogo .................................................................................................................................................................................... 52

Grafo .............................................................................................................................................................................. 53

Definizioni ................................................................................................................................................................................. 53

Alberi visti come grafi ........................................................................................................................................................... 53

Proprietà dei Grafi .................................................................................................................................................................. 54

Graph Trasversal .................................................................................................................................................................... 54

Riepilogo .................................................................................................................................................................................... 56

Ordinamento .............................................................................................................................................................. 57

Ordinamento basato su confronti .................................................................................................................................... 57

Ordinamento non basato su confronti ........................................................................................................................... 60

Riepilogo .................................................................................................................................................................................... 61

- 2 -

Nozioni fondamentali

Problema computazionale

Un problema computazionale Π è una relazione tra un insieme di istanze I e un insieme di

soluzioni S: Π ⊆ I × S

con l’ulteriore vincolo che, per ogni istanza i ∈ I, esiste almeno una soluzione s ∈ S t.c. (i, s) ∈ Π.

Π è un sottoinsieme di tutte le possibili coppie; e in una coppia (i, s), s è soluzione di i.

Es. Π associa a ogni coppia di interi (i) la somma (s);

Π associa a ogni sequenza di interi (i) la sequenza ordinata (s);

Π associa a ogni sequenza di interi (i) la permutazione t.c. sia crescente (s).

Oss. Un’istanza può avere più soluzioni; e una soluzione può risolvere più istanze.

Algoritmo e modello di calcolo

Un algoritmo è una procedura computazionale ben definita che trasforma un dato input in un

output eseguendo una sequenza finita dipassi elementari.

L’algoritmo fa riferimento a un modello di calcolo (o modello di computazione), ovvero

un’astrazione di computer che definisce l’insieme di passi elementari.

Il modello di calcolo più utilizzato è il Random Access Machine: input, output, dati e programma

sono in memoria; i passi elementari sono operazioni primitive quali assegnamento, logica,

aritmetica, indicizzazione, return…

Algoritmo valido

Un algoritmo A risolve un problema computazionale Π se e solo se:

⊆ I × S

- Riceve in input istanze i ∈ I;

- Produce in output soluzioni s ∈ S;

- Dato un input i ∈ I, genera un output s ∈ S tale che (i, s) ∈ Π.

In altre parole, A calcola una funzione che mappa istanze nelle rispettive soluzioni.

Un algoritmo viene solitamente descritto in pseudocodice.

Taglia

La taglia (size) di un istanza è una funzione che mappa ogni istanza in uno o più valori, che

misurano la sua grandezza. La taglia è utilizzata per partizionare l’universo delle istanze in

sottoinsiemi costituiti da istanze tra loro simili e confrontabili, inmodo che l’analisi di un

algoritmo possa essere espressa parametricamente in essa.

“MergeSort richiede tempo O(n log n)”

Es. specifica la complessità dell’algoritmo in funzione della

taglia, in questo caso il numero di argomenti da ordinare.

Strutture dati

Gli algoritmi utilizzano strutture dati per organizzare e accedere in modo sistematico ai dati di

input e a dati intermedi generati durante l’esecuzione.

Una struttura dati è una collezione di oggetti corredata di metodi per accedere e/o modificare la

collezione. Nella definizione di una struttura dati si distinguono due livelli di astrazione:

- Livello logico: specifica l’organizzazione logica degli oggetti della collezione, e la relazione

input-output che caratterizza ciascun metodo (ADT); in Java, le interfacce.

- Livello fisico: specifica il layout fisico dei dati e l’implementazione dei metodi tramite

opportuni algoritmi; in Java, le classi. - 3 -

Es. Specificare come problema computazionale Π la ricerca dell’inizio e della lunghezza del più

lungo segmento di 1 consecutivi in una stringa binaria.

→ I = stringhe binarie ; S = coppie di interi

Π = insieme di coppie (X, (j,k)), con X ∈ I e (j,k) ∈ S, tali che:

- se X contiene almeno un 1, allora il segmento più lungo di 1 consecutivi in X è

X [j ÷ j+k−1]

- se X non contiene 1 (vuota o tutti 0), allora j = -1 e k = 0.

Es. Specificare come problema computazionale Π la verifica se due insiemi finiti di oggetti sono

disgiunti oppure no.

→ I = coppie di insiemi; S = {yes; no}

Π = insiemi di coppie ((X, Y), s), con (X, Y) ∈ I e s ∈ S, tali che:

- se X ⋂ Y = ∅, allora S = yes

- se X ⋂ Y ≠ ∅, allora S = no

CSt. Trovare un insieme di articoli molto diversi tra quelli presenti su siti di giornali, tv, radio, ecc.

→ Formalizzazione (diversity problem): articolo = punto in spazio multidimensionale R; metrica di

distanza d(x,y); diversità di un sottoinsieme di R: minima distanza tra gli elementi di R.

→ I = coppie (X, k) con X ⊂ R, k > 1; S = sottoinsiemi Y ⊂ R di cardinalità k

Π = insieme di coppie ((X, k), Y) tali che Y ⊂ X, |Y| = k, e Y ha diversità massima.

Analisi degli algoritmi: Time Complexity

Si può voler “valutare” un algoritmo → analisi di un algoritmo sotto diversi aspetti:

- complessità temporale o spaziale

- correttezza: terminazione, soluzione del problema computazionale

Sono di nostro interesse complessità temporale e soluzione del problema computazionale.

Time Complexity

È la stima del tempo di esecuzione (running time) di un algoritmo.

Oss. Dipende da:

- istanza di input; cresce con la taglia, ma non solo (caso peggiore dell’InsertionSort)

- hardware (processore, memoria, etc)

- software (linguaggio, OS, compilatore, etc)

L’analisi della time complexity deve:

1. considerare tutti gli input

2. permettere di confrontare algoritmi tra di loro

3. essere fattibile a partire da una specifica high level dell’algoritmo (pseudocodice)

L’approccio generale è il seguente:

- analisi al caso pessimo (worst case) in funzione della taglia dell’istanza (1 e 2)

- conteggio di passi elementari da compiere nel modello RAM (2 e 3)

- calcolo asintotico per semplificare il conteggio.

Complessità al caso pessimo

Sia A un algoritmo che risolve Π e si usi n per denotare la taglia dell’istanza: la complessità al

caso pessimo di A è la funzione t (n) = massimo numero di operazioni (passi elementari) che A

A

esegue per risolvere una istanza di taglia n.

Oss. Il massimo è su tutte le istanze di taglia n; per una data istanza, il numero di op. è fisso.

- 4 -

Es. Si considera il seguente algoritmo:

Algoritmo arrayMax(A,n)

Input: array di interi A di lunghezza n ≥1

Output: max intero in A

1 currMax ← A[0];

2 for i ← 1 to n−1 do

3 if currMax < A[i] then

4 currMax ← A[i];

5 return currMax;

→ Come risolvo? Conto le operazioni per ogni riga.

Riga 1: due operazioni (indicizzazione, assegnamento)

Riga 2: un assegnamento iniziale

Riga 2: n volte devo calcolare n – 1 e vedere se i ≤ n – 1: 1+1 operazioni

Righe 3-4: n – 1 volte devo calcolare

a) la condizione dell’if: indicizzazione e confronto

b) indicizzazione e assegnazione per la riga 4 (se if è true)

c) incrementare i: calcolo e assegnazione

Riga 5: return (1 operazione)

Dunque nel caso peggiore, quello in cui tutti gli if sono true (array crescente), ho

3 + 2n + 6(n – 1) + 1 = 8n – 2 operazioni → t (n) = 8n – 2

A

Il calcolo ha alcune difficoltà:

- calcolo esatto di t (n)

A

- identificare l’istanza peggiore

Si adottano perciò certe semplificazioni:

- Si ignorano fattori moltiplicativi costanti (che non dipendono dalla taglia)

- Si ignorano i termini non dominanti (asintoticamente)

- Si stimano i limiti superiori e inferiori

Questa è pertanto un’analisi asintotica. Non serve identificare l’istanza peggiore (difficile):

- Limite superiore: un’istanza (quella peggiore) ci mette al più t

- Limite inferiore: un’istanza (quella peggiore) ci mette almeno t

Nell’esempio precedente tutto si riduce a dire che tutte le istruzioni fuori dal for hanno un numero

costante di operazioni, e il ciclo for (ripetuto n – 1 volte) ha numero costante di operazioni in ogni

iterazione; dunque arrayMax ha complessità proporzionale a n.

- 5 -

Ordini di grandezza

Siano in tutte le definizioni seguenti f(n) e g(n) due funzioni ℕ → ℝ.

O-grande ≥ 0 t.c. f(n) ≤ cg(n), ∀ n ≥ n .

Si ha che f(n) ∈ O (g(n)) se ∃ c > 0, n 0

0

f(n) è asintoticamente minore di g(n); per esempio, t (n) ∈ O(n) per c = 8, n = 1;

arrayMax 0

t (n) ∈ O(n ) per c = 1, n = 8;

2

arrayMax 0

2 ∈ O(1) per c = 2 , n = 1.

100 100 0

Omega-grande

Si ha che f(n) ∈ Ω (g(n)) se ≥ 0 t.c. f(n) ≥ cg(n), ∀ n ≥ n .

∃ c > 0, n 0

0

Per esempio t (n) ∈ Ω (n) (c = 1, n = 1).

arrayMax 0

Theta-grande

Se entrambe le precedenti condizioni sono soddisfatte, allora f(n) ∈ Θ (g(n)):

∃ c’, c’’ >0 t.c. c′g(n) ≤ f(n) ≤ c′′g(n) ∀ n ≥ n