Le magie del logaritmo binario

Tempo addietro abbiamo parlato dell’algoritmo di bisezione, una tecnica di ricerca estremamente efficiente in grado di identificare un valore in un numero di passaggi sorprendentemente basso.

Riassumiamo brevemente i termini della questione: si tratta di azzeccare un numero intero tra 1 ed N nel numero minore possibile di tentativi. La formalizzazione che abbiamo proposto nel post relativo alla complessità degli algoritmi  è la seguente:

Abbiamo detto che ad ogni passo l’algoritmo dimezza lo spazio di ricerca, quindi se al primo passo il numero di possibilità è pari ad N, al secondo sarà N/2, poi N/4, N/8 e così via. Notate il denominatore: prima un mezzo, poi un quarto e, al passo generico k,  1/2^k (uno su 2 alla k).

Abbiamo visto che l’algoritmo termina quando resta una sola opzione possibile, ovvero quando abbiamo diviso N tante volte per 2 quanto basta a sezionarlo tutto. In altri termini, dopo il numero k di passi per cui:

2^k = N

proprio per quel valore dell’esponente k da dare alla base 2 per ottenere N. Ricordate ? Questa è la definizione del logaritmo in base 2, quindi:

k = log N

dove per log, in questo caso, si intende il logaritmo in base 2, anche detto logaritmo binario.

Il logaritmo binario è uno strumento di grande importanza  che si applica in un numero considerevole di casi. Si usa il logaritmo in base 2 per determinare l’altezza dell’albero binario e in tutti i problemi correlati alla ricerca su bipartizioni (cioé serie di divisioni in due metà uguali).

Problemi di questo tipo sono “nascosti” praticamente ovunque. Quando abbiamo introdotto il gioco delle Torri di Hanoi e visto come sia possibile risolverlo in modo ricorsivo, è emerso che anche questo gioco è rappresentabile mediante un albero binario. Le Torri di Hanoi, lo ricordiamo, consistono nello spostare un numero di dischi arbitrario N su tre pioli, senza mai collocare dischi grandi sopra ai più piccoli.

La soluzione ricorsiva del gioco  prevede che per risolvere il gioco a 3 dischi occorrono 2^3-1 = 7 mosse, a 4 dischi 2^4-1 = 31, e così via. Il numero di dischi, di nuovo, è dato dal logaritmo in base 2 (più uno) del numero di mosse necessarie per risolvere il gioco.

E non è tutto qui: il logaritmo binario gioca un ruolo fondamentale nella Teoria dell’Informazione e consente di fare cose al limite della magia. Ovviamente, ne riparleremo.