Appunti esame elementi di teoria della computazione

UNA MISURA DEL TEMPO

Il numero di passi che utilizza un algoritmo su un particolare input può dipendere da diversi parametri.

Ad esempio, se l’input è un grafo, il numero di passi può dipendere dal numero di nodi, dal numero di archi

e dal grado massimo del grafo, o da una combinazione di questi e/o altri parametri.

Il tempo di esecuzione di un algoritmo sarà calcolato in funzione della lunghezza della stringa che

rappresenta l’input senza considerare eventuali altri parametri.

Ad esempio, se l’input è un grafo G, il tempo di esecuzione di un algoritmo sui grafi sarà calcolato in

⟨ ⟩

funzione della lunghezza della codifica di G.

Considereremo l’analisi del caso peggiore, quindi valuteremo il tempo di esecuzione massimo tra tutti gli

input di una determinata lunghezza. (Non considereremo l’analisi del caso medio.)

Definizione.

(, )

= Σ, Γ, , , ,

Sia una MdT deterministica, a nastro singolo, che si arresta su ogni

0 ∶ →

input. La complessità di tempo di M è la funzione dove f(n) è il massimo numero di passi di

∈

computazione eseguiti da M su un input di lunghezza n, n N.

Se M ha complessità di tempo f(n), diremo che M decide L(M) in tempo (deterministico) f(n).

, , . . . , , ≥ 1,

Se sono configurazioni di M, tali che:

1 2 +1

=

1. è la configurazione iniziale di M con input w

1 0

→ ∈

2. per ogni i {1, . . . , k}

+1

3. è una configurazione di arresto,

+1

il numero di passi eseguiti da M su w è k. ∗

→ , ∈

Quindi, se f è la complessità di tempo di M, f(n) = massimo numero di passi in 0

{ , },

al variare di w in .

Alcune astrazioni.

• Identifichiamo gli input che hanno la stessa lunghezza,

• Valuteremo la complessità nel caso peggiore (cioè relativo alla stringa di input di lunghezza n che

richiede il maggior numero di passi),

• Non valuteremo esattamente la complessità di tempo f(n) di M ma piuttosto stabiliremo un limite

asintotico superiore per f(n), usando la notazione O-grande (analisi asintotica).

• Quindi, dire che M ha complessità di tempo O(g(n)) vuol dire che M ha complessità di tempo f(n) ed

f(n) è O(g(n)).

Analisi Asintotica

+

= insieme dei numeri reali positivi.

Definizione + +

: → , : → .

Siano f e g due funzioni ≥ 0

Diremo che f (n) è O(g(n)) oppure f (n) = O(g(n)) se esistono una costante c > 0 e una costante tali

≥

che, per ogni ,

() ≤ ().

Diremo che g(n) è un limite superiore (asintotico) per f(n).

Esempio1

. Qual è la complessità di tempo della macchina di Turing M che:

1. rifiuta se l’input è la parola vuota

2. cancella il primo carattere dell’input e accetta, se l’input è una stringa non vuota

Ovviamente in questo caso la complessità è O(1) in quanto in ogni caso la macchina esegue un numero

constante di passi indipendente dall’input.

Esempio2

. Qual è la complessità di tempo di una macchina di Turing M che copia il suo input?

2

In caso di una macchina a singolo nastro, la macchina ha complessità O( ) poiché deve scorre avanti e

indietro il nastro per ogni carattere dell’input, quindi, fa 2n passi per ogni n caratteri ossia O(2n x n).

Esempio3

.

Dato il linguaggio

= {0 1 | ≥ 0}

Abbiamo visto una MT M a nastro singolo che decide L.

Sull’input w, M: ∗ ∗

∈ (0 1 ).

1. Verifica che ⊔

2. Partendo dallo 0 più a sinistra, sostituisce 0 con poi va a destra, ignorando 0 e 1, fino a incontrare

⊔. ⊔

3. Verifica che immediatamente a sinistra di ci sia 1: se così non è, rifiuta w. Altrimenti, sostituisce 1

⊔ ⊔.

con e va a sinistra fino a incontrare

⊔:

4. Guarda il simbolo a destra di

⊔,

a. Se è un altro allora accetta w.

b. Se è 1, allora rifiuta w.

c. Se è 0 ripete a partire dal passo 2.

Analisi dell’algoritmo.

Sia |w| = n, cioè utilizziamo n per rappresentare la lunghezza dell’input.

Per analizzare M, consideriamo ciascuna delle sue quattro fasi separatamente. ∗ ∗

(0 1 ), 0 1 ,

Nella prima fase la macchina scansiona il nastro per verificare che l’input è in cioè del tipo

, ∈ . Tale operazione di scansione usa n passi, dove n = |w|. Per riposizionare la testina all’estremità

sinistra del nastro utilizza ulteriori n passi. Per cui il totale di passi utilizzati in questa fase è 2n passi. Nella

notazione O-grande diciamo che questa fase usa O(n) passi.

Si noti che non abbiamo fatto menzione del riposizionamento della testina del nastro nella descrizione della

macchina. L’utilizzo della notazione asintotica ci permette di omettere quei dettagli della descrizione della

macchina che influenzano il tempo di esecuzione al più di un fattore costante.

