Un albero che ha cambiato il mondo …

La volta scorsa abbiamo visto, in termini di algoritmo, un modello matematico del nostro metodo di ricerca per bisezione. Abbiamo anche visto come l’algoritmo proposto sia estremamente efficiente.

Ogni algoritmo può essere rappresentato efficacemente mediante un’altro importante strumento che abbiamo già messo al sicuro nella nostra borsa del matematico: il grafo. L’idea alla base della rappresentazione mediante grafi è di modellare ogni passo di esecuzione del nostro algoritmo mediante un nodo, con gli archi a rappresentare i passaggi tra un passo e l’altro.

Proviamo a costruire il grafo dell’algoritmo visto, supponendo per semplicità che l’intervallo da cercare sia di 7 numeri. Al primo tentativo chiederemmo se il numero cercato è 4, se è maggiore allora proveremmo con un 6, se è minore allora con un 2. Osservate la struttura: ogni nodo, ha due archi collegati sotto di sé. Un grafo di questo tipo è detto albero binario. E’ una struttura matematica fondamentale negli algoritmi di ricerca con cui è stata risolta una quantità di problemi impressionante: mettetelo al sicuro nella vostra borsa del matematico.

Ricordate il concetto di cammino ? E’ l’insieme degli archi e nodi che possiamo percorrere in un grafo. In questo caso, un percorso di soluzione corrisponde ad un cammino massimo di lunghezza 3. Nel caso generico di N numeri interi, la ricerca termina in un numero di passaggi massimo pari all’altezza del nostro albero binario.

Ma osservate ogni riga dell’albero: la prima ha 1 nodo, la seconda 2, la terza 4. Se andassimo avanti all’altezza generica i, il numero di nodi di ogni riga è 2^i, cioé 2 moltiplicato sé stesso i volte. Ciò significa che con un tentativo, indoviniamo un numero, con 2 tre, con 3 sette e così sommando potenze di due.

Notate una finezza delle potenze di due e degli alberi binari: ogni riga contiene un numero di nodi pari alla somma di tutti i nodi nelle righe precedenti più uno. Usiamo questo fatto per rispondere alla domanda iniziale, con 1000 numeri possibili, quanti raddoppi occorrono ? Ne bastano 10, infatti: 2x2x2x2x2x2x2x2x2x2 = 1024.

Tenete a mente la struttura dell’albero binario, la ritroveremo molte volte come modello alla base di altri problemi che, con questo, sembreranno non avere nulla a che fare. Pensate: la cultura cinese lo ha scoperto già migliaia di anni fa.

A Lunedì.