Insalata di matematica e ricette varie: gli algoritmi

Nel post precedente abbiamo visto in modo semiserio un ferro del mestiere molto utile nella borsa del matematico, cioé l’algoritmo di ricerca per bisezione, e come sia possibile applicarlo per indovinare un numero tra 1 e 1000 in 10 tentativi.

L’algoritmo è estramente semplice: ad ogni tentativo si propone il numero che sta a metà tra il minimo ed il massimo corrente. Se il numero pensato dal nostro amico è minore allora il numero proposto diventa il nuovo massimo, viceversa se è maggiore allora avremo un nuovo minimo.

Ma come mai è così efficiente ? Diamo innanzitutto una definzione formale dell’algoritmo applicato alla ricerca di un numero tra 1 ed N, che abbiamo già visto essere un sottoinsieme dei numeri naturali e che si indica con [1, N]. L’algoritmo di bisezione nel nostro caso specifico è descritto come segue:

– poni MIN = 1
– poni MAX = N
– chiedi (MIN + MAX )/ 2
– se la risposta è MINORE, poni MAX = (MIN + MAX) / 2
– se la risposta è MAGGIORE, poni MIN = (MIN + MAX) / 2
– se la risposta è UGUALE, termina l’esecuzione.

(il risultato di (MIN + MAX)/2 va arrotondato al numero intero inferiore)

abbiamo usato per la prima volta una notazione un pò particolare, molto simile a quella matematica delle funzioni ma che esplicita una serie di passi di esecuzione successiva di calcoli e operazioni. Oggetto di questo tipo vanno sotto il nome di algoritmo e forniscono un modo molto compatto di esprimere procedimenti di calcolo costituiti da operazioni elementari in sequenza.

Come mai l’algoritmo di sopra è tanto efficiente da arrivare al numero cercato in così poco tempo ? Il segreto sta, ovviamente, nella scelta del numero ad ogni passaggio. Va da sé che é relativamente difficile azzeccare il numero direttamente, quindi ogni scelta del prossimo numero va fatta anche in ottica di ridurre al massimo il numero di numeri possibili che NON sono quello cercato. Ogni volta che si fa una scelta, infatti, si taglia letteralmente via una fetta di numeri che sappiamo non contentere il numero pensato dal nostro amico. Il numero di passi in cui si prevede che un algoritmo termini è detto complessità, ne parleremo in un post apposito.

Ora, scegliendo il prossimo numero in modo tale che la fetta tagliata via sia più grande possibile, ad ogni passaggio riduciamo in modo drastico il campo di ricerca. Ma come possiamo scegliere il prossimo numero in modo da massimizzare questa fetta ? Semplicemente andando a pescare il numero esattamente a metà, così se dovessimo azzeccare il numero bene, ma se così non fosse avremmo comunque ridotto esattamente della metà l’insieme dei numeri dove effettiuiamo la nostra ricerca. Così. se all’inizio i numeri in cui cercare sono 1000, al secondo tentativo i numeri possibili sono già 500, al terzo 250 e così via fino ad arrivare ad 1 solo numero rimasto, quando il nostro algoritmo termina.

Ma quanti passaggi occorrono perché il nostro algoritmo termini ? Semplice, basta dividere per due i numeri rimasti fino ad arrivare ad 1, ed ecco la serie: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1. 10 passi, appunto. Al prossimo post vedremo come algoritmi e grafi siano una coppia inscindibile.

Ti piace LidiMatematici ? Seguici su Twitter !