1

Teoria degli algoritmi e della computabilità

Terza giornata: Ricerca e ordinamento ottimi. P vs NP, algoritmi di approssimazione, e il potere della randomizzazione

Guido ProiettiEmail: guido.proietti@univaq.it

URL: www.di.univaq.it/~proietti/index_personal

2

Un primo algoritmo è quello di ricerca sequenziale (o esaustiva), che gestisce l’insieme di numeri come una lista L non ordinata

Correzione esercizio:

Il problema della ricerca

Tbest(n) = 1 x è in prima posizioneTworst(n) = n xL oppure è in ultima posizione

Contiamo il numero di confronti (operazione dominante):

3

Algoritmo di ricerca binaria

Confronta x con l’elemento centrale di L e prosegue nella metà sinistra o destra in base all’esito del confronto

Se ipotizzassimo che la sequenza di numeri fosse un array L ordinato, potremmo progettare un algoritmo più efficiente:

4

Esempi su un array di 9 elementi

Cerca 2

Cerca 1

Cerca 9

Cerca 3

3<4 quindi a e b si invertono

5

Analisi dell’algoritmo di ricerca binaria

Tbest(n) = 1 l’elemento centrale è uguale a xTworst(n) = Θ(log n) xL

Infatti, poiché la dimensione del sotto-array su cui si procede si dimezza dopo ogni confronto, dopo l’i-esimo confronto il sottoarray di interesse ha dimensione n/2i. Quindi, dopo i=log n +1 confronti, si arriva ad avere a>b.

Contiamo i confronti eseguiti nell’istruzione 3 (operazione dominante):

• Problema dell’ordinamento:–Lower bound - (n log n) albero di decisione–Upper bound – O(n2) IS,SS

• Proviamo a costruire un algoritmo ottimo, usando la tecnica del divide et impera:1 Divide: dividi l’array a metà2 Risolvi il sottoproblema ricorsivamente3 Impera: fondi le due sottosequenze ordinate

Un algoritmo di ordinamento ottimo: il MergeSort (John von Neumann, 1945)

6

Esempio di esecuzione

7 2 4 5 3 1 5 6

7 2 4 5 3 1 5 6

7 2 4 5 3 1 5 6

7 2 4 5 3 1 5 6

1 2 3 4 5 5 6 7

2 4 5 7 1 3 5 6

2 7 4 5 1 3 5 6

7 2 4 5 3 1 5 6

input

output

Input ed

output delle

chiamate

ricorsive

7

• Due array ordinati A e B possono essere fusi rapidamente:– estrai ripetutamente il minimo di A e B e copialo

nell’array di output, finché A oppure B non diventa vuoto

– copia gli elementi dell’array non ancora completamente svuotato alla fine dell’array di output

Fusione di sequenze ordinate (passo di impera)

Notazione: dato un array A e due indici x y, denotiamo con A[x;y] la porzione di A costituita da A[x], A[x+1],…,A[y]

8

Merge (A, i1, f1, f2)

1. Sia X un array ausiliario di lunghezza f2-i1+1

2. i=1

3. i2=f1+1

4. while (i1 f1 e i2 f2) do

5. if (A[i1] A[i2])

6. then X[i]=A[i1]

7. incrementa i e i1

8. else X[i]=A[i2]

9. incrementa i e i2

10. if (i1<f1) then copia A[i1;f1] alla fine di X

11. else copia A[i2;f2] alla fine di X

12. copia X in A[i1;f2]

fonde A[i1;f1] e A[f1+1;f2] output in A[i1;f2]

Osservazione: usa l’array ausiliario X

Algoritmo di fusione di sequenze ordinate

9

LemmaLa procedure Merge fonde due sequenze ordinate di lunghezza n1 e n2 eseguendo al più n1+ n2 -1 confrontiDim: Ogni confronto “consuma” un elemento di A.Nel caso peggiore tutti gli elementi tranne l’ultimo sonoaggiunti alla sequenza X tramite un confronto.Il numero totale di elementi è n1+ n2. Quindi il numero totaledi confronti è n1+ n2 -1. QED

Numero di confronti: C(n=n1+ n2)=O(n1+ n2)=O(n)(si noti che vale anche C(n)=Ω(minn1,n2))

Numero di operazioni (confronti + copie)? T(n)=(n1+ n2)

Costo dell’algoritmo di merge

10

MergeSort (A, i, f)

1. if (i f) then return

2. m = (i+f)/2

3. MergeSort(A,i,m)

