venerdì 19 giugno 2020

Capacità — 6. The quick brown fox jumps over the lazy dog

“Prendiamo un lucchetto per bicicletta, uno di quelli a combinazione”.

“Con un codice composto da tre o quattro cifre?”.

“Cominciamo con una, poi vediamo”.

“Ok, con una non è che il lucchetto sia molto sicuro”.

“Infatti. Perché non è sicuro?”.

“Perché ci sono solo dieci cifre, non ci vuole molto a provarle tutte”.

“Giusto. Quindi quanta informazione può contenere un singolo disco di un lucchetto?”.

“Ah, esistono flip-flop a dieci livelli?”.

“Temo di no”.

“Però il calcolo è come quello fatto l'altra volta, no? Quello che porta al logaritmo in base 2 di 10, direi”.

“Dici bene. Facciamo rapidamente i calcoli visti l'altra volta: quanti flip-flop ti servono per distinguere 10 casi?”.

“Tre sono troppo pochi, con tre flip-flop distinguo solo otto casi. Devo allora scendere al quarto livello per due volte, in questo modo:”.

“Esatto. Se immaginiamo di indovinare un lucchetto con due cifre, dovrai poi riuscire a distinguere 100 casi”.

“Giusto”.

“Il calcolo mi dice che in 6 casi servono 3 flip-flop, o monete, in 4 casi ne servono 4, il tutto per distinguere 10 possibilità. Quindi (6×3 + 4×4)/10 = 3.4. Che non è proprio uguale al logaritmo in base 2 di 10, ma ci assomiglia”.

“Esatto. La più grande potenza di 2 minore di 100 è 64, cioè 2 elevato alla 6. Quindi dovrò costruire un albero con 6 livelli, in cui però 36 di essi scendono al settimo livello. Quindi avrò (64 − 36) = 28 casi a livello 6 e 72 casi a livello 7. Il calcolo sarà quindi (28×6 + 72×7)/(200) = 672/200 = 3.36, che assomiglia ancora di più al logaritmo in base 2 di 10”.

“Ottimo, direi che questo calcolo sia sufficiente, mi pare che il procedimento sia chiaro. Vorrei farti notare una cosa: un ipotetico lucchetto con un solo disco ha una capacità di circa 3.32 bit. Un altro ipotetico lucchetto con due dischi, invece, che capacità avrà?”.

“Beh, avrà capacità doppia, no?”.

“Sì, e questo ci fa capire ancora di più l'utilità dei logaritmi”.

“Perché?”.

“Perché il numero degli stati di un lucchetto a due cifre non è il doppio del numero di stati di un lucchetto a una cifra”.

“Ah, giusto. Un lucchetto a due cifre ha 100 stati diversi, mentre quello a una cifra solo 10”.

“E un lucchetto reale a tre cifre ne avrà 1000”.

“Quindi il numero di dischi usati in un lucchetto è un esponente”.

“Un esponente di 10, certo. Ma un lucchetto a una cifra può contenere, appunto, una sola cifra, mentre un lucchetto a due cifre ne contiene il doppio, uno a tre cifre il triplo, e così via. Ecco perché ci piace molto il logaritmo: associa l'incremento in progressione geometrica del numero di stati all'incremento in progressione aritmetica della capacità”.

“Comincio a capire, bello”.

“Ottimo. Concludiamo con la telescrivente, allora”.

“Uh, un apparecchio modernissimo”.

“E vedrai l'esempio successivo”.

“Santo cielo. Credo di non sapere nemmeno cosa sia esattamente una telescrivente”.

“Sono dispositivi che sono nati per poter permettere anche a persone che non conoscevano il codice Morse di inviare messaggi”.

“Ah, certo, il codice Morse, come vivere senza?”.

“Beh, la tecnologia si è sviluppata pian piano, non siamo partiti subito da reti geografiche connesse in fibra ottica, no?”.

“Vero anche questo”.

