Guido Proietti

Didattica e Fondamenti degli Algoritmi e della Calcolabilità

Seconda giornata: modelli di calcolo, complessità computazionale e analisi asintotica

Guido Proietti

Email: guido.proietti@univaq.it

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

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(x

,x

,...,x

) = 0

dove p è un polinomio a coefficienti interi.

Ad esempio: 2x

+5y

-7z

=0

x

+y

-z

=0

x

+2y

-z

-12w

=0

Il decimo problema di Hilbert (1)

Data un’arbitraria equazione diofantea, di grado arbitrario e con un numero arbitrario di incognite p(x¹,x²,...,x^m) = 0, decidere

algoritmicamente se p ammette soluzioni intere (cioè in Z).

Ad esempio:

2x⁴+5y⁵-7z³=0 ha soluzioni? Sì, ad esempio x=y=z=1

x²+y²-z²=0 ha soluzioni? Sì, infinite (le terne pitagoriche, ad esempio x=3,y=4,z=5) x⁵+y⁵-z⁵=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!!!)

x⁴+y⁴+z⁴-w⁴=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:

2682440⁴ + 15365639⁴ + 18796760⁴ - 20615673⁴ = 0)

3x⁴+2y⁵-12z³+27w¹⁷=0? Boh… ⁵

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.

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

problema

istanza

modello di calcolo dimensione

dell’istanza caso

peggiore

efficienza

correttezza

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 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

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

Macchina a registri

RAM: random access machine

memoria

(array di dimensione infinita con celle

illimitate)

programma finito

nastro di Input

nastro di Output

PC ACC

CPU

PC: program counter prossima istruzione da eseguire

ACC: mantiene operandi

istruzione corrente ¹³

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è log

n)

• 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

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

• Sia tempo(I) il numero di passi elementari di un algoritmo sull’istanza I. Allora, la complessità computazionale

dell’algoritmo è:

T(n) = max

{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!

Il caso peggiore di un algoritmo

Una grande idea:

la notazione asintotica

17

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.

f(n) = O(g(n)) se  due costanti c>0 e n

≥0 tali che 0f(n) ≤ c g(n) per ogni n ≥ n

Notazione asintotica O

cg(n) f(n) f(n) =



Esempi:

Sia f(n) = 2n

+ 3n, allora

• f(n)=O(n

) (c=1, n

=3)

• f(n)=O(n

) (c=3, n

=3)

• f(n)  O(n)

In generale, un qualsiasi polinomio di

grado k appartiene a O(n

) (e quindi anche a O(n

), O(n

), …)

19

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e strutture dati

Legame con il concetto di limite

Se g(n) è definitivamente diversa da 0 per n∞ (praticamente, tutti i casi di nostro interesse), avremo che

 

   

^{ } _{ }

g n lim f

n g n

f O _n

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)

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