Gli algoritmi: un modello formale

Gli algoritmi

Aversa Antonio Giovanni

VB – Liceo Scientifico Statale Soverato

Prefazione

Siamo in un periodo molto particolare: a chi sostiene che sia l’era del progresso si obietta che in realtà il progresso appartiene ad ogni epoca della storia dell’uomo e dell’universo. Tale obiezione è parzialmente vera, in quanto il progresso, inteso come cambiamento in positivo delle condizioni sociali, economiche e politiche, è sempre avvenuto, seppur alternandosi a fasi di regressione che in molti casi hanno vanificato i molti o pochi passi fatti in avanti.

Dunque da questo punto di vista non vi è stato un cambiamento qualitativamente rilevante, né l’impressione di noi, che siamo all’interno del sistema, può assumere un valore assoluto. La scienza ha dimostrato infatti che le nostre pretese in tal senso sono inutili: “non è possibile, rimanendo all’interno di un sistema totale, formulare i principi che regolano il sistema stesso”.

Per indagare i principi costitutivi dell’universo sarebbe necessario poter uscirne fuori, possibilità che per il momento non ci è permessa e che forse potrebbe essere preclusa all’uomo dalla stessa struttura dell’universo. Non possiamo però escludere a priori tale probabilità, peraltro prevista da alcune teorie del Tutto, ma in attesa che il sogno dell’uomo si realizzi è necessario studiare la realtà ad un livello diverso, ovvero nelle sue manifestazioni e non nei suoi principi.

La legenda narra che fu la caduta di una mela ad indurre Newton a studiare la gravitazione. All’età di 23 anni Isaac Newton fece conoscere al mondo il significato della forza di gravità. Einstein disse che, seduto all’ufficio brevetti a Berna, rimase stupefatto da un pensiero balenatogli in mente: una persona in caduta libera non sente il suo peso.

La meraviglia e lo stupore provati furono un incentivo a studiare la misteriosa forza di gravità. Pochi anni più tardi, con la Teoria della Relatività Generale avrebbe trasformato totalmente la fisica esistente, distruggendo (ma soprattutto riformulando) quello che sembrava il fondamento inattaccabile della fisica: la relatività galileiana.

Sia Isaac Newton che Albert Einstein furono indotti a trasformare irrimediabilmente il volto della scienza da eventi naturali e percezioni fisiche, tutt’altro che qualitativamente circoscritte e quantitativamente definite: nelle condizioni in cui siamo, la nostra scienza non può che essere costruita, mattone dopo mattone, partendo da ciò che il mondo lascia intravedere di sé.

Questa è la grande rivoluzione della scienza: l’introduzione del cosiddetto metodo scientifico.

Da un punto di vista formale il metodo scientifico è identificabile come uno pseudo-algoritmo che permette di risolvere la più ampia delle classi di problemi: in tal caso usare il termine di insieme (o meglio classe – ove per classe si definisce un insieme che abbia per suoi elementi anche altri insiemi o classi) universo è quanto mai appropriato dal momento che tale processo permette di indagare su qualsiasi fenomeno.

Questa suggestiva prospettiva di estensione del significato di algoritmo dimostra quale siano le potenzialità insite in questo strumento matematico. In questa breve trattazione non mi propongo di compiere un percorso nella teoria base degli algoritmi, che è talmente estesa e complessa da non poter essere neanche enunciata nei suoi aspetti fondamentali in così poco spazio.

Non sfrutterò né analizzerò le definizioni astratte e generali di Alan Turing (inventore della celeberrima macchina, che rappresenta assieme all’architettura di John von Neumann il fondamento teorico dei moderni calcolatori, e considerato il padre delle scienze informatiche), in quanto il mio obiettivo non è quello di riproporre il brillante ed eccezionale modello teorico su cui si basa la moderna teoria della computazione ma di focalizzare l’attenzione sul concetto di algoritmo in rapporto all’idea che noi abbiamo di esso, elaborando un modello intuitivo che possa trovare una vantaggiosa applicazione nello studio degli algoritmi.

