Gli algoritmi: un modello formale

della porta di casa: la realizzazione di questo evento, che può essere individuato come una istruzione

singola, passa attraverso la realizzazione di istruzioni che hanno un grado di semplicità maggiore: estrarre la

chiave dalla tasca del cappotto, individuare l’orientamento corretto della chiave, inserire la chiave nella

toppa ecc… Dunque aprire la porta di casa è la finalità di un algoritmo ben preciso che può essere

rappresentato in forma semplice con il seguente diagramma a blocchi:

Tuttavia, dopo aver individuato una possibile serie di istruzioni che possano risolvere il problema,

dobbiamo chiederci: “Questa classe di istruzioni è veramente un algoritmo?”. Per poter rispondere

affermativamente a tale domanda dobbiamo verificare che tutte le condizioni presenti nella definizione

formale siano verificate.

Notiamo per prima cosa che il diagramma a blocchi è composto unicamente di istruzioni (di vario

• tipo, ma sempre istruzioni) in un numero finito, pari a n=9 (considerando anche i necessari

terminatori INIZIO e FINE che sono presenti entrambi). Dunque ed il numero di elementi di

è finito, ovvero . Inoltre .

{“Inizio”, “Guarda nella tasca destra del cappotto”, “C’è la chiave?”, “Guarda

In particolare

nella tasca sinistra del cappotto”, “Prendi la chiave nella tasca”, “Inserisci la chiave nella toppa”,

“Gira la chiave in senso orario”, “La porta si apre?”, “Fine”}. e che

Le frecce che collegano i blocchi-istruzioni rappresentano graficamente le relazioni

• è definita per ogni istruzione

rispettano le condizioni poste al punto 3 della definizione formale:

ad eccezione di “Fine” ed ecco come opera:

“Guarda nella tasca destra del cappotto”};

(“Inizio”)={ 9

nella tasca destra del cappotto”)={ “C’è la chiave?”};

(“Guarda

la chiave?”)={ “Prendi la chiave nella tasca”, “Guarda nella tasca sinistra del cappotto”};

(“C’è nella tasca sinistra del cappotto”)={ “Prendi la chiave nella tasca”};

(“Guarda

la chiave nella tasca”)={ “Inserisci la chiave nella toppa”};

(“Prendi la chiave nella toppa”)={ “Gira la chiave in senso orario”};

(“Inserisci

la chiave in senso orario”)={ “La porta si apre?”};

(“Gira

porta si apre?”)={ “Fine”, “Gira la chiave in senso orario”}.

(“La , ovvero ogni istruzione (ad eccezione di

Com’è evidente

“Fine”) può avere o 1 o 2 istruzioni successive.

, interna ad .

In modo molto simile viene definita

la chiave?”, “La porta si apre?”}. la chiave nella tasca”,

={“C’è Mentre ={“Prendi

Notiamo che

• “Guarda nella tasca sinistra del cappotto”, “Gira la chiave in senso orario”, “Fine”}. Considerando

1=vero 0=falso

e ed assegnando arbitrariamente 0 alle variabili di stato delle istruzioni la cui

istruzione precedente non è condizionale, il vettore dei booleani di stato può essere il seguente:

. Tuttavia il vettore non ha motivo di esistere fino a quando non viene

definita una legge che leghi gli elementi del vettore alle istruzioni. La legge opera nella fattispecie

nel modo seguente:

la chiave?”)=

(“C’è

porta si apre?”)=

(“La nella tasca sinistra del cappotto”)=