4. MergeSort(A,m+1,f)

5. Merge(A,i,m,f)

MergeSort

11

Ovviamente la chiamata principale è Mergesort(A,1,n)

Complessità del MergeSortSi vede facilmente che il tempo di esecuzione

di MergeSort è:

T(n) = 2 T(n/2) + Θ(n) con T(1)=1, da cui:

T(n)=2(2T(n/22)+Θ(n/2))+Θ(n)=

=2(2(2T(n/23)+Θ(n/22))+Θ(n/2))+Θ(n)=…

e per k = log2n si ha n/2k = 1 e quindi

T(n)=2(2(…(2T(n/2k)+Θ(1))+…+Θ(n/22))+Θ(n/2))+Θ(n)

= 2log n·Θ(1)+2log n-1·Θ(2)+2log n-2·Θ(22)+…+ 20·Θ(n)

= n∙Θ(1)+n/2∙Θ(2)+n/4∙Θ(4)+…+1∙Θ(n) = Θ(n log n)

12

Più precisamente…1. Nel caso peggiore, il MS esegue (n log n - 2⌈ ⌉ log n⌈ ⌉ +

1) confronti, che corrisponde ad un numero compreso tra (n log n - n + 1) e (n log n + n + O(log n))

2. Nel caso medio, il MS esegue (n log n - 2⌈ ⌉ log n⌈ ⌉ + 1) – 0.2645·n confronti

3. Nel caso migliore (array già ordinato), il MS esegue n-1 confronti; può essere ottenuto facendo un controllo preliminare nella procedura di Merge tra ultimo elemento della prima sequenza e primo della seconda

13

Osservazioni finali

• Il MergeSort è un algoritmo (asintoticamente) ottimo rispetto al numero di confronti eseguiti nel caso peggiore

• Il MergeSort non ordina in loco, e utilizza memoria ausiliaria (l’occupazione di memoria finale è pari a 2n)

14

Richiamo: gerarchia delle classi

Decidibili

ExpTime(ARRESTO(k))P (ricerca)

NP

NP-completi (SAT)

15

Richiamo: inclusioni proprie?

• Abbiamo visto che:P ⊑ NP ⊑ ExpTime, con P ≠ ExpTime

• In NP c’è una classe molto speciale ed importante di problemi che sicuramente non apparterrebbero a P se fosse NP≠P: i problemi NP-completi

• Per i problemi in P, che possono essere risolti in tempo polinomiale su una RAM, il compito principale dell’algoritmista è progettare algoritmi efficienti, possibilmente ottimi

• Anche per i problemi in NP vorremmo progettare algoritmi efficienti, ma c’è un piccolo dettaglio: si congettura (in realtà, si crede fortissimamente) che i problemi NP-completi non ammettano algoritmi risolutivi polinomiali!

• Che fare allora?

16

17

P vs NP: il problema da un milione di dollari

18

24 marzo 2000, Collège de France, Parigi

Fondazione Clay mette in palio 7 premi da un milione di dollari l’uno per la soluzione di quelli che sono considerati i problemi matematici più importanti del nuovo millennio

problemi del millennio

1) Congettura di Hodge2) Congettura di Poincaré3) Ipotesi di Riemann4) Teoria quantistica

di Yang-Mills5) Equazioni di

Navier-Stokes6) P vs NP7) Congettura di Birch

e Swinnerton-Dyerasd

risolto

19

P vs NP: una formulazione dall’aspetto innocuo

date n città e, per ogni coppia di città i, j, la distanza fra i e j

trovare un tour (un cammino ciclico) di lunghezza minima che passa per tutte le città

il problema del commesso viaggiatore: (TSP, da travelling salesman problem)

una domanda da $ 1.000.000:esiste un algoritmo polinomiale che risolve il TSP?

una domanda da $ 0,01:esiste un algoritmo che risolve il TSP?

Si noti come tale problema ricada tra quelli di ottimizzazione – Richiedono di restituire la soluzione migliore (rispetto ad un prefissato criterio) tra tutte quelle possibili. Ad esempio trovare il cammino di lunghezza minima fra due nodi di un grafo

20

P vs NP: una formulazione dall’aspetto innocuo

un semplice algoritmo per il TSP:

enumera tutti i possibili tour fra le n città, misurando la lunghezza di ciascuno di essi e memorizzando quello più breve via via osservato

è un algoritmo efficiente?quanti tour possibili ci sono con n città?

