Lezione 2.

Teoria degli algoritmi e della
computabilità
Seconda giornata: progettare un
algoritmo corretto, efficiente, e
possibilmente ottimo!
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
Complessità computazionale (o temporale)
di un algoritmo e di un problema
Definizione
Un algoritmo A ha una complessità computazionale
O(f(n)) su istanze di dimensione n se T(n)=O(f(n))
Definizione (upper bound di un problema)
Un problema Π ha una complessità computazionale o
upper bound O(f(n)) se esiste un algoritmo che risolve Π
la cui complessità computazionale è O(f(n))
2
La classe Time
Ora che abbiamo definito i concetti di
dimensione dell’istanza, modello di calcolo
e notazione asintotica ‘’O’’, possiamo
introdurre la classe Time: Data un’istanza
di dimensione n, e data una qualunque
funzione f(n), chiamiamo
Time(f(n))
l’insieme dei problemi che possono essere
risolti sulla RAM in tempo O(f(n)).
3
Esempi
• Il problema della ricerca, ovvero di verificare se un
certo elemento è presente in un dato insieme di
dimensione n, appartiene a Time(n): basta scorrere tutti
gli elementi e verificarne la presenza
• Lo stesso problema, nel caso in cui gli elementi fossero
ordinati, si può dimostrare che appartiene a Time(log n).
Esercizio per casa: Riuscite a progettare un algoritmo
con tale complessità temporale?
• NOTA: Time(1) denota i problemi che possono essere
risolti in tempo costante, indipendentemente dalla
dimensione dell’istanza (sono quindi problemi banali)
4
La classe P
La classe P è la classe dei problemi decidibili in
tempo polinomiale nella dimensione n dell’istanza
di ingresso:
P = Uc≥0 Time(nc)
5
La classe ExpTime
La classe ExpTime è la classe dei problemi decidibili in
tempo esponenziale nella dimensione n dell’istanza di
ingresso, ovvero in O(ap(n)), dove a>1 è una costante e
p(n) è un polinomio in n; più formalmente, si può scrivere:
ExpTime=Uc≥0Time(
)
c
(n
2 )
Chiaramente, P ⊑ ExpTime
Si può dimostrare che l’inclusione è propria, cioè
esistono problemi in ExpTime che non appartengono a P:
uno di questi problemi è quello di verificare se un certo
algoritmo si arresta in al più k passi, con k fissato.
6
Un altro problema in ExpTime: SAT
Data un’espressione booleana in forma normale congiuntiva,
cioè la congiunzione (operatore logico AND) di un insieme di
clausole, in cui ogni clausola è la disgiunzione (operatore logico
OR) di un certo insieme di variabili che possono assumere
valore TRUE o FALSE, il problema della soddisfacibilità (SAT)
richiede di verificare se esiste una assegnazione di valori di
verità alle variabili che rende l’espressione TRUE.
È facile convincersi che SAT appartiene ad ExpTime, in quanto
può essere risolto provando le 2n possibili assegnazioni di verità
alle n variabili. Ma la vera domanda è: SAT appartiene a P?
Sembra incredibile, ma non siamo in grado di dare una risposta
a questa semplice domanda, anche se si congettura che la
risposta sia NO.
7
Non determinismo
• Negli algoritmi visti finora ogni passo è determinato
univocamente dallo stato della computazione; vengono quindi
detti deterministici. Tale ipotesi dipende dal modello di
calcolo che abbiamo adottato.
• Supponiamo ora di avere un modello di calcolo
(apparentemente) più potente, ovvero una macchina non
deterministica che ci consenta, ad ogni passo dell’esecuzione
di un algoritmo, di proseguire la computazione lungo un
numero finito di esecuzioni multiple. Si noti che stiamo
parlando di un modello di calcolo astratto, che non esiste
nella realtà!
• Un algoritmo non deterministico è un algoritmo che ha il
potere, ad ogni istante della computazione non
deterministica, di indovinare l’esecuzione giusta lungo cui
proseguire per arrivare alla risoluzione del problema.
8
Esempio
Come potrebbe funzionare un algoritmo non
deterministico per SAT?
– Indovina ad ogni passo il valore giusto da
assegnare ad una variabile (TRUE o FALSE)
– La computazione sarà descritta da un albero
binario, dove le ramificazioni corrispondono alle
scelte non deterministiche (la computazione
deterministica è invece descritta da una
catena)
– Quindi se la formula è soddisfacibile, esiste
almeno un cammino che porta a una foglia con
valore TRUE. Si noti che tale cammino è lungo n
9
La classe NP
• Data una qualunque funzione f(n), chiamiamo
NTime(f(n)) l’insiemi dei problemi che possono
essere decisi da un algoritmo non deterministico
in tempo O(f(n))
• La classe NP è la classe dei problemi decidibili in
tempo polinomiale non deterministico nella
dimensione n dell’istanza di ingresso:
NP = Uc≥0 NTime(nc)
• SAT appartiene a NTime(n), e quindi SAT
appartiene a NP
10
Gerarchia delle classi
P è incluso in NP oppure no?
– Ovviamente sì: un algoritmo deterministico
è un caso particolare di un algoritmo non
deterministico, in cui però le computazioni
non si ramificano
– L’inclusione è propria? Non si sa, e questo è
uno dei 6 problemi matematici aperti la cui
risoluzione vi farà vincere 1 Milione di
Dollari! (si veda Wikipedia)
11
Gerarchia delle classi (2)
NP è incluso in ExpTime oppure no?
– Ovviamente sì: un algoritmo non
deterministico può essere ‘’simulato’’ da un
algoritmo deterministico che esplora una
dopo l’altra tutte le computazioni
ramificate in tempo esponenziale
– L’inclusione è propria? Non si sa…
12
Gerarchia delle classi (3)
• Quindi abbiamo
P ⊑ NP ⊑ ExpTime, con P ≠ ExpTime
• Si congettura che tutte le inclusioni siano proprie
• In NP c’è una classe molto speciale di problemi
che sicuramente non apparterrebbero a P se
fosse NP ≠ P: i problemi NP-completi
• Si può dimostrare che SAT è NP-completo (più
precisamente, è stato il primo problema per cui si
è provata la NP-completezza [Stephen Cook,
1971])
13
Gerarchia delle classi
Decidibili
P (ricerca)
NP
ExpTime
(ARRESTO(k))
NP-completi (SAT)
Congettura P ≠ NP
14
Altri famosi problemi NP-completi
• Commesso viaggiatore
– Dati un grafo completo G con pesi w sugli archi
ed un intero k, verificare se esiste un ciclo in G
di peso al più k che attraversa ogni vertice una
ed una sola volta
• Colorazione
– Dati un grafo G ed un intero k, verificare se è
possibile colorare i vertici di G con al più k
colori tali che due vertici adiacenti non siano
dello stesso colore
15
Altri famosi problemi NP-completi (2)
• Somme di sottoinsiemi
– Dati un insieme S di numeri naturali ed un intero
t, verificare se esiste un sottoinsieme di S i cui
elementi sommano esattamente a t
• Zaino
– Dati un intero k, uno zaino di capacità c, e n
oggetti di dimensioni s1, …., sn cui sono associati
profitti p1, …., pn, bisogna verificare se esiste un
sottoinsieme degli oggetti di dimensione ≤c che
garantisca profitto ≥k
16
Progettare un algoritmo
Vogliamo ora progettare algoritmi (per
problemi calcolabili!) che:
– Producano correttamente il risultato
desiderato
– Siano efficienti in termini di tempo di
esecuzione ed occupazione di memoria
17
Le quattro proprietà fondamentali di un
algoritmo (oltre l’efficienza)
• La sequenza di istruzioni deve essere finita
• Essa deve portare ad un risultato corretto
• Le istruzioni devono essere eseguibili
materialmente
• Le istruzioni non devono essere ambigue
18
Algoritmi e strutture dati
• Concetto di algoritmo è inscindibile da quello
di dato
• Da un punto di vista computazionale, un
algoritmo è una procedura che prende dei dati
in input e, dopo averli elaborati, restituisce dei
dati in output
 I dati devo essere organizzati e strutturati in
