“E?”.
“E ho capito come funziona con le monete, ma per l'altro esempio che hai fatto, quello del navigatore che mi può dare tre direzioni, come funziona?”.
“Quello che può dire sinistra, diritto, destra? Che problema c'è?”.
“Eh, quanta informazione ho se mi dice diritto? Non è una moneta. Devo cambiare unità di misura? Una moneta a tre facce?”.
“Un flip-flap-flop”.
“COSA?”.
“L'analogo della moneta, quando si parla di computer, è il flip-flop. Un flip-flop è un circuito in grado di immagazzinare un unico dato, che può essere uno 0 oppure un 1. Alla base di tutti i nostri computer ci sono i flip-flop”.
“Ok, questo lo sapevo: alla base dei nostri computer c'è la numerazione binaria, fatta di 0 e 1. Ma un flip-flap-flop?”.
“Sarebbe un flip-flop a tre stati. Possiamo chiamarli 0, 1 e 2, oppure -1, 0, 1, oppure anche sinistra, diritto, destra. Secondo Knuth prima o poi i computer adotteranno circuiti a tre livelli. Per ora ci limitiamo ai circuiti con due livelli, ma chissà se in futuro le cose cambieranno. Certamente un circuito a tre livelli può contenere più informazione di uno a due”.
“Ecco, non capisco questa cosa: possiamo misurare il flip-flap-flop con una moneta? Come faccio a convertire i tre livelli in solo due?”.
“Domanda profonda, che ha bisogno di una risposta lunga”.
“Ah”.
“Potremmo cambiare unità di misura, usare il flip-flap-flop, e dire che il navigatore ha informazione 1 flip-flap-flop, ma se dobbiamo cambiare unità di misura ogni volta sarebbe un delirio”.
“Eh, sì. Però, dicevi l'altra volta, la funzione matematica che fa il calcolo è il logaritmo, quindi forse potremmo usare quello e buonanotte. Cioè, posso dire che il flip-flap-flop ha informazione pari al logaritmo in base 2 di 3? Si riesce a simulare un dispositivo a tre livelli con una moneta? E poi, boh, il logaritmo in base 2 di 3 è circa 1.585. Che senso ha prendere 1.585 monete?”.
“Partiamo dall'inizio: usare una moneta per avere informazioni, di qualunque tipo, significa fare delle domande alle quali si può rispondere solo sì o no. Per capire come funziona, immagina che io sia il navigatore, e tu puoi farmi delle domande per capire in che direzione andare. Attenzione, però, perché io posso rispondere solo sì oppure no. Prova”.
“Ehm. Ok. Devo andare dritto?”.
“No”.
“Devo andare a destra?”.
“No”.
“Devo… ehi, no, non devo fare altre domande, so già che devo andare a sinistra”.
“Benissimo”.
“Però ho impiegato due domande, non 1.585”.
“Esatto. Ora immagina di arrivare a un altro incrocio: riprova”.
“Va bene. Devo andare dritto?”.
“Sì”.
“Oh, già finito. Questa volta una sola domanda. Ma non potrò mai fare una domanda e mezzo”.
“Non potrai mai, vero. Però potrai chiederti: in media, quante domande devi fare?”.
“Ah. Ho visto che a volte mi basta una domanda, a volte me ne bastano due, certamente non devo mai farne tre o più, però come faccio a fare i conti?”.
“Facciamoci aiutare da uno schemino:”.
“In un caso ti serve una domanda, in due casi te ne servono due. Il numero di domande medio da fare è uguale a (1 + 2 + 2)/3, cioè 5/3”.
“Cioè uno virgola sei periodico. Ma cosa? Qual è l'unità di misura? La moneta?”.
“Esatto, la moneta, o il bit. In media ti servono circa 1.667 domande per sapere quale direzione devi prendere. Il navigatore potrebbe risponderti anche in codice: se ti dice 1, significa sì, cioè vai diritto. Se ti dice 01, ti dice prima un no e poi un sì, cioè vai a sinistra. Se ti dice 00, vai a destra”.
“Però il logaritmo in base 2 di 3 non è uguale a 1 virgola 6 periodico, quindi cosa c'è di sbagliato? Questo calcolo o quello?”.
“Nessuno dei due, bisogna solo capire bene di cosa stiamo parlando. Supponi di non dover fare un viaggio corto, e di aver bisogno di interpellare il navigatore due volte. Potresti farlo in due momenti diversi, ma potresti anche farlo nello stesso momento, facendoti dire dal navigatore quale strada prendere al primo incrocio e al secondo”.
“Oh, in questo caso ho più messaggi”.
“Prova a elencarli”.
“Va bene, però uso le iniziali. Ah, no, accidenti, Diritto e Destra hanno la stessa iniziale”.
“Fai come nel flip-flap-flop: usa tre numeri”.
“Giusto. Allora userò 1, 2 e 3, perché usare 0, 1 e 2 mi sembra troppo matematico. Ecco i messaggi: 11, 12, 13, 21, 22, 23, 31, 32, 33. Sono 9: mi sembra corretto”.
“Lo è: 3 possibilità al primo incrocio, altre 3 al secondo, totale 3×3 = 9. Come costruiresti un albero binario di lunghezza minima per poter esplorare tutti i casi”.
“Se fossero 8 sarebbe perfetto, si farebbe un albero a tre livelli, e sarebbe tutto molto bello e ordinato. Però, con 9 casi, devo scendere di un altro livello”.
“Scegli di farlo con il minor numero di casi possibile”.
“Potrei sfruttare una sola delle ultime foglie per scendere di un livello: tolgo un caso e ne aggiungo due, arrivo a nove. Può andare?”.
“Ci sono 7 casi in cui ne bastano 3, e 2 in cui invece ne servono 4. Totale: 7×3 + 2×4 = 29, da dividere per 9 casi”.
“Eh, no, se dividi per 9 ottieni il numero medio di domande per avere due indicazioni dal navigatore. Se vuoi sapere quante domande ti servono per ogni indicazione, devi dividere per 18”.
“Giusto, questo mi era sfuggito. Allora, 29/18 fa circa 1.611”.
“Un valore un po' più basso di quello precedente, e un po' più vicino al logaritmo in base 2 di 3”.
“Ah! Allora il logaritmo mi dice il valore medio a cui mi avvicino aumentando il numero di domande”.
“Il valore medio minimo alla lunga”.
“Vabbé”.
“Vuoi provare a fare anche il caso in cui il navigatore ti dà la strada per i prossimi tre incroci?”.
“Oh, proviamo. Con tre incroci mi servono 27 risposte possibili, che non è una potenza di 2”.
“Purtroppo nessuna potenza di 2 è anche una potenza di 3”.
“Già. Se per costruire l'albero uso 4 livelli, arrivo a 16 risposte: poche”.
“Qualcuna di queste 16 foglie andrà sdoppiata”.
“Sì, mi chiedo quante”.
“Pensa che ogni volta che una foglia si sdoppia, togli un nodo terminale e ne aggiungi due”.
“E quindi, se da 16 devo arrivare a 27, la differenza è 11”.
“Quindi 11 foglie si sdoppiano”.
“Provo”.
“Ottimo. Prova a fare i conti”.
“Vado: 5 casi a cui si arriva con 4 domande, e 22 a cui si arriva con 5, totale 5×4 + 22×5 = 130, da dividere per 3×27… risulta 130/81, cioè circa 1.605 monete per ogni incrocio”.
“Giusto. Ora vuoi provare a fare i conti con 4 incroci, anche senza disegnare l'albero?”.
“Ok, provo. Con 4 incroci ci sono 34 = 81 casi possibili. La potenza di 2 più vicina è 26 = 64: troppo bassa, mancano 81−64 = 17 casi. Quindi avrò 17×2 = 34 nodi a livello 7, e 64−17 = 47 nodi a livello 6. Il calcolo allora diventa 47×6 + 34×7 = 520, che va diviso per 81×4. Mi viene 520/324 che è circa uguale a 1.605. Mi pare di aver capito: faccio anche i conti con 4 incroci, giusto per fare un ultimo calcolo?”.
“Vai”.
“Con 5 incroci ci sono 35=243 casi possibili. La potenza di 2 più vicina è 27=128: troppo basso. Mancano 243−128=115 casi. Quindi avrò 115×2=230 nodi a livello 8, e 128−115=13 nodi a livello 7. Il calcolo allora diventa 13×7+230×8 che fa 1931, che deve essere diviso per 243×5. Quindi finalmente arrivo alla frazione 1931/1215 che è circa uguale a 1.5893. Ci stiamo avvicinando”.
“Tutto perfetto. Se vuoi ti riassumo quello che stiamo facendo”.
“Grazie”.
“Facciamo un'analisi sul numero medio di domande da porre al navigatore per poter affrontare N incroci. Abbiamo quindi 3N possibili risposte”.
“Bene”.
“Le domande sono binarie, sono del tipo sì o no, e quindi cominciamo a studiare la potenza di 2 più vicina a 3N. Stiamo cercando, quindi, il valore di m per cui 2m < 3N < 2m+1”.
“Gulp, va bene”.
“Perciò abbiamo che 2m/N < 3 < 2(m+1)/N”.
“Sempre peggio”.
“Ultimo passaggio: m/N < log2(3) < (m+1)/N”.
“Santo cielo. Comunque, sì, almeno capisco che le frazioni che stavamo calcolando sono approssimazioni del logaritmo in base 2 di 3”.
“Proprio così. Un'ultima cosa: se indichiamo con d(N) il numero medio di domande, sappiamo che esso deve risultare un numero compreso tra m e m+1”.
“Giusto: deve essere più grande di m perché la potenza di 2 che ha esponente m è minore di esso, mentre la potenza con esponente aumentato di 1 è già troppo grande”.
“Ok. Allora se m < d(N) < m+1, dividendo tutto per N otteniamo che m/N < d(N)/N < (m+1)/N”.
“Ah, la stessa disuguaglianza di prima! Allora significa che d(N)/N si avvicina sempre di più a log2(3)”.
“Ed ecco il significato di quel logaritmo: se aumentiamo la lunghezza delle domande, il numero di monete, o di bit, che ci servono per ottenere le risposte dal navigatore si avvicina sempre di più al logaritmo in base 2 di 3. Dire che la quantità di informazione che ci fornisce il flip-flap-flop è il logaritmo in base 2 di 3 significa dire che il numero medio minimo di domande binarie che dobbiamo fargli, alla lunga, è il logaritmo in base 2 di 3”.
“Questa è stata difficile”.
“La prossima volta studiamo il lucchetto a combinazione da bicicletta”.
“Oh, proviamo. Con tre incroci mi servono 27 risposte possibili, che non è una potenza di 2”.
“Purtroppo nessuna potenza di 2 è anche una potenza di 3”.
“Già. Se per costruire l'albero uso 4 livelli, arrivo a 16 risposte: poche”.
“Qualcuna di queste 16 foglie andrà sdoppiata”.
“Sì, mi chiedo quante”.
“Pensa che ogni volta che una foglia si sdoppia, togli un nodo terminale e ne aggiungi due”.
“E quindi, se da 16 devo arrivare a 27, la differenza è 11”.
“Quindi 11 foglie si sdoppiano”.
“Provo”.
“Ottimo. Prova a fare i conti”.
“Vado: 5 casi a cui si arriva con 4 domande, e 22 a cui si arriva con 5, totale 5×4 + 22×5 = 130, da dividere per 3×27… risulta 130/81, cioè circa 1.605 monete per ogni incrocio”.
“Giusto. Ora vuoi provare a fare i conti con 4 incroci, anche senza disegnare l'albero?”.
“Ok, provo. Con 4 incroci ci sono 34 = 81 casi possibili. La potenza di 2 più vicina è 26 = 64: troppo bassa, mancano 81−64 = 17 casi. Quindi avrò 17×2 = 34 nodi a livello 7, e 64−17 = 47 nodi a livello 6. Il calcolo allora diventa 47×6 + 34×7 = 520, che va diviso per 81×4. Mi viene 520/324 che è circa uguale a 1.605. Mi pare di aver capito: faccio anche i conti con 4 incroci, giusto per fare un ultimo calcolo?”.
“Vai”.
“Con 5 incroci ci sono 35=243 casi possibili. La potenza di 2 più vicina è 27=128: troppo basso. Mancano 243−128=115 casi. Quindi avrò 115×2=230 nodi a livello 8, e 128−115=13 nodi a livello 7. Il calcolo allora diventa 13×7+230×8 che fa 1931, che deve essere diviso per 243×5. Quindi finalmente arrivo alla frazione 1931/1215 che è circa uguale a 1.5893. Ci stiamo avvicinando”.
“Tutto perfetto. Se vuoi ti riassumo quello che stiamo facendo”.
“Grazie”.
“Facciamo un'analisi sul numero medio di domande da porre al navigatore per poter affrontare N incroci. Abbiamo quindi 3N possibili risposte”.
“Bene”.
“Le domande sono binarie, sono del tipo sì o no, e quindi cominciamo a studiare la potenza di 2 più vicina a 3N. Stiamo cercando, quindi, il valore di m per cui 2m < 3N < 2m+1”.
“Gulp, va bene”.
“Perciò abbiamo che 2m/N < 3 < 2(m+1)/N”.
“Sempre peggio”.
“Ultimo passaggio: m/N < log2(3) < (m+1)/N”.
“Santo cielo. Comunque, sì, almeno capisco che le frazioni che stavamo calcolando sono approssimazioni del logaritmo in base 2 di 3”.
“Proprio così. Un'ultima cosa: se indichiamo con d(N) il numero medio di domande, sappiamo che esso deve risultare un numero compreso tra m e m+1”.
“Giusto: deve essere più grande di m perché la potenza di 2 che ha esponente m è minore di esso, mentre la potenza con esponente aumentato di 1 è già troppo grande”.
“Ok. Allora se m < d(N) < m+1, dividendo tutto per N otteniamo che m/N < d(N)/N < (m+1)/N”.
“Ah, la stessa disuguaglianza di prima! Allora significa che d(N)/N si avvicina sempre di più a log2(3)”.
“Ed ecco il significato di quel logaritmo: se aumentiamo la lunghezza delle domande, il numero di monete, o di bit, che ci servono per ottenere le risposte dal navigatore si avvicina sempre di più al logaritmo in base 2 di 3. Dire che la quantità di informazione che ci fornisce il flip-flap-flop è il logaritmo in base 2 di 3 significa dire che il numero medio minimo di domande binarie che dobbiamo fargli, alla lunga, è il logaritmo in base 2 di 3”.
“Questa è stata difficile”.
“La prossima volta studiamo il lucchetto a combinazione da bicicletta”.
Nessun commento:
Posta un commento