Algoritmi e strutture dati

Introduzione agli algoritmi

Aingresso x di A il corrispondente valore in uscita f (x).

A1.4.5 Nota storica

La parola "algoritmo" ha origine nel Medio Oriente. Essa proviene dall'ultima parte del nome dello studioso persiano Abu Jàfar Mo-hammed ibn Musa al-Khowarizmi, il cui testo di aritmetica (825d.C. circa) esercitò una profonda influenza nei secoli successivi.

Tradizionalmente gli algoritmi erano impiegati esclusivamente per risolvere problemi numerici. Tuttavia, l'esperienza con i calcolatori ha dimostrato che i dati possono virtualmente rappresentare qualunque cosa.

Di conseguenza, l'attenzione della scienza dei calcolatori si è trasferita allo studio delle diverse strutture con cui si possono rappresentare le informazioni, e all'aspetto ramificato o decisionale degli algoritmi, che permette di eseguire differenti sequenze di operazioni in dipendenza dello stato delle cose in un particolare istante.

È questa la caratteristica che rende talvolta preferibili.

Per la rappresentazione e l'organizzazione delle informazioni, i modelli algoritmici sono preferibili ai modelli matematici tradizionali (D.E. Knuth).

Definizione formale di problema.

Definizione 1: Un problema è una funzione P : D → D definita su un insieme D di elementi che chiamiamo istanze, ed a valori su un insieme D di soluzioni. Diciamo che un algoritmo A risolve un problema P se P(x) = f(x) per ogni istanza x.

Programma

La seguente definizione di programma è dovuta a D.E. Knuth, uno dei padri fondatori dell'informatica:

Un programma è l'esposizione di un algoritmo in un linguaggio accuratamente definito. Quindi, il programma di un calcolatore rappresenta un algoritmo, per quanto l'algoritmo stesso sia un costrutto intellettuale che esiste indipendentemente da qualsiasi rappresentazione. Allo stesso modo, il concetto di numero 2 esiste nella nostra mente anche quando non sia espresso graficamente. (D.E. Knuth)

Programmi per risolvere problemi numerici sono stati

1.7 Costi

Ad ogni programma di calcolo sono associati dei costi.

1.7. COSTI

• L'Ingegneria del Software si occupa tra l'altro di minimizzare i costi relativi allo sviluppo (analisi del problema, progettazione, implementazione) dei programmi ed alla loro successiva manutenzione;
• La Teoria della Complessità Computazionale si occupa tra l'altro di minimizzare i costi relativi alla esecuzione dei programmi.

Inutile dirsi, le due aree difficilmente si conciliano tra loro: non solo gli obiettivi sono diversi, ma anche i metodi utilizzati.

1.7.1 Risorse di calcolo

Definizione 2: Il costo relativo all'esecuzione di un programma viene definito come la quantità di risorse di calcolo che il programma

1. Il Tempo utilizzato per eseguire l'algoritmo;
2. Lo Spazio di lavoro utilizzato per memorizzare i risultati intermedi.
3. Il Numero degli esecutori, se più esecutori collaborano per risolvere lo stesso problema.

• lo spazio di lavoro diventa la memoria del calcolatore;
• il numero degli esecutori diventa il numero dei processori a nostra disposizione, in un sistema multi-processore.

1.7.2 Efficienza.

Definizione 3: Un algoritmo è efficiente se fa un uso contenuto (ovvero "parsimonioso") delle risorse a sua disposizione.

18 CAPITOLO 1. INTRODUZIONE

È molto

Importante saper valutare la quantità di risorse consumate, poiché un consumo eccessivo di risorse può pregiudicare la possibilità di utilizzo di un algoritmo. Per valutare correttamente il consumo di risorse di un algoritmo è necessario fissare a priori un modello di calcolo, e definire in base a questo:

• la nozione di algoritmo;
• la nozione di risorse consumate.

Modello di calcolo

Definizione 4: Un modello di calcolo è semplicemente una astrazione di un esecutore reale, in cui si omettono dettagli irrilevanti allo studio di un algoritmo per risolvere un problema. Esistono tanti differenti modelli di calcolo (Macchina di Turing, RAM, ecc.). L'adozione di un particolare modello di calcolo dipende da vari fattori:

1. capacità espressiva del modello in relazione al problema assegnato; in altre parole, un modello è preferibile ad un altro per esprimere la soluzione algoritmica di un determinato problema;
2. livello di astrazione, ovvero il livello di dettaglio;

generalità; ovvero esistono modelli più generali di altri (un primo modello è più generale di un secondo se tutti i problemi risolubili con il secondo sono risolubili con il primo). Uno dei risultati più sorprendenti della teoria riguarda l'esistenza di modelli di calcolo assolutamente generali. Uno di questi è la macchina di Turing.

1.7.4 Irrisolubilità

Definizione 5: Un problema è non risolubile algoritmicamente se nessun procedimento di calcolo è in grado di fornire la soluzione in tempo finito. Un risultato piuttosto sconcertante riguarda l'esistenza di problemi non risolvibili algoritmicamente.