modo tale che la procedura che li elabora sia
“efficiente”
19
Analisi di algoritmi
Correttezza:
– dimostrare formalmente che un algoritmo è
corretto
Complessità:
– Stimare la quantità di risorse (tempo e
memoria) necessarie all’algoritmo
– stimare il più grande input gestibile in tempi
ragionevoli
– confrontare due algoritmi diversi
– ottimizzare le parti “critiche”
20
Notazione asintotica W
f(n) = W(g(n)) se  due costanti c>0 e n0≥0 tali
che f(n) ≥ c g(n) per ogni n ≥ n0
f(n) = W(g(n))
f(n)
c g(n)
n0
21
n
Esempi
• Sia f(n) = 2n2 - 5n; vogliamo dimostrare che f(n)= W(n2).
f(n)/n2 = (2n2 - 5n)/n2 = 2 - 5/n
ma 2 - 5/n ≥ 1 per n ≥ 5
quindi basta scegliere c=1 e n0=5 e avremo che
2n2 - 5n ≥ 1n2 per n ≥ n0=5.
• f(n) = W(n)
(c=1, n0=2)
• f(n) = W(log n)
(c=1, n0=2)
• Invece, f(n)  W(n3)
22
Legame con il concetto di limite
fn 
0
gn 

fn   Wgn 
fn   Wgn 

