Con l’avanzare dell’informatizzazione generale della nostra società, si sente parlare sempre più spesso di algoritmi informatici. Capita sempre più di frequente di sentire frasi del tipo “l’algoritmo ha stabilito che…” oppure “hanno fatto girare l’algoritmo”… ma cos’è un algoritmo? Solitamente quando utilizziamo questa parola intendiamo un algoritmo informatico, ma come vedremo la nozione di algoritmo può essere applicata anche in altri campi.
Indice
- Cos’è un algoritmo?
- Da dove viene la parola algoritmo?
- Utilizzi più frequenti degli algoritmi
- Come si definisce un algoritmo
- Esempi algoritmi informatica
- Conclusioni
Cos’è un algoritmo?
Partiamo, nella nostra scoperta del significato di algoritmo, dalla definizione che ci da Wikipedia nella pagina dedicata a questo termine. Data la mancanza di una definizione formale di questo termine, il sito riporta due diverse definizioni informali, che trascriveremo insieme qui sotto.
Un algoritmo è una strategia che serve per risolvere un problema ed è costituito da una sequenza finita di operazioni (dette anche istruzioni), consente di risolvere tutti i quesiti di una stessa classe.
Una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito
Wikipedia – Algoritmo
Leggendo queste parole, forse a molti potrà venire in mente un esempio di algoritmo che tutti probabilmente conosciamo, chi con più passione e chi meno. Leggendo queste parole ci rendiamo conto che il procedimento di una ricetta di cucina può rispondere abbastanza bene alle definizioni riportate. Si tratta infatti di una strategia che serve per risolvere un problema, ovvero cucinare qualcosa. Una ricetta è inoltre costituita da una sequenza finita e ordinata di operazioni o istruzioni, che troviamo scritte chiaramente nel procedimento. Il risultato dell’algoritmo è ben determinato e raggiungibile in un tempo finito, ogni ricetta permette di cucinare un certo alimento, e nessuna ricetta dura all’infinito, il risultato si raggiunge solitamente nel giro al massimo di qualche ora.
Forse vi starete chiedendo “Ma cosa c’entrano le ricette di cucina con i programmi informatici?” in realtà la risposta è che un algoritmo non è un programma informatico. Come abbiamo visto un algoritmo è una sequenza di passi ben definita che permette di raggiungere uno scopo. Possiamo dire che un algoritmo è in sostanza la ricetta per fare qualcosa.
Un programma informatico solitamente non fa altro che eseguire delle istruzioni che sono state scritte da un programmatore, e che permettono ad un computer di elaborare dati. Un programma informatico è quindi un “esecutore” di istruzioni, segue una ricetta che gli è stata data. Applicando la nostra analogia con le ricette culinarie possiamo azzardare dicendo che il programma informatico è lo chef che legge la ricetta e la applica producendo il piatto finale.
A differenza di quanto si intende solitamente, un algoritmo è quindi solamente la definizione di una procedura per risolvere un problema, e non l’entità che poi realmente risolve il problema.
Da dove viene la parola algoritmo?
Il concetto di algoritmo ha origini antichissime. Gli algoritmi aritmetici come quello della divisione fra due numeri, erano utilizzati già dai babilonesi nel 2500 a.c., e da tutte le generazioni di matematici seguenti, Egiziani, Greci Arabi e così via.
L’origine del termine però sembra risalire a tempi un po’ più recenti, ovvero al nono secolo d.c., derivante dalla trascrizione latinizzata del nome del matematico persiano Muhammad ibn Musa al-Khwarizmi. Trascritto come Algorizmi, questo termine venne utilizzato per diversi secoli in ambito matematico, per poi arrivare alla prima attestazione del termine inglese algorithm nel diciassettesimo secolo. La definizione moderna di algoritmo fu poi introdotta nel diciannovesimo secolo.
Utilizzi più frequenti degli algoritmi
Il termine algoritmo viene solitamente utilizzato in matematica ed in informatica (concetti simili prendono altri nomi in altri campi, avremo la ricetta e non l’algoritmo per fare la pasta).
In matematica un algoritmo è la procedura da utilizzare per risolvere un problema. Avremo quindi algoritmi per ogni tipo di problema matematico: fare una moltiplicazione, fare una divisione, risolvere un’espressione algebrica, risolvere un problema di geometria, e così via. Possiamo quindi stabilire che un problema è calcolabile se è risolvibile seguendo un algoritmo.
In informatica, come abbiamo detto, è facile scambiare un algoritmo con un programma informatico.
Usando un algoritmo, un programmatore può “dire” ad un computer di ricercare in un database i dati del fatturato del mese scorso, poi di compararli con quelli del mese precedente, e dello stesso mese dell’anno precedente, e infine di farne un grafico. Mettendo insieme molti algoritmi nasce un programma informatico come siamo abituati a conoscerlo. Per riassumere quindi, un algoritmo è la definizione della soluzione di un problema, l’algoritmo viene poi trasformato in codice in un determinato linguaggio di programmazione, e più “pezzi di codice” uniti insieme formano un programma informatico.
Come si definisce un algoritmo
Un algoritmo può essere definito in vari modi, e con diversi livelli di specificità.
- Una semplice lista di operazioni da eseguire in ordine.
- Un diagramma di flusso.
Vediamo cosa contraddistingue questi due modi di formalizzare un algoritmo.
Algoritmo come lista di operazioni
Questa è la forma che solitamente troviamo quando cerchiamo una ricetta di cucina: una lista di operazioni da eseguire nell’ordine in cui sono definiti.
Un algoritmo può essere descritto in maniera più o meno specifica ed approfondita:
- Descrizione di alto livello
- Descrizione dell’implementazione
- Descrizione formale
Nella descrizione di alto livello si descrive l’algoritmo ignorando i dettagli d’implementazione, dandone quindi una descrizione “in prosa”.
Nella descrizione formale si utilizza un linguaggio molto più vicino al linguaggio di un programma informatico, utilizzando quello che viene generalmente chiamato pseudocodice.
La descrizione dell’implementazione è una via di mezzo, ovvero una descrizione dell’algoritmo un po’ più dettagliata di quella di alto livello ma senza utilizzare tutti i dettagli dello pseudocodice della descrizione formale.
Prendiamo ad esempio l’algoritmo di ricerca del numero più grande da una lista di numeri.
Possiamo darne una descrizione di alto livello scrivendo:
- Se non ci sono numeri nella lista, allora non c’è un numero più grande.
- Consideriamo il primo numero della lista come il numero più grande corrente.
- Per ogni numero rimanente nella lista: se questo numero è più grande del numero più grande corrente, allora questo numero diventa il numero più grande corrente.
- Quando i numeri della lista sono finiti, il numero più grande corrente è il numero più grande della lista.
Come possiamo osservare, questo algoritmo è composto da una sequenza ordinata e finita di operazioni, che portano al risultato di ottenere il numero più grande della lista. Questa descrizione è però una descrizione ad alto livello, non contiene alcun riferimento all’eventuale implementazione in un programma informatico. Un computer non può interpretare questa descrizione, ma l’algoritmo è ben descritto e una persona potrebbe essere in grado di interpretarlo, eseguirlo, o trasformarlo in un codice eseguibile da un computer.
Lo stesso algoritmo può essere descritto anche facendone una descrizione più formale, possiamo ad esempio scrivere il seguente pseudocodice:
Algoritmo NumeroMaggiore
Input: Una lista di numeri L
Output: Il numero maggiore nella lista L
if L.size == 0 return null
piuGrande = L[0]
for each elemento in L, do
if elemento > piuGrande, then
largest = item
return largestIn questa descrizione troviamo lo stesso algoritmo che abbiamo descritto prima con un elenco numerato, ma questa volta il linguaggio utilizzato non è più la lingua comune, ma un linguaggio molto più vicino ad un linguaggio di programmazione informatica. Questa descrizione offre qualche dettaglio in più sulla modalità di implementazione di un eventuale programma informatico che dovrà risolvere il problema.
Algoritmo come diagramma di flusso
A volte la descrizione di un algoritmo come lista di operazioni può essere troppo complessa per essere facilmente leggibile ed interpretabile. Questo accade particolarmente per algoritmi particolarmente lunghi o particolarmente densi di istruzioni condizionali e salti da un punto all’altro della lista.
Per questi casi può essere più semplice rappresentare l’algoritmo come un diagramma di flusso, ovvero una sequenza di blocchi uniti da frecce. Un esempio di questo tipo può essere l’algoritmo di ricerca del massimo comune divisore di due numeri. Vediamo il diagramma qui sotto:
In questa descrizione dell’algoritmo troviamo dei rettangoli, che indicano delle azioni, dei rombi che indicano la verifica di determinate condizioni ( B=0? oppure A>B?) e delle frecce che indicano come muoversi nella sequenza di operazioni da fare. Notiamo ad esempio per le istruzioni condizionali che ogni rombo ha due frecce in uscita, una da seguire se la condizione è verificata ( se B è uguale a 0 nel primo caso e se A è maggiore di B nel secondo), e l’altra da seguire se la condizione non è verificata.
Questo algoritmo potrebbe essere descritto anche come lista di operazioni, ma la rappresentazione visuale del diagramma aiuta a capire molto più a colpo d’occhio il flusso delle operazioni. A partire da questo diagramma sarà poi possibile eventualmente costruire una descrizione formale tramite pseudocodice o direttamente un codice scritto in un linguaggio di programmazione e quindi interpretabile da una macchina.
Esempi algoritmi informatica
Nel campo dell’informatica, ogni programma è in sostanza un algoritmo, o meglio è la trasposizione in un linguaggio di programmazione di un determinato algoritmo.
Abbiamo visto già alcuni esempi di algoritmi che potrebbero essere implementati in informatica, come ad esempio la ricerca del numero più grande in una lista o del massimo comune divisore di due numeri.
Un altro esempio di algoritmo informatico può essere l’algoritmo utilizzato per ordinare gli elementi di una lista (ad esempio dei numeri dal più piccolo al più grande o dal più grande al più piccolo
Un altro algoritmo di cui si sente parlare è quello che viene chiamato “l’algoritmo di google”. Si tratta in questo caso di un algoritmo di ricerca molto complesso, di cui non si conoscono neanche tutti i dettagli. In questo ambito però ci sono anche algoritmi di ricerca più semplici, come ad esempio l’algoritmo di ricerca di una stringa in una lista di stringhe, ovvero la ricerca della presenza di una determinata sequenza di caratteri in una lista. Di quest’ultimo possiamo provare a dare una descrizione come lista di operazioni:
- Se non ci sono elementi nella lista, la stringa non è presente
- Esaminiamo uno ad uno gli elementi della lista: se si tratta della stringa che stiamo cercando l’abbiamo trovata, possiamo quindi interrompere la ricerca con esito positivo, altrimenti se non si tratta della stringa passiamo all’elemento successivo
- Se siamo arrivati alla fine della lista senza trovare la stringa cercata, allora possiamo dire che quest’ultima non è nella lista.
Naturalmente è possibile creare algoritmi più complessi unendo più algoritmi, potremmo ad esempio estrarre il numero più grande da una lista, utilizzando l’algoritmo dell’esempio fatto in precedenza, poi estrarre il numero più grande da un’altra lista, e successivamente cercare il massimo comune divisore dei due numeri trovati. L’algoritmo di trovare il massimo comune divisore dei numeri più grandi di due liste può quindi essere definito combinando insieme i due algoritmi di base.
Un programma informatico è solitamente la composizione di più algoritmi che operano insieme per fornire le funzionalità e creare un software. Abbiamo parlato a fondo di cos’è il software in un articolo dedicato.
Conclusioni
Abbiamo quindi analizzato cos’è un algoritmo, il suo significato e visto qualche esempio di algoritmo informatico. Abbiamo visto come alla parola algoritmo si associ solitamente un algoritmo informatico, ma che il significato di questa parola è decisamente più ampio della sola informatica.