Glossario

Algoritmo

Un algoritmo è una sequenza finita di istruzioni non ambigue che, a partire da dati in ingresso, porta a risolvere un problema o a eseguire un compito. Lo stesso algoritmo, applicato agli stessi dati, produce sempre lo stesso risultato. In informatica è alla base di ogni programma e di ogni software.

Cos’è un algoritmo e come funziona

Un algoritmo riceve dati in ingresso, li elabora con una serie di passaggi precisi e restituisce un risultato. Deve avere tre caratteristiche: ogni istruzione è chiara, il numero di passaggi è finito e il procedimento arriva sempre a una conclusione. Una ricetta di cucina segue la stessa logica, con gli ingredienti come dati in ingresso e il piatto finito come risultato.

In informatica un algoritmo si scrive in un linguaggio di programmazione, come Python, e lo esegue un computer. Lo stesso problema può avere più algoritmi, diversi per velocità e per memoria occupata. La parola deriva dal nome di al-Khwarizmi, matematico persiano del IX secolo.

Tipi di algoritmo più diffusi

Gli algoritmi di ordinamento mettono i dati in sequenza, per data o per importo. Quelli di ricerca trovano un elemento in un insieme. Gli algoritmi sui grafi calcolano percorsi, come la strada più breve proposta da un navigatore. Gli algoritmi di crittografia proteggono i dati, mentre quelli di compressione riducono lo spazio occupato da un file.

Come si misura l’efficienza di un algoritmo

Si usa la complessità computazionale, che descrive come crescono tempo e memoria all’aumentare dei dati. Si indica con la notazione O grande: un algoritmo O(n) raddoppia il tempo quando i dati raddoppiano, uno O(n²) lo quadruplica. Con dieci nomi la differenza è impercettibile, mentre con dieci milioni di righe l’elaborazione può durare un secondo oppure un’ora.

Differenza tra algoritmo e programma

L’algoritmo è il procedimento, indipendente dal linguaggio. Il programma è la sua realizzazione in un linguaggio preciso, che un computer sa eseguire. Lo stesso algoritmo può diventare programmi diversi in Python, Java o C, con prestazioni che dipendono dal linguaggio e dal modo in cui è scritto il codice.

Algoritmi e intelligenza artificiale

Gli algoritmi di machine learning ricavano le regole dai dati invece di riceverle scritte a mano. Sono comunque algoritmi: il procedimento di addestramento è definito, e a variare sono i parametri che ne derivano. Nei sistemi di intelligenza artificiale convivono regole scritte dagli sviluppatori e regole apprese dai dati.

Come si rappresenta un algoritmo

Prima di scriverlo in un linguaggio, un algoritmo si descrive in forme più vicine al ragionamento. Il diagramma di flusso mostra i passaggi con riquadri e frecce, e le decisioni con rombi. Lo pseudocodice li scrive in frasi strutturate come un programma, senza la sintassi di un linguaggio preciso. Si usano per discutere la soluzione con persone non tecniche e per controllarne la logica prima dello sviluppo.

Le proprietà di un buon algoritmo

Un algoritmo è corretto quando produce il risultato giusto per ogni dato ammesso, compresi quelli che nessuno ha provato durante lo sviluppo. Deve poi terminare in un numero finito di passaggi ed essere efficiente, cioè usare una quantità ragionevole di tempo e di memoria. Conta anche la leggibilità: un procedimento che un collega capisce in pochi minuti si corregge e si migliora con più facilità. Infine un buon algoritmo è generale, perché risolve una classe di problemi e non un caso isolato.

Algoritmi noti e a cosa servono

L’algoritmo di Euclide calcola il massimo comun divisore di due numeri e risale a oltre duemila anni fa. La ricerca binaria trova un elemento in un elenco ordinato dimezzando a ogni passo lo spazio da esaminare: su un milione di voci bastano circa venti confronti. L’algoritmo di Dijkstra, pubblicato nel 1959, trova il percorso più breve in una rete, ed è alla base di molti sistemi di navigazione. Il quicksort, proposto da Tony Hoare, ordina grandi quantità di dati in modo rapido. Il PageRank, ideato dai fondatori di Google, assegna un’importanza alle pagine web in base ai collegamenti che ricevono.

Come si progetta un algoritmo

Si comincia definendo con precisione i dati in ingresso e il risultato atteso. Si scompone poi il problema in parti più piccole, si sceglie come organizzare i dati e si scrive la soluzione, prima in forma di pseudocodice e poi in un linguaggio di programmazione. La verifica si fa con casi di prova che comprendono anche le situazioni limite, come un elenco vuoto o un valore mancante. Alla fine si misurano i tempi su quantità di dati simili a quelle reali, perché un algoritmo veloce su cento righe può essere lento su dieci milioni.

Algoritmi che influenzano decisioni sulle persone

Alcuni algoritmi concorrono a decidere se concedere un prestito, quali candidati convocare o quale prezzo mostrare a un cliente. Quando la decisione ha effetti rilevanti sulla persona, il GDPR riconosce il diritto di non essere sottoposti a una decisione basata unicamente su un trattamento automatizzato. Il regolamento europeo sull’intelligenza artificiale tratta come sistemi ad alto rischio diversi usi di questo tipo, tra cui la selezione del personale e la valutazione del merito di credito. Per questo le aziende documentano come funziona l’algoritmo, con quali dati e con quale controllo umano.

Fonti e approfondimenti