Didattica dei Fondamenti
dell’Informatica 2
Prima giornata: spunti di teoria della
calcolabilità e principali classi di complessità
computazionale dei problemi
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
Mille dubbi…
• Uhmmm…devo inventarmi un corso che sia
utile e che parli di come parlare dei
fondamenti dell’informatica
• Avverto subito che il problema è difficile
da risolvere: contiene nella sua definizione
una ricorsione! 
• …e poi, devo parlare dei fondamenti
dell’informatica, ma che cos’è veramente
l’informatica, e dove risiede la sua anima?
2
La dicotomia tra informatique e
computer science
•
•
•
•
•
Nell’accezione comune, l’informatica viene associata all’utilizzo dei
calcolatori automatici (computer, in senso lato)
Non è un caso: informatica deriva infatti dal francese informatique,
contrazione di information automatique
Si noti invece che nella lingua inglese informatica si traduce con il
termine computer science, o più precisamente computing science,
rendendo esplicito il presupposto dell'esistenza della figura di uno
scienziato (con tutto il conseguente carico epistemologico) interessato
allo studio dei processi computazionali (si noti, non necessariamente
automatici!)
Definizione da Wikipedia: scienza che ha per oggetto lo studio dei
fondamenti teorici dell'informazione, della sua computazione a livello
logico e delle tecniche pratiche per la loro implementazione e applicazione
in sistemi elettronici automatizzati detti quindi sistemi informatici.
Estremizzando: Computer Science is no more about computers than
astronomy is about telescopes. (Edsger W. Dijkstra)
3
Domanda aperta
L’informatica è quindi un ramo della
matematica, una disciplina ingegneristica o
una scienza della natura?
4
Le tre anime dell’informatica
(C. Mirolo)
All’interno della disciplina convivono tre
concezioni principali:
• Anima matematica (paradigma razionalista),
tipica dell’informatica teorica (gli anglofoni
direbbero della computer science)
• Anima ingegneristica (paradigma tecnologico),
tipica dell’ambito dell’ingegneria del software
(gli anglofoni direbbero della information and
communication technology, o ICT)
• Anima scientifica (paradigma scientifico), tipica
dell’ambito dell’intelligenza artificiale
5
L’anima matematica
Rimanda al razionalismo in filosofia
• La ragione pura (conoscenza a priori) è più
affidabile dell’esperienza sensoriale
(conoscenza a posteriori)
• Programmare è assimilabile a un’attività
matematica
• Esempi: teoria della calcolabilità, complessità
computazionale, verifica formale della
correttezza dei programmi, semantica dei
linguaggi di programmazione, etc.
6
L’anima ingegneristica
Rimanda all’empirismo in filosofia
• L’esperienza è alla radice di ogni conoscenza
• Da un punto di vista ingegneristico l’informatica mira
a produrre sistemi affidabili e i metodi
dell’informatica teorica sono considerati speculativi
• È impraticabile, se non impossibile, acquisire
(dedurre) conoscenza a priori sui programmi reali
• Esempi: ingegneria del software (requisiti, progetto,
design patterns, architettura, manutenzione ed
evoluzione, testing, etc.)
7
L’anima scientifica
• La conoscenza a priori (deduttiva) deve essere
corroborata/refutata da evidenza empirica
(sperimentale)
• L’informatica è una disciplina scientifica e le
proprietà dei suoi modelli e risultati sono
oggetto di indagine scientifica
• Esempi: debugging, intelligenza artificiale,
reti neurali artificiali, modelli e simulazione,
programmazione evolutiva
8
Il punto di vista del legislatore:
l’informatica nella scuola del riordino
DM 22/08/2007 n. 139: Asse scientificotecnologico
Competenze di base a conclusione dell’obbligo di
istruzione:
• Osservare, descrivere ed analizzare fenomeni
appartenenti alla realtà naturale e artificiale e
riconoscere i concetti di sistema e di
complessità
• Essere consapevole delle potenzialità e dei
limiti delle tecnologie nel contesto culturale e
sociale in cui vengono applicate
9
Il punto di vista del legislatore:
l’informatica nella scuola del riordino (2)
DM 7/10/2010 n. 211: Liceo Scientifico – Opzione
delle scienze applicate
Competenze di base a conclusione dell’obbligo di istruzione: Il
collegamento con le discipline scientifiche, ma anche con la filosofia e
l’italiano, deve permettere di riflettere sui fondamenti teorici
dell’informatica e delle sue connessioni con la logica, sul modo in cui
l’informatica influisce sui metodi delle scienze e delle tecnologie, e su
come permette la nascita di nuove scienze.
 Nelle declaratorie, prevalgono l’anima matematica e quella