Il punto di partenza dunque non è una costruzione formale, ma la definizione “discorsiva” e storica che viene in genere sfruttata quando è necessario spiegare ad uno studente del primo anno di liceo cosa è un algoritmo, senza perdersi in puntualizzazioni corrette ma complesse.

A tale definizione segue una serie di considerazioni teoriche che nascono da una visione intuitiva e non inquadrata in forme precostituite: ad ogni passaggio verrà definito un elemento in più, con particolare attenzione al rigore della formalizzazione, che sempre e comunque avverrà per gradi.

Con il procedere della trattazione il livello teorico-formale verrà gradualmente a sostituirsi alla visione pratica, ma ogni definizione sarà sempre inserita in un contesto applicativo: non a caso molti paragrafi iniziano con un algoritmo o un confronto fra due algoritmi differenti nell’aspetto che dovrà essere trattato.

La trattazione prevede la formalizzazione del concetto di istruzione che è risultata necessaria per rendere la costruzione teorica solida ed estendibile. L’istruzione è stata definita sotto il suo aspetto processuale di modifica dello stato di un ambiente, e ciò ha permesso una definizione agevole del concetto di esecuzione di un algoritmo, oltre che l’introduzione dei concetti di variabile, oggetto e ambiente che permettono di “monitorare” l’algoritmo nella fase applicativa.

È in quest’ottica che sono stati formalizzati i concetti di spazio e tempo di esecuzione. Tali grandezze quantitative, in rapporto alla velocità ed alla potenzialità del calcolatore che esegue l’algoritmo (cui è dedicato il paragrafo “Esecutore di un algoritmo”), permettono di giungere alla definizione quantitativa e non soltanto qualitativa di performance di un algoritmo.

L’ultimo paragrafo della trattazione mostrerà come sia possibile ottenere informazioni riguardo la performance di due algoritmi al fine di compiere un paragone fra di essi. Grazie al modello formale introdotto, sarà possibile calcolare un indice di prestazione, stima di performance, che non soltanto dimostrerà in maniera rigorosa la superiorità delle prestazioni dell’algoritmo di bisezione rispetto alla trisezione ed in generale rispetto agli algoritmi di n-sezione, ma potenzialmente permetterà di fare un raffronto quantitativo fra due qualsiasi algoritmi che risolvono lo stesso problema.

L’estensione ed il miglioramento di questo modello, nella fase attuale assolutamente inadatto a valutare architetture informatiche eterogenee, potrebbe permettere lo studio di algoritmi molto complessi, che non vengono affrontati nella trattazione per problemi di spazio, di tempo e per difficoltà di natura teorica che dimostrano quanto ancora il modello possa essere irrobustito.

Le prospettive di una struttura formale in grado di analizzare algoritmi molto complessi sono eccezionali non soltanto da un punto di vista teorico, ma anche da un punto di vista pratico. Difatti il rapporto fra l’informatica applicata e la teoria della computazione è identico al rapporto intercorrente fra la cosiddetta fisica tecnica e il modello fisico fondamentale, che a sua volta sfrutta oggetti matematici ad alto grado di astrazione e generalizzazione.

Alcuni fra i concetti matematici più importanti sono storicamente nati da esigenze applicative, seppure hanno assunto in seguito un “carattere puro” liberandosi dai vincoli della praticità. Molti concetti ci sono stati dunque presentati in forma teorica precostituita, ma il più delle volte sono nati dalla realtà, dall’osservazione, dalla ricerca operativa.

La sistemazione teorica è fondamentale e imprescindibile, ma è solo l’ultimo passo di un lungo percorso che dovrebbe ogni giorno essere ricompiuto: la strada che porta dall’uomo alla teoria.

