Didattica e Fondamenti degli
Algoritmi e della Calcolabilità
Seconda giornata: modelli di calcolo,
complessità computazionale e analisi
asintotica
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
Riassunto
• Abbiamo imparato che non tutti i
problemi sono risolubili
algoritmicamente
• Ad esempio, decidere se un algoritmo
arbitrario su un input arbitrario termina
2
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.
3
Equazioni diofantee
Un'equazione diofantea è un'equazione in
più variabili della forma
p(x1,x2,...,xm) = 0
dove p è un polinomio a coefficienti interi.
Ad esempio: 2x4+5y5-7z3=0
x2+y2-z2=0
x5+2y2-z5-12w9=0
ma anche una classicissima equazione lineare:
3x+y-1=0
4
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, decidere
algoritmicamente se p ammette soluzioni intere (cioè in Z).
Ad esempio:
2x4+5y5-7z3=0 ha soluzioni? Sì, ad esempio x=y=z=1
x2+y2-z2=0 ha soluzioni? Sì, infinite (le terne pitagoriche, ad esempio x=3,y=4,z=5)
x5+y5-z5=0 ha soluzioni non banali (cioè diverse da x=y=z=w=0)?
No, ultimo teorema di Fermat (enunciato in forma di congettura nel 1637, e
risolto da A. Wiles nel 1994!!!)
4
x +y4+z4-w4=0 ha soluzioni non banali?
Eulero alla fine del ‘700 congetturò che non avesse soluzioni non banali, ma si
sbagliava: nel 1988 è stato dimostrato che ammette soluzioni, e anzi, che ne
ammette infinite (si può dimostrare partendo da:
26824404 + 153656394 + 187967604 - 206156734 = 0)
3x4+2y5-12z3+27w17=0? Boh…
5
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.
6
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 .
Andiamo dunque al cuore dell’algoritmica,
ovvero parliamo della complessità
computazionale.
7
Complessità computazionale:
alcuni concetti di cui non è
sempre facile parlare
algoritmo
modello di
calcolo
problema
dimensione
dell’istanza
efficienza
istanza
caso
peggiore
correttezza
8
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 su una specifica istanza è misurata come numero di
operazioni eseguite/memoria utilizzata sul modello di calcolo prescelto, e
dipende dalla dimensione dell’istanza e dall’istanza stessa.
DOMANDA 1: Qual è invece la complessità temporale/spaziale assoluta
dell’algoritmo? È il 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 2: Quanto è difficile il problema, ovvero, qual è la complessità
temporale/spaziale del miglior algoritmo risolutivo che posso sperare di
9
progettare? D’ora in avanti, ci concentreremo sulla risorsa tempo
Modelli di calcolo
Innanzitutto, per parlare di complessità
computazionale, dobbiamo parlare di
modello di calcolo
10
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 complessità computazionale
11
Un modello più realistico
• Macchina a registri (RAM: random access machine)
– un programma finito, che rappresenta la codifica di un algoritmo
– un nastro di ingresso e uno di uscita
– una memoria strutturata come un array di dimensione infinita
• 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!
12
Macchina a registri
RAM: random access machine
nastro di Input
nastro di Output
CPU
memoria
(array di dimensione
infinita con celle
illimitate)
PC
ACC
PC: program counter
prossima istruzione
da eseguire
ACC: mantiene operandi
istruzione corrente
programma
finito
13
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
14
Modello di calcolo: cosa posso fare
• L’analisi della complessità di un algoritmo è basata sul
concetto di passo elementare
• Passi elementari di costo unitario su una RAM
– istruzione ingresso/uscita (lettura o stampa di un elemento
in input/output)
– operazione aritmetico/logica sugli operandi
– accesso/modifica del contenuto di una cella della memoria
15
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?
16
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.
Nota: nel seguito ci concentreremo su funzioni
intere positive.
17
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
18
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) (e quindi anche a
O(nk+1), O(nk+2), …)
19
Legame con il concetto di limite
Se g(n) è definitivamente diversa da 0 per
n∞ (praticamente, tutti i casi di nostro
interesse), avremo che
fn   Ogn 

limn
fn 
gn 

ovvero f(n)=O(g(n) se e solo se f(n) è un
infinito di ordine non superiore a g(n)
20
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))
22
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)).
NOTA: Time(1) denota i problemi che possono essere
risolti in tempo costante, indipendentemente dalla
dimensione dell’istanza (sono quindi problemi banali)
23
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, e a darne dimostrazione di
correttezza?
24