scientifica, in quest’ordine. Questo non vuol dire che l’anima
ingegneristica sia meno importante, ma solo che le altre due anime le
sono propedeutiche!
10
Nanos gigantum humeris insidentes
Per costruire un
sillabo coerente
con le premesse,
proviamo a salire
come nani sulle
spalle dei giganti!
11
Sviluppare il ragionamento matematico
“Il ragionamento
matematico può essere
considerato piuttosto
schematicamente come
l'esercizio di una
combinazione di due
capacità, che possiamo
chiamare intuizione e
ingegnosità.“
Alan M. Turing (19121954)
12
Sviluppare il ragionamento algoritmico
“Se è vero che un problema non si capisce a
fondo finché non lo si deve insegnare a
qualcuno altro, a maggior ragione nulla deve
essere compreso in modo più approfondito
di ciò che si deve insegnare ad una
macchina, ovvero di ciò che va espresso
tramite un algoritmo."
Donald Knuth, nume tutelare degli
algoritmisti, autore di The Art of
Computer Programming
13
Problemi ed algoritmi
Per risolvere un problema (matematico), i
giganti ci suggeriscono di coltivare e
sviluppare l’intuito e l’ingegno dell’individuo
- qualità invero piuttosto innate attraverso il duro lavoro della
comprensione iniziale della intrinseca
difficoltà del problema stesso (ovvero del
suo ‘’nucleo’’ matematico), seguita poi dallo
sviluppo di una appropriata procedura di
risoluzione algoritmica (se possibile!)
14
Gli obiettivi di questo corso
Tutto ciò premesso, ci concentreremo sull’anima
matematica dell’informatica, ovvero la teoria della
computazione, che a sua volta può essere suddivisa in due
grandi filoni:
• La teoria della calcolabilità, ovvero lo studio della (ir)risolubilità
dei problemi computazionali mediante un procedimento di calcolo
(algoritmo)
• La teoria degli algoritmi e della complessità computazionale,
ovvero lo studio delle risorse di calcolo (principalmente tempo di
esecuzione e spazio di memoria utilizzato) necessarie e sufficienti
ad un algoritmo (esatto, approssimato, randomizzato) per risolvere
un problema computazionale
Il tutto verrà illustrato cercando di utilizzare un
linguaggio rigoroso ma senza eccedere nel formalismo, con
l’obiettivo quindi di fornire delle idee e del materiale da
riutilizzare in classe (opportunamente adattato alle
esigenze di ciascuno, ovviamente!)
15
Le tre giornate
• Oggi
– Facile, difficile, impossibile: spunti di teoria
della calcolabilità e principali classi di
complessità computazionale dei problemi
• Venerdì 19/4
– Essere algoritmista: progettare un algoritmo
corretto, efficiente, e possibilmente ottimo
• Venerdì 26/4
– Quando il problema è troppo arduo e tutto il
resto fallisce: algoritmi di approssimazione e
il potere della randomizzazione
16
Complessità computazionale
(dei problemi)
• Che cos’è un algoritmo?
• Posso sempre risolvere (algoritmicamente) un
dato problema?
• Quanto velocemente? Caratterizzazioni dei
problemi in funzione della loro “difficoltà”
computazionale: le classi di complessità
• Il problema da 1 Milione di Dollari: P versus NP
17
Definizione (necessariamente
informale) di algoritmo
Procedimento effettivo che consente di risolvere un
problema (ovvero di ottenere una risposta ad un
determinato quesito) eseguendo, in un determinato
ordine, un insieme finito di passi semplici (azioni), scelti
tra un insieme (solitamente) finito di possibili azioni.
Algoritmo ≠ Programma: un algoritmo è l’essenza computazionale di un
programma, ovvero della sua codifica in un certo linguaggio di
programmazione, in quanto fornisce una procedura risolutiva depurata
da dettagli riguardanti il linguaggio di programmazione stesso,
l’ambiente di sviluppo, il sistema operativo
18
Etimologia della parola algoritmo
Il termine Algoritmo deriva da
Algorismus, traslitterazione latina del
nome di un matematico persiano del IX
secolo, Muhammad al-Khwarizmi, che ne
descrisse il concetto applicato alle
procedure per eseguire alcuni calcoli
matematici
19
Problemi computazionali
• Un problema computazionale è una relazione tra un
insieme di istanze (input) e un insieme di soluzioni
(output).
• Una soluzione algoritmica ad un problema
computazionale consiste in un algoritmo che calcola
per ogni istanza del problema almeno una soluzione, o
che rilascia un certificato di non esistenza di una
soluzione. Ad esempio, il problema della
fattorizzazione:
“Dato un intero positivo n,
scomporlo in fattori primi“
ammette una soluzione algoritmica: basta guardare ad
uno ad uno tutti i valori minori di n, e per ciascuno di
essi, verificare se è primo (scomponendolo a sua volta
in fattori primi), e se sì, verificare se divide n.
20
Tipologie di problemi computazionali
• Problemi di decisione
– Richiedono una risposta binaria ad una domanda.
Ad esempio, il numero 29 è primo?
• Problemi di ricerca
– Richiedono di restituire una soluzione del
problema. Ad esempio, trovare la media
aritmetica di un insieme di numeri
• Problemi 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
21
Una domanda apparentemente strana
• Possono esistere problemi non calcolabili, cioè
irrisolubili (algoritmicamente)? Si noti che se un
tale problema esistesse, allora sarebbe preclusa
soltanto (si fa per dire!) la sua risoluzione in un
numero finito di passi. Ma il concetto di infinito è
troppo elusivo per la nostra mente…
• La risposta alla domanda è sì, e anzi i problemi non
calcolabili "sono molti di più" di quelli calcolabili! I
problemi si classificano quindi in:
– problemi non calcolabili (problemi che non ammettono
una soluzione algoritmica)
– problemi calcolabili, a loro volta classificabili in:
• problemi trattabili (cioè risolvibili in tempi ‘’ragionevoli’’)
• problemi intrattabili
22
Insiemi numerabili
• Un insieme è numerabile (possiede un’infinità
numerabile di elementi)
⇔
i suoi elementi possono essere messi in
corrispondenza biunivoca con i numeri naturali.
• In altre parole, un insieme numerabile è un
insieme i cui elementi possono essere enumerati,
ossia descritti da una sequenza del tipo
a1, a2, ... , an, ...
23
Insiemi numerabili: esempi
• Insieme dei numeri naturali N
• Insieme dei numeri interi Z:
n ↔ 2 n+ 1 n ≥0
n ↔2 |n| n< 0
Enumerazione: 0, -1, 1, -2, 2, -3, 3, -4, 4, ...
• Insieme dei numeri naturali pari:
2n ↔ n
Enumerazione: 0, 2, 4, 6, 8, ...
• Insieme delle sequenze (stringhe) su un
alfabeto finito.
24
Enumerazione delle sequenze
• Si vogliono elencare in un ordine ragionevole le
sequenze costruite su un certo alfabeto (finito)
• Ordine lessicografico: Si ordinano i caratteri
dell’alfabeto (arbitrariamente); quindi si
ordinano le sequenze in ordine di lunghezza
crescente, e, a parità di lunghezza, in “ordine
alfabetico”
• Una sequenza s arbitraria si troverà, tra quelle
di |s| caratteri, in posizione alfabetica tra
queste.
25
Esempio
Alfabeto = {a,b,c, ..., z}
a, b, c, ..., z,
aa, ab, ..., az, ba, ..., bz, ..., za, ..., zz,
aaa, aab, .... , baa, ...., zaa, ... , zzz,
...
26
Enumerazione delle sequenze
Ad una sequenza arbitraria corrisponde il
numero che ne indica la posizione
nell’elenco
Ad un numero naturale n corrisponde la
sequenza in posizione n
 Corrispondenza biunivoca con N