1.7. COSTI 19

Esempio 4: Un noto problema non risolvibile algoritmicamente è il problema dell'ALT della macchina di Turing.

La logica matematica si occupa (tra l'altro) dei limiti della computabilità, ovvero dello studio e della classificazione dei problemi non risolvibili algoritmicamente.

1.7.5 Intrattabilità

Definizione 6: Un problema è intrattabile se...

qualunque algoritmo che lorisolva richieda una quantità molto elevata di risorse. La logica matematica fornisce alla teoria degli algoritmi gli strumenti per riconoscere e classificare i problemi intrattabili. Problemi intrattabili sorgono ad esempio in giochi quali la dama o gli scacchi.

Capitolo 1. INTRODUZIONE

Capitolo 2. La macchina di Turing

In questa lezione sarà esaminato un modello di calcolo molto generale, la Macchina di Turing. Tale argomento è stato probabilmente già presentato nel corso di Programmazione, per introdurre in modo assolutamente formale la nozione di algoritmo e la Tesi di Church.

Nel contesto del nostro corso la Macchina di Turing è un eccellente strumento didattico, poichè ci consente di definire esattamente la nozione di algoritmo, ma sopratutto ci consente di definire in modo semplice ed inequivocabile la nozione di risorse utilizzate da un algoritmo (spazio e tempo).

In virtù dell’esistenza di un modello di calcolo assolutamente generale, la

nozione di irrisolubilità già introdotta nelle lezioni precedenti assumerà nuova luce. Al fine di agevolare la comprensione dell'argomento, saranno presentate durante la lezione alcune Macchine di Turing molto semplici.

2.1 Definizione di Macchina di Turing

Una Macchina di Turing consiste di:

• Un nastro infinito, suddiviso in cellette. Ogni celletta può contenere un solo simbolo, tratto da un insieme finito S detto alfabeto esterno.
• Una testina di lettura capace di leggere un simbolo da una celletta, scrivere un simbolo in una celletta, e muoversi di una posizione sul nastro, in entrambe le direzioni.
• Un insieme finito Q di stati, tali che la macchina possa trovarsi in esattamente uno di essi in ciascun istante.
• Un programma, che specifica esattamente cosa fare per risolvere un problema specifico.

2.1.1 L'alfabeto esterno della M.d.T.

L'alfabeto esterno S = {s1, ..., se} è utilizzato per codificare

L'informazione1 kin input e quella che la MdT produce nel corso della computazione. Assumiamo che S contenga un simbolo speciale detto lettera vuota oblank, indicato con b. Diciamo che una cella è vuota se contiene b. Scrivendola lettera vuota b in una cella viene cancellato il contenuto di quella cella.

2.1.2 Gli stati della M.d.T.

I possibili stati di una macchina di Turing sono denotati q , q , . . . , q , q , q .1 2 n 0 f

• Gli stati q , . . . , q sono detti stati ordinari.1 n

• Lo stato q è detto stato iniziale.0

• Lo stato q è detto stato finale.f

2.1.3 Configurazione iniziale della MdT.

La macchina di Turing si trova inizialmente nello stato q . L’informazione0da elaborare è contenuta in cellette contigue del nastro, ed è codificata uti-lizzando i simboli dell’alfabeto esterno S. Tutte le altre cellette del nastrocontengono inizialmente la lettera vuota. La testina di lettura scrittura èposizionata in corrispondenza del primo simbolo valido.

(quello che si trova più a sinistra).

2.1.4 Il programma nella M.d.T.

Indichiamo con q lo stato in cui la MdT si trova ad un certo istante, e con sil simbolo che si trova sul nastro in corrispondenza della testina.∈

Per ogni possibile coppia (q, s) QxS il programma dovrà specificare:

• in quale nuovo stato q la MdT dovrà portarsi;
• il simbolo s da scrivere sul nastro nella posizione corrente;
• se la testina di lettura debba rimanere ferma, spostarsi di una posizione a sinistra, o spostarsi di una posizione a destra.

2.1.5 Il Programma come funzione

Sia T := erma, sinistra, destra. Possiamo vedere il programma eseguito da una MdT come una funzione →f : QxS QxSxT

E possibile specificare un programma utilizzando una matrice, detta matrice funzionale o matrice di transizione, le cui righe sono indicizzate utilizzando l'alfabeto esterno, e le cui colonne sono indicizzate utilizzando l'insieme degli

stati.Il generico elemento della matrice di indice (q , s ) conterrà f (q , s ).i j i j

2.1.6 Terminazione della computazione.La computazione termina non appena la macchina raggiunge lo stato q .fAl termine della computazione, sul nastro sarà presente il risultato dellacomputazione.

2.2 Ipotesi fondamentale della teoria degli al-goritmi(Tesi di Church) Qualunque algoritmo può essere espresso sot-to forma di matrice funzionale ed eseguito dalla corrispondenteMacchina di Turing.

2.2.1 IrrisolubilitàAlla luce della Tesi di Church, possiamo riformulare la nozione