Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari, chiari e non ambigui.
Il termine deriva dalla trascrizione latina del nome del matematico persiano al-Khwarizmi, vissuto nel IX secolo d.C., che è considerato uno dei primi autori ad aver fatto riferimento
a questo concetto scrivendo il libro “Regole di ripristino e riduzione”.
L’algoritmo è un concetto fondamentale dell’informatica, anzitutto perché è alla base della nozione teorica di calcolabilità: un problema è calcolabile quando è risolvibile mediante
un algoritmo.
Inoltre, l’algoritmo è un concetto cardine anche nella fase di programmazione dello sviluppo di un software: preso un problema da automatizzare, la programmazione costituisce
essenzialmente la traduzione o codifica di un algoritmo per tale problema in programma, scritto in un certo linguaggio, che può essere quindi effettivamente eseguito da un calcolatore
rappresentandone la logica di elaborazione.
Nonostante ciò, una definizione del concetto di algoritmo che sia formale e non tecnica manca tuttora e si è pertanto costretti ad accontentarsi dell’idea intuitiva di algoritmo come:
“una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito”.
La definizione di algoritmo appena riportata è piuttosto informale, mentre era necessario disporre di una definizione più rigorosa per trattare il concetto di algoritmo con strumenti
matematici.
Al tal fine sono stati definiti alcuni modelli matematici di algoritmo, fra i quali uno dei più celebri è la macchina di Turing.
Essa rappresenta una sorta di computer ideale corredato di un programma da eseguire, ma, rispetto a un computer ideale, la macchina di Turing ha un funzionamento estremamente più semplice
cosicché il suo funzionamento possa essere facilmente descritto in termini matematici, facendo uso di concetti come insieme, relazione e funzione.
La macchina di Von Neumann, che è il modello di architettura primigenio di tutti i computer attuali, è equivalente, in termini di potere di calcolo, alla macchina di Turing.
In altre parole, è stato dimostrato che un certo problema può essere risolto da un computer (opportunamente programmato) se e solo se esso può essere risolto anche da una macchina
di Turing.
Oltre alla macchina di Turing, proposta da Alan Turing nel 1936, nello stesso periodo altri matematici hanno elaborato diverse rappresentazioni formali del concetto di algoritmo,
fra i quali ricordiamo, per esempio, il lambda calcolo.
Proprietà fondamentali degli algoritmi
Dalla precedente definizione di algoritmo si evincono alcune proprietà necessarie, senza le quali un algoritmo non può essere definito tale:
i passi costituenti devono essere “elementari”, ovvero non ulteriormente scomponibili (atomicità);
i passi costituenti devono essere interpretabili in modo diretto e univoco dall’esecutore, sia esso umano o artificiale (non ambiguità);
l’algoritmo deve essere composto da un numero finito di passi e richiedere una quantità finita di dati in ingresso (finitezza)
l’esecuzione deve avere termine dopo un tempo finito (terminazione);
l’esecuzione deve portare a un risultato univoco (effettività).
Per esempio, il calcolo del massimo comune divisore fra due numeri è un esempio di “problema”, e i suoi dati di ingresso, variabili di volta in volta, sono i due numeri in questione.
A un non matematico questa potrebbe apparire come una “famiglia di problemi” (il problema di calcolare il massimo comune divisore fra 10 e 15, il problema di calcolarlo fra 40 e 60,
fra 35 e 95, e così via). Il matematico e l’informatico identificano con la parola problema” l’intera famiglia e con “istanza” o “x” ciascuno dei quesiti specifici ottenuti fissando
due particolari valori. Data questa premessa, un algoritmo risolve un problema se per qualunque istanza del problema esso produce in un tempo finito la soluzione desiderata,
ovvero un certo risultato o dato in uscita (output) a partire da dei dati in ingresso (input).
Se questa idea aveva già una certa importanza per il calcolo matematico, l’avvento dell’informatica l’ha arricchita di una nuova importanza, ed è infatti con l’informatica che il termine
“algoritmo” ha iniziato a diffondersi. Difatti, se per ottenere un certo risultato (risolvere un certo problema) esiste un procedimento infallibile, che può essere descritto in modo non
ambiguo fino ai dettagli, e conduce sempre all’obiettivo desiderato in un tempo finito, allora esistono le condizioni per affidare questo compito a un computer, semplicemente introducendo
l’algoritmo in questione in un programma scritto in un opportuno linguaggio comprensibile alla macchina.
Inizialmente un algoritmo può essere descritto attraverso l’uso di un diagramma di flusso o ricorrendo a uno pseudocodice.
Successivamente, nella fase di programmazione l’algoritmo così scritto verrà tradotto in linguaggio di programmazione a opera di un programmatore sotto forma di codice sorgente dando vita
al programma che sarà eseguito dal calcolatore, eventualmente dopo un’ulteriore traduzione in linguaggio macchina.
Particolare rilevanza teorica in tale ambito assume il teorema di Böhm-Jacopini che afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza,
la selezione e il ciclo (iterazione), da applicare ricorsivamente alla composizione di istruzioni elementari.
Nella pratica corrente il programmatore professionista nel suo lavoro svolge automaticamente questo processo di traduzione scrivendo direttamente il codice sorgente necessario
nelle suddette modalità avendo già trovato la soluzione al problema dato.
Approccio matematico
Esistono numerosi modelli matematici di algoritmo. In generale, un algoritmo riceve un insieme di valori (dati) in input e ne genera uno in output (chiamato soluzione).
Dato dunque un algoritmo A si denota con fA la funzione che associa a ogni ingresso x di A la corrispondente uscita.
Questa corrispondenza tra input e output non rappresenta il problema risolto dall’algoritmo. Formalmente, un problema è una funzione
f ( D i ) → D
definita su insieme Di di elementi che chiameremo restanze, a valori su un insieme Ds di risoluzioni.
Lo studio di un algoritmo viene suddiviso in due fasi:
sintesi (detta anche disegno o progetto): dato un problema A, costruire un algoritmo f per risolvere A, cioè tale che f=fa.
analisi: dato un algoritmo f e un problema A, dimostrare che f risolve A, cioè f=fa (correttezza) e valutare la quantità di risorse usate da f (complessità concreta).
L’informatica quantistica è l’insieme delle tecniche di calcolo e del loro studio che utilizzano i quanti per memorizzare ed elaborare le informazioni.
Molte sono le differenze con l’informatica classica, soprattutto nei principi fondamentali.
La macchina di Turing (MT) è una architettura elaborativa utilizzata per lo studio dei computer tradizionali e della scienza dell’informazione che fu realizzata
allo scopo di creare un calcolatore e che è costruita in base agli assiomi della fisica classica: ossia lo stato del nastro e della testina sono sempre univocamente
identificabili, gli spostamenti sempre regolati dalle leggi del moto, etc.
Quindi la MT è totalmente deterministica (MTD).
Una sua variante, equivalente ma più veloce, è la macchina di Turing probabilistica (MTP).
Può risolvere ogni problema risolvibile via MTD, ma di solito lo fa più velocemente (nel senso della teoria della complessità algoritmica).
Anch’essa, però, è soggetta agli assiomi della fisica classica, e soprattutto nessuna delle due è reversibile, per il secondo principio della termodinamica.
Dato che la meccanica quantistica è reversibile, lo è anche una macchina di Turing quantistica (MTQ).
Inoltre deve rispettare i vincoli della meccanica quantistica, tra cui il principio di indeterminazione di Heisenberg e l’equazione di Schrödinger.
Lo sviluppo di una MTQ, quindi di un calcolatore quantistico, ha richiesto diversi passaggi. Nel 1973 Charles Bennet dimostrò che è possibile costruire una MT reversibile.
Nel 1980, Paul Benioff dimostrò che la reversibilità è una condizione necessaria per realizzare una MTQ. Due anni dopo Richard Feynman pubblicò il suo famoso lavoro sul
computer quantistico. In esso, stabilisce che: Una MTD può simulare un sistema quantistico solo con un rallentamento esponenziale (nel senso della teoria della complessità algoritmica).
Un computer basato sui qubit non è soggetto a tale limitazione, ed è dunque un simulatore quantistico universale.
Finalmente, nel 1985, David Deutsch dell’Università di Oxford descrisse la prima vera MTQ.
I primi prototipi di computer a qubit furono realizzati dal Centro ricerche dell’IBM di Almaden nel 1997, misurando lo spin dei nuclei atomici di particolari molecole
tramite la risonanza magnetica nucleare. Sono stati realizzati “processori” a 5 e 7 qubit, con cui tra l’altro è stato applicato per la prima volta l’algoritmo di
fattorizzazione di Shor.
Le regole che stanno alla base del calcolo quantistico differiscono notevolmente da quelle classiche, e sembrano molto più restrittive.
In realtà, è possibile mostrare che le macchine di Turing quantistiche (MTQ) non solo permettono di raggiungere la stessa affidabilità nei calcoli, ma riescono a eseguire compiti
che le macchine di Turing classiche non possono fare: ad esempio, generare numeri veramente casuali, e non pseudo-casuali.