27
Insiemi non numerabili
Esempi:
• insieme dei numeri reali compresi
nell’intervallo chiuso [0,1]
• insieme dei numeri reali compresi
nell’intervallo aperto (0,1)
• insieme dei numeri reali
• insieme di tutte le linee nel piano
• insieme delle funzioni in una o più variabili.
28
Quante sono le funzioni da numeri
naturali in numeri naturali?
• Sono enumerabili? NO!!!
• Come possiamo dimostrare che le
funzioni da naturali in naturali non sono
enumerabili?
• Si procede con un argomento proposto
dal matematico tedesco Georg Cantor
nel 1891: la diagonalizzazione
29
Considerazioni preliminari
• Consideriamo i possibili sottoinsiemi non
vuoti dei numeri naturali: {0}, {0,1},
{2,5,7}…
• Per ogni sottoinsieme S di N possiamo
costruire una funzione che associa ad ogni
elemento di N il valore 1 se questi
appartiene ad S, e 0 altrimenti
• Le funzioni da N in N sono quindi almeno
tante quanti i sottoinsiemi di N
• Quanti sono i possibili sottoinsiemi di N?
30
I sottoinsiemi di N
• Supponiamo per assurdo che i sottoinsiemi di N
siano enumerabili
• Consideriamo la seguente tabella:
f0
f1
…
1
0
1
2
1
0
3
1
0
4
0
0
…
…
…
• fi è la funzione che identifica l’i-esimo insieme
31
Una funzione speciale
• Costruiamo la seguente funzione:
f
1
2
3
4
…
x0
x1
x2
x3
…
dove xi è 1 se l’i-esimo elemento della diagonale è 0,
0 altrimenti.
• Questa funzione definisce un sottoinsieme di N ma
non può apparire nella tabella!!!!
• Quindi l’ipotesi che le funzioni che definiscono
sottoinsiemi di N siano enumerabili non può essere
vera!
32
Funzioni non calcolabili
• Abbiamo dimostrato che un
sottoinsieme delle funzioni da N a N non
è numerabile
• Quindi tali funzioni sono più dei numeri
naturali
33
Dalle funzioni ai problemi
• Ricordiamo che un problema
computazionale è una funzione
matematica che associa ad ogni insieme
di dati il corrispondente risultato
⇒ Esistono tanti problemi computazionali
quante sono le funzioni ⇒ le funzioni non
sono numerabili ⇒ i problemi non sono
numerabili.
34
Algoritmi vs Problemi
• D’altro canto, un algoritmo è una
sequenza finita di caratteri su un
alfabeto finito, e abbiamo visto che tali
sequenze sono numerabili ⇒
|{Algoritmi}| < |{Problemi}|
⇒ Devono esistere problemi per cui non
esiste un algoritmo di calcolo, cioè
problemi non calcolabili!
35
Alla ricerca di un problema
non calcolabile
• Abbiamo dimostrato l’esistenza di
funzioni/problemi non calcolabili.
• I problemi che si presentano
spontaneamente sono tutti calcolabili.
• Non è stato facile individuare un
problema che non lo fosse.
• Turing (1930): Problema dell’arresto.
36
Il problema dell’arresto
Consiste nel chiedersi se un generico
algoritmo A avente come input un
insieme di dati D termina in tempo finito
la sua esecuzione, oppure “va in ciclo”,
ovvero continua a ripetere la stessa
sequenza di istruzioni all’infinito
(supponendo di non avere limiti di tempo
e memoria).
37
Esempio #1:
Stabilire se un intero p > 1 è primo.
Primo(p)
//scritto in C
fattore = 2;
while (p % fattore != 0)
fattore++;
return (fattore == p);
Termina sicuramente (la guardia del
while diventa falsa quando fattore = p).
38
Esempio #2
• Algoritmo che trova il più piccolo
numero intero pari (maggiore di 4) che
NON sia la somma di due numeri primi.
• L’algoritmo si arresta quando trova n ≥ 4
che NON è la somma di due primi.
39
Un corrispondente programma
Goldbach() //scritto in C
n = 2;
do {
n = n + 2;
controesempio = true;
for (p = 2; p ≤ n - 2; p++) {
q = n - p;
if (Primo(p) && Primo(q))
controesempio = false;
}
} while (!controesempio);
return n; //n non è la somma di due primi
40
Congettura di Goldbach
1792: “ogni numero intero pari n ≥ 4 è la somma di
due numeri primi”
Congettura falsa  Goldbach() si arresta
Congettura vera  Goldbach() NON si arresta
 Il programma Goldbach() è funzionalmente
