Lezione 2 - Algoritmi (parte 2)

Alcune note attorno al concetto di Algoritmo.

 

Non vi è un limite superiore alla dimensione dell'input. Non vi è limite superiore alla memoria di lavoro.

Nonostante i requisiti di finitezza. Bisogna prestare attenzione a non porre limitazioni superiori alle dimensioni degli stati. Infatti, banalmente noi vogliamo poter calcolare mcd(m,n) per ogni valore di m,n naturale. Quindi non vi possono essere limiti superiori per i valori di m,n. Lo stesso per il numero dei passi di calcolo, e quindi per la memoria temporanea (variabili) usate durante i calcoli. Notare che questo non contraddice l'ipotesi di finitezza, perchè per quanto non limitabili superiormente le quantità citate sono comunque sempre finite.

La sequenza delle istruizioni è definita in modo da poter individuare senza ambiguità qual'è l'istruzione successiva a quella appena eseguita.

Un algoritmo specifica in modo non ambiguo la sequenza delle operazioni. I passi dello pseudo-codice sono ordinati, e di solito l'ordine di esecuzione è sequenziale (si eseguono le istruzioni seguendo l'ordine specificato nel testo dello pseudo-codice). Le istruzioni di controllo del flusso (salta a..) possono modificare quest'ordine in questo caso è importante distinguere due casi:

  • Algoritmi Deterministici: le istruzioni di controllo del flusso d'esecuzione, possono cambiare l'ordine d'esecuzione delle istruzioni, solo in funzione del valore delle variabili usate dall'algoritmo (compreso le variabili d'input). Il calcolo è completamente Deterministico, fissato l'input, l'algoritmo produce sempre la stessa computazione, in particolare la stessa sequenza di stati intermedi, e lo stesso stato finale.
  • Algoritmi Randomizzati: le istruzioni di controllo del flusso d'esecuzione possono cambiare l'ordine d'esecuzione in funzione di variabili aleatoree (numeri casuali). Si assume che l'esecutore, può generare una sequenza di valori casuali con distribuzione uniforme (equiprobabili). A partire da questa sequenza è possibile generare distribuzioni di probabilità diverse. Quindi due esecuzioni diverse dello stesso algoritmo con lo stesso input, in generale, possono dare risultati diversi.

L'ipotesi che l'esecutore disponga di un generatore di numeri casuali è piuttosto forte. Come vedremo nel corso è possibile per algoritmi deterministici generare delle sequenze dette pseudo-casuali. Queste sequenze simulano in modo statisticamente accettabile il comportamento di un generatore casuale. Pertanto, nonostante un algoritmo che usi numeri pseudo-casuali resti comunque deterministico, esso può essere considerato un'approssimazione di un algoritmo randomizzato e viene generalmente indicato con questo termine.

Dato un problema (computazionale) P, esiste solo un algoritmo A che calcola una soluzione di P a partire dai dati iniziali? Se ne esiste più di uno, allora in cosa si differenziano?

Abbiamo visto che un algoritmo corretto A è definito da una funzione totale che determina i passi di un procedimento di trasformazione da stato in stato . La funzione è definita su ogni (stati iniziali) ed il risultato del calcolo è uno stato finale . Poichè gli stati sono descrivibili in modo finito, è possibile dimostrare che ogni è codificabile in un numero naturale. Esiste cioè una corrispondenza biunivoca . Possiamo quindi associare ad ogni algoritmo la funzione totale:

Notiamo inoltre che la costante ha un significato preciso: è il numero di passi impiegati dall'algoritmo per risolvere il problema sull'istanza , nell'ipotesi (semplificatrice) che ogni passo della funzione di transizione impieghi tempo unitario (le operazioni atomiche usate dalla sono semplici e tutte eseguibili in un unico passo). Possiamo quindi associare all'algoritmo A anche un altra funzione definita come che indica la sua complessità di tempo (dettagli sotto).

In generale, dato un problema, abbiamo molti (infiniti) algoritmi A,A',A'' che calcolano la stessa funzione: . Se ad esempio A è l'algoritmo di Euclide, possiamo creare infiniti algoritmi che calcolano il massimo comune divisore semplicemente aggiungendo un ulteriore passo n. 4, con l'istruzione con un numero naturale arbitrario. Notate che il passo 3 dell'algoritmo salta in ogni caso al passo 1, e il passo 2 termina l'esecuzione o passa al passo 3, quindi il passo 4 non verrà mai eseguito ma nondimeno contribuisce al testo dell'algoritmo e quindi a definire la funzione di transizione associata (che quindi definisce delle trasformazioni di stato che non saranno mai calcolate), la funzione invece è sempre la stessa (il calcolo del massimo comune divisore). E' facile estendere questo ragionamento anche al testo di un Programma (che d'altra parte è la trascrizione in un linguaggio di programmazione specifico di un algoritmo); quindi in generale esistono infiniti programmi per un certo problema calcolabile algoritmicamente. Notiamo inoltre che nell'esempio sopra, è immediatamente evidente che gli algoritmi calcolano la stessa funzione, ma in generale come vedremo successivamente decidere se due algoritmi (o programmi) diversi calcolano la stessa funzione (risolvono lo stesso problema) è uno di quei problemi che purtroppo non ammettono nessuna soluzione algoritmica, sono cioè non-calcolabili.

