Il termine algoritmo deriva dal nome del matematico persiano che per primo ne definì il significato. Si tratta di un concetto fondamentale dell’informatica, anche se non ne esiste in realtà una definizione ben precisa. Si può indicare, infatti, con il termine algoritmo, un generico procedimento che permette, a partire da dati (o condizioni iniziali), in un numero finito di passi, di raggiungere il risultato voluto.
Un algoritmo, di per sé, non viene espresso in un particolare linguaggio di programmazione: piuttosto, è una descrizione del tutto generale dei vari passi e della loro corretta sequenza, che occorre compiere per arrivare a un determinato risultato. Una volta definito e descritto opportunamente un algoritmo, si può pensare di tradurlo in un programma mediante una codifica in un linguaggio ad alto livello. Per esempio, si può parlare di un algoritmo per ordinare gli elementi di un vettore, oppure per determinare quali sono i primi 100 numeri primi. Gli algoritmi più comuni possono essere classificati in algoritmi di ordinamento, di ricerca, genetici, di compressione ecc.
Per definire in modo formale un algoritmo si può fare riferimento al modello matematico astratto della macchina di Turing (dal nome del matematico inglese che nel secolo scorso definì tale concetto). Si tratta di una macchina ideale, in grado di leggere e manipolare i dati che scorrono su un nastro infinito, in base a regole prefissate. Le operazioni che la macchina di Turing è in grado di fare sono: cambiamento del suo stato interno, lettura o scrittura su nastro, spostamento della testina di lettura/scrittura su nastro di una posizione.
Per definire in modo formale un algoritmo, si indica come algoritmo una qualsiasi elaborazione che può essere portata a termine sulla macchina di Turing. Le caratteristiche che deve avere la descrizione di un algoritmo sono le seguenti:
- deve essere costituito da un numero finito di passi.
- I passi devono essere elementari, ovvero non scindibili in operazioni più semplici.
- La loro interpretazione deve essere univoca, ovvero non deve dar luogo ad ambiguità.
- L’esecuzione deve avvenire in un tempo finito.
- Il risultato deve essere univoco.
Di notevole importanza assume in informatica anche lo studio della complessità degli algoritmi, che tende a stimare come si modificano il tempo di esecuzione di un algoritmo e/o la sua occupazione di memoria, al crescere della complessità del problema. Per esempio, un algoritmo di ordinamento di un vettore di numeri avrà una complessità espressa in funzione del numero di elementi del vettore che devono essere ordinati.
Manuale di cultura generale – Informatica – Gli algoritmi – Continua
