L’algoritmo rappresenta, nell’odierna società digitale, uno dei concetti fondamentali. Il termine ha origini antiche, risalenti al 9° secolo d.C., e oggi viene tipicamente utilizzato per descrivere i processi di calcolo svolti dai computer e dalle intelligenze artificiali.
Ecco cosa rappresenta un algoritmo, i suoi caratteri fondamentali e gli elementi che lo distinguono dai più noti programmi.
Perché si chiama algoritmo?
Il termine algoritmo discende dalla trascrizione in latino del nome del matematico persiano vissuto nel IX secolo d.C. Il matematico al-Khwarizmi viene considerato il primo autore a far riferimento al concetto di algoritmo per come oggi lo conosciamo, all’interno dei suoi scritti, presentando le prime soluzioni sistematiche di equazioni lineare e quadratiche.
Nel XII secolo, infatti, i suoi testi matematici furono tradotti in latino, sdoganando il sistema numerico decimale nell’Occidente. Più nello specifico, il termine “algoritmo” deriva dall’algorismo, ossia dalla tecnica di calcolo aritmetica con numeri indù-arabi sviluppata da al-Khwārizmī. Sia “algoritmo” che “algorismo” derivano dalle forme latinizzate del nome di al-Khwārizmī, rispettivamente algoritmi e algorismi.
Le opere più influenti di Al-Khwārizmī nel campo dell’aritmetica sono il testo kitāb al-ḥisāb al-hindī (‘Libro del calcolo indiano’), e un testo più elementare, kitab al-jam’ wa’l-tafriq al-ḥisāb al-hindī (‘Addizione e sottrazione nell’aritmetica indiana‘). All’interno di tali opere, venivano descritti alcuni algoritmi basati su numeri decimali che potevano essere eseguiti su una lavagna di polvere chiamata takht in arabo (latino: tabula), una tavola coperta da un sottile strato di polvere o sabbia impiegata per i calcoli, su cui le figure potevano essere scritte con uno stilo e facilmente cancellate e sostituite quando necessario.
Gli algoritmi di Al-Khwarizmi sono stati utilizzati per quasi tre secoli, fino a quando non sono stati sostituiti dagli algoritmi di Al-Uqlidisi che potevano essere eseguiti con carta e penna, e hanno gradualmente sostituito i precedenti metodi di calcolo latini basati sull’utilizzo dell’abaco.
La creazione del primo algoritmo informatico, invece, è da attribuirsi alla matematica britannica Ada Lovelace nella prima metà dell’800, per il calcolo dei numeri di Bernoulli.
Cos’è un algoritmo e come funziona?
Innanzitutto, occorre definire cosa si intende col termine generico “algoritmo”. Come anticipato precedentemente, il termine nasce nel Medioevo per indicare i procedimenti di calcolo numerico che si fondavano sull’utilizzo dei numeri arabi. Con gli anni, e con l’avvento dei computer capaci di svolgere complesse operazioni di calcolo matematico, il termine è arrivato a definire qualsiasi schema o procedimento matematico di calcolo, che presenti una serie di caratteristiche e sia strutturato in fasi.
Nella logica matematica, l’algoritmo definisce poi “qualsiasi procedimento «effettivo» di computo di una funzione o di decisione di un insieme (o predicato), cioè qualsiasi procedimento che consenta, con un numero finito di passi eseguiti secondo un insieme finito di regole esplicite, di ottenere il valore della funzione per un dato argomento, o di decidere se un dato individuo appartiene all’insieme (o soddisfa il predicato)”.
Sebbene sia prevalentemente riferita al mondo matematico, la definizione di algoritmo ricomprende, in linea generale, una successione di istruzioni, passaggi e operazioni da eseguire in sequenza su un gruppo di dati (input) per ottenere un determinato risultato (output).
In linea generale, l’algoritmo funziona secondo una sequenza: le istruzioni sono poste in ordine, una dopo l’altra, e vengono eseguite nell’esatto ordine in cui sono originariamente inserite. All’interno della sequenza, come nel diagramma di flusso, possono essere previste anche delle regole operative condizionali, che indicano all’esecutore (solitamente una macchina) come comportarsi a seconda della circostanza in cui si trova, e quali scelte compiere. Tipicamente, le istruzioni dell’algoritmo sono espresse in un linguaggio naturale, dovendo essere comprese dalla persona che dovrà eseguirlo; nel caso in cui ad eseguirlo sia una macchina, le istruzioni saranno tradotte in un linguaggio comprensibile alla stessa (il c.d. linguaggio di programmazione).
Quali sono le caratteristiche di un algoritmo?
Sebbene esistano diverse tipologie di algoritmo, è possibile identificare delle caratteristiche comuni che consentono di classificare una sequenza di operazione come un vero e proprio algoritmo. Dette caratteristiche sono state definite negli anni ’60 da Donald Knuth della Stanford University, e servono a garantire che la sequenza di operazioni possa effettivamente giungere al termine ed essere compresa:
- finitezza: un algoritmo non può essere infinito, ma deve essere composto da un numero determinato e finito di operazioni;
- definitezza e non ambiguità: ogni operazione della sequenza deve essere rigorosamente definita, e non deve presentare caratteri di ambiguità, al fine di poter essere interpretate in modo diretto e univoco dal loro esecutore (sia esso una macchina o un umano);
- input: deve possedere un numero finito di dati in entrata;
- effettività: l’algoritmo deve generare un risultato univoco;
- terminazione: l’esecuzione dello schema algoritmico deve avvenire in un tempo finito e ragionevole;
- generale: deve rendere la stessa soluzione per tutti i quesiti appartenenti a una stessa classe.
Fra gli algoritmi che meglio rispecchiano le caratteristiche descritte vi è quello proposto da Turing nella sua macchina, ancora oggi utilizzato come modello per definire se una serie di operazioni possano essere eseguite mediante l’ausilio di una macchina automatica.
Esempi di algoritmo
Abbiamo definito come un algoritmo sia, in linea generale, una sequenza di operazioni atta a risolvere un problema.
Esempi classici di algoritmi matematici sono:
- algoritmo di Euclide per il calcolo del massimo comun divisore (MCD) partendo da due numeri naturali interi;
- algoritmo per la soluzione di equazioni di primo grado;
- algoritmo adottato da Google per stabilire quale sito far comparire per primo fra i risultati della ricerca;
Algoritmi non matematici possono essere, invece, anche le istruzioni di assemblaggio dei mobili o le indicazioni stradali per raggiungere un certo luogo.
A seconda della loro funzione, gli algoritmi possono essere raggruppati in categorie. Tra le più note e semplici, vi sono gli algoritmi c.d. iterativi, costituiti da una sequenza di azioni ripetuta fino al raggiungimento del risultato, secondo un processo strutturato come un ciclo finito.
Un algoritmo ricorsivo, invece, è un algoritmo la cui esecuzione comporta la progressiva semplificazione o suddivisione dell’insieme di dati posti come input, e l’applicazione dell’algoritmo su detti insiemi semplificati di dati. Si tratta di algoritmi particolarmente utilizzati per l’esecuzione di compiti ripetitivi, e la risoluzione di problemi non troppo complessi.
Tra i più diffusi, poi, rientrano i noti algoritmi di ricerca, che permettono di trovare uno o più determinati elementi che rispecchino le query, le caratteristiche inserite dall’utente. L’insieme di elementi al cui interno svolgere la ricerca, è caratterizzato tipicamente da una chiave (ossia dai valori che identificano un elemento dell’insieme) e da un gruppo di c.d. dati satellite (dati che non vengono utilizzati nella ricerca). La chiave può essere univoca per un intero gruppo di elementi, oppure multipla, nel caso in cui possa essere condivisa tra più elementi diversi. Nel caso in cui la chiave sia multipla, sarà necessario specificare, al fine di permettere all’algoritmo di giungere a una soluzione, decidere se far restituire allo stesso il primo elemento dotato di una determinata chiave, l’ultimo elemento, un elemento casuale dell’insieme, o l’intero insieme di dati che presenti quella chiave.
Se l’insieme di dati non è ordinato, in informatica viene utilizzata la c.d. ricerca sequenziale (o lineare): in questo caso, l’algoritmo controlla gli elementi dell’insieme in sequenza, arrestandosi quando recupera un elemento che corrisponde con i criteri di ricerca. Poiché l’insieme, come detto, non è ordinato, l’algoritmo deve necessariamente verificare tutti gli elementi. La ricerca lineare è l’algoritmo di ricerca più semplice, e può facilmente essere implementato nei più comuni linguaggi di programmazione, C, Java e Python.
Qual è la differenza tra algoritmi e programmi?
Sulla scorta di quanto sinora esposto, è possibile comprendere come il termine algoritmo sia utilizzato per definire un insieme generico e astratto di istruzioni per la risoluzione di problemi di natura eterogenea, non necessariamente formalizzati o formalizzabili mediante il linguaggio matematico.
Con il termine programma, invece, si identifica specificatamente un codice che può essere eseguito da una macchina: in poche parole, il programma rappresenta una species del genus algoritmo, una sua conversione e traduzione in un linguaggio (come anticipato, il c.d. linguaggio di programmazione) che sia comprensibile dalla macchina e consenta alla stessa di eseguire le istruzioni, generare un output a partire da un input. Il linguaggio di programmazione, infatti, si basa esclusivamente su principi logici, e segue regole grammaticali e di sintassi definite. I linguaggi di programmazione più comuni sono C, Java, PhP, Python, ecc.
Non è possibile, dunque, definire con il termine programma un problema che non possa essere oggetto di una formalizzazione mediante un linguaggio matematico.
In informatica, tuttavia, il termine algoritmo viene utilizzato anche per intendere una procedura che possa risolvere dei problemi computazionali, generando un output a partire da un input.
È possibile sintetizzare le seguenti fasi di passaggio dal semplice algoritmo al programma:
- Analisi: fase di definizione di un algoritmo o di una serie di algoritmi in grado di realizzare un dato compito;
- Progettazione: l’algoritmo così definito viene trascritto in un linguaggio che possa essere compreso dalla macchina;
- Programmazione: il programma così rappresentato viene codificato e inserito nella memoria della macchina;
- Testing: le funzionalità del programma sono valutate rispetto alle specifiche desiderate, e lo stesso viene utilizzato da diversi soggetti per individuare se sussistono dei malfunzionamenti;
- Manutenzione: nel tempo, il programma viene modificato per correggere eventuali difetti, adattare lo stesso a diverse piattaforme, implementare nuove funzioni, ecc.
