[successivo] [precedente] [inizio] [fine] [indice generale] [parte]
Il termine algoritmo è dovuto al matematico arabo del VII° secolo Abu Ja Mohammed Ibn Musa Al-Khowarizmi che, oltre ad essere l'inventore dello zero, ha la paternità di quello che è considerato il primo algoritmo della storia: il metodo per sommare due numeri incolonnandoli e procedendo cifra per cifra da destra verso sinistra tenendo conto dei riporti.
Per algoritmo si può intendere un "insieme di istruzioni che definiscono una sequenza di operazioni mediante le quali si risolvono tutti i problemi di una certa classe" (quest'ultimo aspetto è importante in quanto un algoritmo deve avere tra le sue caratteristiche quella della Generalità).
Si può anche definire più semplicemente un algoritmo come un "metodo di elaborazione da applicare a certi dati iniziali per ottenere dei dati finali o risultati".
È quindi evidente come sia importante, in partenza, che il problema sia "ben posto" e cioè che:
sia chiaro l'obiettivo da raggiungere;
i dati di partenza sia noti e sufficienti;
il problema sia risolubile da parte di chi lo affronta.
Se manca una di queste condizioni l'algoritmo non può essere individuato.
Si deve anche notare come sia importante, quando si affronta un problema, non confondere il risultato (ciò che si vuole ottenere) con la soluzione (il metodo che conduce al risultato elaborando i dati di partenza).
Distinguiamo da ora in poi l'aspetto della risoluzione del problema da quello dell'esecuzione del relativo algoritmo; distinguiamo cioè tra risolutore (l'uomo, che individua il metodo di soluzione del problema) ed esecutore (la macchina che deve eseguire tale metodo descritto tramite un algoritmo). Il nostro esecutore è una macchina non intelligente e cioè capace solo di eseguire istruzioni molto elementari e senza alcuna capacità critica o di ragionamento autonomo.
Un algoritmo deve allora avere le seguenti caratteristiche:
Generalità alla quale si è accennato in precedenza;
Finitezza;
Realizzabilità;
Completezza;
Riproducibilità;
Non ambiguità (o precisione).
Per Finitezza si intende il fatto che l'algoritmo sia composto da un numero finito di istruzioni e termini in un numero finito di passi (per istruzione si intende la descrizione di una certa operazione, per passo si intende l'esecuzione di quella istruzione).
Per Realizzabilità si intende il fatto che l'algoritmo sia realizzabile (e quindi prima di tutto comprensibile) da parte di chi lo deve eseguire; questo comporta anche che l'algoritmo deve essere molto dettagliato cioè composto di istruzioni molto elementari (cioè non ulteriormente scomponibili). Il grado di dettaglio che si deve raggiungere nella stesura di un algoritmo non è definibile con precisione ma deve essere comunque tale da assicurare la realizzabilità delle singole istruzioni da parte dell'esecutore.
Completezza significa che devono essere previste tutte le possibilità che possono verificarsi durante l'esecuzione e per ognuna devono essere definite le azioni da svolgere.
Riproducibilità significa che successive esecuzioni dell'algoritmo con gli stessi dati di partenza devono condurre agli stessi risultati.
La Non ambiguità è molto importante viste le caratteristiche che ha il nostro esecutore.
Gli algoritmi non possono essere ambigui e non possono contenere istruzioni vaghe; quindi non potranno essere descritti con il linguaggio naturale (la lingua parlata) in quanto esso si presta spesso a diverse interpretazioni.
Ad esempio si pensi alle possibili diverse interpretazioni che si possono dare alle seguenti frasi: "succede al Sabato", "lavoro solo da due anni", "mi piace molto la pesca".
Le interpretazioni e le sfumature (dipendenti spesso dal contesto) delle frasi espresse in linguaggio naturale possono essere colte solo da un "esecutore" molto sofisticato, versatile ed elastico: la mente umana.
Si deve quindi ricorrere ad altri strumenti per descrivere algoritmi che dovranno essere eseguiti da macchine non intelligenti; un esempio è costituito dal linguaggio di progetto.
Per ora ricordiamo comunque che, qualunque sia il metodo di descrizione di un algoritmo, le istruzioni che lo compongono devono essere eseguite una alla volta e nell'ordine in cui sono scritte.
Per variabile si intende un oggetto (di solito contrassegnato da una lettera o da un nome) che permette di immagazzinare e conservare determinati valori; l'insieme delle variabili utilizzate in un certo algoritmo prende il nome di area di lavoro relativa ad esso. In un algoritmo possono essere poi presenti altri oggetti, detti costanti, che sono delle entità non modificabili.
Algoritmo per trovare il perimetro di un quadrato di lato 5:
esegui l'operazione 5*4 (moltiplica cinque per quattro);
poni il risultato nella variabile P;
emetti il valore di P.
Vengono usate la variabile P e le costanti numeriche 4 e 5.
Si noti in particolare la natura della seconda istruzione (poni) che è una istruzione distruttiva in quanto cancella il contenuto precedente della variabile P e si chiama istruzione di assegnazione.
L'algoritmo precedente non è generale ma può diventarlo sostituendo una variabile ad una costante:
algoritmo per trovare il perimetro di un quadrato di lato L:
accetta il valore del lato e ponilo in L;
esegui l'operazione L*4 (moltiplica il lato per quattro);
poni il risultato nella variabile P;
emetti il valore di P.
Qui abbiamo le variabili P ed L e la costante 4; sostituendo anche a quest'ultima una variabile si ha una versione ancora più generale:
algoritmo per trovare il perimetro di un poligono regolare di lato L:
accetta il numero dei lati e la misura del lato e ponili in N e L;
esegui l'operazione L*N (moltiplica il lato per il numero degli stessi);
poni il risultato nella variabile P;
emetti il valore di P.
Il nostro linguaggio di progetto sarà basato su alcune parole della lingua italiana, sul simbolo di assegnazione :=, sui normali operatori aritmetici e di confronto.
Con esso dovremo svolgere tutte le normali fasi di descrizione di un algoritmo che sono:
Definizione delle variabili (istruzione VAR);
Acquisizione dei dati (istruzione ACCETTA);
Elaborazione (istruzioni varie tra cui l'assegnazione :=);
Emissione dei risultati (istruzione COMUNICA).
L'inizio dell'algoritmo (dopo la definizione delle variabili) sarà contrassegnato dalla istruzione INIZIO e la fine dalla parola FINE.
Come esempio rivediamo l'algoritmo per il perimetro del quadrato:
VAR L,P; INIZIO ACCETTA (L); P := L*4; COMUNICA (P); FINE. |
Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome gli_algoritmi.html