Note per il corso di Complementi di Algoritmi e Strutture Dati...Note per il corso di Complementi di...

Note per il corso diComplementi di Algoritmi e Strutture Dati∗

a.a. 12/13 - Versione provvisoria

Elena Zucca

26 settembre 2012

IndiceIntroduzione 1

1 Analisi della correttezza e complessita degli algoritmi 11.1 Correttezza di algoritmi ricorsivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Correttezza di algoritmi iterativi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Notazioni asintotiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Complessita di algoritmi e problemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Esempi di progettazione e analisi di algoritmi ricorsivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.6 Teorema fondamentale delle ricorrenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.7 Esempi di progettazione e analisi di algoritmi iterativi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Algoritmi di ordinamento 72.1 Algoritmi elementari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.1 Selection sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.2 Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5 Delimitazione inferiore della complessita del problema dell’ordinamento per confronti . . . . . . . . . . . . . . 212.6 Algoritmi di ordinamento lineari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 Strutture dati 263.1 Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.2 Strutture union-find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 Grafi 314.1 Introduzione e terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Visite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.3 Cammini minimi in un grafo pesato: algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.4 Algoritmo di Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.5 Algoritmo di Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.6 Ordinamento topologico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.7 Componenti fortemente connesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

∗Queste note sono in parte elaborate a partire da materiale didattico del professor Elio Giovannetti, che ringrazio infinitamente. Gli esempi e gli eserciziservono ad acquisire familiarita con le tecniche descritte, ma non saranno oggetto di domande all’orale.

5 Teoria della NP-completezza 435.1 Problemi astratti e concreti e classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.2 Classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.3 Problemi NP-completi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.4 Algoritmi di approssimazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

A Relazioni d’ordine e di equivalenza 51

1 Analisi della correttezza e complessita degli algoritmi

1.1 Correttezza di algoritmi ricorsiviE basata sul principio di induzione, di cui casi particolari sono il principio di induzione aritmetica e quello di induzione aritmeticacompleta, ma che piu in generale si applica a qualunque insieme definito induttivamente. Vediamo cosa significa.

Def. 1.1 [Definizione induttiva] Una definizione induttiva R e un insieme di regole Prc , dove Pr e un insieme detto delle premesse

e c e un elemento, detto la conseguenza della regola. L’insieme definito induttivamente I(R) e il piu piccolo tra gli insiemi Xchiusi rispetto a R, ossia tali che, per ogni regola Pr

c ∈ R, se Pr ⊆ X allora c ∈ X .

In altre parole, I(R) e l’insieme di tutti e soli gli elementi che si ottengono applicando ripetutamente le regole, a partire da quellecon premessa vuota che costituiscono la base della definizione induttiva.Una definizione induttiva e in genere data attraverso una qualche descrizione finita “a parole”, per esempio:

L’insieme dei numeri pari e il piu piccolo insieme tale che (oppure: e l’insieme definito induttivamente da):

• 0 e un numero pari,

• se n e un numero pari, allora n+ 2 e un numero pari.

Questa descrizione corrisponde all’insieme (infinito) di regole: ∅0 ∪ nn+2 | n ∈ N.

Prop. 1.2 [Principio di induzione (forma generale)] Sia R una definizione induttiva, I(R) ⊆ U , e P un predicato su U .Se, per ogni Pr

c ∈ R,

(P (d) vale per ogni d ∈ Pr ) implica che valga P (c) (?)

allora P (d) vale per ogni d ∈ I(R).

Dimostrazione Poniamo C = d | P (d) vero e osserviamo che la condizione (?) puo essere scritta nella forma equivalente:

Pr ⊆ C implica c ∈ C.

Allora e chiaro che C risulta chiuso rispetto a R, quindi I(R) ⊆ C, quindi P (d) vale per ogni d ∈ I(R).Si noti che nel caso Pr = ∅ richiedere la condizione (?) equivale a richiedere che P (c) sia vero. Cio suggerisce la seguenteformulazione equivalente che e quella comunemente usata:Sia R una definizione induttiva, I(R) ⊆ U , e P un predicato su U .Se

Base P (c) vale per ogni ∅c ∈ R

Passo induttivo (P (d) vale per ogni d ∈ Pr ) implica che valga P (c) per ogni Prc ∈ R,Pr 6= ∅

allora P (d) vale per ogni d ∈ I(R).Vediamo alcuni casi particolari del principio di induzione.

Prop. 1.3 [Principio di induzione aritmetica] Sia P un predicato sui numeri naturali tale che

Base vale P (0)

Passo induttivo se vale P (n) allora vale P (n+ 1),

allora P (n) vale per ogni n ∈ N.

2

Dimostrazione N puo essere visto come l’insieme definito induttivamente da

• 0 ∈ N

• se n ∈ N allora n+ 1 ∈ N.

Quindi la proposizione e un caso particolare del principio di induzione.Vediamo un esempio di applicazione.

Esempio 1.4 Proviamo per induzione aritmetica che 20 + 21 + ...+ 2n = 2n+1 − 1, per tutti gli n ∈ N.

Base P (0): 20 = 1 = 21 − 1

Passo induttivo Assumiamo P (i) e dimostriamo P (i+ 1):

20 + 21 + ...+ 2i+1 = (20 + 21 + ...+ 2i) + 2i+1

= (2i+1 − 1) + 2i+1 (per ipotesi induttiva)= 2 · (2i+1)− 1= 2i+2 − 1

Esercizio 1.5

1. Si dimostri che 1 + 2 + ...+ n = n(n+ 1)/2.

2. Si dimostri che 12 + 22 + 32 + ...+ n2 = n(n+ 1)(2n+ 1)/6.

Prop. 1.6 [Principio di induzione aritmetica completa] Sia P un predicato sui numeri naturali tale che

Base vale P (0)

Passo induttivo se vale P (m) per ogni m < n allora vale P (n),

allora P (n) vale per ogni n ∈ N.

Dimostrazione N puo essere visto come l’insieme definito induttivamente da

• 0 ∈ N

• se m | m < n ⊆ N allora n ∈ N.

Quindi la proposizione e un caso particolare del principio di induzione.

Esempio 1.7 Un altro esempio: possiamo dare una definizione induttiva degli alberi binari (con nodi in N ) :

• l’albero vuoto e un albero binario,

• se L e R sono alberi binari e x ∈ N , allora la tripla (x ,L,R) e un albero binario.

Di conseguenza, e possibile provare proprieta degli alberi binari con il principio di induzione, che prende la seguente forma:

Sia P un predicato sugli alberi binari tale che

• P vale sull’albero vuoto,

• se P vale su L e R, allora vale su (x ,L,R),

allora P vale su tutti gli alberi binari.

Esercizio 1.8 Dare una definizione induttiva delle liste e formulare il corrispondente principio di induzione.

Se abbiamo un algoritmo ricorsivo il cui input varia in un insieme definito induttivamente, e definito a sua volta in modo induttivo(ossia ricalcando la definizione induttiva dell’insieme), e facile provare la correttezza dell’algoritmo con il principio di induzione.Per esempio nel caso di un algoritmo sui numeri naturali:

• se l’algoritmo e corretto per 0

• e assumendo che sia corretto per n, e corretto per n+ 1,

3

allora e corretto su qualunque numero naturale. Analogamente si puo applicare il principio di induzione arimetica completa o ilprincipio di induzione per alberi, liste, etc.Inoltre, il principio di induzione non solo ci consente di provare a posteriori la correttezza di un algoritmo, ma fornisce ancheuna guida per il suo sviluppo. Per esempio, nel caso dell’induzione aritmetica:

• si scrive l’algoritmo corretto per 0

• se l’argomento e n > 0, si assume che l’algoritmo sappia operare correttamente su n− 1, e fidandosi di tale assunzione siscrive l’algoritmo corretto per operare su n.

Esempio 1.9 [Algoritmo di Euclide] E nota la seguente proprieta: MCD(a, b) = MCD(b, a mod b) dove a mod b e il restodella divisione intera di a per b.

Base Sappiamo calcolare direttamente MCD(a, 0) per qualunque a, poiche esso e semplicemente a. Quindi mcd(a,0)=a.

Passo induttivo (b > 0).

Ipotesi induttiva La funzione mcd calcola correttamente MCD(a, b′) per qualunque b′ < b (per qualunque a).

Tesi induttiva mcd(a,b) = mcd(b, a mod b) calcola correttamente MCD(a, b). Dimostrazione: si applica laproprieta nota, e poiche a mod b < b, si puo sfruttare l’ipotesi induttiva.

Il principio di induzione e implicitamente alla base, come vedremo, anche della scrittura di algoritmi iterativi corretti.

1.2 Correttezza di algoritmi iterativiCome si scrive un algoritmo iterativo “in modo che sia corretto”?

//Pre: precondizione = quello che sappiamo essere vero all’iniziowhile (B)

C//Post: postcondizione = quello che vogliamo sia vero alla fine

L’algoritmo e corretto se, assumendo che valga Pre all’inizio, possiamo concludere che vale Post alla fine.Cos’e un’invariante di ciclo? qualunque condizione Inv tale che:

//Pre: Inv ∧ BC//Post: Inv

cioe, se devo eseguire il corpo del ciclo e la condizione vale, allora vale anche dopo averlo eseguito.Quando un’invariante serve a provare la correttezza?

• Inv vale all’inizio

• se valgono insieme Inv e ¬ B e allora vale Post .

Infatti, in questo caso e facile vedere per induzione aritmetica sul numero di iterazioni che, assumendo che il comando termini,alla fine vale Post . Come si prova la terminazione? trovando una quantita t (funzione di terminazione) tale che, se devo eseguireil corpo, quindi se valgono Inv e B:

• viene decrementata eseguendo il corpo

• e limitata inferiormente.

Esempio 1.10 [Esempio “didattico”]

//Pre: x = x0 ∧ y = y0 ∧ x ≥ 0while (x != 0)

x = x-1y = y+1

//Post: y = x0 + y0

Ci sono molte invarianti, per esempio x ≥ 0, x ≤ x0, y ≥ y0, true, false, ma quella che mi serve e x+y = x0 +y0∧x ≥ 0.

4

//Pre: x = x0 ∧ y = y0 ∧ x ≥ 0while (x!=0) //Inv: x + y = x0 + y0 ∧ x ≥ 0

x = x-1y = y+1

//Post: y = x0 + y0

Infatti:

• vale banalmente all’inizio

• se vale insieme a x = 0, allora vale la postcondizione.

• se vale insieme a x 6= 0 prima di eseguire il corpo, allora vale dopo

La funzione di terminazione che mi serve e il valore di x, infatti:

• viene decrementato a ogni passo

• assumendo che valga Inv (quindi x ≥ 0), e limitato inferiormente da 0.

Metodologia: l’invariante si ottiene in genere “indebolendo” la postcondizione, in modo da modellare il “risultato parzialeal passo generico”. L’invariante non serve solo per provare la correttezza a posteriori, ma soprattutto come guida allo sviluppodell’algoritmo. In molti algoritmi iterativi, inclusi una buona parte di quelli che vedremo, l’idea iniziale e “una buona invariante”.Una volta trovata la proprieta invariante, si scrivono nell’ordine: il corpo del ciclo in modo che produca un avvicinamento allasoluzione, la condizione di controllo in modo che in uscita si abbia la postcondizione, l’inizializzazione in modo da garantire chel’invariante valga inizialmente. Vedremo esempi di questa metodologia nella sezione 1.7.

1.3 Notazioni asintoticheDef. 1.11 Una funzione g(n) appartiene all’insieme O(f(n)) (si dice anche g(n) e O(f(n))) se esistono due costanti c > 0 en0 ≥ 0 tali che g(n) ≤ cf(n) per ogni n ≥ n0, ossia, da un certo punto in poi, g sta sotto una funzione “multipla” di f (“cresceal piu come f”).Una funzione g(n) appartiene all’insieme Ω(f(n)) (si dice anche g(n) e Ω(f(n))) se esistono due costanti c > 0 e n0 ≥ 0 taliche g(n) ≥ cf(n) per ogni n ≥ n0, ossia, da un certo punto in poi, f sta sopra una funzione “sottomultipla” di f (“cresce almenocome f”).Una funzione g(n) appartiene all’insieme Θ(f(n)) (si dice anche g(n) e Θ(f(n))) se esistono tre costanti c1, c2 > 0 e n0 ≥ 0tali che c1f(n) ≤ g(n) ≤ c2f(n) per ogni n ≥ n0, ossia, da un certo punto in poi, f e compresa tra un “multiplo” di f e un“sottomultiplo” di f (“cresce come f”).

Le espressioni “multiplo” e “sottomultiplo” sono un abuso di linguaggio, giustificato dalla seguente osservazione: nella defini-zione di O e significativo il fatto che c possa essere maggiore di uno, mentre nella definizione di Ω e significativo che c possaessere minore di uno.Per comodita si usa anche scrivere f(n) = O(g(n)), e analogamente per le altre notazioni. Occorre pero ricordare che si trattadi un abuso di notazione, poiche il simbolo = in questo caso non denota un’uguaglianza, ma l’appartenenza a un insieme.

Proprieta della notazione asintotica

Transitivaf(n) = O(g(n)) e g(n) = O(h(n)) implica f(n) = O(h(n))f(n) = Ω(g(n)) e g(n) = Ω(h(n)) implica f(n) = Ω(h(n))f(n) = Θ(g(n)) e g(n) = Θ(h(n)) implica f(n) = Θ(h(n))

Riflessiva

f(n) = O(f(n))f(n) = Ω(f(n))f(n) = Θ(f(n))

Simmetrica f(n) = Θ(g(n)) se e solo se g(n) = Θ(f(n))

Simmetrica trasposta f(n) = O(g(n)) se e solo se g(n) = Ω(f(n))

5

Comportamenti notevoli Trattabili

Θ(1) costanteΘ(log n) logaritmicoΘ(log n)k poli-logaritmicoΘ(n1/2) radice quadrataΘ(n) lineareΘ(n log n) pseudolineareΘ(n2) quadraticoΘ(n3) cubico

IntrattabiliΘ(2n) esponenzialeΘ(n!) fattorialeΘ(nn) esponenziale in base n

1.4 Complessita di algoritmi e problemiIn generale sia il numero di passi elementari che lo spazio richiesto da un algoritmo dipendono dalla dimensione n dell’input.Tuttavia, in generale non sono funzioni di n, perche, a parita di dimensione, input diversi possono richiedere un tempo di calcoloe un’occupazione di memoria molto diversi (per esempio, l’algoritmo di ordinamento insertion sort effettua Θ(n) confronti nelcaso di una sequenza ordinata, mentre in altri casi ne effettua Θ(n2)). Scrivere T (n) ed S (n) sarebbe quindi ambiguo: occorredistinguere, per ogni n, caso migliore, caso peggiore e caso medio. Formalmente, se i e un input, siano t(i) e s(i) il tempo diesecuzione e lo spazio di memoria necessario 1 per l’esecuzione dell’algoritmo per l’input i . Le seguenti funzioni risultano alloraben definite:

complessita temporale del caso peggiore Tworst(n) = maxt(i) | i ha dimensione n

complessita temporale del caso migliore Tbest(n) = mint(i) | i ha dimensione n

complessita temporale del caso medio Tavg(n) = avgt(i) | i ha dimensione n

Queste tre funzioni possono non avere forme matematiche elementari, ma hanno di solito andamenti asintotici ben definiti.Analoghe definizioni si possono dare per la complessita spaziale.Per il caso medio, per ogni n si considerano tutti i possibili input di dimensione n, siano i1, . . . iN , e si fa la media aritmetica deitempi:

Tavg(n) = t(i1)+...+t(iN )N

Tuttavia, se i possibili casi di input non sono equiprobabili, ma si presentano con probabilita p1, . . . , pN con p1 + . . .+ pN = 1,la media deve essere una media pesata:

Tavg(n) = p1 · t(i1) + . . .+ pN · t(iN )

Si noti che (anche nel caso equiprobabile) si fa la media sui diversi casi, non sui diversi tempi (analogia con media dei voti).[MANCA UNA PARTE: VEDI LUCIDI 1]

1.5 Esempi di progettazione e analisi di algoritmi ricorsiviEsempio 1.12 [Torri di Hanoi] [VEDI LUCIDI 2]

Esempio 1.13 [Ricerca binaria] [VEDI LUCIDI 2]

1.6 Teorema fondamentale delle ricorrenze[VEDI LUCIDI 2]

1In aggiunta allo spazio occupato dall’input stesso.

6

1.7 Esempi di progettazione e analisi di algoritmi iterativiEsempio 1.14 [Ricerca binaria iterativa] Sia la sequenza rappresentata con un array a con indici 0..n − 1. Idea: si confrontal’elemento da cercare con l’elemento centrale dell’array, a seconda del risultato ci si restringe a considerare solo la prima o laseconda meta, e cosı via. Idea per l’invariante: al passo generico il valore da cercare x, se presente nell’array, si trova nellaporzione di array compresa fra due indici inf e sup, formalmente:

x ∈ a[0..n− 1]⇒ x ∈ a[inf..sup]

Guidati da questa invariante:

Passo confronto con x l’elemento centrale a[mid] della porzione a[inf..sup], sono possibili tre casi:

• x < a[mid]: x, se c’e, si trova nella porzione a[inf..mid− 1], quindi sup = mid-1

• x > a[mid]: x, se c’e, si trova nella porzione a[mid + 1..sup], quindi inf = mid+1

• x = a[mid]: ho trovato x, fine!

Condizione di controllo la porzione di array su cui effettuare la ricerca non deve essere vuota, quindi inf ≤ sup

Inizializzazione inizialmente la porzione di array su cui effettuare la ricerca e l’intero array, quindi inf = 0 e sup = n− 1.

Algoritmo completo:

binary_search(x,a)inf = 0; sup = n-1 //Pre: inf = 0 ∧ sup = n− 1while (inf <= sup) //Inv: x ∈ a[0..n− 1]⇒ x ∈ a[inf..sup]

mid = (inf + sup)/2if (x < a[i]) sup = mid-1else if (x > a[i]) inf = mid+1else return true

//Post: x 6∈ a[0..n− 1]return false

Vediamo ora un altro esempio in cui il ruolo dell’invariante e ancora piu significativo.

Esempio 1.15 [Bandiera nazionale olandese] Si ha una sequenza di n elementi rossi, bianchi e blu. Vogliamo modificare lasequenza in modo da avere prima tutti gli elementi rossi, poi tutti i bianchi, poi tutti i blu. Le operazioni che possiamo effettuaresulla sequenza sono:

• swap(i,j) scambia di posto due elementi, per 1 ≤ i,j ≤ n

• colour(i) restituisce Red, White, Blue per 1 ≤ i ≤ n

Vogliamo inoltre esaminare ogni elemento una volta sola.Indichiamo con Red(i,j) il predicato “gli elementi da i a j compresi sono tutti rossi” e analogamente White(i,j), Blue(i,j).Siano inoltre U, W e B gli indici del primo elemento ignoto, bianco e blu. La postcondizione sara quindi:

Red(1,W− 1) ∧White(W,B− 1) ∧ Blue(B, n)

e l’invariante:

Red(1,U− 1) ∧White(W,B− 1) ∧ Blue(B, n) ∧ U ≤ W

(l’ultima condizione nell’invariante e aggiunta per chiarezza).Algoritmo completo:

//Pre: U = 1 ∧ W = B = n+ 1while (U < W) //Inv: Red(1,U− 1) ∧White(W,B− 1) ∧ Blue(B, n) ∧ U ≤ W

