Aniello Murano » 1.Overview del corso

Obiettivi del Corso

Il corso è costituito da un’introduzione alla calcolabilità dei problemi e alla loro complessità strutturale.

La teoria della calcolabilità si occupa di stabilire se un problema è risolvibile o meno.

La teoria della complessità è quella parte della teoria della calcolabilità che si occupa di stabilire le quantità di risorse necessarie durante la computazione per risolvere un dato problema. Solitamente, per risorse si intende:

• tempo (quante operazioni occorre fare per risolvere il problema;
• spazio (quanta memoria ha bisogno una algoritmo per essere eseguito);
• altre risorse come ad esempio “quanti processi paralleli sono necessari per risolvere un dato problema”.

Scopo di questo corso è fornire dunque agli studenti gli strumenti necessari per comprendere e affrontare la difficoltà nel risolvere alcuni problemi comuni da un punto di vista computazionale.

Un esempio pratico (segue)

Nel caso peggiore, l’algoritmo Naive deve eseguire un numero di operazioni dell’ordine di n! (n fattoriale)
Viene subito da chiedersi se questo tempo, in termini pratici, è un tempo ragionevole. Facciamo un po’ di conti …

• Per n=5 occorrono 120 operazioni.
• Per n=20 occorrono 2.432.902.008.176.640.000 (2*10¹⁹) operazioni. Supponiamo che abbiamo una macchina in grado di eseguire 10¹⁰ operazioni al secondo e che 3 anni sono circa 10⁸ secondi. Per n=20 ci vogliono circa 60 anni!!!!
• Per n=100 occorrono numero di operazioni dell’ordine di 10¹⁵⁶, dunque un numero di anni dell’ordine di 10¹³⁸!!!!!

Problemi trattabili vs Problemi non trattabili

Per il problema appena visto, cosa è lecito chiedersi e cosa si può concludere:
Il problema e’ risolvibile? Sì (esiste un algoritmo che lo risolve).
Esiste un algoritmo con una performance migliore? La risposta negativa si può provare formalmente con il concetto di “riduzione” (che vedremo in seguito). Per dare una intuizione, bisogna sapere che esistono problemi per i quali non è mai stato trovato un algoritmo migliore di una certa soglia. La “riduzione” della soluzione di uno di questi problemi a quello in esame, porta a concludere che anche quello in esame si deve comportare allo stesso modo.
Se il miglior algoritmo ha un tempo di esecuzione che nel caso peggiore si comporta come quello Naive visto in precedenza, si conclude che il problema affrontato richiede un tempo esponenziale e dunque che si tratta di un problema “intrattabile“. In termini asintotici, si dice che l’algoritmo ha una complessità di tempo O(2^{n log n}).

Programma del corso

• Concetto di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.
• Problemi computazionali: descrizione, istanze, codifica, relazione con i linguaggi: automi e PDA.
• Modelli di calcolo: Macchina di Turing (MdT). Introduzione della classe P
• Le classi di complessità P e NP. Relazione tra NP e P.
• Complessità in spazio
• Teorema di inclusione tra classi in tempo e in spazio.
• Concetto di Macchina di Turing Universale. Teorema di Savitch.
• Riduzioni e completezza! Riduzioni e completezza! Riduzioni e completezza!
• Riduzioni e completezza! Riduzioni e completezza! Riduzioni e completezza!

Per la seconda parte verranno trattati problemi specifici della logica temporale, teoria degli automi e della teoria dei giochi. Per tutti questi problemi verranno poi affrontate questioni di Calcolabilità e Complessità.

Alcuni concetti fondamentali

Nella teoria della calcolabilità i seguenti tre concetti fondamentali si susseguono costantemente:

• Problema: Cosa si vuole computare.
• Modello: Chi risolve il problema.
• Algoritmo: Come si risolve il problema.

Il problema si può vedere come una funzione che dato un input (una istanza del problema) produce il corretto output.
Un esempio di problema può essere la ricerca di un valore x in un ABR T, dove l’input è una coppia (T,x) e l’output è “yes” se x è in T.
In questo corso ci occuperemo principalmente di problemi decisionali, di ricerca, di ottimizzazione, giochi, ecc.

Un modello di computazione può essere un computer sequenziale (o una macchina di von Newman), un computer parallelo, un circuito booleano, ecc. In questo corso considereremo principalmente macchine di Turing (deterministiche, nondeterministiche, a più nastri, ecc.) nonché automi e PDA.

Un algoritmo, è un metodo per risolvere il problema dato su un determinato modello computazionale.

Risorse di calcolo e complessità dei problemi

L’esecuzione di un algoritmo comporta il dispendio di risorse di vario tipo: tempo, spazio, processori (nel caso di computazioni parallele), canali di comunicazioni (nel caso di computazione distribuita), ecc.
La complessità di un algoritmo rispetto ad una data risorsa è l’ammontare di quella risorsa consumata per la sua esecuzione. Dunque, a seconda della risorsa di interesse si può parlare di complessità di tempo (time-complexity), di complessità di spazio (space-complexity), ecc. In questo corso ci occuperemo quasi esclusivamente di time- e space-complexity.
La complessità di un problema rispetto ad una data risorsa è la minima quantità di quella risorsa necessaria affinché un algoritmo possa risolvere quel problema.
L’obiettivo principale della teoria della complessità è

Caratterizzare la complessità dei problemi e classificarli in classi di complessità

Una classe di complessità è un insieme di problemi, ognuno dei quali ha una complessità in un range ben definito.

Raggiungibilità di un nodo in un grafo

Input: Grafo orientato G = (N,E), nodo sorgente s, nodo target t.
Questione da risolvere: verificare se c’è un percorso in G da s a t?
Problema decisionale: output = Si/No

Graph Search
for each v _ N-{s} do {mark[v]=0}
mark[s]=1 ;
Q = {s}
while Q ≠ø do

{ select a node u and delete if from Q
for each v _ N do
if (A[u,v]=1 and mark[v]=0) then
{mark[v]=1; Q=Q _ {v} }
}

If mark[t]=1 then print "Yes" else print "No"

Per calcolare la complessità di questo algoritmo si deve considerare come è implementato G

Matrice di adiacenza

Lista di adiacenza

Time Complexity

Si assuma che G sia implementato con matrice di adiacenza.
L’algoritmo visita ogni elemento della matrice solo una volta quando il vertice corrispondente alla sua riga è stato scelto.
Inoltre, tutte le altre operazioni richieste dall’algoritmo come, scegliere un elemento di Q, marcare un vertice, o dire se esso e marcato o meno, possono essere eseguite in tempo costante
Siccome la matrice ha n² posizioni dove n è il numero dei nodi nel grafo, si deduce che la time-complexity è proporzionale a n². Cioè la time-complexity è O(n²).
La notazione O esprime la complessità dell’algoritmo nel caso peggiore. In pratica, la notazione O permette di sopprimere le costanti dal calcolo preciso della complessità.
In realtà è possibile provare che la complessità è indipendente dalla implementazione di G e dalla implementazione di S. In particolare, anche nel caso in cui S sia una coda (in tal caso l’elemento si scegli in base ad una BFS) o nel caso di uno stack (in tal caso l’elemento si scegli in base ad una DFS).

Growth Rate: Sketch

I problemi rispetto alla complessità per risolverli

Un altro problema

Si supponga di avere una serie di città (rappresentate da un grafo orientato).
Problema: E’ possibile visitare tutte le città esattamente una volta.
Soluzione (naive): Si cercano cioè tutte le città raggiungibile e che non sono state ancora visitate e per queste si considera una possibile visita delle città.
Domanda: Questo problema è trattabile?
Possibili risposte:

• Sì! Fornendo un algoritmo efficiente.

• NO! Provandolo formalmente

Per il No si può utilizzare il concetto di riduzione fra problemi.
Per esempio, uno si può chiedere se è possibile risolvere il problema degli ospiti a tavola una volta risolto il problema del tour.

Relazione tra Problemi

Assumendo l’esistenza di un algoritmo efficiente per il “problema del tour”, c’è allora un algoritmo efficiente per il “problema degli ospiti a tavola”

Il problema degli ospiti a tavola (OSPITI) non può essere “radicalmente” più difficile del problema del tour (TOUR)

La classe dei Problemi NP-completi (NP-C)