“Dunque, dopo alcuni prototipi, il primo modello di telescrivente che ha avuto una notevole diffusione fu inventato da Émile Baudot”.

“Uh, il nome mi dice qualcosa”.

“Sì, nel 1926 in suo onore venne creata una unità di misura, il baud, che misura la velocità di trasmissione dei simboli usati in una linea di comunicazione”.

“Ah, ecco”.

“Lui usava un dispositivo composto da cinque tasti, simili a quelli di un un pianoforte. Ne potevi premere uno solo, oppure due, e così via, in tutti i modi possibili”.

“Anche tutti e cinque?”.

“Sì”.

“Beh, il calcolo qua mi sembra molto facile, i tasti sono come le monete, o i flip-flop: o sono premuti, o non lo sono”.

“È così”.

“Quindi ci sono 25 simboli, cioè 32”.

“Giusto. C'era spazio per tutte le lettere dell'alfabeto”.

“Ma non per i numeri”.

“Ancora giusto, infatti una di queste combinazioni serviva da shift, per passare dalla codifica per le lettere alla codifica per i numeri, e una seconda combinazione serviva per tornare indietro, dai numeri alle lettere”.

“Che roba. Però mi pare che il calcolo della capacità sia facile: il logaritmo in base 2 qua si calcola esattamente, è proprio 5”.

“E infatti possiamo dire che ci siano cinque monete, o cinque flip-flop: i cinque tasti che possono essere premuti”.

“Perfetto. Come dicevo, la telescrivente serviva per velocizzare e facilitare le trasmissioni in codice Morse. Vediamo un po' di studiare anche questo codice, allora”.

“Questo proprio non lo conosco: so solo che ci sono punti e linee, quindi direi che sia un codice binario, come le monete”.

“Qui ti sbagli di grosso, purtroppo. In realtà punto e linea non sono due simboli diversi, e in ogni caso i simboli sono almeno tre: punto, linea e silenzio”.

“Ah, già. Ma in che senso punto e linea non sono simboli diversi?”.

“Nel senso che, ai tempi, non esisteva la possibilità di trasmettere tre simboli diversi: il circuito del telegrafo è molto semplice, perché o è aperto o è chiuso. Se pensi alla trasmissione in codice Morse, cosa ti viene in mente?”.

“Beh, nel Manuale delle Giovani Marmotte che possiedo c'è spiegato come fare una stazione Morse con un po' di rame e una lampadina”.

“Molto bene: vedi che la lampadina può essere solo accesa o spenta. Come si distingue tra punto e linea, quindi?”.

“Con la durata dell'accensione della lampadina”.

“Esatto. Quindi qua abbiamo una variabile in più, che è la durata. Tieni presente che anche i silenzi sono importanti: nel codice Morse esistono uno spazio tra i simboli, uno spazio tra le lettere e uno spazio tra le parole”.

“Oh, e sono diversi?”.

“Già”.

“Ma anche la lunghezza delle lettere è variabile, no? Ricordo che ci sono alcune lettere, forse quelle usate più frequentemente, che sono fatte di pochi simboli, mentre altre lettere sono composte da molti simboli, magari molte linee. Mi pare che la lettera più frequente, la E, sia composta da un solo punto, vero?”.

“Vero. E quindi capisci che il calcolo della capacità di una linea in cui si usa il codice Morse sia un po' complicato”.

“Eh”.

lunedì 1 giugno 2020

Capacità — 5. Flip-flap-flop

“Stavo pensando alla faccenda dell'informazione contenuta in una moneta”.

“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 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:”.

“Ok. Questo albero cosa mi dice?”.

“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 , cioè vai diritto. Se ti dice 01, ti dice prima un no e poi un , 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?”.

“Ottimo. Ora puoi fare i conti: qual è il numero medio di domande che devi fare?”.

“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 3= 81 casi possibili. La potenza di 2 più vicina è 2= 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 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”.