Che cos'è un algoritmo

Il metodo per trovare il massimo comune divisore nel Libro VII degli Elementi di Euclide, scritto circa 2300 anni fa, funziona ancora oggi nei computer.

Un metodo che funziona sempre

Supponi di cercare il numero più grande che divide sia 1071 sia 462. Potresti provare tutti i numeri da 462 fino a 1 e fermarti al primo che li divide entrambi. Funziona, ma può richiedere centinaia di tentativi. C'è una strada più breve. Dividi 1071 per 462 e tieni il resto, 147. Ora dividi 462 per 147 e tieni il resto, 21. Dividi 147 per 21: il resto è 0, quindi la risposta è 21. Tre divisioni invece di diverse centinaia.

Quella strada più breve è un algoritmo: un elenco finito di passi precisi che prende un input e produce l'output giusto. Questo è l'algoritmo di Euclide per il massimo comune divisore, e compare nel Libro VII degli Elementi, scritti intorno al 300 a.C. Euclide lo descriveva con sottrazioni ripetute di lunghezze invece che con divisioni, ma l'idea è la stessa, e la versione con i resti è quella che usano oggi i programmi.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // resto
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

Che cosa rende un elenco di passi un algoritmo

Manuali come quello di Cormen, Leiserson, Rivest e Stein descrivono un algoritmo come una procedura ben definita che trasforma un input in un output. In questa descrizione ci sono tre elementi, e ognuno conta quando scrivi codice.

• Preciso. Ogni passo significa una cosa sola. «Dividi a per b e tieni il resto» è preciso; «rendi i numeri più piccoli in qualche modo» non lo è.
• Finito. Deve fermarsi. Nell'algoritmo di Euclide il resto è sempre più piccolo del numero per cui hai diviso, quindi diminuisce a ogni giro e deve arrivare a 0.
• Corretto. Per ogni input ammesso, l'output è la risposta giusta, non solo per gli esempi che hai provato.

Spesso si porta come esempio quotidiano una ricetta di cucina, ed è un esempio onesto: gli ingredienti sono l'input, il piatto è l'output e i passi sono in ordine. La differenza sta in quanto deve completare chi legge. Un cuoco decide che cosa vuol dire «un pizzico». Un computer non decide niente, ed è per questo che gli algoritmi per computer si scrivono con ogni passo spiegato per intero.

Stesso problema, algoritmi diversi

Di solito un problema ha molti algoritmi corretti, e possono differire moltissimo nella quantità di lavoro che fanno. Per il massimo comune divisore di 1071 e 462, provare tutti i numeri da 462 in giù richiede 442 tentativi prima di arrivare a 21, mentre il metodo di Euclide richiede 3 divisioni. Sono corretti entrambi. Solo uno è veloce. Buona parte di questo corso riguarda questa seconda domanda: una volta che un metodo è corretto, quanti passi richiede, e come cresce quel numero quando l'input diventa più grande?

Per rispondere, gli informatici contano i passi elementari (un confronto, uno scambio, una divisione) invece dei secondi. I secondi dipendono dalla macchina. Il numero di passi dipende solo dall'algoritmo e dall'input, quindi permette di confrontare due metodi in modo equo. Il laboratorio qui sotto conta per te i confronti mentre ordina una fila di barre. Prova lo stesso ordine iniziale con due metodi diversi e osserva i contatori.

Input, output e i passi in mezzo

Prima di scrivere un algoritmo, annota con esattezza che cosa entra e che cosa deve uscire. Per il massimo comune divisore: l'input sono due numeri interi positivi, e l'output è un numero intero che li divide entrambi, senza che un numero più grande faccia lo stesso. Questa descrizione ti dice come verificare il risultato, e spesso suggerisce i passi. Rivela anche i casi limite: e se uno dei numeri è 0? (Il ciclo qui sopra restituisce l'altro numero, che è la risposta corretta.) E se i due numeri sono uguali? Pensare ai casi limite prima di eseguire il codice evita molti errori.