#tour: (n -1)(n -2)(n -3)… 3 2 1=(n -1)!

Ad esempio, 52! fattoriale è:

in milionesimi di secondo è almeno 5000 miliardi di volte più dell’età

dell’universo!!!

80.658.175.170.943.878.571.660.636.856.403.766.975.289.505.440.883.277.824.000.000.000.000

Effettivamente si può dimostrare che TSP è NP-hard, ovvero la sua versione decisionale è NP-completa, e quindi si congettura la non esistenza di algoritmi risolutivi polinomiali

21

Di certo, un algoritmo esponenziale come quello proposto per il TSP è inefficiente. Ma un algoritmo polinomiale è sempre efficiente? Ed uno esponenziale è sempre inefficiente?

può essere considerato efficiente un algoritmo (polinomiale) che ha complessità (n100)?

può essere considerato inefficiente un algoritmo (non polinomiale) che ha complessità (n1+0.0001 log n)?

…no!

…no!

problemi per i quali esistono algoritmi polinomiali tendono ad avere polinomi “ragionevoli” problemi per i quali non si conoscono algoritmi polinomiali tendono a essere davvero difficili in pratica

…ma nella pratica la distinzione funziona!

Efficiente Polinomiale?

22

Crescita polinomiale vs crescita esponenziale

In effetti, la differenza fra complessità polinomiale e non polinomiale è davvero enorme

Tempi di esecuzione di differenti algorimi per istanze di dimensione crescente su un processore che sa eseguire un milione di istruzioni di alto livello al secondo. L’indicazione very long indica che il tempo di calcolo supera 1025 anni.

23

Alcuni problemi facili (che ammettono un algoritmo polinomiale)

24

Premessa: i grafiNel 1736, il matematico Eulero, affrontò l’annoso problema dei 7 ponti di Königsberg (Prussia):

È possibile o meno fare una passeggiata che parta da un qualsiasi punto della città e percorra una ed una sola volta ciascuno dei 7 ponti?

25

La modellizzazione di EuleroEulero affrontò il problema schematizzando topologicamente la pianta della città, epurando così l’istanza da insignificanti dettagli topografici:

…e così Königsberg venne rappresentata con un insieme di 4 punti (uno per ciascuna zona della città), opportunamente uniti da 7 linee (una per ciascun ponte)

A

B

C

D

A

B

C

D

26

Definizione di grafoUn grafo G=(V,E) consiste in:

- un insieme V=v1,…, vn di vertici (o nodi);- un insieme E=(vi,vj) | vi,vjV di coppie (non ordinate) di vertici, detti archi. Esempio: Grafo di Eulero associato alla

città di Königsberg: V=A,B,C,D, E=(A,B), (A,B), (A,D), (B,C), (B,C), (B,D), (C,D)Nota: È più propriamente detto multigrafo, in quanto contiene archi paralleli.

A

B

C

D

27

Torniamo al problema dei 7 ponti…

• Definizione: Un grafo G=(V,E) si dice percorribile (oggi si direbbe Euleriano) se e solo se contiene un cammino (non semplice, in generale) che passa una ed una sola volta su ciascun arco in E.

• Teorema di Eulero: Un grafo G=(V,E) è percorribile se e solo se è connesso ed ha tutti i nodi di grado pari, oppure se ha esattamente due nodi di grado dispari.

• NOTA: Un grafo con tutti i nodi di grado pari può essere percorso partendo da un qualsiasi nodo (e terminando quindi su di esso). Invece, per percorrere un grafo avente due nodi di grado dispari e tutti gli altri di grado pari, è necessario partire da uno qualsiasi dei due nodi di grado dispari, e terminare il percorso sull’altro nodo di grado dispari.

28

Soluzione al problema dei 7 ponti

Il problema dei 7 ponti non ammette soluzione, in quanto i 4 nodi hanno tutti grado dispari, e quindi il grafo non è percorribile. La cosa importante da notare è che la percorribilità può ovviamente essere stabilità efficientemente (addirittura in tempo lineare rispetto alla dimensione del grafo), semplicemente guardando al grado dei nodi del grafo!

29

Un problema molto importante su grafi: il cammino minimo tra due nodi

dato un grafo pesato G=(V,E) con pesi positivi sugli archi, e dati due nodi u e v, trovare un cammino da u a v di costo minimo (che minimizza la somma dei pesi degli archi del cammino)

u

3

v

2

6

7

45

10

18 2

9

6

1 8

30

20

44

16

11

6

18

6