limn
limn
fn   Wgn 
23

limn
fn 
0
gn 
fn 
(se esiste)  0
gn 
Notazione asintotica Q
f(n) = Q(g(n)) se  tre costanti c1,c2>0 e n0≥0 tali
che c1 g(n) ≤ f(n) ≤ c2 g(n) per ogni n ≥ n0
f(n) = Q(g(n))
c2 g(n)
f(n)
c1 g(n)
n0
24
n
Relazioni tra O, Ω e Θ
fn   Qg(n) 

fn   Ogn 
fn   Og(n) 

fn   Θgn 
fn   Qg(n) 

fn   Wgn 
fn   Wg(n) 

fn   Θgn 
fn   Qg(n)   fn   Wgn  e fn   Ogn 
25
Caso migliore di un algoritmo
• Sia tempo(I) il tempo di esecuzione di un
algoritmo sull’istanza I
Tbest(n) = min istanze I di dimensione n {tempo(I)}
• Intuitivamente, Tbest(n) è il tempo di
esecuzione sulle istanze di ingresso che
comportano meno lavoro per l’algoritmo
26
Caso medio di un algoritmo
• Sia P(I) la probabilità di occorrenza dell’istanza I
Tavg(n) = ∑ istanze I di dimensione n {P(I) tempo(I) }
• Intuitivamente, Tavg(n) è il tempo di
esecuzione nel caso medio, ovvero sulle
istanze di ingresso “tipiche” per il problema
• Richiede di conoscere una distribuzione di
probabilità sulle istanze
27
Il problema dell’ordinamento
Dato un insieme S di n elementi presi da un
dominio totalmente ordinato, ordinare S
• Esempi: ordinare una lista di nomi
alfabeticamente, o un insieme di numeri, o un
insieme di compiti d’esame in base al cognome
dello studente
• Subroutine in molti problemi
• È possibile effettuare ricerche in array ordinati in
tempo O(log n) (ricerca binaria)
28
Il problema dell’ordinamento
(non decrescente)
• Input: una sequenza di n numeri (reali)
<a1,a2,…,an>
(NOTA: la dimensione dell’input è n)
• Output: una permutazione {1,2,…,n} 
{i1,i2,…,in}, ovvero un riarrangiamento <ai1,
ai2,…, ain> della sequenza di input in modo tale
che ai1  ai2 … ain
29
SelectionSort
Approccio incrementale: assumendo che i primi k elementi
siano ordinati, estende l’ordinamento ai primi k+1
elementi scegliendo il minimo degli n-k elementi non
ancora ordinati e mettendolo in posizione k+1
30
7
2
4
5
3
1
1
2
3
4
5
7
1
2
4
5
3
7
1
2
3
4
5
7
1
2
4
5
3
7
1
2
3
4
5
7
1
2
3
5
4
7
SelectionSort (A)
1.
for k=1 to n-1 do
2.
m=k
3.
for j=k+1 to n do
4.
5.
NOTA: Assumiamo
che il primo elemento
dell’array sia in A[1]
if (A[j] < A[m]) then m=j
scambia A[m] con A[k]
• linea 2: m mantiene l’indice dell’array in cui si trova il minimo
corrente
• linee 3-4: ricerca del minimo fra gli elementi A[k],…,A[n] (m viene
aggiornato con l’indice dell’array in cui si trova il minimo corrente)
• linea 5: il minimo è spostato in posizione k
31
Correttezza
• Si dimostra facendo vedere che alla fine del generico passo
k (k=1,…, n-1) si ha: (i) i primi k elementi sono ordinati e
(ii) contengono i k elementi più piccoli dell’array
• Induzione su k:
– k=1: Alla prima iterazione viene semplicemente selezionato
l’elemento minimo dell’array  (i) e (ii) banalmente verificate.
– k>1. All’inizio del passo k i primi k-1 elementi sono ordinati e
sono i k-1 elementi più piccoli nell’array (ipotesi induttiva).
Allora la tesi segue dal fatto che l’algoritmo seleziona il minimo
dai restanti n-k elementi e lo mette in posizione k. Infatti:
(ii) i primi k elementi restano i minimi nell’array
(i) l’elemento in posizione k non è mai più piccolo dei primi k-1
elementi
32
Complessità
temporale
SelectionSort (A)
1.
for k=1 to n-1 do
2.
m=k
3.
for j=k+1 to n do
4.
5.
1 assegnamento
n-k confronti
(operaz. dominante)
1 scambio
(3 assegnamenti)
if (A[j] < A[m]) then m=j
scambia A[m] con A[k]
n-1
n-1
k=1
k=1
il tutto eseguito
per k=1,…, n-1
T(n) =  [1+(n-k)+1]=2(n-1)+ k =2(n-1)+n·(n-1)/2 = Q(n2)
Si noti che T(n) è PROPRIO UGUALE ad un polinomio di 2º grado in n,
e quindi la notazione Θ è perfettamente ESPRESSIVA del valore di T(n)
 T(n) = Tbest(n) = Tavg(n) = Q(n2)