Se esiste più di un algoritmo che risolve un problema quale usiamo? è possibile definire un ordinamento in termini di peggiore/migliore tra algoritmi, rispetto a quali parametri?

Supponiamo di disporre di due algoritmi per lo stesso problema. Un modo per distinguerli è definire un concetto di efficienza per ognuno di essi. Un modo per definire tale concetto prende in considerazione le risorse necessarie all'algoritmo durante la sua esecuzione, tali risorse sono normalmente il tempo d'esecuzione (numero di passi di calcolo) e lo spazio di memoria (dimensione dello stato), la quantità di queste risorse usate si chiama complessità computazionale (rispettivamente di tempo e di spazio).

Abbiamo definito già la funzione che associa ad uno stato iniziale il numero di passi impiegati dall'algoritmo per risolvere il problema. Che caratteristiche ha ? Il numero di passi impiegati da può cambiare molto tra un istanza e l'altra, anche in modo drammatico. In generale però, possiamo aspettarci che le istanze del problema siano naturalmente associate ad un concetto di dimensione, e che la funzione sia non-decrescente rispetto a questo concetto. Ad esempio, nel caso di Euclide, è chiaro che

cioè banalmente il tempo cresce con la dimensione dei numeri coinvolti nel calcolo. Un altro esempio: se devo moltiplicare due matrici , il tempo dipende più che dai numeri dentro le matrici, dalla dimensione , quindi ci aspettiamo che moltiplicare matrici possa essere fatto più velocemente che per matrici . Possiamo quindi definire in modo più utile la complessità computazione di un algoritmo non come funzione delle singole istanze, ma come funzione della dimensione dell'istanza.

Definiamo quindi per iniziare il nostro concetto di dimensione e indichiamolo con la funzione . Partizioniamo in sottoinsiemi con . Definiamo allora complessità di tempo dell'algoritmo A nel caso peggiore come:

cioè: il peggior tempo d'esecuzione impiegato da A per risolvere un istanza del problema di dimensione . Usiamo il tempo associato all'istanza peggiore perche esso fornisce una chiara limitazione superiore al tempo d'esecuzione su tutte le istanze di quella dimensione, e quindi una garanzia che la funzione di transizione applicata a input di dimensione terminerà al più in passi.

Esistono problemi difficili da risolvere? (in che senso?)

Visto che come spiegato sopra è possibile definire in modo preciso quante risorse usa un certo algoritmo durante la sua esecuzione, è naturale pensare alla difficoltà di un algoritmo proprio in termini della sua complessità in tempo. In particolare, nel comportamento asintotico della funzione .

La cosa fondamentale come vedremo durante il corso è che esiste una classe molto ampia di problemi che sono risolvibili algoritmicamente, ma la funzione ha forma esponenziale, ad esempio: . Questa classe di problemi è definita difficile proprio perché vista la velocità molto rapida di crescita del tempo d'esecuzione, nella pratica esisterà una costante (purtroppo abbastanza piccola) tale che .

