Per molto tempo si pensò che il termine algoritmo derivasse da una storpiatura del termine logaritmo. L’opinione attualmente diffusa è invece che il termine derivi da al-Khuwarizmi, nome derivante a sua volta dal luogo di origine di un matematico arabo, autore di un libro di aritmetica e di uno di algebra: nel libro di aritmetica si parla della cosiddetta numerazione araba (quella attualmente usata) e si descrivono i procedimenti per l’esecuzione delle operazioni dell’aritmetica elementare. Questi procedimenti vennero in seguito chiamati algoritmi e il termine passò ad indicare genericamente qualunque procedimento di calcolo.
L’algoritmo esprime le azioni da svolgere su determinati oggetti al fine di produrre gli effetti attesi. Una azione che produce un determinato effetto è chiamata istruzione e gli oggetti su cui agiscono le istruzioni possono essere costanti (valori che restano sempre uguali nelle diverse esecuzioni dell’algoritmo) e variabili (contenitori di valori che variano ad ogni esecuzione dell’algoritmo). Si potrà dire brevemente che un algoritmo è una elaborazione di dati: i dati, cioè l’insieme delle informazioni che devono essere elaborate, sono manipolati, secondo le modalità descritte dalle istruzioni, per produrre altri dati. Ciò porta l’algoritmo ad essere una funzione di trasformazione dei dati di un insieme A (dati di input) in dati di un insieme B (dati di output).
In questi appunti, dato che ci si pone il fine di una introduzione alla programmazione, più che una definizione rigorosa di algoritmo se ne fornirà una definizione intuitiva. In questo senso si può definire l’algoritmo come “.. un insieme di istruzioni che definiscono una sequenza di operazioni mediante le quali si risolvono tutti i problemi di una determinata classe”.
Per chiarire meglio il concetto di algoritmo è bene fare riferimento ad alcune proprietà che un insieme di istruzioni deve possedere affinché possa chiamarsi algoritmo:
La finitezza. Il numero di istruzioni che fanno parte di un algoritmo è finito. Le operazioni definite in esso vengono eseguite un numero finito di volte.
Il determinismo. Le istruzioni presenti in un algoritmo devono essere definite senza ambiguità. Un algoritmo eseguito più volte e da diversi esecutori, a parità di premesse, deve giungere a medesimi risultati. L’effetto prodotto dalle azioni descritte nell’algoritmo non deve dipendere dall’esecutore o dal tempo.
La realizzabilità pratica. Tutte le azioni descritte devono essere eseguibili con i mezzi di cui si dispone.
La generalità. Proprietà già messa in evidenza nella definizione che si è data: un algoritmo si occupa della risoluzione di famiglie di problemi.
Per quanto osservato nell’ultima proprietà espressa, gli algoritmi operano principalmente su variabili che conterranno i dati sui quali si vuole svolgere una determinata elaborazione. I valori da elaborare devono essere assegnati alle variabili prima di effettuare l’elaborazione. Si pensi infatti ad una variabile come ad un contenitore. Le istruzioni operano sui valori contenuti: se questi non ci sono non ci si può attendere alcuna elaborazione. Ogni variabile è identificata da un nome che permette di distinguerla dalle altre:
L’istruzione di assegnamento fa in modo che un determinato valore sia conservato in una variabile. In questo modo si prepara la variabile per l’elaborazione o si conserva nella variabile un valore intermedio prodotto da una elaborazione precedente. Si può assegnare ad una variabile un valore costante come anche il valore risultante da una espressione aritmetica.
L’istruzione di input fa in modo che l’algoritmo riceva dall’esterno un valore da assegnare ad una variabile. Nel caso di algoritmi eseguiti da un elaboratore, questi attende che da una unità di input (per esempio la tastiera) arrivi una sequenza di caratteri tipicamente terminanti con la pressione del tasto <Invio>. Il dato verrà assegnato alla variabile appositamente predisposta. Praticamente si tratta di una istruzione di assegnamento solo che stavolta il valore da assegnare proviene dall’esterno.
L’istruzione di output fa in modo che l’algoritmo comunichi all’esterno i risultati della propria elaborazione. Nel caso di un elaboratore viene inviato su una unità di output (per esempio il video) il valore contenuto in una determinata variabile.
Esaminiamo adesso due versioni di un algoritmo per il calcolo dell’area di un rettangolo (i nomi delle variabili sono scritti in maiuscolo):
|
Algoritmo A |
Algoritmo B |
|
|
|
|
Assegna a BASE il valore 3 |
Ricevi BASE |
|
Assegna a ALTEZZA il valore 7 |
Ricevi ALTEZZA |
|
Assegna a AREA valore BASE*ALTEZZA |
Assegna a AREA valore BASE*ALTEZZA |
|
Comunica AREA |
Comunica AREA |
Nell’algoritmo A si assegnano alle variabili BASE ed ALTEZZA dei valori costanti, l’algoritmo calcola l’area di un rettangolo particolare e se si vuole applicare l’algoritmo ad un diverso rettangolo è necessario modificare le due istruzioni di assegnamento a BASE e ALTEZZA: l’algoritmo ha perso la sua caratteristica di generalità. Questo esempio non deve portare a concludere che non ha senso parlare di costanti in un algoritmo perché, per esempio, se si fosse trattato di un triangolo il calcolo dell’area avrebbe assunto l’aspetto: Assegna a AREA valore BASE*ALTEZZA/2. La costante 2 prescinde dai valori diversi che possono essere assegnati a BASE e ALTEZZA, essendo parte della formula del calcolo dell’area di un triangolo qualsiasi.
Nell’algoritmo B i valori da assegnare a BASE e ALTEZZA provengono da una unità di input. L’algoritmo ad ogni esecuzione si fermerà in attesa di tali valori e il calcolo verrà eseguito su tali valori: l’elaborazione è sempre la stessa (l’area di un rettangolo si calcola sempre allo stesso modo) ma i dati saranno di volta in volta diversi (i rettangoli hanno dimensioni diverse).
Gli algoritmi, a causa della loro generalità, lavorano utilizzando variabili. Non si conoscono, al momento della stesura dell’algoritmo stesso, i valori che possono assumere le variabili. Ciò se permette di scrivere algoritmi generali può comportare problemi per alcune istruzioni: si pensi al problema apparentemente banale del calcolo del quoziente di due numeri:
Ricevi DIVIDENDO Ricevi DIVISORE Assegna a QUOZIENTE valore DIVIDENDO/DIVISORE Comunica QUOZIENTE
Il quoziente può essere calcolato se DIVISORE contiene un valore diverso da 0, evento questo non noto in questo momento dipendendo tale valore dal numero proveniente da input. Inoltre è chiaro che, in questa eventualità, sarebbe priva di senso anche l’istruzione di output del valore di QUOZIENTE non essendoci nella variabile alcun valore.
È necessario introdurre, oltre alle istruzioni, degli strumenti che permettano di controllare l’esecuzione dell’algoritmo: le strutture di controllo. La programmazione strutturata (disciplina nata alla fine degli anni 60 per stabilire le regole per la scrittura di buoni algoritmi) impone l’uso di tre sole regole di composizione degli algoritmi:
la sequenza
È l’unica struttura di composizione che si è utilizzata finora. In poche parole questa struttura permette di specificare l’ordine con cui le istruzioni si susseguono: ogni istruzione produce un risultato perché inserita in un contesto che è quello determinato dalle istruzioni che la precedono. Nell’esempio di prima il calcolo di QUOZIENTE, per poter contenere il valore atteso, deve essere eseguito dopo gli input.
la selezione
Questa struttura permette di scegliere tra due alternative la sequenza di esecuzione. È la struttura che ci permette, per esempio, di risolvere in modo completo il problema del calcolo del quoziente fra due numeri:
Ricevi DIVIDENDO Ricevi DIVISORE Se DIVISORE <> 0 Assegna a QUOZIENTE valore DIVIDENDO/DIVISORE Comunica QUOZIENTE Altrimenti Comunica ‘Operazione senza senso’ Fine-se
La condizione espressa nella struttura Se permette di scegliere, in relazione al valore di verità o falsità, quale elaborazione svolgere. La sequenza contenuta nella parte Altrimenti potrebbe mancare se si volesse soltanto un risultato laddove possibile: in tale caso se la condizione DIVISORE ? 0 risultasse non verificata, non si effettuerebbe alcuna elaborazione.
l’iterazione
La struttura iterativa permette di ripetere più volte la stessa sequenza di istruzioni finché non si verifica una determinata condizione. Si voglia, a titolo di esempio, scrivere un algoritmo che calcoli e visualizzi i quadrati di una serie di numeri positivi. Si tratta in altri termini di effettuare la stessa elaborazione (calcolo e visualizzazione del quadrato di un numero) effettuata su numeri diversi (quelli che arriveranno dall’input):
Ricevi NUMERO Mentre NUMERO > 0 Assegna a QUADRATO valore NUMERO*NUMERO Comunica QUADRATO Ricevi NUMERO Fine-mentre
Dentro la struttura iterativa (la parte compresa fra le parole Mentre e Fine-mentre) sono specificate le istruzioni per il calcolo del quadrato di un numero: l’iterazione permette di ripetere tale calcolo per tutti i numeri che verranno acquisiti tramite l’istruzione di input inserita nell’iterazione stessa. La condizione NUMERO>0 viene chiamata condizione di controllo del ciclo e specifica quando deve terminare l’elaborazione (il valore introdotto da input è non positivo): si ricorda che l’algoritmo deve essere finito e non si può iterare all’infinito. Il primo input fuori ciclo ha lo scopo di permettere l’impostazione della condizione di controllo sul ciclo stesso e stabilire, quindi, quando terminare le iterazioni.
In generale si può dire che la struttura di una elaborazione ciclica, controllata dal verificarsi di una condizione, assume il seguente aspetto:
Considera primo elemento Mentre elementi non finiti Elabora elemento Considera prossimo elemento Fine mentre
Le strutture di controllo
devono essere pensate come schemi di composizione: una sequenza può contenere
una iterazione che, a sua volta, contiene una selezione ecc.. Rappresentano
in pratica i mattoncini elementari di una scatola di montaggio le cui diverse
combinazioni permettono la costruzione di architetture di varia complessità.
L’elaborazione ciclica è spesso utilizzata per l’aggiornamento di totalizzatori o contatori. Per chiarire meglio il concetto di totalizzatore, si pensi alle azioni eseguite dal cassiere di un supermercato quando si presenta un cliente con il proprio carrello pieno di merce. Il cassiere effettua una elaborazione ciclica sulla merce acquistata: ogni oggetto viene esaminato per acquisirne il prezzo. Lo scopo della elaborazione è quello di cumulare i prezzi dei prodotti acquistati per stabilire il totale che il cliente dovrà corrispondere.
Dal punto di vista informatico si tratta di utilizzare una variabile (nell’esempio potrebbe essere rappresentata dal totalizzatore di cassa) che viene aggiornata per ogni prezzo acquisito: ogni nuovo prezzo acquisito non deve sostituire il precedente ma aggiungersi ai prezzi già acquisiti precedentemente. Tale variabile:
dovrà essere azzerata quando si passa ad un nuovo cliente (ogni cliente dovrà corrispondere solamente il prezzo dei prodotti che lui acquista)
si aggiornerà per ogni prodotto esaminato (ogni nuovo prezzo acquisito verrà cumulato ai precedenti)
finito l’esame dei prodotti acquistati la variabile conterrà il valore totale da corrispondere.
La variabile di cui si parla nell’esempio è quella che, nel linguaggio della programmazione, viene definita un totalizzatore o accumulatore: cioè una variabile nella quale ogni nuovo valore non sostituisce ma si accumula a quelli già presenti in precedenza. Se la variabile si aggiorna sempre di una quantità costante (per esempio viene sempre aggiunta l’unità) viene chiamata contatore.
In generale si può dire che l’uso di un totalizzatore prevede i seguenti passi:
Inizializzazione totalizzatore Inizio ciclo aggiornamento totalizzatore ... Aggiornamento totalizzatore Fine ciclo Uso del totalizzatore
L’inizializzazione serve sia a dare senso all’istruzione di aggiornamento (cosa significherebbe la frase: aggiorna il valore esistente con il nuovo valore se non ci fosse un valore esistente ?), sia a fare in modo che l’accumulatore stesso contenga un valore coerente con l’elaborazione da svolgere (nell’esempio di prima il nuovo cliente non può pagare prodotti acquistati dal cliente precedente: il totalizzatore deve essere azzerato, prima di cominciare l’elaborazione, affinché contenga un valore che rispecchi esattamente tutto ciò che è stato acquistato dal cliente esaminato).
L’aggiornamento viene effettuato all’interno di un ciclo. Se infatti si riflette sulla definizione stessa di totalizzatore, è facile prendere atto che avrebbe poco significato fuori da un ciclo: come si può cumulare valori se non si hanno una serie di valori ?
Quando i valori da esaminare terminano, il totalizzatore conterrà il valore cercato. Nell’esempio di prima tutto ciò si tradurrebbe: finito l’esame dei prodotti acquistati, si potrà presentare al cliente il totale da corrispondere.
Si voglia, a titolo di esempio di utilizzo di un accumulatore, risolvere il seguente problema: data una sequenza di numeri positivi, se ne vuole calcolare la somma.
Inizializza SOMMA con valore 0 Ricevi NUMERO Mentre NUMERO > 0 Aggiorna SOMMA sommando NUMERO Ricevi NUMERO Fine-mentre Comunica SOMMA
Il totalizzatore SOMMA è inizializzato, prima del ciclo, al valore nullo poiché deve rispecchiare la somma dei numeri introdotti da input e, quindi, non essendo ancora stata effettuata alcuna elaborazione su alcun numero tale situazione viene espressa assegnando il valore neutro della somma.
L’output di SOMMA alla fine del ciclo indica il fatto che si può utilizzare (in questo caso per la conoscenza del valore contenuto) il totalizzatore quando il suo contenuto è coerente con il motivo della sua esistenza: SOMMA deve accumulare tutti i valori e ciò avverrà quando tutti i numeri da considerare saranno stati elaborati, cioè in uscita dal ciclo.