Calcolo delle probabilità - La ricerca dicotomica
rubrica:
Autore:
L’altra sera mio nipote Giacomo mi ha proposto un giochetto molto divertente prendendo spunto dall’episodio della sua amica Giovanna che, a una pesca di beneficenza della parrocchia, si era trovata a dover ricercare il nominativo vincente dell’estrazione della festa di Santa Croce.
Il premio era un motorino – un Malaguti – tanto per fare pubblicità all’amico costruttore di scooter qui vicino a me, a San Lazzaro di Savena.
In merito ai motorini, anche l’altro other friend of mine Andrea Mingardi (Bologna 1940) nel ’76 - all’osteria di via Paolo Fabbri (dove ci dilettava anche Guccini) e dove spesso arrivava anche Lucio Dalla - al quartiere della Cirenaica, aveva scritto in proposito una stupenda zirudela nel suo tredicesimo album dal nome: lo Sfighé.
Nota:
La zirudèla l'è un componimänt scherzåus ch'as cantèva - in uréggin ed sòlit in canpâgna - par i matrimòni o pr î gran magnèr campagnû
Traduco:
La zirudela è un componimento dal tono scherzoso che si cantava – originariamente in campagna – durante le feste di matrimonio o in occasione delle grandi abbuffate.
…
Questo il testo di Mingardi:
“… alla pesca del rione ierin vanzè vent bigliat par venzer al moturen … al moturen. Mè che san ‘na volpe ahi ho cumprè tot al mazat ad bigliet e a’hai ho vint al moturen …”
Traduco:
“… alla pesca del rione erano rimasti venti biglietti per vincere un motorino … un motorino … e io che sono una volpe ho comprato tutta la mazzetta di biglietti rimanenti e ho vinto il suddetto motorino …”.
Tornando a mio nipote Giacomo, la domanda della sua amica Giovanna era la seguente: dato un elenco di indirizzi, qual è il modo più veloce per rintracciare un nominativo prescelto?Detto in altri termini: dato un nominativo qualsiasi, per esempio, Rossi Mario, quale sarà il percorso più veloce per rintracciarlo in una lista?
Il problema si può risolvere attraverso il concetto della dicotomia.
Il termine dicotomia deriva dal greco - dichotomía: dich (due) tomo (divido) - ed è usato in matematica, filosofia ed in informatica.
La dicotomia consiste nella divisione di un corpo in due parti tali da non poter essere entrambe contemporaneamente vere e completamente esaustive l'una rispetto all'altra.
In altre parole, la dicotomia non lascia spazio per una terza parte; si può quindi considerare una partizione in due parti precise.
Per essere più chiari, alla domanda "questo animale è provvisto di ossa?" la risposta è la divisione delle specie in vertebrati ed in invertebrati, dato che nessun animale può essere vertebrato o invertebrato contemporaneamente, né, tantomeno, può non appartenere a nessuna delle due categorie.
Anche in biologia, la dicotomia sta a significare la ripartizione tra una specie e l’altra senza possibilità di situazioni intermedie.
Tornando al problema di Giovanna - l’amica di mio nipote Giacomo - la dicotomia si presta a una soluzione di tipo informatico.
Giovanna si trova a dover rintracciare un elemento “e” all’interno di una serie sequenziale “S e”.
La condizione indispensabile del problema di Giovanna è che la serie numerica di ricerca sia in ordine crescente, cioè sequenziale, un po’ come avviene in un mazzo di carte ordinate.
Nel suo esperimento, Giovanna è certa che i partecipanti alla pesca di beneficenza risultano perfettamente ordinati in modo ascendente: dalla A alla Zeta: come esempio, il primo sarà Accorsi e l’ultimo sarà Zinelli.
…
Per risolvere velocemente il problema, basterà caricare i nominativi da ricercare in una schiera (secondo la notazione IBM) oppure su un array (cioè: “tabella” secondo la notazione Iso internazionale).
Altra condizione fondamentale sarà quella di caricare i nominativi di ricerca (da Accorsi a Zinelli) in un array potenza di 2.
Esempio: se la ricerca da effettuare è su un elenco di circa 200 elementi, creeremo un array potenza di 2 in eccesso, cioè 256 celle che corrispondono a 2 elevato all’ottava.
Nel linguaggio di programmazione Cobol (Common Business Oriented Language), la definizione dell’area di memoria su cui si applica la schiera sarà la seguente:
01 SCHIERA.
02 ELEM PIC X(30) OCCURS 256 TIMES.
Stiamo dando istruzione al computer di utilizzare un’area di memoria tabellare di 256 elementi, ciascuno costituto da 30 caratteri alfanumerici, quelli corrispondenti ai nominativi da caricare (da Accorsi a Zinelli).
Poiché la schiera è stata creata in sovrabbondanza di elementi (per esempio 200 elementi caricati contro 256 previsti in schiera), le celle di schiera vuota saranno coperti da valori esadecimali più alti possibili (in gergo: HV – cioè High Value – in pratica da una stringa di valori “ZZZZZZ”).
…
Torniamo al processo di ricerca dicotomica per capirlo con più facilità.
L’algoritmo cerca un elemento all'interno di un array ordinato effettuando mediamente meno confronti rispetto ad una ricerca sequenziale, e quindi più rapidamente rispetto ad essa.
La tecnica è simile al metodo usato per trovare una parola sul dizionario: sapendo che il vocabolario è ordinato alfabeticamente, l'idea è quella di iniziare la ricerca non dal primo elemento, ma da quello centrale, cioè a metà del dizionario.
A questo punto il valore cercato viene confrontato con il valore dell'elemento preso in esame:
- se corrisponde la ricerca termina indicando che l'elemento è stato trovato
- se è inferiore, la ricerca viene ripetuta sugli elementi precedenti (cioè sulla prima metà del dizionario), scartando quelli successivi
- se è superiore, la ricerca viene ripetuta sugli elementi successivi (cioè sulla seconda metà del dizionario), scartando quelli precedenti
- se tutti gli elementi sono stati scartati, la ricerca termina indicando che il valore non è stato trovato
In sostanza, se l’amica Giovanna cerca il vincente della lotteria “Mazzoni” il computer cerca “Mazzoni” iniziando tramite una “spaccatura” dell’’array in due porzioni di 128 + 128 elementi.
Se “Mazzoni” è inferiore alla prima metà, la ricerca procede ridivendo la tranche in 64 + 64 elementi, diversamente la ricerca procede a destra tra i 129° e il 256° elemento.
La ricerca dicotomica è sempre molto più veloce di quella sequenziale in cui si parte dall’inizio (lettera A) e si procede fino al termine (lettera Z).
L’algoritmo dicotomico in linguaggio C potrebbe essere il seguente:
/*funzione di ricerca su un array di interi*/
int ricerca_binaria(int array[], int x, int start, int end) /*x è il valore da cercare!*/
{
int m;
while(end >= start)
{
m= (start + end)/2;
if(x == array[m]) return m;
(x < array[m])? end=(m-1) : start= (m+1);
ricerca_binaria(array[],x,start,end)
}
return (-1);
}
…
Va bene, abbiamo capito!
Anche in biologia la variabile monocotilene / dicotilene assume un preciso significato di dicotomia, cioè di divisione in parti mutuamente esclusive.
Ancora una volta i processi naturali sono assimilabili a quelli della logica pura … oppure, al contrario, la scienza ha ‘copiato’ dalla natura i processi fondamentali dell’esistenza.
Appuntamento alla prossima trovata matematica.
Francesco Caranti