switch (Colour(W-1)case Red : swap(U, W-1); U = U + 1case White : W = W - 1case Blue : swap(W-1, B-1); W = W-1; B = B-1

//Post: Red(1,W− 1) ∧White(W,B− 1) ∧ Blue(B, n)

7

Prova di correttezza:

• Inv vale all’inizio banalmente

• Inv ∧ U ≥ W implica Post perche is ha U = W

• se vale Inv e U < W eseguendo il corpo del ciclo vale ancora Inv : si vede per casi

• come funzione di terminazione possiamo prendere W− U, infatti decresce eseguendo il corpo del ciclo in ognuno dei casi,e se vale la condizione di controllo e limitata inferiormente.

2 Algoritmi di ordinamentoProblema dell’ordinamento: data una sequenza di elementi, ordinarla rispetto a una relazione d’ordine totale definita suglielementi, per esempio rispetto a una chiave. Gli algoritmi che risolvono tale problema, cioe gli algoritmi di ordinamento, sonoclassificabili secondo diversi criteri, quali la complessita asintotica, oppure il fatto che godano o no di certe proprieta interessanti.

Stabilita Un algoritmo di ordinamento si dice stabile se non altera l’ordine relativo di oggetti distinti che siano uguali rispettoalla relazione d’ordine. Ossia, se nella sequenza da ordinare vi sono due elementi x e y uguali rispetto alla relazione d’ordine,e x si trova prima di y, anche nella sequenza ordinata x deve trovarsi prima di y. Se una sequenza di elementi gia ordinatasecondo un certo criterio viene ordinata secondo un altro criterio per mezzo di un algoritmo stabile, elementi uguali secondo ilnuovo criterio risultano ordinati secondo il precedente criterio. Per esempio, se una sequenza di persone e ordinata per nome,ordinandola per cognome con un algoritmo stabile si ottiene una sequenza in cui le persone con lo stesso cognome sono ordinateper nome. Naturalmente la stabilita non ha importanza se elementi uguali rispetto alla relazione d’ordine non sono distinguibili(per esempio una sequenza di interi).

Algoritmi sul posto Un algoritmo di ordinamento si dice sul posto (o in loco, o in place) se la memoria aggiuntiva (oltre aquella necessaria per l’input ed eventualmente per la ricorsione) utilizzata e costante, ossia se l’algoritmo riordina la sequenzasenza usare una sequenza ausiliaria o comunque uno spazio proporzionale al numero di elementi.

2.1 Algoritmi elementari2.1.1 Selection sort

Sia la sequenza rappresentata con un array a con indici 0..n− 1. Idea: si cerca il minimo dell’array e lo si mette al primo posto(mettendo il primo al posto del minimo), poi si cerca il minimo nella parte di array dal secondo elemento alla fine, e lo si metteal secondo posto, e cosı via. Invariante, assumendo che i sia il primo elemento ancora non esaminato:

• ordered(a, 0,i− 1)

• ∀h ∈ 0..i− 1, l ∈ i..n− 1.a[h] ≤ a[l] (lo abbreviamo a[0..i− 1] ≤ a[i..n− 1])

Si noti che ogni elemento della parte ordinata e al suo posto definitivo (a differenza di insertion sort, vedi dopo).

Passo Si scambia a[i] con l’elemento di valore minimo in a[i..n− 1], si ottiene:

• ordered(a, 0,i)

• a[0..i] ≤ a[i + 1..n− 1]

quindi incrementando i l’invariante vale ancora.

Condizione di uscita Non occorre controllare l’ultimo elemento, perche in base alla seconda condizione nell’invariante e gia alposto giusto, quindi i < n− 1.

Inizializzazione La parte da ordinare a[i..n− 1] e l’intero array, quindi i = 0.

Algoritmo completo con asserzioni (l’ultima condizione nell’invariante e aggiunta per chiarezza):

8

selectsort(a)i = 0 //Pre: i = 0while (i<n-1) //Inv: ordered(a, 0,i− 1) ∧ a[0..i− 1] ≤ a[i..n− 1] ∧ i ≤ n− 1swap(a,i,indexMinFrom(a, i))i++

//Post: ordered(a, 0, n− 1)

• Pre ⇒ Inv perche 0..i− 1 vuoto

• Inv ∧ i ≥ n− 1⇒ Post perche si ha i = n− 1, quindi ordered(a, 0, n− 2) ∧ a[0..n− 2] ≤ a[n− 1]

• Inv si mantiene

• terminazione: n− 1− i decresce a ogni passo e se vale la condizione di controllo e limitata inferiormente.

L’algoritmo puo ovviamente essere realizzato con un for:

for(i = 0; i<n-1; i++)swap(a,i,indexMinFrom(a, i))

Complessita temporale della procedura indexMinFrom: deve percorrere a[i..n− 1], quindi n− i passi.Complessita temporale dell’algoritmo di ordinamento: indexMinFrom viene invocata per i che varia da 0 a n− 2, il numerototale di passi e quindi:

n+ (n− 1) + (n− 2) + ...+ 3 + 2 = n(n+ 1)/2− 1 = n2 + n2 − 1

L’algoritmo e quadratico. A differenza di insertion sort (vedi dopo) non esistono un caso peggiore e un caso migliore: il numerodi passi non dipende dal modo in cui sono disposti i valori nell’array. Selection sort e quindi un algoritmo peggiore di insertionsort, che, pur essendo anch’esso in media quadratico, ha un caso migliore lineare.Complessita spaziale: l’algoritmo non usa array ausiliari, ma solo un numero fissato (e piccolo) di variabili. E pertanto unordinamento sul posto. Inoltre, essendo un algoritmo iterativo, la dimensione dello stack e costante. La complessita spaziale equindi Θ(1).Stabilita: come quasi tutti gli algoritmi di ordinamento basati su scambi, il selection sort non e stabile. Esercizio: trovare unesempio che lo mostri.

2.1.2 Insertion sort

Sia la sequenza rappresentata con un array a con indici 0..n− 1. Idea: si prende il primo elemento non ancora esaminato e lo siinserisce al posto giusto nella parte gia ordinata. Invariante, assumendo che i sia il primo elemento ancora non esaminato:

ordered(a, 0,i− 1)

Passo Inserisco a[i] al posto giusto in a[0..i− 1], si ottiene ordered(a, 0, i), quindi incrementando i l’invariante vale ancora.

Condizione di controllo i < n.

Inizializzazione Un array di un solo elemento e ordinato quindi i = 1.


insertsort(a)i = 1 //Pre: i = 1while (i < n) //Inv: ordered(a, 0,i− 1) ∧ i ≤ ninsert(a,a[i],i)//inserisce a[i] al posto giusto in a[0..i− 1]//ordered(a, 0,i)i++

//Post: ordered(a, 0, n− 1)

• Pre ⇒ Inv perche a[0..0] ordinato

• Inv ∧ i ≥ n⇒ Post perche si ha i = n

9

• Inv si mantiene

• terminazione: n− i decresce a ogni passo e se vale la condizione di controllo e limitata inferiormente.

Inserimento di x in a[0..i − 1]. Idea: confrontiamo x con gli elementi in a[0..i − 1], a partire dall’ultimo, e se e minore lispostiamo di un posto a destra finche non troviamo l’indice in cui inserire x.

j = i //Pre: j = i ∧ ordered(a, 0,i− 1)while(j > 0 && x < a[j-1])//Inv: ordered(a, 0,j− 1) ∧ ordered(a,j + 1,i) ∧ x < a[j + 1..i] ∧ j ≥ 0

a[j] = a[j-1]j--;

//Post: Inv ∧ (j = 0 ∨ x ≥ a[j− 1])a[j] = x//ordered(a, 0,i)

• Pre ⇒ Inv perche j + 1..i risulta vuoto

• Inv ∧ ¬(j > 0 ∧ x < a[j− 1]) e proprio Post

• Inv si mantiene

• terminazione: j decresce a ogni passo e se vale la condizione di controllo e limitato inferiormente.

Se si esce dal ciclo con j = 0, dopo l’assegnazione si ha a[0] < a[1..i] e ordered(a, 1,i), da cui la tesi. Se si esce dal ciclocon x ≥ a[j− 1], dopo l’assegnazione si ha a[j− 1] ≤ a[j] < a[j+ 1..i], ordered(a, 0,j− 1) e ordered(a,j+ 1,i), da cuila tesi.Complessita temporale dell’algoritmo di inserimento:

• caso migliore: valore da inserire maggiore o uguale dell’ultimo elemento della parte ordinata, un solo confronto

• caso peggiore: valore da inserire minore di tutti gli elementi della parte ordinata, i confronti

• caso medio: numero medio di confronti = (1 + ...+ i)/i = i(i + 1)/2i = (i + 1)/2

Complessita temporale dell’algoritmo di ordinamento: il ciclo viene eseguito per i che varia da 1 a n− 1

• caso migliore: array ordinato, ogni inserimento fa un solo confronto, in totale n− 1 confronti

• caso peggiore: array ordinato inversamente, numero totale di confronti 1 + 2 + 3 + ...+n− 1 = n(n− 1)/2 = n2/2− n2

• caso medio: 1/2(2 + 3 + ...+ n) = 1/2(n(n+ 1)/2− 1) = n2/4 + n/4− 1/2.

L’algoritmo e O(n2), perche e Θ(n2) nel caso peggiore, e Ω(n), perche e Θ(n) nel caso migliore, ma non e Θ(n2) ne Θ(n): perogni dimensione n vi sono sia input per cui il tempo e proporzionale a n, sia input per cui e proporzionale a n2. Complessitaspaziale: come il selection sort, e iterativo e non usa array ausiliari (algoritmo sul posto), quindi S(n) = Θ(1). Inoltre e stabile.Per esercizio: si spieghi perche.

2.2 MergesortProblema preliminare: date due sequenze ordinate, (fonderle in modo da) ottenere una sequenza degli stessi elementi ordinata.Idea: si percorrono contemporaneamente le due sequenze inserendo ogni volta in fondo alla sequenza risultato il piu piccolo deidue elementi di testa.Algoritmo con asserzioni, assumendo le due sequenze rappresentate con due array a e b con indici, rispettivamente, 0..n − 1 e0..m − 1, e la sequenza risultato rappresentata con un array c con indici 0..n + m − 1, e le asserzioni ordered(a, 0, n − 1) eordered(b, 0,m− 1) costantemente vere in quanto questi array non vengono modificati:

merge(a,b)i = 0; j = 0 \\Pre: i = 0 ∧ j = 0while (i < m && j < n)\\ Inv: c[0..i + j− 1] = merge(a[0..i− 1],b[0..j− 1]) ∧ i ≤ m ∧ j ≤ nif(a[i] <= b[j]) c[i+j] = a[i]; i++else c[i+j] = b[j]; j++

10

\\Post: Inv∧(i = m ∨ j = n)while (i < m) c[i+j] = a[i]; i++while(j < n) c[i+j] = b[j]; j++return c

• Pre ⇒ Inv vale banalmente perche 0..i− 1, 0..j− 1, e 0..i + j− 1 sono vuoti

• Inv ∧ ¬(i < m ∧ j < n) e proprio Post

• Inv si conserva, per l’invariante e il fatto che i due array sono ordinati

• terminazione: la coppia (m− i, n− j) decresce e se vale la condizione di controllo e limitata inferiormente.

Complessita dell’algoritmo di fusione: percorre interamente i due array, una volta sola, quindi Θ(n + m), assumendo che i duearray abbiano approssimativamente la stessa lunghezza Θ(n). Non vi e distinzione fra caso migliore, caso peggiore e caso medio.Variante (utilizzata da mergesort) che fonde due porzioni adiacenti di un array usando un array ausiliario (usiamo espressioni ++per compattezza):

merge(a,inf,mid,sup)\\fonde a[inf..mid] con a[mid+1..sup]aux = array con indici 0..sup− inf + 1i = inf; j = mid+1; k = 0while(i <= mid && j <= sup)

if(a[i]<= a[j]) aux[k++] = a[i++]else aux[k++] = a[j++]

while(i <= mid) aux[k++] = a[i++]while(j <= sup) aux[k++] = a[j++]for(h = 0; h < sup-inf; h++) a[inf + h] = aux[h]

La complessita spaziale e anch’essa lineare in n lunghezza dell’array. Esistono varianti dell’algoritmo le quali, attraverso mec-canismi complicati di scambi, non utilizzano un array ausiliario. Tali varianti, pero, per la loro complicazione, sono in generalepiu lente.Vediamo ora l’algoritmo mergesort.Schema astratto dell’algoritmo (di tipo divide-et-impera, mentre i due precedenti erano di tipo incrementale):

mergesort(s)if (|s|> 1)dividi s in due sequenze s1 ed s2 di lunghezza |s|/2mergesort(s1)mergesort(s2)merge(s1,s2,s)//fonde ordinatamente s1 ed s2 in s

Correttezza: si prova per induzione aritmetica completa sulla lunghezza di s.

Base Una sequenza di lunghezza zero o uno e ordinata, e infatti l’algoritmo non fa nulla.

Passo induttivo Poiche n2 < n, dopo l’esecuzione di mergesort(s1); mergesort(s2) per ipotesi induttiva si ha che s1

e s2 sono ordinate. Quindi, in base alla specifica di merge, la sequenza che si ottiene alla fine e ordinata e ha gli stessielementi della lista di partenza.

Complessita temporale: si ha la seguente relazione di ricorrenza (la fusione ha costo lineare, la divisione ha costo costante perun array e lineare per una lista)T (1) = 1T (n) = 2T (n2 ) + n per n > 1

Possiamo trovare la soluzione (assumendo per semplicita n = 2k) espandendo l’albero di ricorsione (si hanno k+1 livelli ognunodi costo n), o per sostituzioni successive:T (n) = 2T (n2 ) + n

= 2(2T (n22) + n

2 ) + n = 22T (n22) + 2n

= 22(2T (n23) + n

22) + 2n = 23T (n2

3) + 3n

= ... = 2k(T (n2k)) + kn = n(k + 1) = n(log n+ 1)

Possiamo a questo punto verificare per induzione aritmetica:

11

Base T (20) = 1(0 + 1)

Passo induttivo T (2k) = 2T (2k−1) + 2k = (per ip. ind.) 2 · 2k−1 · k + 2k = 2k · k + 2k = 2k(k + 1)

La soluzione poteva anche essere trovata direttamente applicando il teorema master. Poiche l’algoritmo di merge ha complessitaΘ(n) in ogni caso, anche per il mergesort non c’e distinzione fra caso peggiore, migliore e medio, ma si ha sempre T (n) =Θ(n log n).Complessita spaziale: lo spazio di memoria necessario per la ricorsione e la massima profondita dello stack = altezza dell’alberodi ricorsione, quindi Θ(log n). L’algoritmo di fusione fa uso di una sequenza ausiliaria per ogni chiamata, che puo poi essererimossa, quindi richiede uno spazio Θ(n). La complessita spaziale e percio S (n) = Θ(log n)+Θ(n) = Θ(n). E anche possibiledare una versione “ecologica” che usa un’unica sequenza ausiliaria che viene passata come argomento aggiuntivo (vedi sotto).Stabilita: l’algoritmo e stabile se la fusione e realizzata in modo che quando nelle due sequenze si trovano due elementi ugualirispetto alla relazione d’ordine, venga inserito per primo l’elemento della prima sequenza (quindi e fondamentale il ≤ nel test).Diamo ora una versione concreta in cui la sequenza e rappresentata con un array con indici 0..n−1 ed utilizziamo l’ottimizzazionedetta sopra:

mergesort(a) =aux = array con indici 0..n− 1mergesort(a,0,n-1,aux)

mergesort(a,inf,sup,aux)if (inf<sup)

mid = (inf+sup)/2mergesort(a,inf,mid,aux)mergesort(a,mid+1,sup,aux)merge(a,inf,mid,sup,aux)//fonde a[inf..mid] con a[mid+1..sup] usando aux

merge(a,inf,mid,sup,aux)//fonde a[inf..mid] con a[mid+1..sup] usando auxi = inf; j = mid+1; k = infwhile(i <= mid && j <= sup)

if(a[i] <= a[j]) aux[k++] = a[i++]else aux[k++] = a[j++]

while(i <= mid) aux[k++] = a[i++]while(j <= sup) aux[k++] = a[j++]for (h = inf; h <= sup; h++) a[h] = aux[h]

Ottimizzazione ulteriore: si puo evitare di copiare la parte non esaurita di array in aux per poi ricopiarla in a nel modo seguente:

• se la parte non esaurita e la seconda, questa e gia al suo posto, quindi non deve essere ricopiata

• se la parte non esaurita e la prima, la si sposta direttamente al posto giusto in a, partendo dal fondo (perche?). L’algoritmodi fusione diventa quindi:

merge(a,inf,mid,sup,aux)i = inf; j = mid+1; k = infwhile(i <= mid && j <= sup)

if(a[i]<= a[j]) aux[k++] = a[i++]else aux[k++] = a[j++]

for (h = mid, l = sup; h >= i;) a[l--] = a[h--]// while(j <= sup) aux[k++] = a[j++]

for (h = inf; h < k; h++) a[h] = aux[h]

Per esempio, se a = [20 30 40 | 10], dopo il primo ciclo avro aux = [10 ], e poi:a = [ 40] copio da a stessoa = [ 30 40] copio da a stessoa = [ 20 30 40] copio da a stessoa = [10 20 30 40] copio da aux

Versione “a passi alterni”: si puo evitare di ricopiare ogni volta l’array ausiliario nell’array da ordinare, scambiando a ogni livellodi ricorsione i ruoli dei due array.

12

merge(a,inf,mid,sup,b)i = inf; j = mid+1; k = infwhile(i <= mid && j <= sup)

if(a[i]<= a[j]) b[k++] = a[i++]else b[k++] = a[j++]

while(i <= mid) b[k++] = a[i++]while(j <= sup) b[k++] = a[j++]//for(h = inf; h < sup-inf; h++) a[inf + h] = aux[h]

//Post: b[inf..sup] = merge(a[inf..mid],a[mid + 1..sup])

mergesort(a,inf,sup,b) //Pre: a[inf..sup] = b[inf..sup]if(inf<sup)

mid = (inf+sup)/2mergesort(b,inf,mid,a)mergesort(b,mid+1,sup,a)merge(b,inf,mid,sup,a)

//Post: ordered(a,inf,sup)

mergesort(a)//top-levelaux = copia di amergesort(a,0,n-1,aux)

Prova di correttezza:

Base inf ≤ sup: ok

Passo Induttivo Si ha inf < sup. Dato che la lunghezza mid−inf e minore di sup−inf, e la precondizione b[inf..mid] =a[inf..mid] e verificata, la chiamata ricorsiva mergesort(b,inf,mid,a) ordina b[inf..mid], e analogamentemergesort(b,mid+1,sup,a) ordina b[mid+1..sup].

A questo punto merge(b,inf,mid,sup,a) produce una copia ordinata di b[inf..sup] in a[inf..sup]. Quindi,mergesort(a,inf,sup,b) ordina a[inf..sup].

Nota: questa versione del mergesort e in sostanza quella che si trova nella libreria di Java (nella classe Arrays).Gli elementi che alla fine si trovano in a provengono da a oppure da b a seconda del numero pari o dispari di livelli di ricorsione,anzi sono un misto se la lunghezza dell’array non e una potenza di due. Esempio:

a = [60a 50a 40a], b = [60b 50b 40b]

mergesort(a,0,2,b):mergesort(b,0,0,a) non fa nullamergesort(b,1,2,a):

mergesort(a,1,1,b) non fa nullamergesort(a,2,2,b) non fa nullamerge(a,1,2,b) ordina a[1..2] in b[1..2]

a = [60a 50a 40a], b = [60b 40a 50a]

merge(b,0,2,a)ordina b[0..2] in a[0..2]

a = [40a 50a 60b], b = [60b 40a 50a]

Un’altra (importante) ottimizzazione: se quando si deve effettuare la fusione l’ultimo elemento del segmento sinistro e minoreo uguale al primo elemento del segmento di destra, la sequenza dei due segmenti e gia un segmento ordinato e quindi la fusionenon e necessaria. Esercizio: con tale ottimizzazione la complessita asintotica in qualche caso cambia? Si considerino le diverseversioni viste sopra.

2.3 QuicksortE l’algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronti. E stato ideato da CharlesAntony Richard Hoare nel 1961. E molto popolare dato che e facilmente implementabile, ha un buon comportamento in un’ampia

13

varieta di situazioni, e sul posto. Gli svantaggi sono dati dal fatto che non e stabile, nel caso peggiore ha un comportamentoquadratico ed e fragile, nel senso che un errore nella sua implementazione puo passare inosservato ma causare in certe situazioniun drastico peggioramento nelle prestazioni. E stato sottoposto a un’analisi matematica approfondita ed estremamente precisa,i risultati ottenuti in fase di analisi sono stati verificati sperimentalmente in modo esteso e l’algoritmo di base e stato miglioratoal punto da diventare il metodo ideale per un gran numero di applicazioni pratiche. Praticamente dal momento in cui Hoarepubblico per la prima volta il suo lavoro, sono state provate e analizzate molte varianti, ma spesso un miglioramento in un sensoporta a un peggioramento delle prestazioni in qualche altro punto.Schema astratto dell’algoritmo, anch’esso di tipo divide-et-impera:

quicksort(s)if (|s| > 1)

togli un elemento p da s (per esempio il primo)partiziona gli altri elementi di s in due parti:una sequenza s1 contenente tutti gli elementi < puna sequenza s2 contenente tutti gli elementi ≥ pforma la sequenza s1 p s2

quicksort(s1)quicksort(s2)

L’elemento p e detto pivot o perno della partizione. E facile provare la correttezza dell’algoritmo per induzione aritmeticacompleta sulla lunghezza n della sequenza s:

Base Una sequenza di lunghezza zero o uno e ordinata, e infatti l’algoritmo non fa nulla.

Passo Dopo la partizione si ha:

elementi di s1 < p ≤ elementi di s2

Per ipotesi induttiva, l’algoritmo ordina correttamente sequenze di lunghezza < n. Le sequenze s1 ed s2 hanno certamentelunghezza < n perche e stato tolto p, quindi dopo le due chiamate ricorsive s1 ed s2 sono ordinate; allora la sequenzas1 p s2 e chiaramente ordinata.

Variante:

quicksort(s)if (|s| > 1)

scegli un elemento p di s (per esempio il primo)partiziona gli elementi di s in due parti:

una sequenza s1 contenente elementi ≤ puna sequenza s2 contenente elementi ≥ p

forma la sequenza s1 s2

quicksort(s1)quicksort(s2)

In questa variante, il pivot non viene tolto, quindi il procedimento con cui si effettua la partizione deve garantire che s1 ed s2risultino sempre non vuote, quindi entrambe di lunghezza minore della lunghezza di s.Complessita temporale: assumiamo di poter effettuare la partizione in tempo lineare e senza usare strutture ausiliarie (vedremopoi alcuni algoritmi concreti). Il tempo T (n) necessario per ordinare una sequenza di lunghezza n e quindi (per esempio per laseconda versione):

T (1) = Θ(1)T (n) = Θ(n) + T (r) + T (n− r) per n > 1

dove Θ(n) e il tempo necessario per effettuare la partizione, T (r) il tempo necessario per ordinare s1 di lunghezza r, T (n− r)il tempo necessario per ordinare s2 di lunghezza n− r, ed r > 0 e diverso per ogni chiamata ricorsiva.Nota: nel quicksort tutto il lavoro dell’algoritmo viene effettuato dal partizionamento, cosı come nel mergesort veniva effettuatodalla fusione.Il caso migliore si avra quando, a ogni chiamata ricorsiva, le due parti s1 ed s2 risultano di uguale lunghezza (partizione semprebilanciata). In questo caso avremo

T (1) = Θ(1)T (n) = Θ(n) + T (n2 ) + T (n2 ), per n > 1.

14

Questa relazione di ricorrenza e la stessa del mergesort e, come abbiamo visto, ha soluzione T (n) = Θ(n log n).Il caso peggiore si avra quando, a ogni chiamata ricorsiva, le due parti s1 ed s2 risultano una di lunghezza 1 e l’altra di lunghezzan− 1 (partizione sempre sbilanciata al massimo). In questo caso avremo:

T (1) = Θ(1)T (n) = Θ(n) + T (n− 1) per n > 1.

che ha soluzione T (n) = Θ(n2), infatti assumendo per semplicita T (1) = 1,T (n) = n+ T (n− 1) ed espandendo si ha

T (n) = n+ (n− 1) + ...+ 1 = n(n+ 1)/2

come si puo verificare facilmente per induzione aritmetica.Si puo provare (vedi nel seguito) che si ha anche

Tavg(n) = Θ(n log n)

Complessita in spazio: il quicksort opera la partizione sul posto, cioe senza bisogno di un array ausiliario. Tuttavia, essendo unalgoritmo ricorsivo, ha bisogno dello spazio per lo stack. L’altezza dell’albero di ricorsione e la massima profondita di chiamatericorsive annidate, quindi:

Sbest(n) = Θ(log n)Sworst(n) = Θ(n)Savg(n) = Θ(log n)

Partizionamento: prima versione “semplice” (ignoti in fondo) In questa variante si segue il primo schema ricorsivo. Sea[inf..sup] e la porzione di array da ordinare, si sceglie il pivot p, per esempio a[inf], e il resto dell’array viene partizionatoin due parti: a[inf+ 1..i] gli elementi minori di p, a[i+ 1..sup] gli elementi maggiori o uguali a p. Si scambia quindi a[inf]con a[i] e si ordinano ricorsivamente a[inf..i− 1] e a[i + 1..sup].L’array risulta in ogni momento intermedio diviso in tre parti, la prima formata da elementi minori del pivot, la seconda daelementi maggiori o uguali, la terza da elementi non ancora esaminati, come indicato in figura:

< >= unknownjiinf+1inf sup

Usiamo l’indice i per l’ultimo degli elementi minori del pivot, l’indice j per il primo degli “ignoti”.

Passo Si considera il primo elemento ignoto, se questo e minore del pivot lo si scambia con l’elemento di posto i + 1 e siincrementano i e j, altrimenti basta incrementare j.

Condizione di controllo Finche ci sono elementi ignoti, quindi j ≤ sup.

Inizializzazione Tutti gli elementi sono ignoti, quindi i = inf e j = inf + 1.


i = inf; j = inf+1 //Pre: i = inf ∧ j = inf + 1while (j <= sup) //Inv: a[inf + 1..i] < p ∧ a[i + 1..j− 1] ≥ p ∧ j ≤ sup + 1

if (a[j] < p) i++; swap(a,i,j)j++

//Post: a[inf + 1..i] sup⇒ Post ovviamente perche si ha j = sup + 1

• terminazione: sup− j decresce e se vale la condizione di controllo e limitata inferiormente.

Inserimento del pivot: deve essere scambiato con a[i], e poi si ordinano ricorsivamente a[inf..i − 1] e a[i + 1..sup]. Piusinteticamente con un ciclo for:

15

i = inffor(j = inf+1; j <= sup; j++)

if (a[j] < p) i++; swap(a,i,j)swap(a,inf,i)

Cosa succede in questa versione se l’array e ordinato: il pivot p e inizialmente il minimo, quindi alla fine della partizione la partesinistra risulta vuota e la parte destra ha lunghezza n − 1. Inoltre la condizione a[j] < p e sempre falsa, quindi non si effettuanessuno scambio. Di conseguenza, dato che la parte destra non viene modificata, il suo primo elemento e di nuovo il minimo, ecosı via. E evidentemente un caso peggiore: ad ogni partizione si ha sempre il massimo sbilanciamento fra le due parti: quindi,si ha complessita temporale quadratica e complessita spaziale lineare.

Partizionamento: seconda versione “semplice” (ignoti al centro) Anche in questa variante si segue il primo schema ricorsivoma, come nel problema della bandiera olandese, si tengono gli elementi non esaminati al centro. Quindi, dopo aver tolto il pivota[inf], l’array risulta in ogni momento intermedio diviso in tre parti, la prima formata da elementi minori del pivot, la secondada elementi non ancora esaminati, la terza da elementi elementi maggiori o uguali del pivot, come indicato in figura:

< >=unknownjiinf+1inf sup

Usiamo l’indice i per il primo degli “ignoti”, l’indice j per l’ultimo.

Passo Si considera il primo elemento ignoto, se questo e minore del pivot basta incrementare i, altrimenti lo si scambia conl’ultimo e si decrementa j.

Condizione di controllo Finche ci sono elementi ignoti, quindi i ≤ j.

Inizializzazione Tutti gli elementi sono ignoti, quindi i = inf + 1 e j = sup.


i = inf+1; j = sup //Pre: i = inf + 1 ∧ j = supwhile (i <= j) //Inv: a[inf + 1..i− 1] < p ∧ a[j + 1..sup] ≥ p ∧ i ≤ j + 1

if (a[i] < p) i++else swap(a,i,j); j--

//Post: a[inf + 1..i− 1] j⇒ Post ovviamente perche si ha i = j + 1

• terminazione: j− i decresce e se vale la condizione di controllo e limitata inferiormente.

Inserimento del pivot: deve essere scambiato con a[j = i− 1], e poi si ordinano ricorsivamente a[inf..j− 1] e a[j+ 1..sup].Il caso dell’array ordinato e ancora un caso peggiore? Come nella prima versione il pivot e inizialmente il minimo, e alla fine dellapartizione la parte sinistra e vuota e la destra ha lunghezza n− 1. Tuttavia, in questo caso la condizione a[i] < p risulta semprefalsa, e quindi si operano sempre degli scambi. La parte destra risulta modificata, e il primo elemento non e piu il minimo, ma ilsecondo piu piccolo. La partizione della parte destra risultera quindi lievemente meno sbilanciata e, via via che si scende nellaricorsione, lo sbilanciamento diminuisce. Il caso dell’array ordinato non e piu un caso peggiore, il tempo di calcolo e espressoda una relazione di ricorrenza complessa ed e comunque superiore a quello per un array con elementi in “ordine casuale”.Vediamo un esempio:

[10 20 30 40 50] pivot 10[ |20 30 40 50| ] 20 ≥ 10, scambio e decremento j[ |50 30 40|20] 50 ≥ 10, scambio e decremento j[ |40 30|50 20] 40 ≥ 10, scambio e decremento j[ |30|40 50 20] 30 ≥ 10, scambio e decremento j[ | |30 40 50 20] inserisco il pivot[ |10|30 40 50 20]

16

Osservazione: in entrambe le versioni viste finora, gli elementi possono essere spostati due volte. Per esempio, nella versionecon gli ignoti in mezzo, se a[i] e a[j] sono ≥ p, l’elemento di posto j viene prima scambiato con quello di posto i, e poi alpasso successivo riportato a destra. In altri termini, l’algoritmo mette al posto giusto solo un elemento alla volta, eventualmentespostandone un altro dalla parte sbagliata.Altra osservazione: in entrambe le versioni viste finora, se nel partizionamento vi sono molti elementi uguali al pivot (anchese scelto a caso) essi finiscono tutti da una stessa parte, producendo cosı uno sbilanciamento. Un array di elementi tutti uguali,o quasi tutti uguali, costituisce quindi un caso peggiore, di complessita quadratica, anche con pivot scelto a caso. La versioneoriginale di Hoare (vedi dopo) e la tripartizione (ossia un algoritmo di partizionamento in cui si distinguono elementi minori,uguali e maggiori) evitano questo problema. Nel caso della tripartizione, su un array di elementi tutti uguali non viene effettuatanessuna chiamata ricorsiva, quindi questo costituisce un caso migliore molto particolare di complessita temporale lineare espaziale costante. Svantaggi della tripartizione: il test e piu complesso e quindi piu dispendioso in tempo; tenere gli elementiuguali al pivot in mezzo costringe a effettuare uno scambio per ogni elemento diverso dal pivot, e questo si presume sia il casopiu frequente. Un rimedio al difetto precedente puo essere ottenuto posizionando la parte degli uguali al pivot a sinistra o adestra invece che in mezzo, spostandola poi in mezzo solo alla fine del partizionamento, e combinando la tripartizione con alcuniaspetti della versione alla Hoare, come nella versione di Bentley-McIllRoy (vedi dopo).

Partizionamento: versione [simile a] originale di Hoare In questa variante si segue il secondo schema ricorsivo, quindi glielementi uguali al pivot possono stare da entrambe le parti, e si deve garantire che alla fine le due parti su cui si effettuanole chiamate ricorsive siano non vuote. La parte da esaminare e in mezzo, e si effettua uno scambio solo quando entrambi glielementi dopo lo scambio saranno in posizione giusta. Nessun elemento viene quindi scambiato piu di una volta. Gli elementiuguali al pivot vengono sempre scambiati. Usiamo l’indice i per il primo degli “ignoti”, l’indice j per l’ultimo.

≤ ≥unknownjiinf sup

Invariante: a[inf..i− 1] ≤ p ∧ a[j + 1..sup] ≥ p.

Condizione di controllo i ≤ j

Inizializzazione i = inf, j = sup

Passo Si incrementa i fino a trovare un elemento ≥ p, poi si decrementa j fino a trovare un elemento ≤ p. A questo punto sihanno tre casi possibili:

• i < j: occorre scambiare i e j, e poi incrementare i e decrementare j

• i = j: (quindi a[i] = p) scambiare i e j e inutile ma non dannoso, e poi occorre spostare gli indici per terminare ilciclo

• i = j + 1: scambiare i e j sarebbe errato.

Per semplificare possiamo ridurci a due casi: si fa lo scambio e si spostano i e j a meno che gli indici non siano“incrociati”.

Algoritmo di partizionamento completo con asserzioni:

i = inf; j = sup //Pre: i = inf ∧ j = supwhile(i <= j) //Inv: a[inf..i− 1] ≤ p ∧ a[j + 1..sup] ≥ p ∧ ((i = inf ∧ j = sup) ∨ (inf p) j-- //a[j] ≤ pif(i <= j)

swap(a,i,j)i++; j--

//Post: a[inf..i− 1] ≤ p ∧ a[j + 1..sup] ≥ p ∧ inf < i ∧ j < sup// ∧((i = j + 1) ∨ (i = j + 2 ∧ a[i− 1] = p))

Correttezza: anzitutto, i due cicli interni terminano senza uscire dai limiti dell’array. Infatti, nella prima iterazione gli indici sifermano alla peggio sul pivot, perche il segmento a[i..sup], essendo a[inf..sup], contiene sicuramente il pivot, e analogamentea[inf..j]. Si effettua quindi un primo scambio (alla peggio del pivot con se stesso) e si spostano gli indici, quindi dopo la prima

17

iterazione si ha sicuramente inf < i e j < sup, ossia le due porzioni a[inf..i − 1] e a[j + 1..sup] sono sicuramente nonvuote (eventualmente con intersezione non vuota). Quindi, a[j + 1] funge da guardia per i e viceversa.L’uscita dal ciclo puo avvenire in tre modi:

• alla fine dei due cicli interni ho i < j, effettuo lo scambio e incrementando gli indici ho i = j + 1

• alla fine dei due cicli interni ho i = j (quindi a[i] = p), effettuo lo scambio e incrementando gli indici ho i = j + 2

• alla fine dei due cicli interni ho i = j + 1, non faccio nulla.

Quindi i = j + 1 oppure i = j + 2. In entrambi i casi richiamo ricorsivamente su a[inf..j] e a[i..sup], e so che le dueporzioni non sono vuote. Infatti:

• nel primo caso richiamo su a[inf..i− 1] e a[j + 1..sup] che so essere non vuote (da dopo la prima iterazione)

• nel secondo caso richiamo su a[inf..i− 2] e a[i..sup], entrambe di lunghezza minore di quella della sequenza inizialeperche ho escluso l’elemento a[i− 1] = p.

Algoritmo completo (usiamo un ciclo do-while in quanto si effettua almeno un’iterazione):

quicksort(a,inf,sup)if (inf < sup)

p = a[inf]; i = inf; j = supdo

while (a[i] < p) i++while (a[j] > p) j--if (i <= j) swap(a,i,j); i++; j--

while(i <= j)quicksort(a,inf,j)quicksort(a,i,sup)

Come si vede, il corretto funzionamento di questa versione, che minimizza il numero di spostamenti e di confronti inutili, dipendeda dettagli abbastanza sottili.

Partizionamento: versione di Bentley-McIlroy (1993) Adottata dalla Sun nelle API di Java. Combina vantaggi della versioneoriginale di Hoare (ogni elemento e spostato al piu una volta) e della tripartizione (efficienza in caso di elementi ripetuti).L’array e diviso in cinque porzioni:

<= =>unknownjih kinf sup

Invariante: a[inf..h− 1] = p ∧ a[h..i− 1] p ∧ a[k + 1.. sup] = p.

Passo

• a[i] = p: swap(a,i,h); h++; i++

• a[i] < p: i++

• a[j] = p: swap(a,j,k); k--; j--

• a[j] > p: j--

• else: swap(a,i,j); i++; j--

Il ramo else (quindi la sequenza i++; j--) viene eseguito nel caso a[i] > p ∧ a[j] < p, quindi non puo essere i = j, ma siha i < j. Quindi nell’invariante si ha i ≤ j + 1, quindi in uscita i = j + 1.

<= =>j ih kinf sup

Bisogna ancora spostare le due porzioni di elementi uguali al pivot al centro, si procede nel modo seguente:

18

• se la parte “uguali di destra” e piu corta di quella dei minori, si scambiano gli “uguali” con una parte dei minori

=>

= >

• se la parte “uguali di destra” e piu lunga di quella dei minori, si scambiano i minori con una parte degli uguali

=>

= >

• analogamente a sinistra.

Per esercizio: scrivere il codice completo di quicksort in questo caso e la prova di correttezza per il ciclo.

Analisi rigorosa del caso medio Assumiamo che per ogni lunghezza n tutte le possibili coppie di lunghezze delle due partisiano ugualmente probabili. E piu semplice considerare la prima versione, in cui il pivot viene tolto, e quindi le possibili coppiedi lunghezze sono:

(0, n− 1), (1, n− 2) , (2, n− 3), . . . , (k, n− 1− k), . . . , (n− 1, 0)

Si ha quindi

T (n) = n+ 1n (T (0) + T (n− 1) + T (1) + T (n− 2) + . . .+ T (n− 1) + T (0))

= n+ 2n

n−1∑i=0

T (i)

Per ottenere T (n) in funzione di T (n−1), espandiamo analogamente T (n−1), e otteniamo T (n−1) = n−1+ 2n−1

n−2∑i=0

T (i),

quindin−2∑i=0

T (i) = n−12 (T (n− 1)− n+ 1)

e sostituendo nell’espressione di partenza:

T (n) = n+ 2n (n−12 (T (n− 1)− n+ 1) + T (n− 1))

Semplificando si ottiene

T (n) = n+1n T (n− 1) + 2n−1

n

che e una relazione di ricorrenza di forma usuale. Per risolverla, maggioriamo in questo modo:

T (n) ≤ n+1n T (n− 1) + 2(n+1)

n

e poi usiamo il metodo delle sostituzioni successive:

T (n) ≤ n+1n ( n

n−1T (n− 2) + 2nn−1 ) + 2(n+1)

n

T (n) ≤ n+1n−1T (n− 2) + 2(n+1)

n−1 + 2(n+1)n

. . .T (n) ≤ n+1

n−1T (n− (n− 1)) + 2(n+1)2 . . .+ 2(n+1)

n−1 + 2(n+1)n (assumendo per semplicita T (1) = 0)

T (n) ≤ 2(n+ 1)n∑i=2

1i

Questa sommatoria e la somma armonica che si prova essere Θ(log n). Si puo infatti osservare che12 + 1

3 + 122 + 1

5 + 16 + 1

7 . . .+123 + . . . ≤ 1 + 1

2 + 12 + 1

22 + 122 + 1

22 + 122 + . . . = log n

19

Randomizzazione Il caso peggiore si verifica quando, a ogni chiamata ricorsiva, gli elementi della porzione di array consideratasono o tutti minori o tutti maggiori/uguali del pivot. Un buon modo per evitare questo consiste nello scegliere ogni volta il pivota caso. Si scambia poi l’elemento-pivot con il primo in modo da riportarsi alla situazione vista precedentemente. In questo modonessuna particolare istanza di input si comporta da caso peggiore. Un utilizzatore “maligno” puo produrre un caso peggiore soloconoscendo l’algoritmo usato per la generazione dei numeri pseudo-casuali.Un’altra tecnica e basata sull’osservazione che la partizione e perfettamente bilanciata se il pivot e la mediana (valore apparte-nente all’insieme tale che meta degli elementi dell’insieme sono minori o uguali, e l’altra meta sono maggiori o uguali).2 Nonconoscendo la mediana, si puo scegliere come pivot il mediano di un certo numero di elementi, per esempio il mediano di primo,ultimo, ed elemento centrale, o di nove elementi presi ad intervalli regolari. In questo modo il caso peggiore non e piu l’arrayordinato, ma e comunque una fissata configurazione dell’array. Si possono anche combinare i due meccanismi, ossia scegliere ilmediano di un certo numero di elementi di cui alcuni scelti a caso.

Uso di algoritmi elementari Il quicksort e asintoticamente molto piu efficiente di algoritmi di ordinamento quadratici comel’insertion sort, tuttavia la sequenza di operazioni che esso esegue per ciascun elemento dell’array e piu complessa e quindi piudispendiosa in tempo, quindi per piccoli valori di n (alcune decine) un algoritmo quadratico ma semplice, come l’insertion sort,e piu efficiente di quicksort. Si possono quindi confrontare sperimentalmente i tempi di calcolo di quicksort e insertion sort perdeterminare in modo approssimato il valore di n0, e quando la lunghezza della porzione da ordinare e inferiore a n0 eseguiredirettamente insertion sort.

2.4 HeapsortIdea: si parte dal selection sort (ordinamento per estrazione successiva del minimo), quadratico, ma, invece di cercare ogni voltail minimo, si inseriscono tutti gli elementi in una coda a priorita. Si operano quindi delle estrazioni successive del minimo. Se lacoda a priorita e realizzata tramite heap, vedi sezione 3.1, l’estrazione del minimo costa O(log n) anziche O(n), e quindi il ciclodi n estrazioni costa O(n log n) invece di O(n2). Analogamente per il ciclo di inserimento nella coda.Sia la sequenza rappresentata con un array a con indici 0..n− 1. Prima versione dell’algoritmo (non sul posto):

heapsort(a)Q = heap di lunghezza nfor (i = 0; i < n; i++) Q.insert(a[i])for (i = 0; i < n; i++) a[i] = Q.getMin()

Versione sul posto: possiamo osservare che ogni elemento si trova sempre o nell’array o nello heap, quindi e possibile utilizzarel’array stesso come heap, nel modo seguente.

Prima fase Si costruisce lo heap nella porzione iniziale dell’array da ordinare.

heap parte ancora da esaminare

i

A ogni iterazione, la porzione a[0..i− 1] (inizialmente il solo elemento a[0]) e uno heap, l’elemento di posto i e gia nellaposizione di ultima foglia, basta quindi farlo risalire, rendendo cosı uno heap la porzione a[0..i]. Alla fine della prima fasetutto l’array e uno heap.

Seconda fase Si sostituisce la porzione finale dello heap con un array ordinato.

heap ancora da svuotare parte già ordinata

i

A ogni iterazione, la porzione a[0..i] (inizialmente tutto l’array) e uno heap. Si scambia l’ultima foglia (elemento diposto i) con la radice, che quindi viene aggiunta a sinistra della porzione ordinata dell’array. Poi si fa scendere la radice,rendendo cosı nuovamente uno heap la porzione a[0..i− 1]. Alla fine lo heap e vuoto e l’array ordinato.

Attenzione: per ottenere l’ordine giusto e non quello inverso nella seconda fase, occorre utilizzare nella prima fase uno heap amassimo anziche a minimo.In questo modo l’algoritmo e sul posto, ha complessita temporale O(n log n) ottimale in ogni caso come mergesort (non uncaso peggiore quadratico come quicksort) e inoltre, a differenza di mergesort e quicksort, e un algoritmo iterativo, quindi con

2La mediana e spesso una nozione statistica piu significativa della media, per esempio considerando 11 persone, di cui 5 guadagnano al mese 2000 euro, 5guadagnano 3000 euro, e uno guadagna 100000 euro, la media e circa 11364, la mediana 3000.

20

complessita spaziale (in ogni caso) Θ(1). Lo heapsort e quindi, dal punto di vista asintotico, l’algoritmo di ordinamento migliorefra quelli esaminati. Tuttavia nella maggior parte delle situazioni l’algoritmo di ordinamento piu veloce risulta essere quicksort.Nella versione in place di heapsort, se si ordina un array con indici 0..n − 1, lo heap partira dall’indice 0 invece che dall’indice1, quindi i figli del nodo i saranno 2i+ 1 e 2i+ 2, e il genitore (i− 1)/2. Inoltre, dato che lo heap e a massimo, nella moveUp(qui chiamata addToHeap) e nella moveDown i test sono invertiti rispetto alla versione data nella sezione 3.1. Si ha quindi ilcodice seguente, dove scriviamo heap(a, 0, i) per “la porzione di array a[0..i] e uno heap (a massimo)”.

heapsort(a) //a con indici 0..n− 1for (i = 1;i < n;i++) addToHeap(a,i) //Inv: heap(a, 0,i− 1)for (i = n - 1; i > 0;i--) getMax(a,i)//Inv: heap(a, 0,i) ∧ ordered(a,i + 1, n− 1) ∧ a[0..i] ≤ a[i + 1]

addToHeap(a,i) //Pre: heap(a, 0,i− 1)elem = a[i] //elemento da far salirewhile (i > 0 && elem > a[(i-1)/2]) //Inv: i posto vuoto

a[i] = a[(i-1)/2] //scende il genitorei = (i-1)/2 //sale il posto vuoto

a[i] = elem//Post: heap(a, 0,i)

getMax(a,i) //Pre: heap(a, 0,i)swap(a,0,i) //scambia massimo con ultima fogliamoveDown(a,0,i-1)

//Post:heap(a, 0,i− 1) ∧ a[0..i− 1] ≤ a[i]

moveDown(a,k,i)elem = a[k] //elemento da far scenderej = 2*k+1 //j figlio sinistrowhile (j a[j]) //Inv: i posto vuoto

if (j+1 < i && a[j+1] < a[j]) j++ //j figlio destroa[k] = a[j] //sale il figliok = j //scende il posto vuoto

a[k] = elem//Post: heap(a,k,i)//invocata anche con k 6= 0 nella versione ottimizzata

Ottimizzazione: l’array puo essere trasformato in uno heap, invece che con n inserimenti successivi, con tempo totale Θ(n log n),applicando ripetutamente moveDown ai nodi a partire dal basso. Cio richiede solo un tempo Θ(n) (vedi sotto).Infatti:

• un albero costituito solo da una foglia e uno heap

• un albero quasi completo i cui sottoalberi sinistro e destro sono degli heap diventa uno heap se si applica moveDown allasua radice.

Corrispondente algoritmo ricorsivo:

heapify(a) //a con indici 0..n− 1heapify(a,0)

heapify(a,i) //a con indici 0..n− 1j = 2*i+1 //figlio sinistroif(j < n) //i ha almeno un figlio

heapify(a,j)heapify(a,j+1)moveDown(a,i,n-1)

//Post: heap(a,i, n− 1)

Nota: non occorre gestire a parte il caso in cui esista solo il figlio sinistro, perche l’algoritmo invocato su un figlio destroinesistente non fa nulla, come nel caso di una foglia.

21

Con l’utilizzo dell’algoritmo heapify la complessita asintotica non cambia, perche il ciclo di estrazioni successive del massimorimane Θ(n log n), tuttavia si ha un miglioramento rispetto a 2n log n. Trattandosi di un algoritmo ricorsivo cresce ovviamentela complessita in spazio, e facile tuttavia dare un algoritmo iterativo equivalente, che cioe esegue esattamente la stessa sequenzadi chiamate di moveDown:

heapify(a) //a con indici 0..n− 1for (j = (n-2)/2; j >= 0; j--)

moveDown(a,j,n-1);

Si noti che (n− 2)/2, essendo il genitore dell’ultima foglia, e l’ultimo nodo interno.Versione finale compatta di heapsort:

heapsort(a)for (j =(n-2)/2; j >= 0; j--) moveDown(a,j,n)for(i = n-1; i > 0; i--)

swap(a,0,i)moveDown(a,0,i)

Calcolo della complessita di heapify: se h e l’altezza dell’albero heap, 2h e il numero delle foglie e 2h+1− 1 = n e il numerodei nodi, quindi, considerando la versione ricorsiva, otteniamo la seguente relazione di ricorrenza:

T (20+1 − 1) = 0T (2h+1 − 1) = h+ 2T (2h − 1) (infatti 2h+1 − 1− 1 = 2h+1 − 2 = 2(2h − 1) )= h+ 2(h− 1 + 2T (2h−1 − 1))= 20h+ 21(h− 1) + 22(h− 2 + 2T (2h−2 − 1))= . . .= 20h+ 21(h− 1) + . . .+ 2h−11 + 2hT (2h−(h−1) − 1)= 2h−1 + 2h−22 + . . .+ 21(h− 1) + 20h

Possiamo giungere alla stessa conclusione dalla versione iterativa, osservando che il tempo di esecuzione e proporzionale (nelcaso peggiore) alla somma delle altezze dei sottoalberi non foglie, che sono: uno di altezza h, due di altezza h − 1, . . . , 2h − 1di altezza uno.Per calcolare questa sommatoria la scriviamo su h righe nel modo seguente:

2h−1+ 2h−2+ . . . + 2+ 1 = 2h − 12h−2+ . . . + 2+ 1 = 2h−1 − 1

. . . = . . .2+ 1 = 22 − 1

1 = 21 − 1

Quindi si ha 2h − 1 + 2h−1 − 1 + . . . + 22 − 1 + 21 − 1 + 20 − 1 = 2h+1 − (h + 1). Ricordando che 2h+1 − 1 = n, si haT (n) = O(n).

2.5 Delimitazione inferiore della complessita del problema dell’ordinamento per confrontiPer ordinare una sequenza di n elementi bisogna almeno esaminare tutti gli elementi, quindi la complessita del problema hadelimitazione inferiore (in ogni caso) Ω(n).Si noti che, in casi particolari, l’ordinamento di una sequenza puo essere effettuato senza ricorrere a confronti. Per esempio,se si ha un array di 50 elementi, ognuno con una chiave da 0 a 49, per ordinarlo basta disporre di un array ausiliario dellastessa lunghezza e percorrere l’array di partenza, mettendo nell’array ausiliario ogni elemento al suo posto. Ovviamente ciorichiede un tempo Θ(n), e non viene effettuato nessun confronto. Questo algoritmo tuttavia usa informazione aggiuntiva, e non eutilizzabile in generale. Consideriamo quindi il problema dell’ordinamento assumendo che l’informazione possa essere ottenutasolo mediante confronti. Si prova che qualunque algoritmo di ordinamento per confronti deve eseguire nel caso peggiore almenon log n passi, perche deve effettuare almeno n log n confronti.Prova semi-formale: le possibili permutazioni di n elementi sono n!, percio un algoritmo di ordinamento deve poter produrrele n! permutazioni diverse di una sequenza. Eseguendo k confronti, possiamo ottenere 2k insiemi diversi di risultati booleani,quindi questi 2k insiemi distinti di booleani devono essere non meno delle n! possibili permutazioni. Si ha quindi:

T (n) ≥ k ≥ log(n!)

E facile dare una minorazione di log(n!), osservando che:

22

n! = n · (n− 1) · (n− 2) · . . . · 1 ≥ (prendendo solo meta dei fattori)n · (n− 1) · (n− 2) · . . . · n2 ≥ (n2 ) · (n2 ) · (n2 ) · . . . · (n2 ) = (n2 )

n2

Quindi log(n!) ≥ log(n2 )n2 = n

2 log(n2 ), quindi

T (n) = Ω(n log n)

Prova piu rigorosa: un insieme di possibili sequenze di confronti puo essere rappresentato come un albero binario (detto alberodi decisione). In questo albero, ogni nodo interno rappresenta un confronto, per effetto del quale l’insieme delle possibilipermutazioni risultato si restringe, e ogni foglia rappresenta una permutazione risultato. Fissata la lunghezza n della sequenza,a ogni algoritmo di ordinamento per confronti corrisponde un albero delle decisioni, e a ogni esecuzione dell’algoritmo (ossia, aogni particolare input) corrisponde un particolare cammino dalla radice a una foglia.Ogni albero di decisione (corrispondente a un certo algoritmo) per una sequenza di lunghezza n avra comunque almeno n!foglie (se l’algoritmo e inefficiente vi possono essere piu foglie corrispondenti ad una stessa permutazione). Il caso peggiore perquell’algoritmo corrispondera al cammino piu lungo, la cui lunghezza e quindi l’altezza dell’albero. Tuttavia, dato che l’alberoha almeno n! foglie, avra altezza (quindi cammino piu lungo) non inferiore a log(n!).Osservazione: un algoritmo di ordinamento ottimale avra un albero di decisione bilanciato, quindi l’altezza dell’albero saralog(n!), quindi Θ(n log n). Un algoritmo di ordinamento non ottimale, invece, avra un albero di decisione sbilanciato e/o connodi corrispondenti a confronti inutili.Per esempio, il seguente e l’albero di decisione per insertion sort su una sequenza di tre elementi.

b?a

c?b

c?b

c?a

c a b

a b c

a b c

c b ab c a

b a c

a c b

≥ <

<

<<

<≥

≥

≥

≥b?a

Il numero massimo di confronti e 3, e non potrebbe essere minore in quanto dlog(3!)e = 3. Infatti, per ordinare tre elementia, b, c e certamente necessario:

1. effettuare un primo confronto, per esempio di a con b

2. effettuare un secondo confronto, di c con a oppure con b

3. in qualche caso “sfortunato”, per esempio se abbiamo confrontato c con a e risulta a > b e a > c, effettuare un terzoconfronto, per esempio di b con c.

Su tre elementi quindi l’albero di decisione di insertion sort risulta bilanciato.Per esercizio: dare l’albero di decisione per insertion sort su 4 elementi. E bilanciato? In caso di risposta negativa, si spieghidove l’algoritmo non applica la migliore strategia possibile.Per esercizio: dare l’albero di decisione per selection sort su tre elementi. E bilanciato? Effettua confronti inutili?

2.6 Algoritmi di ordinamento lineariCome gia osservato, se si ammettono algoritmi non per soli confronti, si possono dare ordinamenti in tempo lineare. Tali algoritmipero, a differenza di quelli per confronti, non sono applicabili in tutte le situazioni. Vediamo alcuni casi in cui e possibile dareun ordinamento lineare.

• Ordinare un array di n elementi aventi chiavi intere tutte diverse in 0..n− 1 (gia visto).

• Ordinare un array di n elementi aventi chiavi intere tutte diverse in m..m + n − 1 (m intero), per esempio ordinare pernumero di matricola 1000 studenti di matricola compresa tra 42000 e 42999, con matricole non duplicate (generalizzazionedel precedente).

• Ordinare una sequenza di n interi compresi nell’intervallo m..m+n− 1, senza elementi ripetuti. In questo caso non serveun array ausiliario, anzi non serve neppure l’array di input, basta for(i = 0; i < n; i++) a[i] = m + i.

23

• (Integer sort) Ordinare un array di n interi compresi nell’intervallo 0..k−1, con possibili ripetizioni (sicuramente se n > k)Idea: utilizzare un array ausiliario c di contatori con indici 0..k − 1. Si percorre l’array da ordinare a, incrementando, perogni elemento a[i], il contatore c[a[i]] corrispondente. Poi, si percorre l’array dei contatori, inserendo in a, per ognunodei k valori, tanti elementi uguali a k quanti contati in precedenza.

integersort(k,a) //a con indici 0..n− 1, ∀i ∈ 0..n− 1.0 ≤ a[i] < kc = array con indici 0..k − 1for (v = 0;v < k;v++) c[v] = 0//prima fase: se a[i] = v incremento il v-esimo contatorefor (i = 0; i < n; i++) c[a[i]]++//seconda fasei = 0 //indice su afor(v = 0;v < k;v++)

for(j = 0; j < c[v]; j++) a[i++] = v//tanti valori v quanti contati nella prima fase vengono messi nell’array

Complessita: k passi per inizializzare i contatori (se inizializzazione non di default), n passi per contare i valori (primafase), n passi per riempire l’array (seconda fase), in totale 2n oppure 2n+ k iterazioni.

Riassumendo:

• nel caso di elementi con chiavi tutte presenti e non ripetute, la chiave fornisce direttamente il posto in cui metterel’elemento, ma serve array ausiliario per non sovrascrivere gli elementi

• nel caso di elementi interi “puri”, ripetuti e mancanti: bisogna contare il numero di presenze di ciascun valore, ma nonserve array ausiliario, perche i valori si scrivono direttamente senza copiarli (si sa quali sono).

Counting sort Consideriamo ora il caso di elementi (non interi puri) con chiavi ripetute e mancanti. Ossia il problema e:ordinare un array di n elementi aventi chiavi intere nell’intervallo 0..k − 1. Come nel caso di integer sort, per ogni possibilevalore v della chiave bisogna contare gli elementi di chiave uguale a v. Tuttavia, ora elementi con chiavi uguali contengonoanche altri dati, quindi serve un array ausiliario e non si puo semplicemente inserire il giusto numero di copie di ogni valore.Idea: quale e la posizione in cui deve andare ciascun elemento nell’array ausiliario b? Il primo degli elementi di chiave v deveandare nel posto successivo a tutti gli elementi di chiave < v. Quindi dobbiamo calcolare, per ciascuna chiave v, il numero deglielementi di chiave < v. Si ottiene l’algoritmo counting sort. Assumiamo che il metodo key restituisca la chiave intera di unelemento.

countsort(k,a)for (v = 0; v < k; v++) c[v] = 0//prima fasefor (i = 0; i < n; i++) c[a[i].key()]++//seconda fasetot = 0for (v = 0; v< k; v++) //Inv: ∀j ∈ 0..v− 1.c[j] = numero elementi di chiave < j

//∧ tot = numero di elementi di chiave < vtemp = c[v] //temp = numero elementi di chiave = vc[v] = tottot += temp

//terza fasefor (i = 0; i < n; i++) b[c[a[i].key()]++] = a[i]

Esempio:a = [A1|B2|C1|D1|E1|F0|G0|H0]

Prima fase:c[0] = 3,c[1] = 4,c[2] = 1Seconda fase:c[0] = 0,c[1] = 3,c[2] = 7

24

Terza fase:b = [ | | |A| | | | ] c[1] = 4b = [ | | |A| | | |B] c[2] = 8b = [ | | |A|C| | |B] c[1] = 5b = [ | | |A|C|D| |B] c[1] = 6. . .

Variante: l’ultimo degli elementi di chiave v deve andare nell’ultimo posto di tutti gli elementi di chiave ≤ v. Quindi, poiche gliarray sono indiciati a partire da 0, l’indice dell’ultimo elemento di chiave v e il numero di elementi di chiave ≤ v, decrementatodi 1.

countsort(k,a)for (v = 0; v < k; v++) c[v] = 0//prima fase ugualefor (i = 0; i < n; i++) c[a[i].key()]++//seconda fasec[0]--for(j = 1; v < k; v++) c[j] += c[j-1]//terza fase: dalla fine, per ottenere un ordinamento stabilefor(i = n-1; i >= 0; i--) b[c[a[i].key()]--] = a[i]

Esempio:a = [A1|B2|C1|D1|E1|F0|G0|H0]

Prima fase:c[0] = 3,c[1] = 4,c[2] = 1Seconda fase:c[0] = 2,c[1] = 6,c[2] = 7

Terza fase:b = [ | |H| | | | | ] c[0] = 1b = [ |G|H| | | | | ] c[0] = 0b = [F |G|H| | | | | ] c[0] = −1b = [F |G|H| | | |E| ] c[1] = 5. . .

Osservazioni:

• alla fine si puo ricopiare l’array ausiliario b nell’array di partenza a, in modo che l’algoritmo abbia la funzionalita usualedegli algoritmi di ordinamento

• e un algoritmo di ordinamento stabile, perche il primo degli elementi di chiave v nell’array a viene messo al primo postofra gli elementi di chiave v nell’array b, il secondo nel secondo, e cosı via

• l’algoritmo puo facilmente essere adattato al caso in cui le chiavi sono in un intervallo che non inizia da zero, cioe da m am+ k − 1, con m 6= 0.

Complessita temporale:

• eventuale ciclo for che inizializza i contatori: k passi

• prima fase, ciclo che conta gli elementi: n passi

• seconda fase, ciclo che somma i contatori: k passi

• terza fase, ciclo che mette in b in ordine: n passi

• ciclo che ricopia b in a: n passi

quindi:

T (n, k) ∼= 3n+ 2k oppure 3n+ k = Θ(n+ k)

Se k e dello stesso ordine di grandezza di n, si ha:

T (n) = Θ(n)

25

(complessita lineare)Complessita spaziale: l’algoritmo utilizza due array ausiliari, b di lunghezza n e c di lunghezza k. Quindi anche lo spazio elineare:

S (n, k) = Θ(n+ k)

Nota: se l’insieme delle possibili chiavi e molto grande l’algoritmo non e usabile: troppo dispendioso in spazio e in tempo. Peresempio, non si puo usare il counting sort per ordinare una sequenza di stringhe. Assumendo una lunghezza massima di 20caratteri, il numero k di chiavi sarebbe 2620.

Bucket sort Risolve stesso problema del counting sort, ossia ordinare un array di n elementi con chiavi intere fra 0 e k − 1 (ofra m ed m+k−1). Opera come integer sort e counting sort, mantenendo pero un array di liste (bucket) anziche di contatori. Lav-esima lista conterra gli elementi con chiave uguale a v. Alla fine si concatenano le liste in una lista risultato, o si ricopiano inun array. Complessita: Θ(n + k). Conveniente se la sequenza e gia rappresentata da una lista, nel caso di array, invece, sono ingenere migliori counting sort o integer sort. Per avere un algoritmo stabile, in ogni bucket gli elementi devono essere nell’ordinein cui sono nell’array originale, quindi vanno inseriti in fondo. Inoltre, se si usa il bucket sort per ordinare un array, quando siestraggono gli elementi per metterli nell’array risultato, essi devono essere estratti dall’inizio. Quindi i bucket sono code.

Radix sort Ordinamento in base a una tupla di chiavi: per esempio, si supponga di voler ordinare in base a cognome, nome eanno di nascita (nell’ordine) una sequenza di persone, si puo operare in vari modi:

• definire una funzione di confronto che confronta prima i cognomi, se questi sono uguali i nomi, e cosı via

• ordinare prima per cognome mettendo gli elementi con cognomi uguali in liste, poi ordinare per nome ogni lista di cognomiuguali, e cosı via

• ordinare prima la sequenza per anno di nascita, poi riordinarla per nome con un algoritmo stabile, infine riordinarla per co-gnome con un algoritmo stabile; poiche un algoritmo stabile preserva l’ordine precedente, alla fine gli elementi risulterannoordinati nel modo voluto.

Radix sort ordina una sequenza di elementi con chiavi d-tuple di valori nell’intervallo 0..k − 1 per mezzo del terzo metodoillustrato, usando il counting sort o il bucket sort come algoritmo di ordinamento stabile. Il numero totale di iterazioni e quindicirca d(3n+ k), con d e k costanti. Si ha quindi ancora complessita temporale lineare:

T (n, k) = Θ(n+ k)

Se d non e molto piccolo (poche unita), la costante moltiplicativa influenza pesantemente l’efficienza.Esempio: vogliamo ordinare array di elementi di tipo intero a 32 bit (come int di Java), possiamo:

• scomporre il campo di tipo int in due campi di 16 bit

• ordinare due volte l’array con il counting sort:

• prima rispetto ai 16 bit meno significativi

• poi rispetto ai 16 bit piu significativi

oppure:

• scomporre il campo di tipo int in 4 campi di 8 bit (byte)

• ordinare quattro volte l’array con il counting sort:

• prima rispetto al byte piu basso

• poi rispetto al secondo byte dal basso

• e cosı via

quale delle due scomposizioni e piu efficiente? Si ha

• 2 counting sort su 16 bit:

T (n) ∼= 2(3n+ 216)

26

• 4 counting sort su 8 bit:

T (n) ∼= 4(3n+ 28)

Il tempo del primo metodo cresce piu lentamente, ma ha costante iniziale molto piu grande. Al di sotto di una soglia il secondometodo sara quindi piu efficiente del primo, approssimativamente il valore di n tale che:

2(3n+ 216) = 4(3n+ 28) ; n ∼= 20000

Il secondo metodo, inoltre, occupa meno spazio del primo (i contatori sono 28 invece di 216).In generale, radix sort su interi di b bit si effettua mediante b

r esecuzioni del counting sort su r bit (con r sottomultiplo di b),quindi:

T (n) = Θ( br (n+ 2r))

Come scegliere r, cioe la dimensione dei “pezzi”? In br vogliamo r il piu grande possibile , ma in n+ 2r non vogliamo 2r molto

maggiore di n, cioe r molto maggiore di log n, quindi:

r il piu grande possibile ma che non superi (troppo) log n.

Si noti che 2r cresce esponenzialmente al crescere di r, mentre br si riduce proporzionalmente, quindi non conviene prendere un

r troppo grande.Riprendiamo l’esempio di un array di int (32 bit):

• array di dimensione n ∼= 1000:log 1000 ∼= 10 ; r = 8 e una scelta ottimale (4 counting sort)

• array di dimensione n ∼= 100000:log 100000 ∼= 17 ; r = 16 e ottimale (2 counting sort)

I risultati sono in accordo con quelli della valutazione piu precisa precedente.Nota: rispetto ai migliori algoritmi di ordinamento per confronti, il radix sort su interi e piu efficiente per array di lunghezzamolto grande, altrimenti una buona implementazione di quicksort e di solito piu veloce.

3 Strutture dati

3.1 HeapUna coda a priorita e una collezione di elementi ognuno dei quali possiede una certa priorita, rappresentata per esempio da unnumero naturale (in genere per consuetudine 1 indica la priorita piu alta possibile), e si estrae ogni volta l’elemento (o uno deglielementi) con priorita piu alta. Le operazioni fondamentali sono quindi:

• inserimento di un elemento con una data priorita

• estrazione (o solo lettura) dell’elemento con il valore minimo di priorita

• test se la coda e vuota o no

Si puo considerare la coda costituita di coppie (elemento, priorita) oppure considerare la priorita come una proprieta degli ele-menti. Si possono inoltre definire altre operazioni, come: variazione della priorita di un elemento, cancellazione di un elemento,fusione di due code a priorita, etc.Nelle realizzazioni “ingenue” si ha:

• liste ordinate: estrazione del minimo costa Θ(1), ma inserimento costa O(n)

• liste non ordinate: inserimento costa Θ(1), ma estrazione del minimo costa O(n).

Idea migliore: usare uno heap (a minimo), ossia un albero binario quasi completo, cioe completo fino al penultimo livello, incui la chiave di ciascun nodo e minore o uguale delle chiavi dei figli. Il fatto che l’albero sia quasi completo garantisce che siabilanciato, vedi sezione ??, quindi che la lunghezza di un cammino sia O(log n) con n numero dei nodi. Per fare in modo chel’albero rimanga sempre quasi completo, si puo procedere nel modo seguente:

• nell’inserimento, aggiungere il nuovo elemento come foglia all’ultimo livello e poi farlo risalire al posto giusto mediantescambi successivi col genitore

27

• nell’estrazione del minimo, spostare al posto della radice una foglia dell’ultimo livello, e poi farla scendere al posto giustomediante scambi successivi col minore dei figli.

I due algoritmi ausiliari di base sono quindi:

• moveUp: data una foglia, o piu in generale un nodo che sia al posto giusto rispetto ai figli ma non necessariamente rispettoal genitore, lo fa risalire fino al posto giusto, scambiandolo via via con il genitore

• moveDown: data la radice, o piu in generale un nodo che sia al posto giusto rispetto al genitore ma non necessariamenterispetto ai figli, lo fa scendere fino al posto giusto, scambiandolo via via con il minore dei figli.

Quindi: inserimento: crea una foglia + moveUp, estrazione del minimo: sposta da foglia a radice + moveDown.Per poter realizzare concretamente con complessita logaritmica i due algoritmi astratti precedenti, bisogna:

• trovare in tempo costante (o al piu logaritmico) quale foglia tagliare oppure creare

• essere in grado, nell’algoritmo di inserimento, di risalire dal figlio al padre in tempo costante.

Una soluzione semplice consiste nell’assumere che lo heap sia quasi completo da sinistra, e rappresentarlo con un array in cui inodi sono memorizzati consecutivamente per livelli. Se i nodi vengono memorizzati nell’array a partire dall’indice 1 (lasciandoinutilizzato l’elemento di indice 0), i figli del nodo memorizzato nell’elemento di indice i risultano memorizzati rispettivamentenegli elementi di indice 2i e 2i+ 1, e il genitore in quello di indice i/2.Come in altre situazioni dello stesso genere, in cui un elemento deve venire scambiato piu volte successivamente (per esempioinsertion sort), conviene memorizzare tale elemento in una variabile temporanea e inserirlo solo alla fine nella posizione giusta.E quindi come se ogni volta si scambiasse un elemento con un “posto vuoto”, il quale alla fine raggiunge la posizione corretta incui inserire il valore.Supponiamo che lo heap Q sia rappresentato con un oggetto3 con due attributi a array degli elementi e sup indice dell’ultimoelemento utilizzato (0 quando lo heap e vuoto), e scriviamo gli algoritmi come metodi.

moveUp e inserimento Se i e l’indice di un elemento eventualmente fuori posto rispetto al genitore, cioe minore del genitore,l’algoritmo moveUp lo fa risalire al posto giusto.

Q.moveUp(i) //1 ≤ i ≤ supelem = a[i] //elemento da far salirewhile(i > 1 && elem < a[i/2]) //i posto vuoto

a[i] = a[i/2] //scende il genitorei = i/2 //sale il posto in cui mettere l’elemento

a[i] = elem

Q.insert(elem)if (sup == a.length-1) errore o riallocazionea[++sup] = elem //mette l’elemento in una nuova fogliaQ.moveUp(sup) //lo fa risalire al posto giusto

moveDown e rimozione del minimo Se i e l’indice di un elemento eventualmente fuori posto rispetto ai figli, cioe maggioredi almeno un figlio, lo fa scendere al posto giusto, scambiandolo ogni volta con il minore dei figli. E anche chiamato fixHeap.

Q.moveDown(i) //1 ≤ i ≤ supelem = a[i] //elemento da far scenderej = 2*iwhile (j <= sup && elem > a[j]) //i posto vuoto, j figlio sinistro

if (j+1 <= sup && a[j+1] < a[j]) j++ //j figlio destroa[i] = a[j] //sale il figlioi = j //scende il posto in cui mettere l’elemento

a[i] = elem

Q.getMin()if (sup == 0) errore

3Utilizzeremo per le strutture dati il paradigma di programmazione a oggetti.

28

min = a[1]if (sup == 1) sup = 0 //lo heap diventa vuotoelse

a[1] = a[sup--]Q.moveDown(1)

return min

Ulteriore operazione derivata che cambia la priorita di un elemento:

Q.changePriority(i,delta) if (i > sup || i < 1) errorea[i] += deltaif (delta > 0) Q.moveDown(i)else if (delta < 0) Q.moveUp(i)

Analsi della complessita: gli algoritmi moveUp e moveDown sono entrambi nel caso peggiore logaritmici nel numero deglielementi, poiche percorrono al massimo un cammino (fra radice e foglia) in un albero binario quasi completo impiegando untempo costante per ogni passo. Tali sono quindi anche tutte le operazioni considerate, in particolare l’estrazione del minimo el’inserimento. Per esse si ha dunque: Tworst(n) = Θ(log n).

3.2 Strutture union-findProblema (versione astratta): rappresentare una collezione di insiemi disgiunti sulla quale siano possibili le seguenti operazioni:

• makeSet(a) aggiunge l’insieme costituito dal solo elemento a (singleton)

• union(A,B) sostituisce gli insiemi A e B con la loro unione

• find(a) restituisce l’insieme che contiene l’elemento a.

Se ho n makeSet posso eseguire al piu n − 1 union.Supponiamo di identificare ogni insieme con un suo elemento (se pensiamo gli insiemi come classi di equivalenza, un suorappresentante). Si ha quindi:

• makeSet(a) aggiunge l’insieme costituito dal solo elemento a (singleton)

• union(a,b) sostituisce gli insiemi (rappresentati da) a e b con (un rappresentante del)la loro unione

• find(a) restituisce (il rappresentante del)l’insieme che contiene l’elemento a.

Idea generale per l’implementazione: ogni insieme e un albero la cui radice e il rappresentante. Si usano alberi con numeroarbitrario di figli, in genere difficili da implementare, ma in questo caso interessa solo risalire al padre. La collezione di insiemie quindi una foresta. Se gli elementi sono i numeri naturali da 0 a n − 1, e possibile implementare gli alberi con array in cui gliindici corrispondono ai nodi, e ogni elemento dell’array (nodo) contiene l’indice del padre.Basandosi su questa idea generale, e possibile dare diverse rappresentazioni con diverse caratteristiche di efficienza. Vediamoprima due rappresentazioni elementari, assumendo che n sia il numero di makeSet.

Alberi QuickFind Permettono di eseguire rapidamente la find. Sono alberi di altezza uno.

• makeSet(a) aggiunge un nuovo albero con due nodi, radice a e figlio a: O(1)

• union(a,b) rende la radice dell’albero che contiene a padre di tutti i nodi dell’albero che contiene b: O(n)

• find(a) restituisce il padre di a: O(1)

• occupazione di spazio: a ogni istante il numero totale di nodi e O(n) (massimo 2n , minimo n + 1), il numero totale diarchi e O(n).

29

Alberi QuickUnion Permettono di eseguire rapidamente la union. Sono alberi di altezza arbitraria.

• makeSet(a) aggiunge un nuovo albero con un unico nodo a: O(1)

• union(a,b) tra rappresentanti rende a padre di b: O(1).

• union(a,b) generica, richiede prima una find: O(n)

• find(a) risale la catena dei padri di a: O(n)

• occupazione di spazio: a ogni istante il numero totale di nodi e n, il numero totale di archi eO(n) (massimo n−1, minimo0).

QuickUnion con union-by-size oppure union-by-rank L’operazione piu costosa e la find, perche l’altezza degli alberi puocrescere senza controllo. Si consideri per esempio:

makeSet(1) ... makeSet(n)union(n-1,n)...union(1,2)

Per mantenere gli alberi bilanciati, l’unione viene effettuata scegliendo sempre come radice del nuovo insieme quella dell’insiemedi cardinalita maggiore, cioe la radice dell’albero con meno nodi diventa figlio della radice dell’altro.

Teorema 3.1 Con la union-by-size, l’altezza di ogni albero della struttura union-find e al piu logaritmica nel numero di nodidell’albero.

Dimostrazione Proviamo che h ≤ log |T |, ossia 2h ≤ |T |, per ogni albero T di altezza h, e una proprieta invariante dellastruttura union-find.

• vale all’inizio: la proprieta vale banalmente per la struttura vuota

• vale dopo una makeSet: si ha un nuovo albero T con un solo nodo, per esso si ha quindi banalmente 2h = |T |

• vale dopo una union, infatti, siano T e T ′ i due alberi che vengono fusi, di altezza h e h′ rispettivamente, con 2h ≤ |T |,2h′ ≤ |T ′| e, per esempio, |T ′| ≤ |T |:

– se h′ + 1 ≤ h, si ottiene un nuovo albero di altezza h e numero di nodi |T |+ |T ′|, e 2h ≤ |T | < |T |+ |T ′|– se h′+1 > h, si ottiene un nuovo albero di altezza h′+1 e numero di nodi |T |+|T ′|, e 2h

′+1 ≤ 2|T ′| ≤ |T |+|T ′|.

Si ha quindi:

• union tra rappresentanti: O(1).

• union generica: O(log n)

• find: O(log n)

Una tecnica alternativa a quella dell’unione per dimensione, detta union-by-rank4, e la seguente: l’unione viene effettuata sce-gliendo come radice del nuovo albero quella dell’albero di altezza maggiore, cioe la radice dell’albero meno alto diventa figliodella radice di quello piu alto.

Teorema 3.2 Con la union-by-rank, l’altezza di ogni albero della struttura union-find e al piu logaritmica nel numero di nodidell’albero.

Dimostrazione Proviamo che h ≤ log |T |, ossia 2h ≤ |T |, per ogni albero T di altezza h, e una proprieta invariante dellastruttura union-find.

• vale all’inizio e dopo una makeSet: banalmente, analogamente a prima

• vale dopo una union, infatti, siano T e T ′ i due alberi che vengono fusi, di altezza h ed h′ rispettivamente, con 2h ≤ |T |,2h′ ≤ |T ′| e, per esempio, h′ ≤ h:

4Chiamiamo questa tecnica union-by-rank piuttosto che union-by-height perche, come vedremo piu avanti, puo essere generalizzata scegliendo in base nonall’altezza effettiva ma a un suo maggiorante.

30

– se h′ < h, si ottiene un nuovo albero di altezza h e numero di nodi |T |+ |T ′|, e 2h ≤ |T | < |T |+ |T ′|– se h′ = h, si ottiene un nuovo albero di altezza h+ 1 e numero di nodi |T |+ |T ′|, e 2h+1 = 2h + 2h

′ ≤ |T |+ |T ′|.Si noti che il campo altezza deve essere aggiornato solo in questo caso.

Nota implementativa: ovviamente, perche le operazioni abbiano la complessita indicata sopra, per ogni albero della foresta union-find sara necessario memorizzare l’informazione sul suo numero di nodi o altezza, in modo che quando si effettua la union ilnumero di nodi o l’altezza dell’albero unione possano essere calcolati in tempo costante a partire da quelli dei due argomenti.In un’implementazione in cui si aggiunga un campo size a ogni nodo, tale campo sara rilevante solo per i nodi radice. Questorende possibile, nel caso in cui l’universo degli elementi sia l’insieme degli interi da 0 a n − 1, un’implementazione con array incui gli indici corrispondono ai nodi, e , se l’indice corrisponde a un nodo non radice, il suo contenuto e l’indice corrispondente algenitore, se a un nodo radice, l’opposto della dimensione dell’albero. In questo modo non si hanno ambiguita, essendo gli indicinumeri non negativi.

Path compression Possiamo fare in modo che la find durante la sua esecuzione tenda a diminuire l’altezza dell’albero, cosıda rendere piu veloci le operazioni successive. Ci sono varie tecniche possibili, consideriamone una: la find rende figli dellaradice tutti i nodi che incontra nel suo percorso di risalita dal nodo alla radice.La realizzazione della path compression puo essere iterativa: dopo aver trovato la radice, si ripercorre il cammino dal nodo allaradice aggiornando in ogni nodo del cammino il puntatore al genitore, oppure ricorsiva: l’aggiornamento del genitore vieneeffettuato dopo la chiamata ricorsiva. In entrambi i casi il numero di passi della find modificata e uguale a quello della findoriginale moltiplicato per un fattore costante, quindi la complessita rimane logaritmica.Versione iterativa:

UF.find(x)root = xwhile (root.parent 6= null) root = root.parentwhile (x.parent 6= root)oldParent = x.parentx.parent = rootx = oldParent

return root

Versione ricorsiva:

UF.find(x)if (x.parent = null) return xx.parent = find(x.parent)return x.parent

Si noti che, dato che la union tra elementi generici consiste di due operazioni di find seguite dall’unione vera e propria,introducendo la compressione dei cammini nella find la introduciamo automaticamente anche nella union.Nota: possiamo utilizzare insieme senza problemi la union-by-size e la compressione dei cammini, in quanto quest’ultima nonmodifica il numero di nodi degli alberi che costituiscono la foresta union-find. In altri termini, in un’implementazione in cui siaggiunga un campo size a ogni nodo, durante la compressione non e necessario aggiornare i campi size dei nodi coinvolti.Nel caso della union-by-rank, invece, la compressione dei cammini puo modificare l’altezza dell’albero cui appartiene il nodoargomento della find. Tuttavia, anche in questo caso e possibile evitare di aggiornare l’informazione, interpretandola non piucome altezza dell’albero, ma come una quantita, chiamata rank, che sappiamo essere maggiore o uguale dell’altezza dell’albero.L’unione viene effettuata in base al rank piuttosto che all’altezza, e, come nel caso dell’altezza, se i due argomenti dell’unionehanno lo stesso rank r l’albero unione deve avere rank r+ 1, per garantire che il rank sia un maggiorante dell’altezza dell’albero.Si ha che:

h ≤ r ≤ log |T |, ossia 2h ≤ 2r ≤ |T |, per ogni albero T di altezza h e rank r, e una proprieta invariante dellastruttura union-find.

Infatti quando si esegue una union vale esattamente il ragionamento della prova precedente considerando il rank invecedell’altezza, e quando si esegue una find il rank resta uguale mentre l’altezza puo diminuire.Il vantaggio della compressione dei cammini si ha quando si effettua una sequenza di operazioni, non puo quindi venire misuratodalla complessita di una singola operazione. Si considera quindi la nozione di complessita ammortizzata. Si tratta di una nozioneutile in tutti i casi in cui il tempo di calcolo impiegato da un algoritmo che realizzi un’operazione su una struttura dati puodipendere, oltre che dalla dimensione n della struttura, dalle operazioni (dello stesso o di altro genere) effettuate prima.Per una sequenza di m operazioni dello stesso tipo si definisce:

31

Tam(n) = Tworst (n)m

Piu in generale si possono anche considerare sequenze di operazioni di diverso tipo (come nel caso delle strutture union-find).Non si confonda la complessita del caso medio (media, eventualmente pesata con una certa distribuzione di probabilita, deltempo di esecuzione su tutti i possibili input) con la complessita ammortizzata (media del tempo di esecuzione su una sequenzadi operazioni, non interviene nessuna nozione probabilistica).Si puo dimostrare (non lo vediamo) che la complessita per una sequenza di n makeSet, m find e n − 1 union e O((n +m) log∗ n), dove log∗ e una funzione dalla crescita lentissima, in pratica costante da un certo punto in poi (per esempio,log∗ 265536 = 5). Quindi, la complessita ammortizzata per questa sequenza di operazioni e “quasi” O(1).

4 Grafi

4.1 Introduzione e terminologiaDef. 4.1 [Grafo] Un grafo (orientato) e una coppia G = (V ,E ) dove:

• V e un insieme i cui elementi sono detti nodi o vertici

• E e un insieme di archi (edges), dove un arco e una coppia di nodi detti estremi dell’arco.

In un grafo non orientato gli archi sono coppie non ordinate, ossia (u, v) e (v , u) denotano lo stesso arco.

Un arco da un nodo in se stesso e detto cappio, e un grafo senza cappi e detto semplice. La definizione di grafo si puo generalizzarea quella di multigrafo, in cui gli archi sono un multiinsieme. Nel caso di grafi orientati, il primo elemento della coppia e dettonodo uscente o coda, il secondo nodo entrante o testa.Dato il seguente grafo non orientato:

A B

C

D E

F

• l’arco (A,B) e incidente sui nodi A e B,

• i nodi A e B sono adiacenti, A e adiacente a B, B e adiacente ad A,

• i nodi adiacenti a un nodo A si chiamano anche i vicini di A,

• il grado δ(u) di un nodo u e il numero di archi incidenti sul nodo, per esempio δ(B) = 4.

Dato il seguente grafo orientato:

A B

C

D E

F

• l’arco (A,B) e incidente sui nodi A e B, uscente da A, entrante in B,

• il nodo B e adiacente ad A, ma A non e adiacente a B,

• i nodi adiacenti a un nodo A si chiamano anche i vicini di A,

• il grado δ(u) di un nodo u e il numero di archi incidenti sul nodo, per esempio δ(B) = 4,

• il grado uscente (outdegree) δout(u) di un nodo u e il numero di archi uscenti dal nodo, per esempio δout(B) = 2,

• il grado entrante (indegree) δin(u) di un nodo u e il numero di archi entranti nel nodo, per esempio δin(B) = 2.

Dato un grafo G = (V ,E ), con n nodi ed m archi, si hanno le seguenti ovvie proprieta:

32

• se G e non orientato

– la somma dei gradi dei nodi e il doppio del numero degli archi:∑

u∈V δ(u) = 2m ,

– m e al massimo il numero di tutte le possibili coppie non ordinate di nodi, ossia n(n + 1)/2, quindi m = O(n2).

• se G e orientato:

– m e al massimo il numero di tutte le possibili coppie ordinate di nodi, ossia n2, quindi m = O(n2).

Naturalmente un grafo dove vi sia un arco per ogni coppia di nodi e un caso limite molto particolare e poco interessante, in generesi avra m minore o molto minore del limite superiore. Quindi la complessita degli algoritmi sui grafi viene di solito espressa infunzione dei due parametri n e m ossia come T (n,m), anche se m e in ogni caso O(n2).Un grafo in cui il numero degli archi sia dell’ordine di n2 si dice grafo denso.In un grafo G :

• un cammino (path) e una sequenza di nodi u1, . . . , un con n ≥ 0 e, per ogni i ∈ 0..n − 1, ui+1 adiacente a ui, ossia(ui, ui+1) e un arco,

• gli archi (ui, ui+1) si dicono contenuti nel cammino,

• n− 1, ossia il numero degli archi, e la lunghezza del cammino,

• un cammino e degenere o nullo se e costituito da un solo nodo, ossia ha lunghezza 0,

• e semplice se i nodi sono distinti, tranne al piu il primo e l’ultimo,

• in un grafo orientato, un cammino non nullo forma un ciclo se il primo nodo coincide con l’ultimo,

• in un grafo non orientato, un cammino di lunghezza ≥ 3 forma un ciclo (semplice) se il primo nodo coincide con l’ultimoe tutti gli altri nodi sono distinti,

• v e raggiungibile da u se esiste un cammino da u a v .

Un grafo G e aciclico se non vi sono cicli in G . Un grafo orientato aciclico e anche detto DAG (directed acyclic graph). Ungrafo non orientato si dice connesso se ogni nodo e raggiungibile da ogni altro. Un grafo orientato si dice fortemente connessose ogni nodo e raggiungibile da ogni altro, debolmente connesso se il grafo non orientato corrispondente e connesso. Un grafoconnesso avente n nodi deve avere almeno n − 1 archi.Un sottografo di G = (V ,E ) e un grafo ottenuto da G non considerando alcuni archi o alcuni nodi insieme agli archi incidentisu di essi. Il sottografo indotto da un sottoinsieme V ′ di nodi e il sottografo di G costituito dai nodi di V ′ e dagli archi di G checonnettono tali nodi.Un albero libero e un grafo non orientato connesso aciclico. Se in un albero libero si fissa un nodo u come radice, si ottieneun albero nel senso usuale (ossia, radicato), avente u come radice. Graficamente si puo pensare di “appendere” il grafo a unqualunque nodo, e si ottiene sempre un albero. Un albero radicato puo equivalentemente essere definito come un grafo orientatoaciclico (DAG) in cui uno e un solo nodo, detto radice, ha grado entrante 0, e tutti gli altri nodi hanno grado entrante 1. Ognialbero radicato secondo la prima definizione puo infatti essere visto, attribuendo agli archi l’ovvio orientamento, come un alberoradicato nel secondo senso.Dato un grafo non orientato e connesso G , un albero ricoprente (spanning tree) di G e un sottografo di G che contiene tuttii nodi ed e un albero libero. Ossia, e un albero che connette tutti i nodi del grafo usando archi del grafo, ha quindi n nodi edn − 1 archi. Analogamente, dato un grafo non orientato (eventualmente non connesso) G , si chiama foresta ricoprente di G unsottografo di G che contiene tutti i nodi ed e una foresta libera. Si vede facilmente che, dato un grafo non orientato, esiste sempreuna foresta ricoprente di G , un albero ricoprente se G e connesso.Le nozioni di albero e foresta ricoprenti possono essere date anche sui grafi orientati:

• un albero ricoprente di un grafo orientato G e un sottografo di G che contiene tutti i nodi ed e un albero radicato (esistesempre se connesso),

• foresta ricoprente di un grafo orientato G e un sottografo di G che contiene tutti i nodi ed e una foresta (esiste sempre).

33

Rappresentazione di grafi

Lista di archi Si memorizza l’insieme dei nodi e la lista degli archi, spazio totale O(n + m). Molte operazioni richiedono discorrere l’intera lista.

operazione tempo di esecuzionegrado di un nodo O(m)nodi adiacenti O(m)esiste arco O(m)aggiungi nodo O(1)aggiungi arco O(1)elimina nodo O(m)elimina arco O(m)

Liste di adiacenza Per ogni nodo si memorizza la lista dei nodi adiacenti. Si hanno n liste, di lunghezza totale 2m per grafo nonorientato, m per grafo orientato, quindi complessita spaziale O(n + m). Diventa piu semplice trovare gli adiacenti di unnodo, operazione cruciale in molte applicazioni, mentre il test di verifica dell’esistenza di un arco non e molto efficiente.Inoltre nel caso di grafo non orientato ogni arco e rappresentato due volte, quindi si ha ridondanza e quindi il problema dimantenere la coerenza dell’informazione.

operazione tempo di esecuzionegrado di u O(δ(u))nodi adiacenti a u O(δ(u))esiste arco (u, v) min(δ(u), δ(v))aggiungi nodo O(1)aggiungi arco O(1)elimina nodo O(m)elimina arco (u, v) O(δ(u) + δ(v))

Liste di incidenza (variante della precedente) Combina vantaggi delle due precedenti, si mantiene la lista degli archi e, perogni nodo, una lista di puntatori agli archi incidenti. Richiede un po piu spazio ma sempre O(n + m).

Matrice di adiacenza assumendo corrispondenza tra nodi e 1..n , matrice quadrataM di dimensione n a valori booleani (oppure0, 1), doveMi,j vero se e solo se esiste l’arco (ui, uj). Richiede piu spazio, O(n2), ma la verifica della presenza di un arcoe in tempo costante. Per contro, trovare gli adiacenti diventa piu costoso (intera riga), e nel caso di grafi non orientati si haridondanza (matrice simmetrica). Il tempo per l’aggiunta ed eliminazione di un nodo tiene conto della riallocazione.

operazione tempo di esecuzionegrado di un nodo O(n)nodi adiacenti O(n)esiste arco O(1)aggiungi nodo O(n2)aggiungi arco O(1)elimina nodo O(n2)elimina arco O(1)

4.2 VisitePer visitare un grafo si possono usare algoritmi simili a quelli visti per gli alberi. Tuttavia, poiche un nodo e raggiungibile in piumodi, bisogna “marcare” i nodi, in modo che se si raggiunge un nodo gia visitato non lo si visiti di nuovo. Le operazioni eseguiteal passo di visita dipendono, come sempre, dal particolare algoritmo.L’insieme dei nodi viene partizionato in tre insiemi, tradizionalmente indicati con i colori bianco, grigio, e nero:

bianco inesplorato, ossia non ancora toccato dall’algoritmo

grigio aperto, ossia toccato dall’algoritmo (visita iniziata)

nero chiuso (visita conclusa)

Le visite iterative usano un insieme F detto frangia da cui vengono via via estratti i nodi da visitare. A seconda della strutturadati impiegata per la frangia si ottengono diversi tipi di visita: analogamente a quanto visto per gli alberi, la visita in ampiezza

34

utilizza una coda, la visita in profondita una pila, mentre gli algoritmi di Dijkstra e Prim che vedremo successivamente utilizzanouna coda a priorita.Consideriamo per semplicita la visita del sottografo connesso a partire da un nodo. Ossia, dati un grafo G e un nodo di partenzas , la visita di tutti i nodi raggiungibili da s . Costruisce implicitamente l’albero di visita T , cioe l’albero di radice s in cui ilgenitore di un nodo u e l’altro estremo v dell’arco (v , u) percorrendo il quale si e arrivati a u . La costruzione dell’albero di visitapuo essere resa esplicita nell’algoritmo stesso, per esempio memorizzando per ogni nodo il suo genitore. I nodi nell’albero divisita corrente sono tutti grigi o neri. Si tratta di un albero ricoprente. Si generalizza a visita completa che costruisce una forestaricoprente dell’intero grafo.

Visita in ampiezza (breadth-first) La frangia e una coda Q.

BFS(G,s) //visita nodi di G raggiungibili a partire da sfor each (u nodo in G) marca u come biancoQ = coda vuotaQ.add(s); marca s come grigio; parent[s] = nullwhile (Q non vuota)

u = Q.dequeue() //u non nerovisita ufor each ((u,v) arco in G)

if (v bianco)marca v come grigio; Q.add(v); parent[v]=u

marca u come nero

Osservazioni: nell’albero BFS ogni nodo e il piu vicino possibile alla radice, ossia, la visita calcola la distanza (lunghezzaminima di un cammino) dalla radice a ogni nodo (vedi dopo). La coda mantiene l’ordine in cui i nodi sono trovati dall’algoritmo,ogni nodo entra in coda una volta sola. Il padre di un nodo viene deciso nel momento in cui il nodo viene incontrato. Invariantedel ciclo: nodi grigi = nodi in F = nodi i cui archi uscenti non sono ancora stati esaminati; nodi in T = nodi neri e grigi.

Visita in profondita (depth-first) La frangia e una pila S.

DFS(G,s) //visita nodi di G raggiungibili a partire da sfor each (u nodo in G) marca u come biancoS = pila vuotaS.push(s); marca s come grigio; parent[s] = nullwhile (S non vuota)

u = S.pop()if (u non nero)

visita ufor each ((u,v) arco in G)

if (v bianco) marca v come grigio; S.push(v); parent[v]= uelse if (v grigio) S.push(v); parent[v]= u //modifica il padre

marca u come nero

Osservazioni: si segue un cammino nel grafo finche possibile. Un nodo puo essere inserito nella pila anche se grigio, quindi piuvolte, nel caso peggiore tante volte quanti sono i suoi archi entranti. Il padre viene modificato ogni volta. Puo essere estrattodalla pila un nodo nero.Complessita della visita completa: assumiamo n = numero nodi, m = numero archi, e che la marcatura e le operazioni diinserimento, eliminazione e modifica delle strutture dati siano fattibili in tempo costante. Nota: assunzioni valide per pila e coda,potrebbero non esserlo con strutture dati diverse, per esempio coda a priorita per algoritmi di Dijkstra e Prim.

• marcature dei nodi: O(n)

• inserimenti in F e T , modifiche di F e T , estrazioni da F : ogni nodo viene inserito una prima volta in F e T , poieventualmente F e T vengono aggiornati al piu m volte: O(n+m)

• esplorazione archi incidenti eseguita n volte, quindi:

– lista di archi: O(n ·m)

– liste di adiacenza: O(n+m) perche ogni lista di adiacenza viene scandita una volta sola– matrice di adiacenza: O(n2)

35

Visita in profondita ricorsiva La visita in profondita si puo anche realizzare molto semplicemente in modo ricorsivo, analogoall’algoritmo ricorsivo per la visita preorder sugli alberi. Occorre tuttavia marcare i nodi come visitati.

DFS(G,s)for each (u nodo in G) marca u come visitatoT = albero di radice sDFS(G,s,T)

DFS(G,u,T)visita u; marca u come visitatofor each ((u,v) arco in G)

if (v non visitato)aggiungi l’arco (u, v) a TDFS(G,v,T)

Visita in ampiezza con livello esplicito

BFS(G,s)for each (u nodo in G) marca u come biancoQ = coda vuotaQ.add(s); marca s come grigio; parent[s]=null; level[s]=0while(Q non vuota)

u = Q.remove()visita ufor each ((u,v) arco in G)

if (v bianco)marca v come grigio; Q.add(v); parent[v]=u; level[v]=level[u]+1

marca u come nero

Proprieta invariante (1) della visita in ampiezza: ogni cammino da s a un nodo u bianco passa per almeno un nodo appartenentea Q.Dimostrazione: l’invariante vale banalmente all’inizio in quanto s e in Q. Si mantiene, in quanto a ogni passo tolgo un nodo u daQ, ma per ogni cammino da s a un nodo bianco v che passava per u , o lo stesso v e adiacente a u e quindi diventa grigio, oppureil nodo adiacente a u nel cammino tra u e v va in Q.Proprieta invariante (2): i nodi appartenenti a Q sono ordinati per livello e si trovano su non piu di due livelli contigui, ossia, seQ = u1 . . . un:

• level(ui) ≤ level(ui+1) per i ∈ 1..n− 1.

• level(un) ≤ level(u1) + 1

L’invariante vale banalmente all’inizio, in quanto inizialmente Q contiene solo s , a livello 0. Si mantiene, in quanto, chiamati idue livelli l1 ed l2 ≤ l1 + 1, si toglie da Q il primo nodo, di livello l1 si inseriscono in fondo a Q nodi adiacenti al nodo tolto, chequindi sono di livello l1 + 1, quindi Q rimane ordinata e al piu su due livelli.Visita in ampiezza e cammini minimi: definiamo d(u) la distanza di u da s , ossia la lunghezza minima di un cammino da s a u .Proprieta invariante (3): il livello di un nodo u nell’albero di visita e uguale alla lunghezza minima di un cammino da s a u , cioelevel(u) = d(u).L’invariante vale banalmente all’inizio, in quanto l’albero di visita contiene solo s . Si mantiene: infatti, la proprieta vale per tuttii nodi gia nell’albero (neri e grigi), quindi per tutti quelli in Q (grigi). Si estrae dalla coda un nodo u , quindi si ha level(u) =d(u). Ogni nodo bianco v adiacente a u viene inserito in coda, e messo al livello level(v) = level(u) + 1 nell’albero. C’equindi un cammino di lunghezza level(u) + 1 da s a v , vediamo che questa lunghezza e minima. Per la Proprieta (1) ognicammino da s a v deve passare per un nodo w di Q, quindi ha lunghezza l ≥ d(w) + 1 = level(w) + 1. Per la Proprieta (2)level(w) ≥ level(u), quindi l ≥ level(u) + 1 = level(v).

4.3 Cammini minimi in un grafo pesato: algoritmo di DijkstraDef. 4.2 [Grafo pesato] Un grafo pesato e un grafo G = (V ,E ) dove ad ogni arco e associato un peso o costo attraverso unafunzione c : E → R. Il costo di un cammino da s a t e la somma dei pesi o costi degli archi che compongono il cammino. Uncammino da s a t si dice minimo se ha peso minimo (detto distanza) fra tutti i cammini da s a t .

36

Naturalmente puo esistere piu di un cammino minimo. Se non esistono archi con peso negativo, un cammino minimo fra duenodi connessi esiste sempre, altrimenti puo non esistere.Problema: dato un grafo orientato pesato G , con pesi non negativi (che a seconda dell’applicazione possono rappresentaredistanze, tempi di percorrenza, costi di attivita, etc.), e dati un nodo di partenza s e un nodo di arrivo t , trovare un cammino dipeso minimo da s a t . Generalizzazione: dati un grafo orientato pesato G con pesi non negativi e un nodo di partenza s , trovareper ogni nodo u del grafo il cammino minimo da s a u .Esempi di applicazione: navigatore satellitare (trovare l’itinerario piu corto, o piu veloce, da un luogo a un altro su una mappastradale); trovare il percorso di durata minima fra due stazioni di una rete ferroviaria o di una rete di trasporto pubblico urbano;protocollo di routing OSPF (Open Shortest Path First) usato in Internet per trovare la migliore connessione da ogni nodo dellarete a tutte le possibili destinazioni.Algoritmo di Dijkstra (1959), idea: e una visita in ampiezza in cui a ogni passo:

• per i nodi gia visitati si ha la distanza minima e l’albero T di cammini minimi

• per ogni nodo non ancora visitato si ha distanza provvisoria minima = distanza minima ottenibile con cammino in T piuun arco

• si estrae dalla coda un nodo a distanza provvisoria minima (che risulta distanza minima)

• si aggiornano le distanze provvisorie dei nodi adiacenti al nodo estratto tenendo conto del nuovo arco in T

Dato che ogni volta si estrae un minimo, conviene rappresentare l’insieme dei nodi ancora da visitare come coda a priorita. L’usodi una coda a priorita realizzata come heap invece che come semplice array o lista fu introdotto da Johnson nel 1977; tale versionedell’algoritmo e quindi talvolta chiamata algoritmo di Johnson.Per non dover trattare a parte il caso di nodi non in coda, conviene inserire all’inizio in coda tutti i nodi assegnando loro comedistanza provvisoria “infinito”.

Djikstra(G,s)for each (u nodo in G) dist[u] = ∞parent[s] = null; dist[s] = 0Q = heap vuotofor each (u nodo in G) Q.add(u,dist[u])while (Q non vuota)

u = Q.getMin() //estraggo nodo a distanza provvisoria minimafor each ((u,v) arco in G)

if (dist[u] + cu,v < dist[v]) // se v nero falsoparent[v] = u; dist[v] = dist[u] + cu,vQ.changePriority(v, dist[v]) //moveUp

Nota implementativa: nell’operazione changePriority, l’argomento non e l’indice dell’elemento nello heap, ma l’elementostesso. Occrre quindi poter trovare l’indice in tempo costante.

Correttezza Sia d [u] la distanza (lunghezza di un cammino minimo) da s a u . L’invariante e composta di due parti:

1. per ogni nodo u non in Q, ossia “nero”dist[u] = d [u]

2. per ogni nodo u in Qdist[u] = d\Q[u] = lunghezza di un cammino minimo da s a u i cui nodi, tranne u , non sono in Q, ossia sono nodi “neri”.

Convenzione: se questo cammino non esiste, ossia u non e raggiungibile da s solo attraverso nodi neri (u e “bianco”), d\Q[u] =∞.L’invariante vale all’inizio:

1. vale banalmente perche non ci sono nodi neri (tutti i nodi sono in coda)

2. vale banalmente perche la distanza e per tutti infinito, tranne che per s per cui vale 0.

L’invariante si mantiene.

37

1. Viene estratto dalla coda il nodo u con dist[u] minima, quindi, per l’invariante (2), tale che esiste un cammino π da sa u minimo tra quelli costituiti da tutti nodi neri tranne l’ultimo. Tale cammino e allora anche il minimo in assoluto fratutti i cammini da s a u . Infatti, supponiamo per assurdo che esista un cammino da s a u di costo minore di quello di π.Questo cammino deve necessariamente contenere nodi non neri, altrimenti avrebbe costo minore o uguale a quello di π.Sia w il primo di tali nodi neri. Il cammino quindi e della forma π1π2 con π1 cammino da s a w e π2 cammino da w a u .Ma il cammino π1, essendo formato solo da nodi neri tranne l’ultimo, ha costo maggiore o uguale a quello di π, e quindi amaggior ragione π1π2 ha costo maggiore o uguale a quello di π.

Quindi, aggiungendo il nodo u estratto dalla coda all’insieme dei nodi neri, l’invariante (1) vale ancora, ossia, e ancoravero che per tutti i nodi neri, compreso il nuovo nodo nero u , e stato trovato il cammino minimo.

2. Poiche l’insieme dei nodi neri risulta modificato per l’aggiunta di u , occorre pero ripristinare l’invariante (2): per ogninodo v in Q, dist[v ] deve essere la lunghezza del minimo fra i cammini da s a v i cui nodi sono tutti, eccetto v neri; maadesso fra i nodi neri c’e anche u , quindi bisogna controllare se per qualche nodo v adiacente a u il cammino da s a vpassante per u e piu corto del cammino trovato precedentemente, e in tal caso aggiornare dist[v ] e parent[v ].

Postcondizione: al termine dell’esecuzione dell’algoritmo la coda e vuota, quindi tutti i nodi sono neri. Poiche vale l’invariante(1), per ogni nodo e stato trovato il cammino minimo da s .Nota: per dimostrare che il ciclo mantiene l’invariante (1), che e quello che interessa, e necessario dimostrare che il ciclo mantieneanche l’invariante (2).

Complessita Se la coda a priorita e realizzata come sequenza non ordinata, ogni inserimento in coda o modifica della priorita hacomplessitaO(1), ma l’estrazione del minimo ha complessitaO(n), quindi la complessita dell’algoritmo eO(n2). Analogamen-te se la coda a priorita e realizzata come sequenza ordinata. Nella versione di Johnson, se n e m sono il numero rispettivamentedei nodi e degli archi, si ha:

• inizializzazione di tutti i nodi come bianchi: O(n)

• n estrazioni dallo heap: O(n log n)

• ciclo interno: ogni arco viene percorso una volta, e per ogni nodo adiacente si ha eventuale moveUp nello heap, quindiO(m log n)

Complessivamente si ha quindi O((m + n) log n). Si noti che se il grafo e denso, cioe m = O(n2), la complessita diventaO(n2 log n), quindi peggiore della versione originale quadratica.

4.4 Algoritmo di PrimDef. 4.3 [Minimo albero ricoprente] Dato un grafo G connesso, non orientato e pesato, un minimo albero ricoprente5 di G e unalbero ricoprente di G in cui la somma dei pesi degli archi e minima.

Un minimo albero ricoprente di G e quindi un sottografo di G tale che:

• sia un albero libero, ossia connesso e aciclico

• contenga tutti i nodi di G

• la somma dei pesi degli archi sia minima.

Esempi di applicazione: costruzione di reti di computer, linee telefoniche, rete elettrica, etc.Idea: simile a Dijkstra, ma si prende ogni volta, fra tutti i nodi adiacenti a quelli per cui si e gia trovato il minimo (neri), quelloconnesso a un nodo nero dall’arco di costo minimo, cioe si cerca il nodo “piu vicino” all’albero gia costruito (poi, come inDijkstra, si aggiornano gli altri nodi).

Prim(G,s)for each (u nodo in G) marca u come non visitato //necessariofor each (u nodo in G) dist[u] = ∞parent[s] = null; dist[s] = 0Q = heap vuotofor each (u nodo in G) Q.add(u, dist[u])

5In inglese minimum spanning tree.

38

while(Q non vuota)u = Q.getMin() //estraggo nodo a minima distanza dai nerimarca u come visitato (nero)for each ((u,v) arco in G)

if (v non visitato && cu,v < dist[v] )parent[v] = u; dist[v] = cu,vQ.changePriority(v,dist[v]) //moveUp

Nota: a differenza di quanto accade in Dijkstra, occorre un controllo esplicito che i nodi adiacenti al nodo u estratto dalla codanon siano gia stati visitati, perche non e detto che per un nodo v gia visitato il test cu,v < dist[v] sia falso.

Correttezza Sia T l’albero di nodi neri (non in Q) corrente. L’invariante e composta di due parti:

1. T ⊆ MST per qualche MST minimo albero ricoprente di G

2. per ogni nodo u 6= s in Qdist[u] = costo minimo di un arco che collega u a un nodo nero.

(se questo arco non esiste consideriamo il costo minimo =∞).L’invariante vale all’inizio:

1. vale banalmente perche T e vuoto (non ci sono nodi neri)

2. vale banalmente perche non ci sono nodi neri e la distanza e per tutti infinito, tranne che per s .

L’invariante si mantiene.

1. Viene estratto dalla coda un nodo u con dist[u] minima, cioe connesso a un nodo nero y da un arco di costo minimo tratutti quelli che “attraversano la frontiera”, cioe uniscono un nodo nero a un nodo non nero. L’arco (y, u) diventa quindiparte dell’albero di nodi neri corrente. Dimostriamo che aggiungendo tale arco si ha ancora un sottoalbero di un minimoalbero ricoprente di G .

Supponiamo per assurdo che aggiungendo (y, u) a T l’albero ottenuto non appartenga a nessun minimo albero ricoprentedi G . Per l’invariante (1), T ⊆ MST per un certo MST minimo albero ricoprente di G . MST , essendo un alberoricoprente, per definizione e un sottografo connesso che connette tutti i nodi di G : quindi in MST , se non c’e l’arco (y, u),ci deve essere un altro cammino da y a u . Questo cammino dovra contenere un (primo) arco (x, z) che “attraversa lafrontiera”, ossia connette un nodo di T a un nodo non di T .

Poiche MST e un albero, quindi ogni coppia di nodi e connessa da un unico cammino, se eliminiamo l’arco (x, z) ottenia-mo un grafo non connesso, costituito da due alberi (sottografi connessi aciclici), siano T1 e T2. Quindi se consideriamo ilsottografo formato da T1, T2 e l’arco (y, u) otteniamo:

• nuovamente un albero

• che contiene tutti i nodi di G , quindi e un albero ricoprente

• in cui la somma dei pesi degli archi e minore o uguale di quella di MST , in quanto differisce da quest’ultimo soloper l’arco (y, u) al posto dell’arco (x, z), e cy,u ≤ cx,z dato che cy,u e il minimo costo di un arco da un nodo nero aun nodo non nero.

Quindi e un minimo albero ricoprente che contiene l’arco (y, u), contro l’ipotesi per assurdo.

2. L’insieme dei nodi neri risulta modificato per l’aggiunta di u , quindi occorre ripristinare l’invariante (2), controllando seper qualche nodo v non nero e adiacente a u l’arco (u, v) ha costo minore del precedente arco che univa v a un nodo nero,e in tal caso aggiornare l’arco e la distanza.

Postcondizione: all’uscita dal ciclo tutti i nodi sono neri, quindi T connette tutti i nodi, cioe e un albero ricoprente di G . Perl’invariante (1), T ⊆ MST per qualche MST minimo albero ricoprente, quindi T = MST .Come in Dijkstra, si noti che per dimostrare che il ciclo mantiene l’invariante (1) e necessario dimostrare che il ciclo mantieneanche l’invariante (2).Nota: L’algoritmo di Prim genera un albero radicato di radice s , ma il minimo albero ricoprente e per definizione un albero nonradicato, quindi e possibile ottenere lo stesso a partire da nodi diversi. In particolare si puo dimostrare che se i pesi degli archisono tutti distinti il minimo albero ricoprente e unico.L’analisi della complessita e esattamente la stessa dell’algoritmo di Dikstra, quindi O((n+m) log n).

39

4.5 Algoritmo di KruskalAnche questo algoritmo risolve il problema del minimo albero ricoprente. In particolare, il minimo albero ricoprente vienecostruito mantenendo una foresta alla quale si aggiunge a ogni iterazione un nuovo arco che unisce due sottoalberi distinti.Quindi l’algoritmo di Kruskal, a differenza di quello di Prim, non costruisce l’albero a partire da un nodo scelto come radice, macome un insieme di archi che alla fine risulta essere un grafo connesso aciclico, quindi un albero libero.Algoritmo astratto:

Kruskal(G)s = sequenza archi di G in ordine di costo crescenteT = foresta formata dai nodi di G e nessun arcowhile (s non vuota)

estrai da s il primo elemento (u,v)if (u,v non connessi in T) T = T + (u,v)

return T

Nella sequenza non si fa nessun reinserimento o variazione di ordine quindi non e una coda ma una semplice sequenza ordinata,realizzabile per esempio con un array.Ottimizzazione: un albero di n nodi ha n − 1 archi, quindi si puo interrompere il ciclo dopo aver aggiunto all’albero n − 1 archi.

Kruskal(G)s = sequenza archi di G in ordine di costo crescenteT = foresta formata dai nodi di G e nessun arcocounter = 0while (counter < n-1)

estrai da s il primo elemento (u,v)if (u,v non connessi in T) T = T + (u,v)counter++

return T

Correttezza Simile a Prim. Invariante: T ⊆ MST per qualche MST minimo albero ricoprente di G .All’inizio vale banalmente perche in T non ci sono archi.Si mantiene, infatti: si sceglie un arco (u, v) di costo minimo tra quelli non ancora inseriti in T .

• Se u e v appartengono a uno stesso albero nella foresta T , aggiungendo l’arco (u, v) si avrebbe un ciclo, quindi esso vienecorrettamente scartato, T rimane uguale e l’invariante vale ancora.

• Se u e v appartengono a due alberi distinti nella foresta T , dimostriamo che aggiungendo l’arco (u, v) a T si ha ancorauna foresta contenuta in un minimo albero ricoprente. Per assurdo supponiamo che non sia cosı. Per l’invariante, tutti gliarchi di T appartengono a un minimo albero ricoprente di G , sia MST . Se in MST non c’e l’arco (u, v), ci deve essereun altro cammino che connette u a v . Tale cammino deve contenere un arco (x, y) che connette un nodo x dell’albero Tu

che contiene u con un nodo y che non appartiene a tale albero, dato che v non vi appartiene. Tale arco non puo appartenerealla foresta corrente T , perche in tal caso sarebbe un arco di Tu . Quindi tale arco e ancora in s, quindi cu,v ≤ cx,y .

Se eliminiamo l’arco (x, y) da MST , otteniamo due alberi non connessi fra loro, e quindi se aggiungiamo a questi duealberi l’arco (u, v) otteniamo, analogamente a Prim:

– nuovamente un albero

– che contiene tutti i nodi di G , quindi e un albero ricoprente

– in cui la somma dei pesi degli archi e minore o uguale di quella di MST , in quanto differisce da quest’ultimo soloper l’arco (u, v) al posto dell’arco (x, y), e cu,v ≤ cx,y .

Quindi e un minimo albero ricoprente che contiene l’arco (u, v), contro l’ipotesi per assurdo.

Postcondizione: all’uscita dal ciclo si ha necessariamente un unico albero, perche l’algoritmo ha esaminato tutti gli archi di Gunendo ogni volta due alberi di T se non ancora connessi (ossia, ha inserito n−1 archi, come si vede direttamente nella versioneottimizzata). Quindi alla fine T e un unico albero, sottoalbero di un minimo albero ricoprente di G contenente tutti i nodi di G ,quindi e un minimo albero ricoprente di G .Complessita algoritmo astratto: il problema e controllare se due nodi sono gia connessi. Farlo in modo banale con una visita deidue alberi richiede tempo O(n) nel caso peggiore, quindi si ha O(m · n). Per migliorare l’efficienza possiamo implementare laforesta con una struttura union-find, vedi sezione 3.2.

40

Kruskal(G)s = sequenza archi di G in ordine di costo crescenteT = foresta formata dai nodi di G e nessun arcoUF = struttura union-find vuotafor each (u nodo in G) UF.makeSet(u)while (s non vuota)

estrai da s il primo elemento (u,v)if (UF.find(u) 6= UF.find(v)) T = T + (u,v)

UF.union(u,v)return T

Si noti che si ha una corrispondenza biunivoca tra gli alberi della foresta corrente T e gli insiemi della struttura union-find: duenodi appartengono a uno stesso albero in T se e solo se appartengono a uno stesso insieme nella struttura union-find.Ottimizzazione: dopo due find che danno lo stesso risultato, si farebbe una union che riesegue le due find. E convienentedefinire un’operazione specializzata per l’algoritmo di Kruskal: union_by_need(x,y) che restituisce un booleano, con laseguente specifica:

• se x e y appartengono allo stesso insieme restituisce falso

• se x e y appartengono a due insiemi diversi, effettua l’unione e restituisce vero.

In questo modo il corpo del ciclo nell’algoritmo di Kruskal diventa:

estrai da s il primo elemento (u,v)if (UF.union_by_need(u,v))

T = T + (u,v)

Complessita dell’algoritmo di Kruskal nella versione con union-find:

• ordinamento degli archi: O(m logm)

• n makeSet , 2m find e n − 1 union: “quasi” O(n+m).

Complessivamente, poiche m = O(n2), e log n2 = 2 log n , possiamo anche dire che la complessita e O(m log n).

4.6 Ordinamento topologicoE facile vedere che in un grafo orientato aciclico (DAG) la relazione sull’insieme dei nodi “v e raggiungibile da u” e un ordineparziale, vedi definizione A.1. Un ordine totale, vedi definizione A.2, che “raffina” questo ordine parziale si chiama ordinetopologico.

Def. 4.4 [Ordine topologico] Un ordine topologico su un grafo orientato aciclico G = (V ,E ) e un ordine totale (stretto) < suV tale che, per ogni u, v ∈ V :

(u, v) ∈ E ⇒ u < v

Problema: dato un DAG trovare un ordine topologico. E un problema rilevante per scheduling di job, realizzazione di diagrammaPERT delle attivita, ordine di valutazione delle caselle in un foglio di calcolo, ordine delle attivita specificate da un makefile, etc.Si vede facilmente che possono esistere diversi ordini topologici per lo stesso grafo.

Def. 4.5 In un grafo orientato definiamo un nodo sorgente (source) se non ha archi entranti, pozzo (sink) se non ha archi uscenti.

E facile vedere che in un grafo orientato aciclico esistono sempre almeno un nodo pozzo e un nodo sorgente: infatti, se perassurdo cosı non fosse a partire da un nodo qualunque si potrebbe sempre costruire un ciclo. Quindi, esiste sempre un ordinetopologico: infatti esiste sempre un nodo sorgente, eliminando questo dal grafo con tutti i suoi archi uscenti esiste sempre unnodo sorgente nel grafo restante, e cosı via.Questa osservazione porta direttamente ad un ovvio algoritmo astratto. Per evitare di modificare il grafo e trovare in tempocostante, a ogni passo, un nodo sorgente, possiamo memorizzare per ogni nodo il suo indegree. Invece di rimuovere un arco(u, v) si decrementa il valore di indegree per il nodo v . Quando il valore di indegree per un nodo diventa zero, lo si inserisce inun insieme di nodi sorgente da cui si estrae ogni volta il nodo successivo da inserire nell’ordine topologico.Si ottiene quindi il seguente algoritmo (n numero nodi, m numero archi):

41

topologicalsort(G)S = insieme vuotoOrd = sequenza vuotafor each (u nodo in G) indegree[u] = indegree di u //m passifor each (u nodo in G) if (indegree[u] = 0) S.add(u) //n passiwhile (S non vuoto) // in tutto m passi

u = S.remove()Ord.add(u) //aggiunge in fondofor each ((u,v) arco in G)

indegree[v]--if (indegree[v]=0) S.add(v)

return Ord

La complessita e quindi O(n+m).Vediamo ora un algoritmo alternativo che consiste essenzialmente in una visita in profondita. Riprendiamo l’algoritmo per lavisita in profondita ricorsiva visto precedentemente, modificato leggermente in modo da avere una visita completa (ossia, anchedi un grafo non connesso) e una marcatura “nero” inutile ai fini dell’algoritmo che evidenzia la fine della visita.

DFS(G)for each (u nodo in G) marca u come biancoT = foresta formata dai nodi di G e nessun arcofor each (u nodo in G) if (u bianco) DFS(G,u,T)

DFS(G,u,T)//inizio visitavisita u; marca u come grigiofor each ((u,v) arco in G)

if (v bianco)T = T + (u,v)DFS(G,v,T)

//marca u come nero//fine visita

Indichiamo ora esplicitamente nell’algoritmo il tempo di inizio e fine visita utilizzando dei timestamp (per semplicita assumiamoun contatore time globale).

DFS(G)for each (u nodo in G) marca u come biancoT = foresta formata dai nodi di G e nessun arcotime = 0for each (u nodo in G) if (u bianco) DFS(G,u,T)

DFS(G,u,T)time++; start[u] = time //inizio visitavisita u; marca u come grigiofor each ((u,v) arco in G)

if (v bianco)T = T + (u,v)DFS(G,v,T)

time++; end[u] = time //marca u come nero//fine visita

Proprieta della visita: se G e aciclico, per ogni (u, v), in qualunque visita in profondita di G si ha:

end[v ] < end[u]

Prova (semi-formale): l’arco (u, v) viene esaminato durante la visita del nodo u , quindi:

• v non puo essere grigio, perche questo significherebbe che c’e un cammino da v a u , mentre G e aciclico

• se v e bianco, viene effettuata la chiamata DFS(G,v,T), ossia inizia la visita di v , quindi dovra essere necessariamenteend[v ] < end[u]

42

• se v e nero, la sua visita e gia terminata, quindi si ha end[v ] < end[u].

Quindi, l’ordine dei nodi di G secondo il tempo di fine visita in una visita in profondita e l’inverso di un ordine topologico. Diconseguenza, per ottenere un ordine topologico dei nodi di un DAG e sufficiente effettuare una visita in profondita, inserendo aogni fine visita il nodo in una sequenza ordinata. La complessita e semplicemente quella della visita, quindi O(n + m).

4.7 Componenti fortemente connesseDef. 4.6 In un grafo orientato G , due nodi u e v si dicono mutuamente raggiungibili, o fortemente connessi, se ognuno dei duee raggiungibile dall’altro, ossia se esistono un cammino da u a v e un cammino da v a u , ossia se u e v appartengono allo stessociclo.

E immediato vedere che la relazione di mutua raggiungibilita o connessione forte, che indichiamo con ↔, e una relazione diequivalenza, vedi definizione A.3.

Def. 4.7 [Componente fortemente connessa] In un grafo orientato G , le componenti fortemente connesse sono le classi diequivalenza della relazione↔, ossia i sottografi massimali di G i cui nodi sono tutti fortemente connessi tra loro.

Passando al quoziente rispetto all’equivalenza↔, si ottiene un grafo G↔ detto grafo quoziente in cui i nodi sono le componentifortemente connesse di G ed esiste un arco (C, C′) se e solo se esiste un arco da un nodo in C a un nodo in C′.E chiaro che il grafo quoziente risulta essere aciclico, quindi su di esso esiste un ordine topologico.

Def. 4.8 Una componente fortemente connessa di un grafo orientato e una sorgente o un pozzo se e, rispettivamente, un nodosorgente o pozzo nel grafo quoziente.

In una visita in profondita di un grafo G , il tempo di fine visita end(C) di una componente fortemente connessa C e il massimodei tempi di fine visita dei nodi appartenenti a C.

Lemma 4.9 Se C e C′ sono due componenti fortemente connesse del grafo G , ed esiste un arco da (un nodo di) C a (un nodo di)C′, allora in qualunque visita in profondita di G si ha:

end(C′) < end(C)

Dimostrazione (semi-formale) Si hanno due casi.

• Il primo nodo visitato di C e C′ e in C, sia u . Allora devono essere visitati tutti i nodi di C e C′ prima di terminare la visitadi u , quindi:

end(C′) < end(u) = end(C)

• Il primo nodo visitato di C e C′ e in C′. Allora, dato che non puo esistere un cammino da C′ a C, la visita attraversa tutti inodi di C′ prima di qualunque nodo di C, ossia la visita dei nodi di C iniziera dopo, e terminera anche dopo, la visita deinodi di C′, quindi:

end(C′) < end(C).

Teorema 4.10 In una visita in profondita di un grafo orientato il nodo avente il massimo tempo di fine visita appartiene a unacomponente fortemente connessa sorgente.

Dimostrazione Sia u il nodo avente il massimo tempo di fine visita. Se la componente fortemente connessa C cui appartiene unon fosse una sorgente, ci sarebbe un arco da un altra componente fortemente connessa C′ a C. Allora, per il lemma precedente,avremmo end(C′) < end(C), e quindi end(u) non sarebbe il massimo tempo di fine visita.

Teorema 4.11 In una visita in profondita di un grafo orientato la visita di un nodo appartenente a una componente fortementeconnessa pozzo C visita tutti e soli i nodi di C.

Dimostrazione Ovvio, perche tutti i nodi raggiungibili vengono visitati e non c’e nessun arco uscente da una componentefortemente connessa pozzo.Si noti che non vale la proprieta simmetrica di quella del Teorema 4.10, ossia il nodo avente il minimo tempo di fine visita nonappartiene necessariamente a una componente fortemente connessa pozzo. Non e quindi possibile con una visita in profonditadi un grafo trovare le componenti fortemente connesse pozzo.Osservazione: una componente fortemente connessa sorgente in un grafo orientato G e una componente fortemente connessapozzo nel grafo trasposto GT, cioe nel grafo che si ottiene da G invertendo l’orientamento degli archi.Dalle precedenti proprieta e facilmente ricavabile un algoritmo per trovare le componenti fortemente connesse di un grafo G :

43

• si effettua una visita in profondita inserendo i nodi in una sequenza Ord in ordine di fine visita

• si estrae via via da Ord l’ultimo nodo u , per il Teorema 4.10 u si trova in una componente fortemente connessa sorgentenel grafo ottenuto da G non considerando le componenti fortemente connesse precedenti

• per trovare tutti i nodi di tale componente fortemente connessa, che per l’osservazione sopra e una componente forte-mente connessa pozzo nel grafo trasposto, per il Teorema 4.11 basta effettuare una visita dei nodi (non ancora visitati)raggiungibili da u nel grafo trasposto GT

• non e necessario durante le visite modificare i grafi G e GT perche basta, come al solito, marcare i nodi visitati.

Piu concretamente:

SCC(G)DFS(G,Ord) //aggiunge i nodo visitati a Ord in ordine di fine visitaGT = grafo trasposto di GOrd↔ = sequenza vuota //ordine topologico delle c.f.c.while (Ord non vuota)

u = ultimo nodo non visitato in Ord //si trova in una c.f.c. sorgenteC = insieme di nodi vuotoDFS(GT,u,C) //aggiunge nodi visitati in COrd↔.add(C) //aggiunge in fondo

return Ord↔

La sequenza delle componenti fortemente connesse ottenute e in ordine topologico, perche ogni volta si individua una compo-nente fortemente connessa a cui arriva un arco da una delle precedenti. Se il grafo e aciclico le componenti fortemente connessesono i singoli nodi, quindi l’algoritmo restituisce semplicemente un ordine topologico dei nodi.Complessita:

• visita in profondita del grafo: O(n+m)

• generazione del grafo trasposto: O(n+m)

• successive visite del grafo trasposto: O(n+m)

quindi complessivamente O(n+m).

5 Teoria della NP-completezzaSignifica “Non deterministic Polinomial time” perche la classe NP fu originariamente studiata nel contesto degli algoritmi nondeterministici. Noi utilizzeremo una nozione equivalente piu semplice, quella di verifica.I problemi vengono suddivisi in termini di complessita computazionale in due classi principali:

• quelli risolvibili con un algoritmo polinomiale (T (n) = O(nk)) sono considerati trattabili (facili)

• quelli per cui non esiste un algoritmo polinomiale (T (n) = Ω(kn)) non trattabili (difficili).

Questo per considerazioni di ordine “pratico”:

• solitamente le complessita O(nk) hanno k piccoli, e possono essere ulteriormente migliorate

• per diversi modelli di calcolo, un problema che puo essere risolto in tempo polinomiale in un modello, puo esserlo anchein un altro

• la classe dei problemi risolvibili in tempo polinomiale ha interessanti proprieta di chiusura, in quanto i polinomi sono chiusiper addizione, moltiplicazione e composizione. Quindi per esempio se l’output di un algoritmo polinomiale e utilizzatocome input per un altro l’algoritmo composto e polinomiale.

Ci sono anche algoritmi dei quali non si conosce la complessita. Tipicamente, non si e ancora riusciti a dimostrare che T (n) =O(nk) oppure T (n) = Ω(kn).Informalmente, la classe P e quella dei problemi risolvibili in tempo polinomiale, la classe NP e quella dei problemi verificabiliin tempo polinomiale. Risolvere un problema significa che data una sua istanza ne fornisco una soluzione. Verificare un problemasignifica che data una sua istanza e una sua soluzione (certificato), controllo se la soluzione risolve effettivamente l’istanza del

44

problema. Ne consegue che P ⊆ NP, perche posso usare un qualsiasi algoritmo di P per generare la soluzione e confrontarla conun certificato. Quello che non si sa e se P = NP, oppure P ⊂ NP, ossia se ci sono problemi verificabili in tempo polinomialeche non sono risolvibili in tempo polinomiale. Sappiamo risolvere i problemi NP solo in tempo esponenziale, ma non possiamoescludere che esistano algoritmi in tempo polinomiale per risolverli.All’interno della classe NP vi e una classe di problemi ritenuti “piu difficili” di tutti gli altri. Questa e la classe dei problemiNP-completi (NP-C). I problemi NP-C godono di un’importante proprieta: se si scoprisse un algoritmo che risolve uno di questiproblemi in tempo polinomiale, tutti i problemi di NP-C (e come conseguenza tutti quelli di NP) sarebbero risolvibili in tempopolinomiale. Si dimostrerebbe quindi che P = NP.Nel seguito:

• formalizziamo la nozione di problema

• mostriamo come astrarre dal particolare linguaggio usato per descrivere il problema

• formalizziamo le classi P, NP, NP-C

• troviamo un (primo) problema in NP-C

• descriviamo altri problemi in NP-C.

5.1 Problemi astratti e concreti e classe PDef. 5.1 Un problema (astratto) e una relazione P ⊆ I × S , dove I e l’insieme degli input (o istanze del problema) e S el’insieme delle soluzioni.

In generale per ogni istanza la soluzione puo non essere unica (per esempio puo esserci piu di un cammino minimo).

Def. 5.2 Un problema (astratto) di decisione P e un problema (astratto) in cui ogni input ha come soluzione vero oppure falso,ossia P : I → T ,F.

Problemi di ricerca sono quelli in cui si cerca una soluzione. Problemi di ottimizzazione sono quelli in cui ci sono diversesoluzioni e se ne cerca una che sia “ottima” (per esempio, il minimo albero ricoprente, oppure il cammino minimo). La teoriadella complessita computazionale si concentra sui problemi di decisione, in quanto in genere, per ogni problema di altro tipoP , e possibile dare un problema di decisione Pd tale che risolvendo il primo si sappia risolvere il secondo. Nel caso di unproblema di ricerca si restituisce vero se e solo se una soluzione esiste, nel caso di un problema di ottimizzazione si pone unalimitazione al valore da ottimizzare. Per esempio: trovare il cammino minimo tra una coppia di nodi in un grafo e un problemadi ottimizzazione. Un problema di decisione collegato e il seguente: dati due nodi determinare se esiste un cammino lungo al piuk. Infatti se abbiamo un algoritmo per risolvere il primo problema, un algoritmo che risolve il secondo si ottiene eseguendo ilprimo e poi confrontando il valore minimo ottenuto con k. In altri termini il problema di decisione Pd e “piu facile” del problemaoriginale P , quindi se proviamo che Pd e “difficile” indirettamente proviamo che lo e anche P .Da ora in poi quindi parleremo semplicemente di “problema” intendendo problema di decisione.Dato un problema P : I → T ,F, diciamo che un algoritmo A risolve P se, per ogni input i ∈ I , A(i) = P(i). Un problemaP e nella classe Time(f(n)) se e solo se esiste un algoritmo di complessita temporale O(f(n)) che lo risolve, dove n e ladimensione dell’input. Analogamente, P e nella classe Space(f(n)) se e solo se esiste un algoritmo di complessita spazialeO(f(n)) che lo risolve. Sia P =

⋃c≥0 Time(nc), PSpace =

⋃c≥0 Space(nc), ExpTime =

⋃c≥0 Time(2n

c

).E facile vedere che P ⊆ PSpace in quanto un algoritmo che impiega un tempo polinomiale puo accedere al piu a un numeropolinomiale di locazioni di memoria. Si puo provare inoltre che PSpace ⊆ ExpTime (intuitivamente, assumendo per semplicitale locazioni di memoria binarie, nc locazioni di memoria possono trovarsi in al piu 2n

c

stati diversi). Non si sa se queste inclusionisiano strette (sono problemi aperti). Sappiamo invece che P ⊂ ExpTime, ossia che esiste (almeno) un problema che puo essererisolto in tempo esponenziale ma non polinomiale.Notiamo che la definizione precedente e semi-formale, perche non essendoci un formato preciso per l’input parliamo generica-mente di “dimensione”.Per essere piu precisi, possiamo uniformare tutti i possibili input codificandoli come stringhe binarie.

Def. 5.3 Un problema concreto P e un problema il cui insieme di istanze e l’insieme delle stringhe binarie, ossia P : 0, 1? →T ,F.

E equivalente considerare qualunque alfabeto con cardinalita almeno 2. Un problema astratto P puo essere rappresentato inmodo concreto tramite una codifica, ossia una funzione iniettiva:

45

c : I → 0, 1?

Il problema concreto c(P) e definito da c(P)(x ) = T se e solo se x = c(i) e P(i) = T , ossia assumiamo convenzionalmenteche la soluzione sia falso sulle stringhe che non sono codifica di nessun input.Tuttavia, codifiche diverse possono portare a tempi computazionali diversi. Supponiamo per esempio che l’input i di P sia unnumero naturale e che il tempo di esecuzione dell’algoritmo sia Θ(i), per esempio un algoritmo che controlla se un numero eprimo dividendolo per tutti i precedenti. Allora, se il numero e codificato nell’usuale formato binario si ha |c(i)| = blog ic + 1e quindi la complessita dell’algoritmo in funzione della stringa e esponenziale, mentre se e codificato in formato unario lacomplessita e polinomiale.Possiamo raggruppare tutte le codifiche che producono la stessa complessita computazionale. Se esistono due funzioni f12 e f21calcolabili in tempo polinomiale tali che:

• se f12(x ) = y , x = c1(i) se e solo se y = c2(i)

• se f21(y) = x , x = c1(i) se e solo se y = c2(i) allora c1 e c2 si dicono correlate polinomialmente.

Se c1 e c2 sono correlate polinomialmente, allora usare una o l’altra e equivalente.

Lemma 5.4 Sia P un problema astratto e siano c1, c2 due codifiche di P correlate polinomialmente. Allora c1(P) e risolvibilein tempo polinomiale se e solo se c2(P) e risolvibile in tempo polinomiale.

Dimostrazione Dimostriamo un’implicazione, l’altra e simmetrica. Dato un algoritmo in tempo polinomiale A1 che risolvec1(P), un algoritmo in tempo polinomiale A2 che risolve c2(P) puo essere ottenuto eseguendo, a partire da y = c2(i), primal’algoritmo in tempo polinomiale che calcola x = f21(y) = c1(i), poi A1(x ). Si noti che |x | = O(|y |) perche essendol’algoritmo polinomiale l’output e anch’esso polinomiale, quindi A2 e polinomiale anche rispetto a |y |. L’algoritmo A2 risolvec2(P) in quanto per y = c2(i) si ha A2(y) = A1(c1(i)) = P(i). Se non esiste un input i tale che y = c2(i), non esiste neancheper x e quindi si ha A2(y) = A1(x ) = F .Come visto sopra, una descrizione artificiosamente lunga puo far apparire la complessita di un algoritmo piu bassa. Al limite,la codifica potrebbe contenere al suo interno (parte della) soluzione, per esempio nella codifica di un grafo potrei includere tuttii suoi cicli semplici. Diremo che una codifica e ragionevole se questo non succede, quindi non sono introdotti dati irrilevanti enon vi e una generazione esponenziale di dati per la rappresentazione di un’istanza del problema.Assumeremo d’ora in poi che le codifiche siano ragionevoli, in particolare che la codifica di un intero sia correlata polinomial-mente alla sua rappresentazione binaria, la codifica di un insieme sia correlata polinomialmente alla lista delle codifiche deglielementi con opportuni separatori, e da queste si derivino codifiche ragionevoli per altri oggetti matematici come n-uple, grafi eformule.Un problema concreto P e nella classe Time(f(n)) se e solo se esiste un algoritmo di complessita temporale O(f(n)) che lorisolve, dove n = |x | e la lunghezza dell’input. Analogamente, P e nella classe Space(f(n)) se e solo se esiste un algoritmo dicomplessita spaziale f(n) che lo risolve.Un problema di decisione concreto puo anche essere visto come un linguaggio sull’alfabeto 0, 1, ossia il sottoinsieme formatoda tutte le stringhe con soluzione vero.

Def. 5.5 Data una stringa x ∈ 0, 1?, un algoritmo A accetta x se A(x ) = T , rifiuta x se A(x ) = F .

Si noti che stringa non accettata non significa stringa rifiutata perche l’algoritmo potrebbe non terminare.

Def. 5.6 Un algoritmo A accetta un linguaggio P se accetta ogni stringa del linguaggio, ossia x ∈ P implica A(x ) = T . Unalgoritmo A decide un linguaggio P se accetta ogni stringa del linguaggio e rifiuta ogni altra stringa, ossia x ∈ P implicaA(x ) = T , x 6∈ P implica A(x ) = F .

Possiamo quindi definire equivalentemente P come la classe dei linguaggi P per cui esiste un algoritmo polinomiale che decideP . Si prova che P e anche la classe dei linguaggi per cui esiste un algoritmo polinomiale che accetta P . Infatti, dato un algoritmoA che accetta P in tempo limitato da p polinomio fissato, un algoritmo che risolve P puo essere costruito nel modo seguente:data un’istanza x di P di lunghezza n, simuliamo l’algoritmo A per il tempo p(n). Trascorso questo tempo, se A ha accettato xallora la soluzione e vero, altrimenti falso.

5.2 Classe NPIntroduciamo ora il significato della classe NP con degli esempi.Consideriamo le formule su un insieme di variabili definite dalla seguente sintassi:

46

x :: = . . .

φ :: = x | φ | φ1 ∧ φ2 | φ1 ∨ φ2 | ∃x .φ | ∀x .φ

In particolare, le formule in forma normale congiuntiva (CNF) e le formule quantificate sono definite nel modo seguente:

l :: = x | x letteralec :: = l1 ∨ . . . ∨ ln clausolaφCNF :: = c1 ∧ . . . ∧ cn formula in CNF

φQ :: = φCNF | ∃x .φQ | ∀x .φQ formula quantificata

Problema della soddisfacibilita SAT : data una formula in forma normale congiuntiva, determinare se esiste un’assegnazione divalori di verita alle variabili che la renda vera.Problema delle formule quantificate: data una formula quantificata, determinare se e vera.Entrambi i problemi possono essere facilmente risolti in tempo esponenziale (possiamo prendere come dimensione dell’istanzadel problema il numero di variabili).

eval(phi)return eval(phi,empty)

eval(exists x.phi,env)return eval(phi,env.add(x,true)) or eval(phi,env.add(x,false))

eval(forall x.phi,env) =return eval(phi,env.add(x,true) and eval(phi,env.add(x,false))

...

sat(phi) //con variabili x_1 ... x_nreturn eval(exists x_1. ... exist x_n.phi)

Anzi sono in PSpace in quanto usano un numero lineare di locazioni di memoria.Questo esempio mostra come spesso un algoritmo di decisione generi, in caso positivo, una “prova”, detta certificato, chedimostra la verita della proprieta da verificare, per esempio, nel caso della soddisfacibilita, l’assegnazione di valori alle variabiliche rende vera la formula. Mentre nel caso della soddisfacibilita verificare la validita di un certificato e facile, nel caso delleformule quantificate il “certificato” stesso consta di un numero esponenziale di assegnazioni di valori di verita a variabili. Questosuggerisce l’idea di usare come classificazione la difficolta di verificare se un certificato e valido per un problema. Informalmente,definiamo NP la classe dei problemi che ammettono certificati verificabili in tempo polinomiale. Per esempio, dato che possiamoverificare in tempo polinomiale se un’assegnazione di valori alle variabili rende vera una formula in forma normale congiuntiva,il problema della soddisfacibilita e nella classe NP. Non possiamo dire altrettanto per il problema delle formule quantificate: none noto se sia in NP, ma si congettura che non lo sia.Un altro esempio: problema del ciclo hamiltoniano in un grafo non orientato. E un ciclo semplice che contiene ogni nodo (quindipassa esattamente una volta per ogni nodo). E facile vedere che questo problema e in NP (un certificato e un ciclo), mentre none noto un algoritmo polinomiale che lo risolva.

Def. 5.7 Un algoritmo di verifica per un problema (astratto) P ⊆ I e un algoritmo A : I × C → T ,F, dove C e un insiemedi certificati, ed esiste un certificato y tale che A(x , y) = T se e solo se x ∈ P .

Nel caso dei problemi concreti, si ha I = C = 0, 1?. Il linguaggio verificato da A e l’insieme delle stringhe verificate da A,ossia x | ∃y .A(x , y) = T. Quindi un algoritmo verifica un linguaggio se per ogni stringa del linguaggio esiste un certificatovalido, e non esiste per stringhe che non vi appartengono. Per esempio nel caso del grafo hamiltoniano se non lo e non e possibileesibire un certificato.La classe NP e quindi la classe dei linguaggi che possono essere verificati da un algoritmo polinomiale. Piu precisamente:

Def. 5.8 Un linguaggio P e nella classe NP se e solo se esistono un algoritmo di verifica polinomiale A e una costante c > 0 taliche

P = x | ∃y .A(x , y) = T , |y | = O(|x|c)

sat_ver(phi,env)return eval(phi,env)

47

Equivalentemente, si puo anche definire NP come la classe dei problemi per cui esiste un algorimo polinomiale non de-terministico che li risolve, tale cioe che se la risposta e positiva ci sia almeno una possibile computazione che dia rispostapositiva.

sat_non_det(phi) //con variabili x_1 ... x_nb_1 = true or b_1 = false...b_n = true or b_n = falsereturn eval(phi, x_1 -> b_1, ..., x_n -> b_n)

Legame con la verifica in tempo polinomiale (informalmente): un algoritmo non deterministico puo sempre essere visto comecomposto di due fasi (vedi esempio sopra):

• una prima fase non deterministica che costruisce un certificato

• una seconda fase deterministica che controlla se questo e un certificato valido.

E facile verificare che P ⊆ NP, perche un algoritmo deterministico e un caso particolare di algoritmo non deterministico, oppureequivalentemente e un caso particolare di algoritmo di verifica in cui si ignora il certificato. Inoltre, la fase deterministica diverifica puo essere eseguita in tempo polinomiale solo se il certificato ha dimensione polinomiale, quindi NP ⊆ PSpace. Sicongettura che entrambe le inclusioni siano proprie, ossia P ⊂ NP ⊂ PSpace ⊂ ExpTime, ma questo non e stato dimostrato.

5.3 Problemi NP-completiI problemi NP-completi sono i “piu difficili” tra i problemi in NP. Ossia, se per qualcuno di questi problemi si trovasse unalgoritmo polinomiale, se ne troverebbe uno per tutti quelli in NP, e quindi si dimostrerebbe che P = NP.Infatti ognuno dei problemi in NP e riducibile a un problema NP-completo, nel senso formalizzato sotto.

Def. 5.9 Dati due problemi concreti P1 e P2, diciamo cheP1 e riducibile polinomialmente a P2, e scriviamoP1 ≤P P2, se esisteuna funzione f : 0, 1? → 0, 1?, detta funzione di riduzione, calcolabile in tempo polinomiale, tale che, per ogni x ∈ 0, 1?,x ∈ P1 se e solo se f(x) ∈ P2.

Per esempio, il problema della soddisfacibilita e polinomialmente riducibile a quello delle formule quantificate.

Lemma 5.10 Dati due problemi concreti P1 e P2 tali che P1 ≤P P2, se P2 ∈ P allora anche P1 ∈ P.

Dimostrazione Dato un algoritmo in tempo polinomiale A2 che risolve P2, un algoritmo in tempo polinomiale A1 che risolveP1 puo essere ottenuto eseguendo, a partire da x , prima l’algoritmo in tempo polinomiale che calcola f(x ), poi A2(f(x )).Analogamente a quanto visto per il Lemma 5.4 l’algoritmo A1 risulta polinomiale. L’algoritmo A1 risolve P1 in quanto A1(x ) =A2(f(x )) = P2(f(x )) = P1(x ).La definizione puo essere generalizzata al caso in cui per risolvere P1 si usa un “piccolo” numero di chiamate a un algoritmoche risolve P2. Questa generalizzazione semplifica molte riduzioni. Per esempio, possiamo far vedere che il problema di trovarese in un grafo esiste un ciclo hamiltoniano, ossia un ciclo che visita ogni vertice esattamente una volta, puo essere ridotto alproblema di trovare se esiste un cammino semplice di lunghezza k tra due nodi di un grafo. Infatti, per verificare se in un grafoesiste un ciclo hamiltoniano, basta verificare che esista un arco u, v tale che u e v siano connessi da un cammino semplice dilunghezza n− 1. In questo caso l’algoritmo per trovare se esiste il cammino viene richiamato al piu tante volte quanto il numerodegli archi, ma la riduzione rimane polinomiale.

Def. 5.11 Un problema concreto P si dice NP-arduo o NP-difficile (in inglese NP-hard) se per ogni problema Q ∈ NP siha Q ≤P P , si dice NP-completo se appartiene alla classe NP ed e NP-arduo. Indichiamo con NP-C la classe dei problemiNP-completi.

Nota: esistono problemi NP-ardui ma non appartenenti alla classe NP.

Teorema 5.12 Se un qualunque problema NP-completo appartiene alla classe P, allora si ha P = NP, o, equivalentemente, se eP 6= NP, quindi esiste almeno un problema in NP non risolvibile in tempo polinomiale, allora nessun problema NP-completo erisolvibile in tempo polinomiale.

48

Dimostrazione Ovvio in base al precedente lemma.Quindi, per risolvere il problema aperto P ?

= NP, basterebbe, per un qualunque problema in NP-C, trovare un algoritmopolinomiale o provare che non ne esiste uno.Per dimostrare che un problema e in NP basta mostrare un algoritmo polinomiale non deterministico che lo risolve, o un algoritmopolinomiale che lo verifica. Come possiamo invece dimostrare che un problema e NP-completo? Una volta dimostrato chealmeno un problema, sia P , e NP-completo, possiamo provare che un altro lo e mostrando la riducibilita di P a questo problema,infatti in questo modo anche il nuovo problema risulta NP-completo per la transitivita della relazione di riducibilita. Bisognaquindi trovare un “primo” problema di cui dimostrare la NP-completezza.Nota metodologica: provare che un problema e NP-completo e utile, perche in tal caso e opportuno cercare un algoritmoapprossimato o ridursi a un sottoproblema per cui si possa trovare un algoritmo polinomiale.Storicamente, il primo problema di cui e stata provata la NP-completezza (da Stephen Cook nel 1971) e il problema dellasoddisfacibilita.

Teorema 5.13 [Teorema di Cook] SAT e NP-completo.

Non diamo la dimostrazione del teorema di Cook. L’idea e la seguente: si definisce un algoritmo che, dato un problema P ∈ NPe un input x per P , costruisce una formula in forma normale congiuntiva che descrive un algoritmo non deterministico per P ,ossia la formula e soddisfacibile se e solo se l’algoritmo restituisce T .Dimostriamo invece la NP-completezza di un altro problema per cui la prova e piu semplice.

Def. 5.14 Dati (la descrizione di) un algoritmo (di verifica) 〈Av 〉, una stringa x e una stringa 1t, il problema dell’arresto limitato(bounded halting problem) BH richiede di decidere se Av verifica x in al piu t passi.

Teorema 5.15 BH e NP-completo.

Dimostrazione E facile vedere che BH appartiene a NP, in quanto si puo costruire un algoritmo di verifica AvBH che, sull’input

((〈Av 〉, x , 1t), y), simula Av su (x , y) per t passi. Nota: occorre assumere che t sia rappresentato in notazione unaria in modoche il tempo sia proporzionale alla dimensione dell’input.Dobbiamo ora dimostrare che ogni problema P ∈ NP e riducibile polinomialmente a BH . Se P ∈ NP, allora esiste un algoritmopolinomiale di verifica Av

P per P , ossia tale che, per ogni input x , esiste un certificato y con |y | = O(|x |) e AvP(x , y) = T

se e solo se x ∈ P . Siano p e q i polinomi fissati che esprimono, rispettivamente, il tempo di esecuzione di AvP in funzione

della lunghezza dell’input e la lunghezza di y in funzione di quella di x . Possiamo ridurre P al problema dell’arresto limitatoattraverso la seguente funzione di riduzione:

fP(x ) = (〈AvP〉, x , 1p(|x|+q(|x |)))

Questa funzione e calcolabile con un algoritmo polinomiale in quanto 〈AvP〉 e una stringa costante. L’algoritmo si limita a

costruire una tripla formata da questa stringa costante, l’input originale x e un numero polinomiale di 1.Si ha inoltre che:x ∈ P ⇔AvP verifica x in t = p(|x|+ q(|x |)) passi⇔

(〈AP〉, x , 1t) ∈ BH .Quindi, se avessi un algoritmo polinomiale ABH che risolve BH , otterrei un algoritmo polinomiale AP per qualunque problemaP in NP nel modo seguente: dato un input x , si richiama l’algoritmo ABH fornendogli in input la descrizione di un algoritmodi verifica 〈Av

P〉 per P , l’input x e 1t con t = p(|x| + q(|x |)) dove p e q sono i polinomi che esprimono la lunghezza di uncertificato e il tempo di esecuzione per 〈Av

P〉.Come anticipato, in genere le dimostrazioni di NP-completezza non si fanno in questo modo diretto, ma facendo vedere che ilproblema si riduce a un altro problema NP-completo. Vediamo degli esempi.

Def. 5.16 Data una formula in 3CNF, ossia in CNF e tale che ogni clausola sia la disgiunzione di esattamente tre letterali, ilproblema della 3-soddisfacibilita 3SAT richiede di verificare se esiste un’assegnazione di valori di verita alle variabili che rendela formula vera.

E un caso particolare del problema di soddisfacibilita, in cui il numero di letterali in ogni clausola e esattamente tre. Nonostantequesta limitazione si puo provare che il problema rimane NP-completo. Questo problema e interessante perche e piu facile daridurre in un altro rispetto alla forma generale.

Teorema 5.17 3SAT e NP-completo.

49

Dimostrazione L’appartenenza a NP e ovvia essendo un caso particolare di SAT . Per dimostrare che e NP-arduo, diamo unariduzione di SAT in 3SAT , ossia mostriamo che ogni formula CNF puo essere trasformata in una formula 3CNF. Anzitutto,scegliamo tre variabili nuove y1, y2, y3 e aggiungiamo alla formula CNF sette nuove clausole che sono tutte le possibili combi-nazioni dei corrispodenti letterali tranne y1 ∨ y2 ∨ y3, in modo tale che l’unica assegnazione di valori a queste variabili che rendevera la loro congiunzione sia y1 = y2 = y3 = T , ossia:

y1 ∨ y2 ∨ y3, y1 ∨ y2 ∨ y3, y1 ∨ y2 ∨ y3, y1 ∨ y2 ∨ y3, y1 ∨ y2 ∨ y3, y1 ∨ y2 ∨ y3, y1 ∨ y2 ∨ y3.

Poi trasformiamo ogni clausola c nella formula in una congiunzione di clausole ognuna di esattamente tre letterali.

• Se c = l , si sostituisce c con l ∨ y1 ∨ y2.

• Se c = l1 ∨ l2, si sostituisce c con l1 ∨ l2 ∨ y1.

• Se c = l1 ∨ l2 ∨ c′ con c′ disgiunzione di almeno un letterale:

– se c′ e un solo letterale non si fa nulla

– altrimenti, si introduce una nuova variabile yc , e si sostituisce c con

yc ∨ c′, l1 ∨ l2 ∨ yc, l1 ∨ yc ∨ y1, l2 ∨ yc ∨ y1.

Le ultime tre clausole implicano che l1 ∨ l2 e equivalente a yc , quindi c e equivalente a yc ∨ c′. A questo punto, siriapplica induttivamente il procedimento a yc ∨ c′.

Per costruzione la congiunzione di tutte le nuove clausole e equivalente alla formula di partenza, e la trasformazione puo essereeffettuata in tempo polinomiale. Quindi SAT ≤P 3SAT .Si puo provare che numerosi altri problemi sono NP-completi usando il problema della 3-soddisfacibilita. Vediamo due esempi:il problema della clique e il problema dell’insieme indipendente.

Def. 5.18 Una clique o cricca in un grafo orientato G = (V ,E ) e un insieme V ′ ⊆ V di nodi tale che per ogni coppia di essiesiste l’arco che li collega, ossia il sottografo indotto da V ′ e completo. La dimensione di una clique e il numero dei suoi nodi. Ilproblema della clique richiede di trovare una clique di dimensione massima in un grafo. Il corrispondente problema di decisionerichiede di determinare se nel grafo esiste una clique di dimensione k.

L’algoritmo banale consiste nell’esaminare tutti i possibili sottoinsiemi di nodi di dimensione k, e ha complessita k2(nk

)se n e il

numero di nodi, che risulta esponenziale se k e funzione di n.

Teorema 5.19 Il problema della clique e NP-completo.

Dimostrazione Un certificato per il problema della clique e una clique di dimensione k. E facile verificare polinomialmentequesto certificato, e questo prova che il problema e in NP. Per dimostrare che il problema e NP-arduo, diamo una riduzionedi 3SAT in questo problema nel modo seguente. Data una formula 3CNF φ formata di k clausole, costruiamo il grafo Gφ nelmodo seguente:

• un nodo per ogni occorrenza di letterale in una clausola, quindi 3k nodi

• un arco tra due occorrenze di letterali se sono in due clausole diverse e non sono uno la negazione dell’altro.

Mostriamo che φ e soddisfacibile se e solo se Gφ contiene una clique di k nodi.

⇒ Se φ e soddisfacibile, significa che esiste un’assegnazione di valori alle variabili tale che almeno un letterale per ogni clau-sola risulta vero. Consideriamo i nodi di Gφ corrispondenti ai letterali scelti. Esiste un arco che collega ogni coppiadi questi nodi, perche sono in clausole diverse e non sono uno la negazione dell’altro, altrimenti non potrebbero esserecontemporaneamente veri. Abbiamo quindi trovato una clique di dimensione k.

⇐ Se Gφ contiene una clique di k nodi, dato che non vi sono archi tra nodi che rappresentano letterali nella stessa clausola,sappiamo che la clique contiene esattamente un nodo per ogni clausola, siano l1, . . . , lk i corrispondenti letterali. Scegliamoun’assegnazione di valori alle variabili tale che l1, . . . , lk risultino veri, cio e possibile in quanto sappiamo che tra di essinon vi sono due letterali che sono uno la negazione dell’altro, altrimenti non vi sarebbe un arco. Con questa assegnazioneogni clausola e soddisfatta, e quindi l’intera formula.

50

Def. 5.20 Un insieme indipendente in un grafo G = (V ,E ) e un insieme V ′ ⊆ V di nodi tale che per ogni coppia di essi nonesiste l’arco che li collega, ossia tale che il sottografo indotto da V ′ non ha archi. La dimensione di un insieme indipendentee il numero dei suoi nodi. Il problema dell’insieme indipendente richiede di trovare un insieme indipendente di dimensionemassima in un grafo. Il corrispondente problema di decisione richiede di determinare se nel grafo esiste un insieme indipendentedi dimensione k.

Teorema 5.21 Il problema dell’insieme indipendente e NP-completo.

Dimostrazione Un certificato per il problema dell’insieme indipendente e un insieme indipendente di k nodi. E facile verificarepolinomialmente questo certificato, e questo prova che il problema e in NP. Per dimostrare che il problema e NP-arduo, defi-niamo una riduzione dal problema della clique nel modo seguente. Dato un grafo G consideriamo il grafo G che ha lo stessoinsieme di nodi e tale che, per ogni coppia di nodi (u, v), in G esiste l’arco (u, v) se e solo se in G non esiste. E immediatovedere che un insieme di nodi definisce una clique in G se e solo se definisce un insieme indipendente in G ′.Si conoscono ormai moltissimi problemi NP-completi, tra questi citiamo:

• commesso viaggiatore: dato un grafo non orientato completo pesato, trovare un ciclo hamiltoniano di costo minimo (nellaversione di decisione stabilire se esiste un ciclo hamiltoniano di costo al piu k)

• zaino: dato uno “zaino” con una certa capacita ed n oggetti a cui sono associati dei pesi, trovare il sottoinsieme di pesomassimo che sia possibile mettere nello zaino (nella versione di decisione trovare se esiste un sottoinsieme di peso ≥ k)

• copertura di vertici: dato un grafo non orientato G = (V ,E ) trovare una copertura di vertici (vertex cover) di dimensioneminima per G , ossia un un insieme V ′ ⊆ V di nodi tale che per ogni arco (u, v) almeno un estremo appartenga a V ′

(nella versione di decisione stabilire se esiste una copertura di vertici di dimensione k)

• colorazione: dato un grafo G = (V ,E ) trovare il minimo k per cui una k-colorazione dei nodi di G , ossia una funzionec : V → 1..k tale che c(u) 6= c(v) se (u, v) ∈ E (nella versione di decisione stabilire se esiste una k-colorazione).

5.4 Algoritmi di approssimazioneNel caso di problemi di ottimizzazione la cui versione decisionale sia NP-completa, puo essere non strettamente necessariotrovare una soluzione ottima. Vediamo come misurare la distanza tra una soluzione “quasi ottima” e una soluzione ottima.

Def. 5.22 Sia P un problema di ottimizzazione. Diciamo che un algoritmo di approssimazione per P ha fattore di approssima-zione ρ(n) (≥ 1) se:

• in un problema di minimizzazione (C∗ ≤ C) si ha C ≤ C∗ρ(n)

• in un problema di massimizzazione (C ≤ C∗) si ha C ≤ C∗ρ(n).

Un modo per riassumere i due requisiti e dire che

max CC∗ ,C∗

C ≤ ρ(n)

ossia il costo C della soluzione prodotta dall’algoritmo su un input di dimensione n differisce di un fattore moltiplicativo≤ ρ(n)dal costo C∗ di una soluzione ottima. Gli algoritmi esatti sono quelli per i quali e esattamente ρ(n) = 1. Il fattore di approssi-mazone ρ(n) e in genere una funzione della dimensione n dell’input, ma a volte e possibile dare algoritmi di approssimazionecon fattore di approssimazione costante, ed esistono persino problemi che possono essere approssimati con qualunque fattoredi approssimazione ε > 0, al prezzo di un tempo di esecuzione piu alto (tipicamente, inversamente proporzionale a ε). Altriproblemi invece sono difficili anche da approssimare, per esempio la colorazione: si e dimostrato che se esistesse un algoritmodi approssimazione per il problema della colorazione con fattore di approssimazione ≤ 4

3 , allora risulterebbe P = NP.Diamo un esempio di algoritmo di approssimazione che risolve un problemi su grafi con fattore di approssimazione costante.

Copertura di vertici Abbiamo visto che si tratta di un problema NP-completo. E possibile tuttavia dare un algoritmoapprossimato molto semplice:

vertex_cover(G)C = insieme di nodi vuoto //coperturaE = insieme archi di Gwhile (E non vuoto) //Inv: C copertura per archi non in E

estrai da E un arco (u,v)

51

C.add(u); C.add(v)for each ((u,w) arco in G) E = E - (u,w)for each ((v,w) arco in G) E = E - (v,w)

return C

Infatti, ogni volta che scegliamo i due estremi u e v di un arco, con essi copriamo non solo l’arco (u, v) ma anche tutti gli altriarchi che hanno u o v come estremi, quindi questi possono essere eliminati. Questo algoritmo ha complessita O(n + m) se ne m sono rispettivamente il numero dei nodi e degli archi. Possiamo provare che l’algoritmo ha fattore di approssimazione 2nel modo seguente: sia A l’insieme degli archi che vengono estratti dall’algoritmo. Una qualsiasi copertura di vertici, inclusa lacopertura ottima C∗, deve contenere almeno un estremo di ognuno di questi archi. Due archi in A non hanno mai un estremocomune, perche ogni volta che si estrae un arco si eliminano tutti quelli con un estremo comune. Quindi non e possibile copriredue archi in A con lo stesso nodo in C∗, quindi si ha: |A| ≤ |C∗|. D’altra parte, si ha |C| = 2|A| perche ogni volta che si estraeun arco si inseriscono in C i suoi due estremi, che sicuramente non erano gia in C. Quindi |C| ≤ 2|C∗|.Si noti la metodologia: si riesce a dimostrare che il fattore di approssimazione e 2 anche se non si conosce la soluzione ottima,in quanto si utilizza la conoscenza di un limite inferiore per la soluzione ottima.

A Relazioni d’ordine e di equivalenzaDef. A.1 [Ordine parziale] Un ordine parziale su un insieme X e una relazione ≤ su X che sia:

riflessiva x ≤ x

antisimmetrica se x ≤ y e y ≤ x allora x = y

transitiva se x ≤ y e y ≤ z allora x ≤ z.

Un ordine parziale stretto su X e una relazione < su X che sia:

antiriflessiva x 6< x,

asimmetrica se x < y, allora y 6< x,

transitiva se x < y e y < z allora x < z.

Dato un ordine parziale≤ a partire da questo possiamo definire il corrispondente ordine parziale stretto: x < y se e solo se x ≤ ye x 6= y, e viceversa dato un ordine parziale stretto < possiamo definire il corrispondente ordine parziale: x ≤ y se e solo sex < y oppure x = y. Quindi e indifferente dare l’uno o l’altro.

Def. A.2 [Ordine totale] Un ordine totale su un insieme X e una relazione ≤ su X che sia un ordine parziale e inoltre sia:

totale x ≤ y oppure y ≤ x.

Analogamente e possibile definire un ordine totale stretto. Un esempio tipico di ordine totale e l’ordinamento usuale sui numerinaturali, interi o reali, mentre un esempio tipico di ordine parziale e la relazione tra nodo padre e nodo figlio in un albero (ci sononodi non confrontabili).

Def. A.3 [Equivalenza] Un’equivalenza su un insieme X e una relazione ∼ su X che sia:

riflessiva x ∼ x

simmetrica se x ∼ y allora y ∼ x

transitiva se x ∼ y e y ∼ z allora x ∼ z.

La classe di equivalenza di x ∈ X e l’insieme di tutti gli elementi equivalenti a x. Un elemento che appartiene a una certa classedi equivalenza si chiama anche rappresentante di tale classe. L’insieme delle classi di equivalenza e detto insieme quoziente diX rispetto a ∼.

52

Note per il corso di Complementi di Algoritmi e Strutture Dati...Note per il corso di Complementi di...

Documents

Transcript of Note per il corso di Complementi di Algoritmi e Strutture Dati...Note per il corso di Complementi di...