Il termine "algoritmo" è ormai entrato a far parte del nostro lessico quotidiano.

Se ne parla dappertutto, quasi come se gli algoritmi guidassero le nostre vite.

Ma cosa si intende esattamente con questo termine? E quali caratteristiche definiscono un algoritmo?

L'origine del termine

Contrariamente a quanto si potrebbe pensare la parola "algoritmo" non deriva da una lingua antica bensì dal nome di una persona: il matematico arabo Muhammad al-Khwarizmi, vissuto tra il 780 e l'850 d.C.

Al-Khwarizmi fu un matematico di grande importanza ed è considerato il padre dell'algebra moderna.

Definizione di algoritmo: molto più di un semplice calcolo

Comunemente si indica come algoritmo un qualsiasi procedimento di calcolo ma questa definizione non è sempre la migliore, in quanto suggerisce che l'algoritmo sia legato esclusivamente ad elaborazioni di natura matematica. In realtà gli algoritmi vengono utilizzati anche in contesti differenti.

Ad esempio possiamo parlare dell'algoritmo per risolvere un'equazione di secondo grado, che è un caso matematico specifico, ma anche di algoritmi per trovare il percorso più breve tra due punti, di algoritmi di ordinamento o di algoritmi di ricerca. Questi ultimi non sono legati necessariamente al mondo dell'algebra.

Una definizione più appropriata e che calza a pennello vede l'algoritmo come la strategia risolutiva di un problema, ovvero quel metodo che ci permette di giungere alla soluzione dello stesso.

Caratteristiche fondamentali di un algoritmo

Affinché una strategia risolutiva possa essere definita rigorosamente come un algoritmo deve possedere delle caratteristiche precise:

1. sequenzialità: un algoritmo è costituito da una serie di passi o istruzioni elementari che vanno eseguite secondo un ordine ben preciso che non può essere modificato

2. non ambiguità: ciascuna istruzione dell'algoritmo deve essere interpretabile esclusivamente in un solo modo. Non deve lasciare spazio a differenti interpretazioni. Questo aspetto è fondamentale specialmente se pensiamo che l'algoritmo dovrà essere eseguito da una macchina. Mentre noi esseri umani siamo spesso in grado di risolvere le ambiguità sfruttando il contesto, per una macchina si tratta di un compito estremamente difficile. I computer quando eseguono un algoritmo (o meglio, un programma che ne è la traduzione) stanno fondamentalmente manipolando dei simboli. Non hanno consapevolezza del significato di ciò che fanno e non sono in grado di cogliere il significato dal contesto per adeguarsi di conseguenza. Dunque l'algoritmo deve essere necessariamente non ambiguo. L'uso di notazioni specifiche come lo pseudocodice aiuta ad evitare l'ambiguità tipica, ad esempio, del linguaggio naturale in cui una stessa parola può avere significati diversi a seconda del contesto (come il verbo "sbarrare": sbarrare gli occhi vs. sbarrare una strada)

3. generalità: un algoritmo non deve risolvere uno specifico caso singolo di un problema (una singola "istanza") ma un'intera classe di problemi che hanno la stessa struttura. Ad esempio un algoritmo per risolvere equazioni di secondo grado non risolve solo l'equazione 2x² + x - 3 = 0 ma tutte quelle del tipo ax² + bx + c = 0 dove a, b e c possono assumere qualsiasi valore reale

4. eseguibilità (o realizzabilità): deve esistere un "esecutore" in grado di mettere in pratica l'algoritmo e arrivare alla soluzione. Tale esecutore può essere sia un essere umano che una macchina

5. finitezza (o terminazione): l'algoritmo deve terminare ovvero concludere la sua computazione. Questo non significa necessariamente che debba farlo in tempi brevissimi. Alcuni algoritmi possono richiedere giorni, mesi o persino anni di elaborazione ma finché è garantita la terminazione sono considerati finiti. L'aspetto del tempo richiesto è legato al concetto di complessità che misura le risorse di calcolo necessarie per l'esecuzione. Un algoritmo che richiede un tempo di elaborazione eccessivamente elevato, pur essendo finito, può perdere valore dal punto di vista pratico ed essere valido solo da quello puramente teorico.

6. determinismo: ad ogni passo dell'algoritmo deve essere possibile determinare univocamente quale sarà l'istruzione successiva da eseguire.

L'algoritmo e la ricetta di cucina: un parallelo utile (con qualche riserva)

Spesso nei testi si paragona l'algoritmo ad una ricetta di cucina per farne comprendere i concetti fondamentali.

1. Gli ingredienti della ricetta possono essere paragonati ai dati di input dell'algoritmo
2. La ricetta stessa è l'analogo dell'algoritmo, in quanto descrive la sequenza di passaggi per ottenere un risultato (il piatto finale)
3. Chi esegue la ricetta (il cuoco) è l'analogo dell'esecutore (noi o un computer)
4. Gli strumenti di cucina (padelle, pentole, etc.) possono essere paragonati all'hardware su cui l'algoritmo viene eseguito.

Tuttavia, la ricetta di cucina mette in evidenza anche quegli aspetti che spesso non la rendono un vero e proprio algoritmo. Infatti può mancare di quella non ambiguità richiesta dagli algoritmi. Indicazioni come "quanto basta" (q.b.) o l'uso di misure imprecise (un cucchiaino senza specificarne le dimensioni) introducono ambiguità.

Se una ricetta recita "aggiungere sale quanto basta", un esecutore (soprattutto una macchina) potrebbe non essere in grado di interpretarlo in modo univoco.

Un vero algoritmo ammette una sola possibile interpretazione delle sue istruzioni.

Algoritmo vs. Programma

È importante distinguere l'algoritmo dal programma informatico, anche se spesso si tende a confondere i due termini.

Il primo rappresenta la strategia risolutiva del problema che può essere descritta anche in un linguaggio non di programmazione, come lo pseudocodice o utilizzando formalisimi grafici come i diagrammi di flusso.

Il programma, invece, è l'implementazione dell'algoritmo in uno specifico linguaggio di programmazione (Java, C++, ecc.).

Include non solo l'algoritmo ma gestisce anche operazioni aggiuntive come l'acquisizione dei dati di input (lettura da tastiera, da file, da Internet) e la gestione dell'output (stampare la soluzione sullo schermo, salvarla su un file ecc.).

Quindi possono esistere diverse implementazioni (programmi) per uno stesso algoritmo.

Conclusioni

In sintesi un algoritmo è una strategia sequenziale, non ambigua, generale, eseguibile e finita per risolvere un problema.

La sua importanza nella vita moderna è indiscutibile e comprendere le sue caratteristiche fondamentali ci aiuta a capire meglio come funzionano molti dei sistemi con cui interagiamo quotidianamente.

Un problema si dice computabile se esiste un algoritmo in grado di risolverlo, anche se la sua complessità pratica deve essere valutata opportunamente.

[VIDEO YOUTUBE]

[PODCAST]