(“Guarda

(“Fine”)=

Graficamente la legge ed il vettore sono rappresentati dai “SI” e dai “NO” sulle frecce di

collegamento fra i blocchi. Infatti le voci “SI” e “NO” sono presenti esclusivamente sulle frecce che

collegano istruzioni che seguono blocchi condizionali, ovvero su tutte le frecce che puntano su

istruzioni . Nel flow-chart, la collocazione delle etichette “SI” e “NO” sulle frecce

indurrebbe a ritenere che lo stato booleano che tali parole rappresentano sia una proprietà

intrinseca delle frecce, ovvero della relazione , e non dei blocchi. Tuttavia si deve obiettare che, se

fosse vero ciò, il codominio della relazione “istruzioni successive” dovrebbe contenere

esclusivamente l’istruzione che dovrebbe essere eseguita dopo la condizione. Tuttavia tale

istruzione non è conoscibile a priori fra due possibili, in quanto dipende dallo stato d’ambiente cui

3

2F

sarà applicata, ed in particolare dallo stato degli oggetti coinvolti nell’istruzione di controllo. 4

3F

in modo tale da risolvere tali problemi, la stessa

Inoltre, se anche venisse modificata la relazione

relazione non potrebbe più mantenere la denominazione di “istruzioni successive”, in quanto

l’immagine della relazione sarebbe in ogni caso un insieme elementare, e non l’insieme di tutte le

istruzioni che succedono (sebbene il codominio rimanga sempre ). Per tali motivi risulta

necessario che la proprietà “risieda” nell’istruzione (elemento di un insieme) e non nella

Definiremo formalmente ambiente, stato e oggetto in seguito. Per ora sia sufficiente sapere che un ambiente (che

3

può possedere uno stato) è composto da oggetti (che a loro volta possono possedere uno stato), ovvero insiemi di

variabili, cui è associato un singolo valore.

Si supponga ad esempio che una istruzione condizionale contenga la seguente condizione booleana:

4 ”. Tale istruzione coinvolge tre oggetti, ovvero a e b, contenenti valori numerici, e c,

“

contenente un valore stringa. Dunque l’ambiente su cui opererà l’istruzione dovrà contenere almeno i tre suddetti

oggetti. E’ evidente che i concetti di ambiente, oggetto e variabile sono funzionali alla formalizzazione dell’esecuzione

di un algoritmo: argomento sul quale ritorneremo a tempo debito. 10

(relazione di “collegamento”). Dal momento che, però, non tutte le istruzioni devono possedere

fra l’insieme delle istruzioni che

uno stato, è stata definita la corrispondenza biunivoca

, e l’insieme degli stati booleani .

“necessitano” di uno stato booleano, ovvero

Se la quaterna di “oggetti matematici” eterogenei sfruttata per definire l’algoritmo sembrava essere troppo

complessa e “fumosa” per un concetto in apparenza semplice, ora si sarà compresa la necessità di introdurre ognuno

dei quattro componenti della quaterna. La definizione data è stata la più semplice fra le coerenti che ho individuato.

Dunque abbiamo tradotto l’algoritmo, intuitivamente espresso sottoforma di diagramma a blocchi, in una

serie di strutture matematiche: un insieme di istruzioni, una relazione che le ordina, una serie di booleani di

stato ed una legge che associa gli stati alle istruzioni. L’insieme di questi 4 “oggetti matematici” determina il

nostro algoritmo.

LA DEFINIZIONE FORMALE DI ISTRUZIONE

base di un algoritmo

Abbiamo definito l’insieme delle istruzioni, ma non abbiamo chiarito con precisione

cosa sia una istruzione. Intuitivamente una istruzione è uno dei tanti passaggi che compongono una ricetta.

Affinché però la definizione di algoritmo sia formalmente corretta è necessario fornire una definizione

rigorosa di istruzione, dal momento che i “mattoni” a fondamento di qualsiasi algoritmo sono le istruzioni

di cui è composto e nulla di solido può essere costruito con mattoni di qualità scadente. Tuttavia prima di

enunciare la definizione di istruzione è necessario formalizzare i concetti di variabile, oggetto, stato di un

oggetto, ambiente e di stato di un ambiente:

variabile

si definisce uno spazio di informazione contenente un valore numerico, letterale o di

• altro tipo; oggetto un vettore finito di variabili;

si definisce

• stato nell’istante t di un oggetto

si definisce il vettore finito di tutti i valori assunti dalle

• nell’istante t;

variabili di ambiente un vettore finito di oggetti;

si definisce

• stato nell’istante t di un ambiente

si definisce il vettore concatenazione di tutti i vettori

• nell’istante t.

stato degli oggetti di Definiamo

La formalizzazione di tali concetti sarà estremamente utile nel proseguo della trattazione.

dunque una istruzione come una funzione capace di modificare (in esecuzione ) lo stato di un ambiente,

restituendo il booleano vero in caso di cambiamento avvenuto correttamente e falso in caso di

cambiamento non avvenuto o avvenuto in maniera errata. L’applicazione di una istruzione ad un

.

ambiente nell’istante t verrà indicata nella seguente forma: Un cambiamento può non

avvenire o avvenire scorrettamente se l’ambiente non è adatto all’esecuzione dell’istruzione oppure se

l’istruzione genera uno stato d’ambiente non accettabile. Se =vero allora una istruzione si dice

5

4F

eseguibile (sottintendendo correttamente) nell’ambiente nell’istante t.

L’esecuzione di una istruzione terminale di FINE deve imporre la terminazione dell’algoritmo.

Si supponga di eseguire l’istruzione “Assegna alla variabile a il valore 1” in un ambiente in cui la variabile a non è

5

membro di nessun oggetto, e dunque non esiste: l’istruzione non verrà applicata. Se invece si vuole eseguire

l’istruzione “Dividi il valore di a per 0” in un ambiente in cui la variabile a esiste, l’istruzione verrà applicata, ma

scorrettamente, generando un errore nel valore di a e quindi nello stato d’ambiente. 11

Una istruzione non è comunque una semplice funzione, in quanto non restituisce semplicemente un valore dato un argomento,

ma è anche capace di modificare lo stato dell’argomento che viene fornito all’istruzione. che

Dalla definizione di istruzione si ricava la seguente proprietà fondamentale: “Dato un ambiente

uno stato e nell’istante uno stato , con , se non vengono

possiede nell’istante allora ”. In simboli:

eseguite istruzioni nell’intervallo di tempo . 6

5F

APPROCCIO LINEARE, PROCEDURALE E FUNZIONALE

Supponiamo di dover costruire un algoritmo che carica in input 3 naturali maggiori di 1 e restituisce per

. A tale scopo una prima

ognuno di essi se possiede o non possiede la proprietà di essere perfetto 7

6F

implementazione dell’algoritmo potrebbe essere la seguente :

8

7F

Definiamo la legge che ad ogni istruzione associa l’insieme degli istanti di tempo in cui l’istruzione è stata

6

eseguita.

Un naturale positivo si dice perfetto quando è uguale alla somma dei suoi divisori (escluso se stesso).

7 Nel flow-chart non è stato inserito il controllo “è >1” per numeri in entrata al fine di rendere troppo contorta e poco

8

leggibile la struttura grafica dell’algoritmo. 12

lineare,

Tale implementazione, detta è la più semplice da un punto di vista strutturale, in quanto dopo aver

identificato il metodo attraverso cui si può stabilire se un numero è perfetto, non si fa altro che applicare

tale metodo 3 volte, tante volte quanti sono i numeri naturali da esaminare. Tuttavia se i numeri fossero

stati 5,10,15… l’algoritmo diverrebbe estremamente lungo, sia da rappresentare che da implementare

sfruttando un linguaggio di codifica.

Per mostrare quanto sia poco vantaggioso sfruttare in questo caso l’approccio lineare, si supponga che, in fase di codifica

dell’algoritmo, il numero di istruzioni da sfruttare per esaminare un solo numero sia x. Nel flow-chart precedente x=9. Per

9

8F

Il fatto che nel flow-chart le istruzioni necessarie siano 9 non implica che esse siano 9 anche nelle implementazioni

9

scritte. Difatti nella codifica Pascal o Java, o in qualsiasi altro linguaggio di programmazione, il numero di istruzioni

potrebbe essere diverso (maggiore o minore), dal momento che per effettuare le 9 operazioni sopra espresse in forma

13

esaminare 3 numeri (come abbiamo fatto nel diagramma di flusso svolto) sono state necessarie quindi un minimo di 3x istruzioni

(in tal caso 27). Per esaminarne 100, avremmo dovuto sfruttare ben 900 istruzioni!

Inoltre sfruttando l’approccio lineare sorge un problema a prima vista insormontabile: se il numero di

naturali da esaminare dovesse essere necessariamente inserito dall’utente, e dunque se esso non fosse

conosciuto a priori, come si dovrebbe implementare l’algoritmo? Il problema sorge in ordine alla necessità

di conoscere a priori il numero di volte che il gruppo di istruzioni preposto ad esaminare un naturale dovrà

essere eseguito. Sfruttando l’approccio lineare, tale problema trova soluzione esclusivamente con

puntatori a variabili 10