Un algoritmo è una procedura iterativa contenente un numero finito di istruzioni, che ripetute più volte permettono di giungere alla soluzione di un problema, o a una sua ragionevole approssimazione.

Il termine algoritmo deriva dal nome del celebre matematico arabo Muhammad ibn Musa al-Khwarizmi, fondatore dell’algebra e inventore di celebri metodi risolutivi.

In realtà algoritmi matematici erano già noti in epoca pre-cristiana, in particolare presso le civiltà mesopotamiche. Storicamente i primi algoritmi erano metodi di calcolo che permettevano di approssimare soluzioni complesse che oggi vengono facilmente implementate su di una calcolatrice.

Occorre notare che il metodo usato da calcolatrici e computer per calcolare numeri irrazionali, come radici e funzioni trigonometriche, altro non è se non una serie di algoritmi che la macchina esegue in vece dell’uomo, con minore fatica e dispendio di energie.

 

Rigorosamente parlando un algoritmo non deve per forza di cose essere un processo matematico o contenere istruzioni matematiche.

Se ad esempio fosse possibile creare una sequenza di operazioni bibliografiche (del tipo 1. provenienza geografica dell’autore studiato 2. Tematica studiata 3. Indurre lista di commentatori specifici 4. Indurre volumi pertinenti 5. Conclusioni) in grado di garantire, previa conoscenza dell’autore e del tema discusso una sicura conclusione (converge su: “l’autore ha ragione” oppure “l’autore ha torto”), saremmo certamente davanti ad un algoritmo.

Dal momento che le istruzioni devono essere inequivocabili (quindi ad esempio 3. non è un istruzione algoritmica), diventa abbastanza improbabile trovare un algoritmo che non faccia esplicito uso di istruzioni matematiche.

D’altra parte la quasi totalità degli algoritmi non garantisce di convergere su di un risultato e oggi sono noti algoritmi particolari che forniscono risultati non ottimali.

 

L’algoritmica è un ramo della matematica e dell’informatica importantissimo. Sono algoritmi tutti i metodi di calcolo implementati su una macchina, ma anche i sistemi di compressione dati (come WinZip), i metodi di stoccaggio audio come Mp3, i metodi di criptaggio e decriptaggio di codici.

Con algoritmi appositi si possono calcolare grandi numeri o numeri con altissima precisione, trovare nuovi numeri primi, calcolare superfici e immagazzinare dati in sistema binario.

 

Il problema che vogliamo analizzare è più ristretto, si tratta in particolare di una famiglia di metodi matematici la cui funzione primaria è trovare lungo il percorso di una curva il punto in cui questa attraversa lo zero.

 

Nel disegno vediamo un’immagine con una funzione che incontra il valore zero in tre punti diversi.

 

Questo caso può sembrare molto specifico, ma in realtà è possibile ricondurre un’ampia fetta di problemi matematici alla soluzione di un problema f=0, funzione uguale a zero.

Un tipico problema di fisica è ad esempio trovare la configurazione in cui l’energia di un certo sistema è minima. Questo implica che il sistema in questione è stabile (ad esempio uno sciatore in cima alla montagna è instabile, mentre in fondo alla vallata è stabile, e questo corrisponde a due situazioni di energia cinetica massima e minima).

Anche la costruzione di un ponte, la creazione spontanea di una particella elementare, richiedono di minimizzare l’energia.

Tutti i problemi che richiedono di calcolare un massimo o un minimo possono essere ricondotti ad un problema del tipo f=0.

 

La difficoltà del problema può essere sormontata da un algoritmo di questo tipo:

diciamo che conosciamo l’espressione matematica che descrive la nostra curva (vedi figura), ma che non abbiamo i mezzi tecnici per calcolare lo zero che si trova nel centro.

Sappiamo però che esso è incluso tra due estremi che scegliamo a nostro piacere.

 

Il disegno illustra alcune iterazioni (un’iterazione è l’esecuzione di tutte le istruzioni una volta). È chiaro che questo metodo non permette in generale di ottenere un risultato assolutamente esatto, ma permette di ottenere tanta precisione quanta ne serve, basta avere pazienza e ripetere la procedura.

 

Appaiono immediatamente i difetti di questo algoritmo.

Innanzi tutto esso ha una debolezza. È sufficiente scegliere due punti della funzione entrambi positivi perché l’algoritmo dia un errore e si fermi.

È una debolezza piccola, poiché in generale è piuttosto semplice trovare un “buon” intervallo di partenza.

In seguito non ci sono controindicazioni sulla forma o sul comportamento della funzione.

Il fatto che un algoritmo resista bene ad ogni genere di funzione o abbia invece la tendenza a fermarsi, si chiama robustezza.

 

Il secondo inconveniente è la lentezza di convergenza dell’algoritmo; nel nostro caso sono necessarie davvero moltissime iterazioni anche soltanto per avere una precisione modesta, e questo va a discapito dell’efficacia. Anche per un computer che esegue operazioni molto rapidamente, questo algoritmo può rivelarsi rapidamente eccessivo. Se ad esempio volessi una precisione a dieci cifre significative, partendo da un intervallo spesso un’unità, sarebbero necessarie 33 iterazioni, dunque dato che ogni iterazione richiede 5 calcoli, il computer dovrebbe effettuare 165 operazioni.

 

In generale, la robustezza e la velocità non vanno molto d’accordo; più un algoritmo è robusto più lunghi saranno i tempi di convergenza.

Esistono algoritmi più complessi (questo credo sia il più semplice mai inventato) che permettono di ridurre sensibilmente il numero di calcoli da effettuare.

 

Quasi tutti i metodi che richiedono di testare una qualche proprietà della funzione (del tipo “esiste un solo zero dentro il mio intervallo”, come nel nostro caso, oppure “la mia funzione non diventa mai piatta”, oppure “la funzione non aumenta di valore troppo in fretta”) sono metodi analitici.

Sono cioè sistemi progressivi che si avvicinano inesorabilmente al risultato e forniscono sempre il valore “giusto” oppure nessun valore.

Esistono però problemi che non hanno soluzioni semplici analiticamente, oppure condizioni in cui non sappiamo nulla a priori  della funzione da testare e non possiamo assolutamente permetterci un crash del nostro algoritmo.

Gli algoritmi genetici e le simulazioni di Monte Carlo sono due esempi in cui intervengono metodi basati su altri presupposti, in particolare la scelta casuale di un numero, che permettono di ottenere risultati intriganti, senza ricorrere alla matematica canonica, ma che introducono la necessità di disporre di un sistema in grado di “inventare” in modo davvero casuale.