Esistono soluzioni efficienti per tale problema: per esempio, l’algoritmo di Dijkstra può essere implementato in O(m + n log n), ove m è il numero di archi e n è il numero di nodi

30

2-colorabilitàDato un grafo G (non diretto e non pesato) dire se è possibile colorare i nodi di G con 2 colori in modo tale che per ogni coppia di nodi adiacenti, i due nodi abbiano colori diversi

Esistono soluzioni efficienti per tale problema: basta verificare se il grafo è bipartito mediante una visita in profondità del grafo, la quale richiede tempo O(m + n)

31

Alcuni problemi molto simili a ciclo Euleriano, cammino minimo e 2-colorabilità ma (sorprendentemente) difficili! (per i quali non si conosce nessun algoritmo polinomiale)

32

Ciclo Hamiltoniano

Dato un grafo non orientato G=(V,E) dire se G ammette un ciclo che passaper tutti i nodi una e una sola volta

33

Cammino massimoDato un grafo G (non diretto e non pesato) e due nodi s e t, trovare il cammino (semplice) più lungo fra s e t

s

t

s

t

34

3-colorabilitàDato un grafo G (non diretto e non pesato) dire se è possibile colorare i nodi di G con 3 colori in modo tale che per ogni coppia di nodi adiacenti, i due nodi abbiano colori diversi

Algoritmi approssimati

D. Supponiamo di dover risolvere un problema NP-hard. Cosa posso fare?R. La Teoria dice che è improbabile trovare un algoritmo che abbia tempo polinomiale.

Dobbiamo sacrificare una delle tre caratteristiche desiderate. Risolvere il problema all'ottimo. Risolvere il problema in tempo polinomiale. Risolvere istanze arbitrarie del problema.

Algoritmo di -approssimazione. Gira in tempo polinomiale. Risolve istanze arbitrarie del problema. Trova soluzioni entro un rapporto dal vero ottimo.

Sfida. E' necessario dimostrare che il valore di una soluzione è vicino all'ottimo, senza nemmeno sapere quale sia il valore ottimo!

35

Approssimazione

• Un algoritmo che restituisce una risposta C che è “vicina” alla soluzione ottima C* è detto un algoritmo di approssimazione.

• La “vicinanza” solitamente è misurata dal limite del rapporto (n) che l'algoritmo produce :

• Pb di Minimizzazione: C/C* ≤ (n)• Pb di Massimizzazione: C*/C ≤ (n)

36

Esempio: VERTEX-COVER

Istanza: un grafo non diretto G=(V,E).Problema: trovare un insieme CV di taglia minima tale che per ogni (u,v)E, o uC oppure vC.

Esempio:

37

Un algoritmo di 2-approssimazione

C E’ Ewhile E’

do sia (u,v) un arco arbitrario di E’ C C u,v rimuovi da E’ ogni arco incidente a u oppure a v.

return C.

38

Demo

39

La complessità temporale è O(n3), ossia, polinomiale

C E’ Ewhile E’ do

sia (u,v) un arco arbitrario di E’ C C u,v rimuovi da E’ ogni arco incidente a u oppure a v

return C

O(n2)O(1)

O(n)

O(m)=O(n2)

40

Correttezza

L’insieme di vertici che il nostro algoritmo restituisce è chiaramente un vertex-cover, dato che iteriamo fino a che ogni arco viene coperto.

41

Quanto è buona un’approssimazione?

Osserviamo l’insieme di archi scelti dal nostro algoritmo

il nostro VC li contiene entrambi, quindi è al più grande il doppio rispetto a qualsiasi VC, e in particolare del VC ottimo, cioè:

|nostro VC|/|qualsiasi VC| ≤ 2 e quindi |nostro VC|/|VC ottimo| ≤ 2 il fattore di approssimazione è pari a 2.

ogni VC ne contiene 1 in ognuno

nessun vertice in comune!

42

Lista tesine

1. Il problema dell’arresto (Di Ghionno)2. Modelli di calcolo: macchina di Turing e RAM

(Gallina)3. La notazione asintotica: classi O, Ω e Θ (Gregori)4. Classi P, NP e ExpTime (Laconi)5. Selection sort (Lops)6. Insertion sort (Massi)7. Lower bound problema dell’ordinamento

(Mitrangolo)8. Merge sort (Palombo)9. Ricerca sequenziale e binaria (Terregna)10. Il problema del cammino minimo (Cetrullo)11.Algoritmi di approssimazione (Del Casale)

43