Ormai si definisce la derivata come limite di un rapporto, definito incrementale, ed il limite come veridicità di una disequazione nell’ambito di un dominio posto dal limite stesso, e purtroppo viene soltanto accennata la storia incredibile della derivata, che è frutto delle geniali intuizioni di Isaac Newton e Gottfried Leibniz: intuizioni diverse in ambiti diversi che hanno portato allo stesso risultato.

Per sviluppare una vera mentalità scientifica, un approccio consapevole alla scienza, ed essere protagonisti attivi, e non passivi, della rivoluzione che si sta compiendo negli ultimi 4 secoli è necessario sapere destreggiarsi bene nella realtà, per ripercorre il sentiero che ha portato Newton e Leibiniz al fondamento della matematica moderna: essere in grado di sfruttare il concetto di derivata ci indurrà a conoscere la matematica, non a costruirla ed è questo il compito che siamo chiamati a svolgere “per la maggior gloria dello Spirito Umano” (Piergiorgio Odifreddi – Il matematico impertinente).

Lo spirito con il quale ho affrontato la sfida di questa breve trattazione è stato proprio questo. Purtroppo consapevole di non poter dare moltissimo alla scienza, spero che altri possano farlo ispirati dalle mie parole.

Aversa Antonio Giovanni

Sommario

• Gli algoritmi .................................................................................................................................................. 1
• Prefazione ................................................................................................................................................... 2
• Sommario .................................................................................................................................................... 5
• L’algoritmo – una definizione “informale” ed un modello intuitivo ......................................... 6
• L’algoritmo – un esempio “casalingo” ................................................................................................ 8
• La definizione formale di istruzione .................................................................................................. 11
• Approccio lineare, procedurale e funzionale ................................................................................. 12
• La struttura iterativa ........................................................................................................................... 18
• La complessità della struttura di un algoritmo.......................................................................... 25
• Algoritmi finiti e algoritmi infiniti .................................................................................................... 27
• L’esecuzione di un algoritmo .............................................................................................................. 28
• Funzionalità di un algoritmo ............................................................................................................ 29
• La classificazione delle istruzioni ...................................................................................................... 30
• Lo spazio di esecuzione di un algoritmo ........................................................................................... 33
• Il tempo di esecuzione di un algoritmo ............................................................................................ 36
• L’esecutore di un algoritmo ................................................................................................................ 38
• La performance di un algoritmo ....................................................................................................... 39
• Lo studio della performance – algoritmi di bisezione e trisezione ........................................... 39

L’algoritmo – una definizione “informale” ed un modello intuitivo

Dobbiamo l’originaria definizione di algoritmo al matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī (dal nome del quale deriva il termine stesso “algoritmo”), il primo ad aver utilizzato esplicitamente tale concetto il quale, pur essendo stato espresso in una quantità di forme anche notevolmente differenti, è sintetizzabile nella seguente definizione (informale): “un algoritmo è una sequenza ordinata e finita di istruzioni elementari non ambigue la cui esecuzione permette, in ogni caso, la risoluzione di un problema o di un ambito di problemi”.

Da tale definizione non è però possibile individuare quali siano le caratteristiche che fanno di un generico insieme di n istruzioni una vera e propria base di un algoritmo. Individueremo ora da un punto di vista formale le caratteristiche di un algoritmo, al fine di poterne ricavare una definizione più rigorosa.

Secondo la nostra “visione empirica” di algoritmo, in generale, devono valere le seguenti condizioni:

1. (insieme delle istruzioni) deve essere finito e non vuoto, ovvero .

2. Deve contenere le due istruzioni terminatrici, ovvero di INIZIO algoritmo e di FINE algoritmo: quindi .

3. Deve essere definito un ordine fra gli elementi dell’insieme. Ciò significa che devono esistere le relazioni “istruzioni precedenti” e “istruzioni successive” .

La relazione “istruzioni precedenti” per qualsiasi elemento appartenente all’insieme , che non sia , deve restituire la classe non vuota degli elementi (appartenenti ad ) che precedono . La relazione “istruzione successiva” per qualsiasi elemento appartenente all’insieme , che non sia , deve restituire la classe non vuota degli elementi (appartenenti ad ) che seguono .