33
InsertionSort
Approccio incrementale: assumendo che i primi k elementi
siano ordinati, estende l’ordinamento ai primi k+1
elementi, inserendo l’elemento in posizione k+1-esima
nella giusta posizione rispetto ai primi k elementi
34
7
2
4
5
3
1
2
4
5
7
3
1
2
7
4
5
3
1
2
3
4
5
7
1
2
4
7
5
3
1
1
2
3
4
5
7
InsertionSort (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
for j=1 to k+1 do
4.
5.
if (A[j] > x) then break
if (j < k+1) then
6.
for t=k downto j do A[t+1]= A[t]
7.
A[j]=x
• Linea 2: elemento x=A[k+1] da inserire nella posizione che gli
compete
• Linee 3 e 4: individuano la posizione j in cui va messo x
• Linee 5 e 6: se la posizione j è diversa da k+1, si fa spazio per
inserire x, “shiftando” tutti gli elementi da j a k verso destra
35
Correttezza
• Si dimostra facendo vedere che alla fine del generico
passo k (k=1,…, n-1) i primi k+1 elementi sono ordinati
(si noti la differenza con il Selection Sort, in cui invece
dovevamo far vedere anche che erano i più piccoli)
• Induzione su k:
– k=1: banale: si riordinano A[1] e A[2];
– k>1: All’inizio del passo k i primi k elementi sono ordinati
(ipotesi induttiva). Allora la tesi segue dal fatto che
l’algoritmo inserisce A[k+1] nella giusta posizione rispetto
alla sequenza A[1],…,A[k]
36
Complessità temporale
InsertionSort (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
for j=1 to k+1 do
4.
1 assegnamento
if (A[j] > x) then break
5.
if (j < k+1) then
6.
for t=k downto j do A[t+1]= A[t]
7.
A[j]=x
j*≤k+1
confronti
k+1–j*
assegnamenti
n-1
T(n) = Q(n)+ (k+1) = Q (n2)
k=1
T(n) = Tbest(n) = Tavg(n) = Q(n2)
Possiamo fare meglio?
37
k+1
oper.
il tutto eseguito
per k=1,…, n-1
Una variante dell’IS più efficiente
InsertionSort2 (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
j=k
4.
while j > 0 e A[j] > x do
5.
tk ≤ 2k
assegnam.
A[j+1] = A[j]
6.
j= j-1
7.
A[j+1]=x
n-1
il tutto eseguito
per k=1,…, n-1
n-1
T(n)=Q(n)+ tk ≤ Q(n)+ 2k = Q(n)+n·(n-1) = Q(n2)
k=1
 T(n) = O(n2)
38
k=1
Si noti che T(n) è AL PIÙ UGUALE ad un
polinomio di 2º grado in n, e quindi la
notazione O è perfettamente ESPRESSIVA del
valore di T(n)
Caso migliore, peggiore, e medio di
InsertionSort2
• Caso migliore
– array già ordinato in ordine crescente  tk = 0
 Tbest(n) = Q(n) (costo del ciclo for esterno)
• Caso peggiore
– array ordinato in ordine decrescente  tk = 2k
n-1
 T(n) =  2k = Q(n2)
k=1
• Caso medio
– L’elemento in posizione k+1 ha la medesima probabilità di essere
inserito in ciascuna delle k posizioni che lo precedono  la sua
posizione attesa è k/2  il valore atteso di tk = k
n-1
 Tavg(n) =  k = Q(n2)
k=1
39

Legge di Murphy?
« Se qualcosa può andar male, lo farà. »
In realtà, negli algoritmi il caso medio costa spesso
come il caso peggiore (asintoticamente), in quanto le
strutture di controllo fondamentali degli algoritmi sono i
cicli, e spesso il caso medio implica l’esecuzione della
metà delle istruzioni di un ciclo, senza quindi avere un
abbattimento asintotico della complessità.
40
Riepilogo
Caso
Caso Caso
migliore medio peggiore
41
Selection Sort
Θ(n2)
Θ(n2)
Θ(n2)
Insertion Sort 1
Θ(n2)
Θ(n2)
Θ(n2)
Insertion Sort 2
Θ(n)
Θ(n2)
Θ(n2)
Complessità spaziale
Ricordiamo che oltre alla complessità temporale
dobbiamo valutare anche la complessità spaziale di un
algoritmo, ovvero lo spazio di memoria necessario per
ospitare le strutture di dati utilizzate dall’algoritmo.
La complessità spaziale del Selection Sort
e dell’Insertion Sort è Θ(n)
Nota: Se la complessità spaziale di un certo algoritmo è Θ(g(n)), e se tale
algoritmo “ispeziona” l’intera memoria occupata, allora la complessità
temporale dell’algoritmo è W(g(n)), ovviamente.
42
Conseguenze per il problema dell’ordinamento
La complessità spaziale di qualsiasi algoritmo che risolve il
problema dell’ordinamento è W(n) (dimensione input)
…ma qualsiasi algoritmo che risolve il problema
dell’ordinamento deve ispezionare tutti i dati in ingresso, e
quindi ha complessità temporale T(n)=W(n)

Tutti gli algoritmi che risolveranno il problema
dell’ordinamento avranno una complessità temporale W(n)
43
Delimitazioni inferiori (lower bound)
Definizione
Un algoritmo A ha complessità computazionale W(g(n)) su istanze di
dimensione n se T(n)=W(g(n)) (significa che numero di passi elementari
necessari per eseguire A nel caso peggiore è W(g(n)), e quindi non è
detto che debbano essere necessari per ogni istanza di dimensione n:
istanze facili potrebbero richiedere meno risorse!)
Definizione (lower bound o complessità intrinseca di un problema)
Un problema P ha una delimitazione inferiore alla complessità
computazionale W(g(n)) se ogni algoritmo che risolve P ha
complessità computazionale W(g(n)).
44
Ottimalità di un algoritmo
Definizione
Dato un problema P con complessità intrinseca W(g(n)), un
algoritmo che risolve P è ottimo (in termini di complessità
asintotica, ovvero a meno di costanti moltiplicative e di
termini additivi/sottrattivi di “magnitudine” inferiore) se ha
complessità computazionale O(g(n)).
45
Quindi, per il problema dell’ordinamento…
• Upper bound temporale: O(n2)
– Insertion Sort, Selection Sort
• Lower bound temporale: W(n)
– “banale”: dimensione dell’input
Abbiamo un gap lineare tra upper bound e lower bound!
Possiamo fare meglio, ovvero abbassare
l’upper bound e/o innalzare il lower bound ?
46
Ordinamento per confronti
Dati due elementi ai ed aj, per determinarne l’ordinamento relativo
effettuiamo una delle seguenti operazioni di confronto:
a i  aj ; ai  aj ; a i  aj ; ai  aj ; ai  aj
Non si possono esaminare i valori degli elementi o ottenere
informazioni sul loro ordine in altro modo.
Notare: Tutti gli algoritmi di ordinamento considerati fino ad
ora sono algoritmi di ordinamento per confronto.
47
Lower bound W(n log n) per l’ordinamento
• Consideriamo un generico algoritmo A, che ordina
eseguendo solo confronti: dimostreremo che A esegue (nel
caso peggiore) W(n log n) confronti
• Un generico algoritmo di ordinamento per confronti lavora
nel modo seguente:
- Confronta due elementi ai ed aj (ad esempio effettua il test ai  aj);
- A seconda del risultato, riordina e/o decide il confronto
successivo da eseguire.
 Un algoritmo di ordinamento per confronti può essere
descritto in modo astratto usando un albero di decisione,
nel quale i nodi interni rappresentano i confronti, mentre le
foglie rappresentano gli output prodotti
48
Albero di decisione
• Descrive le diverse sequenze di confronti che A esegue
su un’istanza <a1,a2,…,an> di lunghezza n; i movimenti
dei dati e tutti gli altri aspetti dell’algoritmo vengono
ignorati
• Nodo interno (non foglia): i:j (modella il confronto
tra ai e aj)
• Nodo foglia: i1,i2,…,in (modella una risposta (output)
dell’algoritmo, ovvero una permutazione <ai1,ai2,…,ain>
degli elementi)
• L’albero di decisione è associato ad un algoritmo e alla
dimensione n dell’istanza
49
Esempio
Input <a1,a2,a3>
Š
1,2,3
1:2
Š
2:3
Š
1,3,2
Š

1:3


3,1,2
2,1,3
1:3
Riconoscete
l’algoritmo
associato?

2:3
Š

2,3,1
3,2,1
È proprio l’Insertion Sort 2!
Esercizio per casa: costruire l’albero di decisione
per il SS su una sequenza di 3 elementi.
50
Proprietà
• Per una particolare istanza, i confronti eseguiti da
A su quella istanza rappresentano un cammino
radice – foglia
• L’algoritmo segue un cammino diverso a seconda
delle caratteristiche dell’input
– Caso peggiore: cammino più lungo
– Caso migliore: cammino più breve
• Il numero di confronti nel caso peggiore è pari
all’altezza dell’albero di decisione (ovvero alla
lunghezza, in termini di numero di archi, del più
lungo cammino radice-foglia)
51
Altezza in funzione delle foglie
Lemma: Un albero strettamente binario (ovvero, in cui ogni
nodo interno ha esattamente due figli) con k foglie ha altezza
h(k)  log2 k.
Dim: Dimostrazione per induzione su k:
– Caso base k=1 (albero-nodo ): banale h(k)=0≥ log21=0
– Caso k>1: supposto vero per k-1 foglie, dimostriamolo per k;
poiché la radice ha 2 figli, uno dei due suoi sottoalberi deve
contenere almeno la metà (parte intera sup.) delle foglie, e quindi
h(k) ≥1+h(k/2) ≥ (hp induttiva) 1+log2(k/2)
=1+log2k-log22=log2k.
QED
52
Il lower bound W(n logn)
• Consideriamo l’albero di decisione di un qualsiasi algoritmo
che risolve il problema dell’ordinamento di n elementi
• Tale albero deve avere almeno n! foglie: infatti, se l’algoritmo
è corretto, deve contemplare tutti i possibili output, ovvero le
n! permutazioni della sequenza di n elementi in input
• Dal lemma precedente, avremo che l’altezza h(n) dell’albero di
decisione sarà:
h(n)  log2(#foglie)  log2(n!) > log2 (n/e)n =
Formula di Stirling:
n!  (2pn)1/2 ·(n/e)n
> (n/e)n
53
= n log2 (n/e) =
= n log2 n – n log2 e =
= W(n log n)
QED