Le azioni 2 e 3 richiedono ciascuna O(n) passi e sono eseguite al più volte. Infatti, la macchina esegue

2

ripetutamente la scansione del nastro e cancella uno 0 e un 1 ad ogni scansione. Ogni scansione utilizza

O(n) passi. Poichè ogni scansione elimina due simboli, possono verificarsi al più scansioni. Poi la macchina

2

2 2

() + () = () + ( ) = ( ).

accetta o rifiuta. Quindi M decide L in tempo 2

Classi di Complessità.

Classificheremo i linguaggi in base alla complessità di tempo di un algoritmo che li decide.

Raggrupperemo in una stessa classe linguaggi i cui corrispondenti decider hanno complessità di tempo che

sia un O-grande della stessa funzione.

Definizione (Classe di complessità di tempo deterministico)

+

: →

Sia una funzione, sia M l’insieme delle MT deterministiche, a nastro singolo e che si arrestano su

ogni input.

La classe di complessità di tempo deterministico TIME( f(n) ) è

(()) = { | ∃ ∈ ℎ (())}

Una classe di complessità di tempo è una famiglia di linguaggi. La proprietà che determina l’appartenenza

di un linguaggio L alla classe è la complessità di tempo di un algoritmo per decidere L.

Esempio.

= {0 1 | ≥ 0}.

Torniamo al linguaggio L’analisi precedente mostra che

2

= {0 1 | ≥ 0} ∈ ( ) 2 2

( ) ( )

Infatti, abbiamo fornito una macchina di Turing M che decide L in tempo e contiene tutti i

2

( ).

linguaggi che possono essere decisi in tempo

Esiste una macchina che decide L in modo asintoticamente più veloce?

Potremmo migliorare il tempo di esecuzione, cancellando due simboli 0 e due simboli 1 ad ogni scansione

invece di uno solamente, perché questo ridurrebbe il numero di scansioni della metà.

Ma questo migliorerebbe il tempo di esecuzione solo per un fattore 2 e non influenzerebbe il tempo di

esecuzione asintotico.

La seguente macchina , utilizza un metodo differente per decidere L asintoticamente più velocemente.

2

∈ ( ).

Essa mostra che

= {0 1 | ≥ 0}

Il seguente algoritmo M (ovvero la MdT equivalente ad M) decide in tempo

( ).

= “Sulla stringa input w:

2

= 0 1

1. Verifica che (altrimenti rifiuta w)

2. Ripete le due operazioni seguenti finché almeno un carattere 0 e almeno un carattere 1 resta sul

nastro:

a. Verifica che la lunghezza della stringa sia pari (altrimenti rifiuta).

b. Cancella ogni secondo zero, a partire dal primo zero, e ogni secondo 1, a partire dal primo 1

3. Se nessun carattere uguale a 0 e a 1 resta sul nastro, accetta. Altrimenti rifiuta.”

(Correttezza dell’algoritmo.) L’algoritmo, in primo luogo, verifica se w è una stringa di caratteri uguali a 0

= 0 1

seguiti da una stringa di caratteri uguali a 1, cioè .

In ogni scansione eseguita nella fase 2b, il numero totale di 0 rimanenti è ridotto della metà e ogni

eventuale resto viene scartato. Ad esempio, dopo la prima esecuzione del passo 2b, l’algoritmo è applicato

−1 −1

+1 +1

0 1 0 1

alla stringa se t e q sono pari, alla stringa se t e q sono dispari.

2 2 2 2

Quando la fase 2a controlla che il numero totale di 0 e 1 rimanenti sia pari, in realtà sta controllando la

coerenza della parità (pari/dispari) del numero di 0 con la parità del numero di 1.

Cioè controlla che siano entrambi pari o entrambi dispari. Se le parità corrispondono sempre, le

rappresentazioni binarie dei numeri t di 0 e q di 1 coincidono, e quindi i due numeri sono uguali.

Questo perché la sequenza delle parità fornisce sempre l’inversa della rappresentazione binaria.

Per analizzare il tempo di esecuzione di , per prima cosa osserviamo che le fasi 1 e 3 vengono eseguite

2

una volta, impiegando un tempo totale O(n).

Poi osserviamo che si tratta di un ciclo, l’iterazione è evidenziata al passo 2.

Ogni fase del ciclo richiede tempo O(n) = O(|w|).

Determiniamo poi il numero di volte in cui ognuna viene eseguita.

La fase 2b scarta almeno metà dei simboli 0 e 1 ogni volta che viene eseguita, quindi si verificano al

massimo O(log|w|) iterazioni del ciclo prima di averli cancellati tutti.

Il tempo totale delle fasi 2,2a, e 2b è O(n log n). Il tempo di esecuzione di è O(n) + O(n log n) = O(n log

2

n).

Da ciò otteniamo che: 2

= {0 1 | ≥ 0} ∈ ( ) ∈ ( )

Differenze tra teoria della computazione e teoria della complessità.

Abbiamo parlato di complessità di tempo di una MdT deterministica, a nastro singolo, che si arresta su ogni

input. Anche nella definizione di classe di complessità abbiamo fatto riferimento al modello a nastro

singolo.

Potremmo definire più in generale e in maniera analoga la complessità di tempo di una MdT deterministica

multinastro. Cambierebbe qualcosa?

La complessità di tempo