Il che rende chiaramente solvibile il problema, ma piuttosto inutile dal punto di vista della persona che prova a usare l'algoritmo A, il fatto che esso esista.

Tutti i problemi computazionali sono risolvibili? Esiste cioè un algoritmo per ogni problema?

Un problema computazionale è modellato, come già spiegato, come una funzione (parziale) dai naturali ai naturali. Dimostriamo che esistono problemi che non ammettono nessun algoritmo.  Sappiamo già che (vedi post Contare L'infinito). Di solito i matematici chiamano numerabili gli insiemi infiniti con cardinalità , mentre è chiamata anche cardinalità del continuo o semplicemente continuo.

E' facile verificare che l'insieme di tutte le funzioni dai naturali ai naturali ha la cardinalità del continuo. Per far questo usiamo:

Teorema di Cantor: Per ogni insieme , , dove è l'insieme delle parti di , cioè l'insieme dei suoi sottoinsiemi.

Consideriamo il sottoinsieme , ogni elemento di questo insieme può essere messo in corrispondenza biunivoca con un sottoinsieme di . Infatti, data possiamo associarla all'insieme , e viceversa, dato un sottoinsieme di la sua funzione indicatrice (o caratteristica) è chiaramente un elemento di ; quindi per Cantor .

Adesso consideriamo la cardinalità dell'insieme delle funzioni associate ad algoritmi scritti nello pseudo-codice; cioè l'insieme . Vedremo che questo insieme è numerabile. Infatti gli algoritmi sono testi, e come tali, possono essere ordinati per ordine di lunghezza crescente. A parità di lunghezza, è possibile ordinarli in ordine alfabetico. Il dettaglio di questo modo di ordinare il "testo" dell'algoritmo dipenderà dal linguaggio (o meglio pseudo-linguaggio usato) ma è sempre possibile costruire questo "elenco". Notiamo che un elenco ordinato non è altro che una biiezione con .

Quindi da una parte le funzioni dai naturali ai naturali sono in quantità più che numerabile, e dall'altra, l'insieme delle funzioni calcolabili è numerabile. Esistono quindi infinite funzioni per cui non esiste alcun algoritmo. Tali funzioni sono dette non-calcolabili. Inoltre esisteranno infiniti tali che la funzione caratteristica di è non-calcolabile, tali insiemi si dicono non-decidibili (poichè appunto, non è possibile calcolare se ).

Notate che l'insieme dipende dal formalismo usato per scrivere i nostri algoritmi, quindi potrebbe sembrare che tale dimostrazione (di non calcolabilità di certi problemi) sia da rifare per ogni eventuale linguaggio con cui esprimiamo i nostri algoritmi. Nell'ambito dell'informatica teorica sono stati sviluppati moltissimi linguaggi (o meglio formalismi) per definire algoritmi. La cosa interessante è che ogni formalismo sufficientemente potente da poter calcolare funzioni come il massimo comune divisore è stato dimostrato equivalente ad ogni altro formalismo sviluppato anche di tipo molto diverso. Leggete la bibliografia di  Alan Turing (videoEnigmaMdTIA). Tutti i modelli di calcolo di questo tipo si dicono Turing-equivalenti ed i computer attuali soddisfano questa definizione, sono cioè delle versioni ultra-accelerate e un po speciali (ma non troppo) di una macchina di Turing.

Gli Informatici esprimono tramite una tesi (non un teorema), chiamata tesi di Church-Turing, l'idea che la nozione (intuitiva) di calcolabilità coincida con la nostra definizione di algoritmo e che tale risultato non dipenda dal particolare formalismo usato per descrivere i nostri algoritmi. La calcolabilità o meno di un problema pertanto non dipende dai limiti di questo o quel modello di calcolo (se comunque sono Turing-equivalenti) ma è intrinsica a certi problemi, le funzioni calcolabili sono dette anche Turing-calcolabili.