utile solo nel caso in cui la congettura sia falsa!
Ad oggi la congettura è ancora aperta, ed è nota
essere vera fino a numeri dell’ordine di 1018
41
Osservazione
Un algoritmo che risolvesse il problema
dell’arresto costituirebbe dunque uno
strumento estremamente potente:
permetterebbe infatti di dimostrare in
tempo finito congetture ancora aperte
sugli interi (tipo la congettura di
Goldbach).
42
Teorema
Turing ha dimostrato che riuscire a calcolare se
un programma arbitrario si arresta e termina la
sua esecuzione non è solo un’impresa ardua, ma è
addirittura IMPOSSIBILE!
TEOREMA
Il problema dell’arresto non è calcolabile
(più precisamente, NON È DECIDIBILE).
43
DIMOSTRAZIONE (per assurdo)
Se il problema dell’arresto fosse
decidibile, allora esisterebbe un algoritmo
ARRESTO che, presi A e D come
generici dati di input, determinerebbe in
tempo finito le risposte:
ARRESTO(A,D) = 1 se A(D) termina
ARRESTO(A,D) = 0 se A(D) non termina
44
Osservazioni (1)
L’algoritmo ARRESTO non può consistere
in un algoritmo che simuli la
computazione A(D):
se A non si arresta su D, ARRESTO non
sarebbe in grado di rispondere 0 in tempo
finito.
45
Osservazioni (2)
• Osserviamo anche che il dato D può
legittimamente essere un algoritmo: gli
algoritmi sono rappresentabili con sequenze di
simboli, che possono essere presi dallo stesso
alfabeto usato per codificare i dati di input.
• Quindi, ha senso considerare l’ipotesi di dover
progettare un algoritmo che indaghi sulle
proprietà di altri algoritmi, trattando questi
ultimi come dati.
46
DIMOSTRAZIONE (1)
• Un algoritmo per algoritmi è un algoritmo
A, comunque formulato, che può operare
sulla rappresentazione di un altro algoritmo
B, che cioè calcola A(B).
• In particolare, può avere senso
determinare se A(A) termina in tempo
finito, cioè
ARRESTO(A,A) = 1
⇔
A(A) termina
47
DIMOSTRAZIONE (2)
Se esistesse l’algoritmo ARRESTO,
esisterebbe anche il seguente algoritmo:
PARADOSSO(A)
while (ARRESTO(A,A)) {
;
}
48
DIMOSTRAZIONE (3)
L’ispezione dell’algoritmo PARADOSSO
mostra che:
PARADOSSO(A) termina
⇔
x = ARRESTO(A,A) = 0
⇔
A(A) non termina
49
DIMOSTRAZIONE (4)
Cosa succede calcolando PARADOSSO(PARADOSSO)?
PARADOSSO(PARADOSSO) termina
⇔
x = ARRESTO(PARADOSSO, PARADOSSO) = 0
⇔
PARADOSSO(PARADOSSO) non termina
contraddizione!
50
DIMOSTRAZIONE (5)
L’unico modo di risolvere la contraddizione
è che l’algoritmo PARADOSSO non possa
esistere.
Dunque non può esistere nemmeno
l’algoritmo ARRESTO.
In conclusione, il problema dell’arresto è
indecidibile!
QED
51
Osservazione
Aver dimostrato che il problema dell’arresto è
indecidibile implica che non può esistere un
algoritmo che decida in tempo finito se un
algoritmo arbitrario termina la sua
computazione su input arbitrari.
Attenzione: ciò non significa che non si possa
decidere in tempo finito la terminazione di
algoritmi particolari su input particolari (o
anche arbitrari)!
52
Altri problemi non calcolabili
• Esistono risultati di non calcolabilità relativi
ad altre aree della matematica, tra cui la
teoria dei numeri e l'algebra, e per problemi
meno ‘’esoterici’’ del problema dell’arresto
• Tra questi, occupa un posto di rilievo il ben
noto decimo problema di Hilbert.
53
Equazioni diofantee
Un'equazione diofantea è un'equazione
della forma
p(x1,x2,...,xm) = 0
dove p è un polinomio a coefficienti
interi.
54
Il decimo problema di Hilbert (1)
Data un’arbitraria equazione diofantea, di
grado arbitrario e con un numero arbitrario
di incognite
p(x1,x2,...,xm) = 0
stabilire se p ammette soluzioni intere.
55
Il decimo problema di Hilbert (2)
• La questione circa la calcolabilità di
questo problema è rimasta aperta per
moltissimi anni, e ha attratto
l'attenzione di illustri matematici
• È stata risolta negativamente nel 1970
da un matematico russo allora poco più
che ventenne, Yuri Matiyasevich.
56
Problemi risolubili
Concentriamoci ora sui problemi risolubili,
ovvero quelli per cui esiste un algoritmo
risolutivo (che opera in tempo finito). Il
nostro obiettivo è ora quello di separare i
problemi trattabili da quelli intrattabili,
dove intuitivamente trattabile significa
che il problema può essere risolto prima
che sia diventato inutile averne trovato la
soluzione 
57
Complessità computazionale:
alcuni concetti di cui non è
sempre facile parlare
algoritmo
modello di
calcolo
problema
dimensione
dell’istanza
efficienza
istanza
caso
peggiore
correttezza
58
A cosa vogliamo rispondere?
CONTESTO: Abbiamo un problema a cui sono associate diverse (infinite)
istanze di diversa dimensione. Vogliamo risolvere (automaticamente) il
problema progettando un algoritmo. L’algoritmo sarà eseguito su un
modello di calcolo e deve descrivere in modo non ambiguo (utilizzando
appositi costrutti) la sequenza di operazioni sul modello che risolvono una
generica istanza. La complessità temporale/spaziale di un’esecuzione
dell’algoritmo è misurata come numero di operazioni eseguite/memoria
utilizzata sul modello e dipende dalla dimensione dell’istanza e dall’istanza
stessa. Invece, la complessità temporale/spaziale di un algoritmo è il suo
numero di operazioni eseguite/memoria utilizzata nel caso peggiore, cioè
rispetto all’istanza più difficile da trattare, normalizzato però ovviamente
rispetto alla dimensione dell’istanza stessa (perché altrimenti istanze
grandi risulterebbero più ‘’difficili’’ di istanze piccole solo per via della
loro dimensione).
DOMANDA: Quanto è difficile il problema, ovvero, qual è la complessità
temporale/spaziale del miglior algoritmo risolutivo che posso sperare di
progettare? D’ora in avanti, ci concentreremo sulla risorsa tempo
59
Modelli di calcolo
Innanzitutto, per parlare di complessità
computazionale, dobbiamo parlare di
modello di calcolo
60
Un modello storico: la macchina di
Turing
- troppo di basso livello: somiglia troppo poco ai
calcolatori reali su cui girano i programmi
- utile per parlare di calcolabilità ma meno utile
per parlare di efficienza
61
Un modello più realistico
• Macchina a registri (RAM: random access machine)
– un programma finito
– un nastro di ingresso e uno di uscita
– una memoria strutturata come un array
• ogni cella può contenere un qualunque valore intero/reale, e quindi ha
una dimensione infinita
– due registri speciali: PC e ACC
• La RAM è un’astrazione dell’architettura di von Neumann, ed è
Turing-equivalente, cioè si può dimostrare che tutto quello che
si può calcolare su una Macchina di Turing si può calcolare anche
su una RAM, e viceversa. Questo non è un caso: infatti, la tesi di
Church-Turing, universalmente accettata, afferma che tutti i
modelli di calcolo ragionevoli sono o equivalenti o meno potenti
della Macchina di Turing!
62
Macchina a registri
RAM: random access machine
nastro di Input
nastro di Output
CPU
memoria
(come un grosso
Array con celle
illimitate)
PC
ACC
PC: program counter
prossima istruzione
da eseguire
ACC: mantiene operandi
istruzione corrente
programma
finito
63
Il concetto di dimensione dell’istanza
• Formalmente, è il numero di bit strettamente
necessari per rappresentare l’istanza sul nastro di
input della RAM. Quindi, ad esempio, se l’input è un
valore numerico n, allora la dimensione dell’istanza
sarà pari alla sua codifica binaria (ed è pari quindi
ad un numero di bit logaritmico rispetto al valore,
cioè log2n)
• Si noti però che se l’input è un insieme di dati
‘’omogenei’’ di cardinalità n (ad esempio, un insieme
di numeri da ordinare), allora si assume, al fine di
semplificare l’analisi dell’algoritmo, che la
dimensione dell’input è pari ad n
64
Modello di calcolo: cosa posso fare
• L’analisi della complessità di un algoritmo è basata sul
concetto di passo elementare
• Passi elementari su una RAM
– istruzione ingresso/uscita (lettura o stampa)
– operazione aritmetico/logica
– accesso/modifica del contenuto della memoria
65
Il caso peggiore di un algoritmo
• Sia tempo(I) il numero di passi elementari di un algoritmo
sull’istanza I. Allora, la complessità computazionale
dell’algoritmo è:
T(n) = max istanze I di dimensione n {tempo(I)}
• Intuitivamente, T(n) è il numero di passi elementari
dell’algoritmo sulle istanze di ingresso che comportano più lavoro
per l’algoritmo stesso
• Perché è importante? Perché rappresenta una garanzia (cioè una
limitazione superiore) sul tempo di esecuzione su ogni possibile
istanza di input!
• Domanda: Analogamente a quanto accade con lo studio delle
funzioni in analisi matematica, ha senso caratterizzare T(n) al
tendere di n all’infinito, cioè al crescere della dimensione
dell’input?
66
Una grande idea:
la notazione asintotica
Idea: descrivere T(n) in modo qualitativo, ovvero
perdere un po’ in precisione (senza perdere
l’essenziale) e guadagnare in semplicità, al fine di
raggruppare gli algoritmi in classi di equivalenza
rispetto alla loro complessità computazionale.
67
Notazione asintotica O
f(n) = O(g(n)) se  due costanti c>0 e n0≥0 tali che
0f(n) ≤ c g(n) per ogni n ≥ n0
f(n) = ( g(n) )
cg(n)
f(n)
n0
n
68
Esempi:
Sia f(n) = 2n2 + 3n, allora
• f(n)=O(n3)
(c=1, n0=3)
• f(n)=O(n2)
(c=3, n0=3)
• f(n)  O(n)
In generale, un qualsiasi polinomio di grado
k appartiene a O(nk)
69
Notazione asintotica O e concetto di limite
fn   Ogn 

fn 
limn
c
gn 

fn 
c
gn 
asintotica mente
fn   Ogn 
fn   Ogn   limn
fn 
(se esiste)  
gn 
70
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 P ha una complessità computazionale o
upper bound O(f(n)) se esiste un algoritmo che risolve P
la cui complessità computazionale è O(f(n))
71
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)).
72
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)
• NOTA: Time(1) denota i problemi che possono essere
risolti in tempo costante, indipendentemente dalla
dimensione dell’istanza (sono quindi problemi banali)
73
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)
74
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.
75
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.
76
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.
77
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
78
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
79
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)
80
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…
81
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])
82
Gerarchia delle classi
Decidibili
P (ricerca)
NP
ExpTime
(ARRESTO(k))
NP-completi (SAT)
83
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 un 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
84
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
85