Dunque la relazione deve essere interna ad , mentre la relazione deve essere interna ad . Dalle condizioni sopra descritte nel punto 3 deriva che ogni algoritmo deve iniziare con istruzioni e terminare con . Per tale proprietà le due istruzioni ed sono chiamate terminatrici. Qualunque algoritmo che non si attenga a tali regole è da considerarsi incompleto.

Pertanto, sfruttando un diagramma a blocchi, la struttura fondamentale dell’algoritmo è la seguente: Figura 1: la struttura fondamentale di un algoritmo

Anche nei linguaggi di programmazione sono presenti implicitamente o esplicitamente le istruzioni ed , sottoforma di keywords (parole chiave) o brackets (parentesi e delimitatori). La codifica begin end.

Pascal preferisce le keywords ed Il linguaggio Java ed in generale tutti i linguaggi C/C++ oriented prediligono i delimitatori simbolici delle parentesi graffe, aperte e chiuse. Ecco dunque nei due linguaggi la cella fondamentale di un algoritmo:

program algoritmo public void class algoritmo(String[] Args)

begin {

... ...

end }

Si noti che la “istruzioni precedenti” e la “istruzioni successive” sono relazioni e non funzioni.

1 6

4. La relazione può associare ad una istruzione una classe non vuota con più di un elemento soltanto se essa è una istruzione di controllo .

Se , ovvero se un’istruzione ammette una classe di istruzioni successive contenente un numero di elementi maggiore di 1, l’istruzione sarà condizionale ed ammetterà solo due istruzioni successive possibili.

La scelta dell’istruzione da seguire sarà determinata dal valore di verità della proposizione . Se si suppone che e che sia legata al valore di verità di Vero contenuta in è legata al valore di verità di falso (percorso NO), allora se il valore di verità è Vero, seguirà l’istruzione , altrimenti seguirà istruzione . 2

1F

Dalla condizione 4 si evince che le istruzioni che seguono una istruzione condizionale devono possedere una proprietà intrinseca, una variabile di stato booleana che indichi se l’istruzione è sul percorso SI oppure sul percorso NO. Dunque è necessario imporre la seguente condizione (5):

5. all’insieme deve essere associato un vettore di booleani (insieme totalmente ordinato) tale che abbia lo stesso numero di elementi dell’insieme delle istruzioni che seguono una istruzione condizionale. In simboli: ad ogni istruzione di deve essere associata una variabile booleana di stato di , ovvero deve essere definita una legge che ad ogni elemento di associ uno ed uno solo elemento di . Per quanto precedentemente detto, la funzione deve essere biettiva.

Sfruttando un diagramma a blocchi la rappresentazione della struttura condizionale è la seguente:

L’istruzione che “seguirà” è in realtà l’istruzione che verrà eseguita e come tale rientra nell’ambito di esecuzione dell’algoritmo, non intervenendo in alcun modo nella struttura “ontologica” dell’algoritmo stesso. Dunque non sarebbe necessario definire la modalità di procedere nella scelta dell’istruzione. Tuttavia, al fine di rendere più fluida la trattazione e per introdurre la struttura condizionale, essa è stata anticipata in questo punto. Verrà formalizzata nel paragrafo relativo all’esecuzione di un algoritmo. 7

Figura 2: il flow-chart della struttura condizionale

In codice Java e Pascal invece la struttura condizionale è espressa dal seguente codice:

... ...

if(A==true) if A=true

then begin

{

EseguiIstruzioneA(); EseguiIstruzioneA;

end

}

else else begin

{ EseguiIstruzioneB;

end;

EseguiIstruzioneB();

} ...

... Post e dunque le condizioni fondamentali ... definiamo formalmente l’algoritmo come la quaterna

, , ) dell’insieme , sottoposto alla legge , i cui elementi membri anche del sottoinsieme sono associati dalla legge agli elementi del vettore dei booleani di stato .