lunedì 17 agosto 2020

Capacità — 7. Il codice Morse

L'altra volta ho fatto un piccolo errore: avevo citato il Manuale delle Giovani Marmotte, ma in realtà volevo parlare del Manuale di Archimede. Guarda:”.



“Che meraviglia! Stavo proprio guardando il codice Morse: è un delirio”.

“Beh, è un codice reale che è nato quando c'erano certe esigenze e certe disponibilità tecniche, c'è poco da fare”.

“Almeno ho capito che non è un codice binario”.

“No, anche se in effetti usa solo due segnali: luce accesa e luce spenta, oppure corrente che passa e corrente che non passa, oppure beep e silenzio”.

“Vero, ma c'entra anche la durata di questi segnali”.

“Sì. Facciamo un riassunto di tutto quello che può succedere nel codice Morse. Possiamo distinguere quattro tipo di segnale: il punto, la linea, lo spazio tra le lettere e lo spazio tra le parole”.

“I due spazi si distinguono per la durata, vero?”.

“Sì. Prima di definire i segnali, definiamo ciò che sta alla base di tutto: l'unità di tempo. I segnali Morse sono scanditi dal passare del tempo, come se ci fosse un metronomo. La velocità di trasmissione non è predefinita: due bravi operatori possono trasmettere segnali con una velocità molto alta, due operatori che invece stanno imparando il codice andranno certamente più lenti”.

“Ok”.

“Ora, definiamo i segnali:”. 
  • Punto (P): linea chiusa per un'unità di tempo, seguita da linea aperta per un'altra unità di tempo 
  • Linea (L): linea chiusa per tre unità di tempo, seguita da linea aperta per un'unità di tempo
  • Spazio tra le lettere (S): linea aperta per tre unità di tempo
  • Spazio tra le parole (V): linea aperta per sei unità di tempo

“Uhm, qualcosa non mi torna, io ho letto cose diverse su Wikipedia”.

“Cosa?”.

“Beh, che il punto corrisponde semplicemente alla linea chiusa per un'unità di tempo, non seguita da nulla, così come la linea, mentre lo spazio tra le lettere corrisponde alla linea aperta per quattro unità di tempo, e quello tra le parole alla linea aperta per sette unità”.

“Uhm. Ai fini dei calcoli che faremo dopo, è più comodo pensare che dopo un punto o una linea ci sia sempre uno spazio vuoto della durata di un'unità di tempo, e questo corrisponde anche al fatto che io ti ho detto che lo spazio tra le parole corrisponde a uno spazio vuoto che dura sei e non sette unità: dopo un qualunque simbolo c'è una unità vuota obbligatoria che si somma alle altre sei. Questo è un sistema che usano gli informatici per decodificare in automatico una stringa di bit: si chiama codice prefix-free o comma-free. Però, però, mmh”.

“Non torna quello che dici riguardo lo spazio tra le lettere”.

“Esattamente. Secondo Shannon, che si è fatto tutto il calcolo che vorrei raccontarti, lo spazio tra le lettere sarebbe di 1+3 unità di tempo, cioè 4, mentre secondo lo standard attuale lo spazio è solo di 3 unità”.

“Mi stai dicendo che Shannon ha fatto un errore?”.

“Mah, non oso arrivare a tanto, eppure c'è una incongruenza. Secondo me l'ha fatto per poter fare un esempio, con i calcoli che fa in seguito, più completo. Nel suo articolo scrive: Thus in telegraphy suppose the symbols are: (1) A dot, consisting of line closure for a unit of time and then line open for a unit of time; (2) A dash, consisting of three time units of closure and one unit open; (3) A letter space consisting of, say, three units of line open; (4) A word space of six units of line open.”.

“Ah. Quando definisce il letter space, dice say”.

“Sì, probabilmente adatta l'esempio in modo da avere tante lunghezze diverse: il punto dura 2 unità, la linea 4, lo spazio tra le lettere 3 e quello tra le parole 6. Così facendo ha lunghezze pari a 2, 3, 4 e 6, tutte diverse. Se avesse scelto lo spazio tra le lettere lungo 2 unità, avrebbe avuto lunghezze pari a 2, 2, 4 e 6. Quelle due lunghezze uguali danno un po' fastidio.”.

“Va bene, allora prendiamo per buone le lunghezze date da Shannon. Ora che succede?”.

“Ora dobbiamo conoscere le regole di composizione. Per esempio: dopo un punto o una linea ci può essere un altro punto, un'altra linea, oppure uno dei due spazi”.

“E fin qua mi sembra facile”.

“Ma dopo uno spazio non può esserci un'altro spazio, ma solo un punto o una linea, e non si può nemmeno iniziare una trasmissione con uno spazio”.

“Ah, comincia a essere meno facile”.

“Questa figurina riassume tutte le regole di composizione:”.
 


“Vedo. Fissando la partenza, impedisci che si possa iniziare con uno dei due tipi di spazio. Interessante, anche se non avrei idea di come proseguire nello studio”.

“Lo studio è molto complicato, sì. Partiamo dal caso più semplice di tutti: può esistere una trasmissione Morse di lunghezza 1?”.

“Cosa vuol dire? Un punto?”.

“Un punto, l'abbiamo definito poco fa, è un simbolo di lunghezza 2, perché è composto da due segnali: linea chiusa per un'unità di tempo, linea aperta per un'altra unità di tempo”.

“Allora non esistono trasmissioni di lunghezza 1, no?”.

“Esatto. Se indichiamo con N(t) le trasmissioni di lunghezza t, abbiamo che N(1) = 0”.

“Bene, questa era facile. Non mi dire che ora andiamo avanti con le trasmissioni di lunghezza 2, poi 3, eccetera”.

“Esatto, faremo proprio questo. Prima, però, di complicarci la vita, facciamo un riassunto di tutti i possibili finali di trasmissione”.

“Immagino che ci siano delle regole per terminare una trasmissione Morse”.

“Sì, ma non intendevo questo. Lasciamo perdere le convenzioni utilizzate nelle trasmissioni, e rimaniamo aderenti solo allo schema che abbiamo visto. In pratica, studiamo solo quel grafo”.

“Va bene. Hai domandato quali possono essere i possibili finali: immagino di dover muovermi lungo quell'albero e vedere come si può finire”.

“Sì. Un possibile finale l'abbiamo visto, il più semplice di tutti: percorri solo un arco di quel grafo, quello che corrisponde a un punto. In quel caso, il finale è semplicemente P”.

“Ok. Allora un altro finale potrà essere L”.

“Giusto, invece di un punto trasmetti una linea, e basta”.

“Ora però le cose si complicano. Dopo aver percorso l'arco P o l'arco L, ho varie scelte”.

“Se la tua prima scelta è stata P e la seconda è stata di nuovo P, la tua trasmissione è PP, che però finisce con P”.

“Ma perché guardiamo i finali?”.

“Per ora guardiamo i finali, che sono i casi più semplici. Le trasmissioni più complicate si faranno aggiungendo finali a trasmissioni più brevi”.

“Ah. Allora, vediamo questi finali. Oltre a P e a L potrei avere PS?”.

“Esatto: un punto seguito da uno spazio tra le lettere”.

“E non potrei avere un solo spazio come finale?”.

“Eh, no. Ammettere S come finale significa che, nel caso di trasmissione più semplice possibile, tu possa trasmettere un singolo spazio, ma questo non è possibile. S è necessariamente preceduto da qualcosa, come mostra il grafico”.

“Allora di finali con lo spazio tra le lettere ce ne sono due: PS e LS”.

“Proprio così. E poi ci saranno anche i finali con la V, lo spazio tra le parole”.

“Che saranno PV e LV”.

“Giusto. Facciamo quindi un riassunto dei possibili finali:”.

  • P: lunghezza 2
  • L: lunghezza 4
  • PS: lunghezza 5
  • LS: lunghezza 7
  • PV: lunghezza 8
  • LV: lunghezza 10

“Mamma mia, e questi sono solo i finali”.

“Eh. Alleniamoci un po' sulle cose semplici: abbiamo già visto che N(1) = 0: non ci sono trasmissioni di lunghezza 1”.

“E immagino che N(2) sia uguale a 1, perché c'è una sola trasmissione di lunghezza 1, il nostro P”.

“Giusto. Quanto vale invece N(3)?”.

“Non ci sono finali di lunghezza 3”.

“Vero. Ed è possibile combinare due finali più brevi per farne uno di lunghezza 3?”.

“Non mi sembra, dato che non ci sono trasmissioni di lunghezza 1, non posso combinarne P, che è lungo 2, con un qualcosa lungo 1 che non esiste”.

“Ok. Quindi N(3) = 0”.

“Sì. Provo ad andare avanti con le trasmissioni di lunghezza 4. C'è L, la linea, che è lunga 4”.

“Ma non è l'unica trasmissione di lunghezza 4: potresti anche trasmettere PP”.

“Oh, vero, anche quella è lunga 4, cioè 2 + 2. Quindi N(4) = 2”.

“Volendo complicarci la vita, per capire le difficoltà che incontreremo andando avanti, potrei dirti che N(4) = N(2) + 1”.

“Uh. Capisco che sia vero, ma non capisco il senso”.

“Quella formula ci sta dicendo che per ottenere una trasmissione di lunghezza 4 si prendono tutte quelle di lunghezza 2 (che si possono far diventare di lunghezza 4 mettendo un P davanti) e, in più, se ne aggiunge una nuova, che è poi L”.

“Una definizione ricorsiva?”.

“Esattamente. Se ci fossero 42 trasmissioni di lunghezza 2, ne potresti ottenere altre 42 di lunghezza 4 facendole tutte precedere da un P. Poi si aggiunge una nuova trasmissione di lunghezza 4, cioè L”.

“Credo di capire. Ora provo a calcolare N(5), vediamo cosa combino”.

“Vai”.

“Allora, le trasmissioni di lunghezza 5 si possono ottenere da quelle di lunghezza 3 aggiungendo una P davanti (ma di trasmissioni di lunghezza 3 non ce ne sono), oppure da quelle di lunghezza 1 aggiungendo una L davanti (ma anche di queste non ce ne sono), e poi ce n'è una nuova, che è PS”.

“Ottimo! La formula è quindi: N(5) = N(3) + N(1) + 1”.

“Che dà come risultato un semplice 1, però”.

“Non importa: hai capito il procedimento, andando avanti non aggiungerai sempre degli zeri”.

“Ma quando mi fermo?”.

“Ti fermi quando capisci la regola generale”.

“E la regola generale quando la capisco?”.

“Quando smetti di aggiungere roba nuova”.

“Aha! Allora provo ad andare avanti”.

“Prima permettimi di complicarti ancora un po' la vita”.

“Argh”.

“Ti riscrivo la formula per N(5) in questo modo: N(5) = N(5−2) + N(5−4) + 1”.

“Ah, credo di capire: hai scritto N(5−2) invece di N(3) perché ciò che conta è quel 2: aggiungi un simbolo di lunghezza 2 davanti”.

“Perfetto. Ora prova a calcolare N(6)”.

“Ok, vado. Una trasmissione di lunghezza 6 si ottiene aggiungendo a una trasmissione più breve una P, che è lunga 2, oppure una L, che è lunga 4, oppure una PS, che è lunga 5. E non ci sono finali di lunghezza 6, quindi la formula è questa: N(6) = N(6−2) + N(6−4) + N(6−5)”.

“Ottimo: fai i conti”.

“Ecco: N(6) = N(4) + N(2) + N(1) = 2 + 1 + 0 = 3”.

“Ed ecco qua l'elenco delle trasmissioni di lunghezza 6: PPP, PL, LP”.

“E, dato che non ho aggiunto nuovi finali, ho finito, vero?”.

“Eh, no. Non hai aggiunto nuovi finali non perché non ce ne siano più, ma perché i finali che rimangono sono lunghi più di 6”.

“Ah, vero. Che peccato. Beh, allora proverò ad andare avanti, però non adesso”.

“La prossima volta”.

“Ok”.

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

sabato 2 maggio 2020

Capacità — 4. Monete

“Bene, dopo tutta questa introduzione possiamo finalmente parlare d'altro”.

“Ma come? Era un'introduzione?”.

“Sì, giusto per scaldarci un po'”.

“Ah. E di cosa parliamo?”.

“Di informazione”.

“Singolare?”.

“Sì, del concetto di informazione, di come si fa a misurarla”.

“Non sapevo che si misurasse. Ma cosa significa, poi, misurarla?”.

“L'idea è questa: abbiamo un dispositivo che immagazzina dati, oppure che può trasmetterli da una sorgente a una destinazione”.

“E fin qua è chiaro”.

“Chiamiamo messaggi i dati che vengono immagazzinati o trasmessi, così ci leghiamo al concetto di informazione. Che strada devo prendere al prossimo incrocio? Qual è il primo verso della Divina Commedia?”.

“Le risposte a queste domande sono i messaggi?”.

“Esatto. Mettiamoci poi nel caso in cui il numero di messaggi che un sistema può inviare (o conservare) sia un numero finito. La strada che devo prendere al prossimo incrocio è destra, sinistra, oppure dritto. Il primo verso della Divina Commedia è un messaggio composto da 35 lettere dell'alfabeto, che sono in numero finito, e così via”.

“Va bene”.

“Ora la domanda è: che numero possiamo prendere per misurare l'informazione prodotta quando viene scelto uno dei messaggi disponibili? Il messaggio vai diritto quanta informazione porta con sé? E il messaggio Nel mezzo del cammin di nostra vita?”.

“Non saprei proprio come risponderti”.

“Partiamo dal caso più semplice possibile: prendiamo come contenitore di messaggi, o come canale che trasmette i messaggi, una moneta”.

“Eh? Come una moneta?”.

“Una moneta parla: dice testa o croce. Permette di salvare, o trasmettere, due messaggi diversi. Come misuriamo la quantità di informazione che si produce quando selezioniamo testa o croce?”.

“Non so. Ancora non capisco di cosa stiamo parlando: come fa una moneta a essere il caso più semplice di tutti? Una moneta porta due messaggi: non si può pensare a un caso ancora più semplice in cui il messaggio è uno solo?”.

“Ma se il messaggio è uno solo, ti serve conoscerlo?”.

“Uh?”.

“L'idea che si vuole tradurre in linguaggio matematico è questa: tu non sai una cosa, poi ricevi un messaggio e la conosci. Quanto vale quel messaggio? Quanto pesa? Quanta informazione ti porta? Se sai già che il messaggio è uno solo…”.

“Non mi porta nessuna informazione! Perché io non conosca il messaggio, ce ne devono essere almeno due! Ecco perché la moneta è il caso più semplice”.

“Esatto. E nota che nel caso della moneta, la parola testa può anche essere abbreviata con una singola lettera, T, mentre se parli dei versi della Divina Commedia sapere che a un certo punto c'è una T invece di una C è una informazione più forte”.

“Vero: la parola Torre è diversa da Corre”.

“Non solo: in questo caso non hai solo due possibilità, cioè T o C, ma puoi anche avere altre lettere, e generare parole ancora diverse, come per esempio Porre. Inoltre, qui il messaggio T è diverso dal messaggio Testa, mentre nella moneta sono uguali”.

“Va bene, sto capendo qualcosa, ma ancora non saprei come misurare questa quantità di informazione, anche se ho capito che dipende dal contesto. Potremmo forse dire che la quantità di informazione dipende dai possibili messaggi?”.

“Sì, potremmo farlo. Potremmo dire che l'informazione T o C relativa al lancio della moneta vale 2, perché i casi sono solo due. Se invece stiamo parlando di lettere dell'alfabeto, la scelta di T o C vale di più”.

“Ci sono 26 possibilità, ammesso che Dante abbia usato anche le lettere straniere”.

“Nella Divina Commedia ci sono due J, un sacco di X che sono state usate per numerare i canti (ma non solo), e una Y. Non ho trovato delle W e delle K”.

“Quindi servono almeno 24 caratteri”.

“Senza contare tutti i segni di interpunzione e lo spazio, e senza fare differenza tra lettere maiuscole e lettere minuscole”.

“Oh già. Potremmo allora dire che l'informazione delle lettere dell'alfabeto usate per la Divina Commedia vale 24, senza contare tutto il resto?”.

“Potremmo, se la Divina Commedia fosse composta da un solo carattere”.

“Oh, già. Ma… allora l'informazione contenuta nella Divina Commedia è un numero enorme!”.

“Vorrei ben vedere, soprattutto se la paragoniamo al lancio di una moneta. Dante non sarebbe felice di sapere che ha prodotto poca informazione”.

“Sì, capisco, sarebbe un po' deludente”.

“Abbiamo detto, quindi, che per calcolare la quantità di informazione potremmo contare il numero di messaggi che un sistema può inviare. Ma non faremo così”.

“E perché?”.

“Perché useremmo una scala che non ci piace”.

“Mh. Come fa a non piacerci una cosa che definiamo noi?”.

“Te lo spiego con un esempio. Se una moneta produce informazione uguale a 2, secondo te quanta informazione produce una coppia di monete?”.

“Il doppio, no?”.

“Eh, il doppio, cioè 4”.

“Certo. Cosa c'è che non va?”.

“Come lo hai calcolato 4? Facendo 2+2 oppure 2×2?”.

“Cosa cambia? Fa comunque 4”.

“Il risultato non cambia, ma l'idea sì. Quanta informazione producono 3 monete?”.

“Sarà il triplo, no?”.

“Il triplo di 2 è 6”.

“Certo”.

“E allora qualcosa non torna: il numero di messaggi che si possono trasmettere con 3 monete non è 6”.

“Oh. È vero! Con 3 monete posso trasmettere 8 messaggi: TTT, TTC, TCT, TCC, CTT, CTC, CCT, CCC”.

“E quindi 4 era uguale a 2+2 oppure a 2×2?”.

“Era uguale a 2×2. Con 3 monete devo calcolare 23, con 4 invece 24, eccetera”.

“Quindi l'informazione prodotta da 3 monete non è il triplo dell'informazione prodotta da una moneta”.

“Eh, no. Purtroppo no. Capisco perché dici che non ci piace: io vorrei un modo di misurare questa informazione che mi permetta invece di dire che l'informazione prodotta dalla somma di tot monete è tot volte l'informazione prodotta da una moneta. Ma come si fa?”.

“Si fa, si fa. Ci sono i logaritmi apposta”.

“Ah! Se uso la base 2, con la moneta è facilissimo: una moneta ha informazione 1, due monete hanno informazione 2, eccetera”.

“Sì, è la scelta più naturale”.

“E possiamo dare un nome all'unità di misura? Una moneta ha informazione 1 cosa?”.

“Io direi che, per un po', potremmo continuare a chiamare questa unità di misura moneta. Anche se tutto il mondo la chiama bit”.

domenica 5 aprile 2020

Capacità — 3. Sezione aurea

La volta scorsa abbiamo detto che una possibile soluzione alla relazione di Fibonacci potrebbe essere una funzione esponenziale”.

“Mi ricordo: abbiamo detto che la relazione di Fibonacci potrebbe essere scritta come ΔF= Fn-1; ho capito che la soluzione potrebbe essere un'esponenziale, perché il Δ si comporta bene con quel tipo di funzioni, però non saprei come trovare l'esponenziale giusta”.

“Si prova”.

“Ma come?”.

“Si prende una successione esponenziale incognita, che possiamo scrivere come an, e la si sostituisce nella relazione di Fibonacci Fn+1 FFn-1”.

“Tutto qua? Allora provo a sostituire. Mi viene an+1 aan-1”.

“Bene”.

“E adesso?”.

“Adesso la semplifichiamo un po'. Si potrebbe raccogliere an-1, che è un fattore comune”.

“Giusto. Ecco qua: an-1(a− − 1)=0”.

“Ottimo. È possibile che quell'espressione sia uguale a zero?”.

“Uhm, a potrebbe essere uguale a zero, ma forse non ci interessa”.

“Ottima osservazione: in effetti la successione 0, 0, 0, … soddisfa la relazione di Fibonacci”.

“Ma non è la successione che conosciamo! Perché?”.

“Perché tutto dipende dal punto di partenza. Se parti da 0 e 0, ogni termine della successione sarà 0”.

“Ah, se invece parto da 0 e da 1 ottengo la successione famosa. O devo partire da 1 e 1?”.

“Non importa, bisogna mettersi d'accordo. O dici che la successione di Fibonacci è 0, 1, 1, 2, 3, 5,…, o dici che è 1, 1, 2, 3, 5,…. Non c'è un modo più giusto dell'altro: dipende se quello zero iniziale ti serve oppure no”.

“Ok. Noi però abbiamo trovato 0, 0, 0,…”.

“Questo se a fosse uguale a zero, ma non c'è solo questa possibilità”.

“Già, vero. Se a fosse diverso da zero, cosa potrei fare?”.

“Per cominciare, potresti semplificare quel termine fuori dalla parentesi”.

“Giusto. Ottengo a− a − 1 = 0. Ehi, questa è un'equazione di secondo grado, la so risolvere”.

“Vai”.

“E non è un'equazione anonima, è quella che serve per calcolare la sezione aurea! Però ho due soluzioni: (1 + √5)/2 e (1 − √5)/2”.

“Esatto”.

“E qual è quella giusta?”.

“Perché pensi che ce ne sia una sbagliata?”.

“Oh. Possono andare bene tutte e due?”.

“Non solo: di soluzioni ce ne sono infinite”.

“Ma come è possibile?”.

“Beh, ci siamo già accorti del fatto che ciò che conta è l'equazione a− a − 1 = 0 e non il coefficiente che sta fuori dalla parentesi”.

“Quindi?”.

“Quindi se an è una soluzione, anche kan lo è”.

“Ah, certo! Se sostituisco kan, vedo che posso raccogliere quel fattore k, che poi posso semplificare, ammesso che sia diverso da zero”.

“Certo. E se fosse uguale a zero avremmo la soluzione tutta nulla di cui abbiamo già parlato”.

“Bene, ho capito. Ma quindi abbiamo due infinità di soluzioni?”.

“Se vogliamo esprimerci in termini un po' evocativi, sì. Possiamo dire che una soluzione generale è data da questa formula:”.

an = h[(1 + √5)/2]n + k[(1 − √5)/2]n 

 “Oh, bello. E al posto di h e k posso mettere quello che voglio?”.

“Sì, ma attenzione: per ogni valore di quelle due costanti ottieni una successione che soddisfa alla relazione di Fibonacci, però ognuna di queste successioni parte da condizioni iniziali diverse”.

“E allora come si fa?”.

“Si usano le condizioni iniziali per stabilire quali valori debbano assumere le due costanti”.

“Uhm”.

“Guarda: sappiamo che F= 0, quindi possiamo sostituire nella relazione generale, e otteniamo 0 = h + k”.

“Ok. Provo ad andare avanti: dato che F= 1, se sostituisco ottengo 1 = h[(1 + √5)/2] + k[(1 − √5)/2]”.

“Bene. Dalla prima equazione otteniamo che k = −h”.

“Se sostituisco nella seconda viene qualcosa di brutto: 1 = h[(1 + √5)/2] − h[(1 − √5)/2]. Ah, però posso raccogliere h e semplificare”.

“Sì, non è così brutto, alla fine”.

“Mi viene 1 = h√5”.

“Bene, questo significa che = 1/√5”.

“Allora la formula che ci dà la relazione di Fibonacci è questa:”.

F= (1/√5)[(1 + √5)/2]− (1/√5)[(1 − √5)/2]n

“Proprio così. Ti faccio notare che il termine (1 + √5)/2 è quello che, di solito, si chiama sezione aurea e si indica con φ, mentre il termine (1 − √5)/2 è l'opposto del suo reciproco”.

“Davvero? Dici che 2/(1 + √5) è uguale a − (1 − √5)/2?”.

“Prova: se moltiplichi numeratore e denominatore di 2/(1 + √5) per (1 − √5), cosa ottieni?”.

“Al numeratore ottengo 2(1 + √5). Al denominatore (1 + √5)(1 − √5), che fa 1 − 5, cioè − 4. Ah, poi si semplifica, risulta proprio come dici tu”.

“E quindi quella formula che abbiamo trovato può essere scritta in modo molto elegante così: F= (1/√5)φ− (1/√5)(−φ)−n. O, anche:”.

F= [φ− (−φ)−n]/√5 

sabato 7 marzo 2020

Capacità — 2. Δ

“Siamo arrivati a scrivere la formula di Fibonacci in questo modo:”.

ΔFn = Fn-1.

“Sì, ma non capisco bene perché”.

“Proviamo a studiare il funzionamento di questo Δ, così poi si capirà qualcosa di più”.

“Proviamo”.

“Quanto vale, per esempio, Δ42?”.

“Non capisco proprio la domanda”.

“La possiamo tradurre così: di quanto varia la successione an = 42, ogni volta che n aumenta di 1?”.

“Ma non varia!”.

“Esatto. Quindi Δ42 = 0”.

“Tutto qua?”.

“Tutto qua. Adesso: quanto vale Δn?”.

“Aspetta che provo a tradurre: di quanto varia la successione an= n, ogni volta che n aumenta di 1?”.

“Giusto, hai tradotto bene”.

“Mi piacerebbe di più girare la domanda in questo modo: quanto vale an+1 an?”.

“Sì, è la stessa cosa”.

“Allora il calcolo è facile: (n+1) − n fa 1. Ogni volta che n aumenta di 1, an aumenta di 1, perché è la stessa cosa.”.

“Certo, è una cosa ovvia. Se mettiamo nella prima riga di una tabella i valori di n, e nella seconda i valori che si ottengono facendo la differenza tra i termini di due caselle consecutive, otteniamo una tabella come questa:”.

1 2 3 4 5
1 1 1 1 //

“Sì, è decisamente ovvio. 2 − 1 fa 1, 3 − 2 fa 1, e così via”.

“Ottimo. Altra domanda: quanto fa Δn2?”.

“Provo a giocare un po' con la tabella:”.

0 1 4 9 16
1 3 5 7 //

“Esatto”.

“Nella riga delle differenze ci sono i numeri dispari, direi”.

“Diresti bene, ma come puoi dimostrarlo?”.

“Forse dovrei fare il calcolo algebrico”.

“Prova”.

“Vediamo: Δn= (+ 1)n2, vero?”.

“Vero. Ora svolgi i calcoli”.

“Ecco: (+ 1)n2 = n2 + 2n + 1 − n2 = 2+ 1. È corretto, 2n + 1 è sempre un numero dispari”.

“Benissimo”.

“Mi sembra anche di cogliere un legame con le derivate: se ben ricordo, anche loro fanno abbassare il grado”.

“Solo dei polinomi!”.

“Ah, io ricordo quelle, ehm”.

“Uff. Comunque, sì, l'operatore Δ fa sempre abbassare il grado di una potenza: quando calcoli Δnp ti risulta (n + 1)p np…”.

“… e quando svolgo la potenza di (n + 1) ottengo sempre, come primo termine, np, che si semplifica con il − np che si trova alla fine. Ho capito, ma allora…”.

“Cosa succede?”.

“Eh, se il grado cala sempre, come è possibile che l'equazione di Fibonacci sia vera? Come è possibile che ΔFn abbia lo stesso grado di Fn-1? L'equazione dice anzi molto di più, e cioè che ΔFn deve essere uguale a Fn-1, ma se non possono avere nemmeno lo stesso grado…”.

“Vorrà dire che Fn non è un polinomio”.

“Ah”.

“Vedi come all'improvviso si aprono nuovi mondi”.

“Eh. Ma se non è un polinomio, allora, cosa può essere?”.

“Guarda questa tabella”.

1 2 4 8 16
1 2 4 8 //

“Hai sbagliato qualcosa? Hai ricopiato la riga di sopra su quella di sot… oh”.

“Visto?”.

“Vedo! Non hai ricopiato, hai calcolato le differenze, che sono uguali alla successione di partenza”.

“Esatto. Riconosci la successione di partenza? Puoi scriverne l'espressione e verificare che tutto sia corretto?”.

“Vediamo. Mi pare che la successione di partenza sia quella delle potenze di 2, quindi a= 2n”.

“Ok”.

“Quindi Δ2n = 2n+1 − 2n. E adesso?”.

“Adesso prova a scrivere 2n+1 come 2×2n”.

“Provo: Δ2n = 2×2− 2n. Risulta proprio 2n, è corretto”.

“Quindi vedi che esiste una funzione che non cambia anche se a essa viene applicato l'operatore Δ”.

“Vedo. Vale per tutte le funzioni esponenziali?”.

“Prova con la base 3, per esempio”.

“Provo: Δ3n = 3n+1 − 3n = 3×3n − 3= 2×3n. No, non funziona”.

“Non funziona del tutto: il Δ di un'esponenziale è ancora un'esponenziale, però moltiplicata per una costante. Ma la base dell'esponenziale non cambia”.

“Giusto. Però, uhm, non mi pare di aver risolto l'equazione di Fibonacci. Cioè, se fosse ΔFn = Fn, allora potrei dire che Fn = 2n”.

“Sì, quasi. Quella è una delle possibili soluzioni, ma ce ne sono altre”.

“Ma come?”.

“Guarda, se al posto di 2n consideri c×2n i calcoli non cambiano di molto”.

“Ah, giusto, quella costante c si raccoglie e non dà fastidio: Δc×2n = c×(2n+1 − 2n) = c×2n”.

“Però hai ragione, l'equazione di Fibonacci non è ΔFn = Fn, ma ΔFn = Fn-1”.

“E quindi?”.

“E quindi la soluzione non sarà data dalla funzione esponenziale di base 2, ma magari sarà data da un'altra funzione esponenziale che soddisfa a quella proprietà”.

“Ah. E come facciamo a trovarla?”.

“Cercando”.

lunedì 3 febbraio 2020

Capacità — 1. Come conigli

“Allora, vediamo: un coniglio giovane alla prima generazione, un coniglio maturo alla seconda, e così alla terza avrò un coniglio maturo e suo figlio giovane, e alla quarta uno maturo che lo era già, uno che lo è diventato, e il figlio di quello che lo era già, quindi…”.

“Cosa fai?”.

“Sto cercando di capire il legame tra i numeri di Fibonacci e i conigli”.

“Molto bene”.

“Non è mica una cosa ovvia”.

“Non lo sono mai, fino a che non le capisci”.

“Ottimo”.

“Quindi, hai capito?”.

“Credo di sì. Mi sono fatto questo schemino, dove la c minuscola rappresenta un coniglio giovane, e la C maiuscola un coniglio maturo, che produrrà un figlio alla generazione successiva:”.

c
C
Cc
CcC
CcCCc
CcCCcCcC

“Non è chiarissimo, ma è giusto”.

“Eh, lo so che non è chiaro, ma anche i disegni a albero non sono chiarissimi”.

“Guarda, qua ce n'è uno bello”.

“Ohh, sì, bello, e bello anche l'articolo. Almeno fino a che non comincia a parlare di autovalori e autovettori”.

“Non c'è bisogno di arrivare fino a lì, anche se quella con le matrici è una trattazione molto elegante”.

“Già mi basterebbe aver capito bene la relazione di ricorrenza”.

“E quella è chiara?”.

“Mi pare di sì: data una certa generazione, i conigli adulti sono quelli che erano vivi due generazioni prima”.

“Esatto”.

“E i conigli adulti sono quelli che fanno figli, quindi i figli che nascono in ogni generazione sono tanti quanti erano tutti i conigli di due generazioni prima”.

“Giusto. A questi figli bisogna aggiungere tutti quelli che c'erano già, cioè quelli di una generazione prima”.

“Ed ecco la formula Fn = Fn−1 + Fn−2”.

“Perfetto”.

“Invece quella faccenda degli autovettori e della sezione aurea mi pare incomprensibile. Sarebbe bello capire come trovare una formula chiusa per la successione di Fibonacci senza tutta quella teoria”.

“Si può, si può”.

“E come si fa?”.

“Si comincia da questa tabella”.

1  4  9 16 25 36
3  5  7  9 11 --

“Cosa sto guardando?”.

“Dimmelo tu: cosa c'è nella prima riga?”.

“Vedo i quadrati dei numeri naturali”.

“Ottimo. E nella seconda?”.

“I numeri dispari a partire da 3”.

“Oppure?”.

“Come oppure?”.

“Eh, io non ho scritto i numeri dispari a partire da 3, ho fatto un altro calcolo. Se avessi voluto scrivere i numeri dispari a partire da 3 non avrei lasciato vuota l'ultima casella, avrei scritto 13”.

“Giusto. Allora, uhm. Ah! Ogni numero scritto nella seconda riga è la differenza tra i due numeri che gli stanno sopra nella prima riga”.

“Esatto. E così si spiega perché manca l'ultimo numero: servirebbe un altro numero a destra di 36”.

“Vero. Quindi potrei scrivere la tabella in questo modo:”.

  1    4     9      6     25    36
4-1  9-4  16-9  25-16  36-25  ----


“Sì, esatto”.

“Non capisco bene cosa c'entra tutto questo con i numeri di Fibonacci”.

“Porta pazienza. Per ora prova a analizzare questo problema: è vero che nella seconda riga della tabella compaiono tutti i numeri dispari? Come lo si potrebbe dimostrare?”.

“Oh, dovrei usare un po' di algebra, vediamo. Se nella prima riga ci sono i quadrati, potrei indicare un generico termine con n2”.

“Bene. E il successivo, quindi?”.

“Il successivo sarà (+ 1)2”.

“Ora puoi calcolare la differenza”.

“(n + 1)2n2 = n2 + 2n + 1 − n2. Risulta 2n + 1”.

“Bene. Cosa puoi dire di questo numero?”.

“Che è certamente dispari. E, dato che n parte da 1, il primo numero che ottengo è proprio 3”.

“Perfetto. Ora indichiamo con un simbolo il calcolo che hai fatto: se il generico termine di una successione è an, il calcolo che si fa per riempire la seconda riga della tabella è an+1an, che indichiamo con Δan”.

“Oh, delta”.

“Sì, delta, che si chiama, semplicemente, differenza”.

“Quindi io avrei calcolato Δn2?”.

“Sì, hai trovato che Δn2 = 2+ 1”.

“Ok. A cosa mi serve questo delta?”.

“Tra un po' ci arriviamo. Per ora, scriviamo ancora una volta la relazione di Fibonacci, calcolata però in Fn+1”.

“Così?”.

Fn+1 = Fn + Fn−1

“Sì. Ora porta a sinistra il primo termine che si trova a destra dell'uguale”.

“Ecco:”.

Fn+1Fn = Fn−1

“Benissimo. Ora, riscrivila usando il delta che abbiamo definito prima”.

“Ah, ecco perché la differenza. Ecco qua:”.

ΔFn = Fn−1

“Ok. Ora, ragioniamo: è possibile che un polinomio soddisfi quella relazione?”.

“Boh, e come faccio a saperlo?”.

“Prima hai visto un esempio con un polinomio molto semplice, cioè n3”.

“Sì, in quel caso il delta risultava 2n2 + 1”.

“E, dunque, si passa da grado 3 a grado 2”.

“Sì, vero, ma non capisco bene cosa implichi questo fatto”.

“La proprietà che hai osservato, e cioè che l'operatore Δ prende un polinomio di grado n e ne restituisce uno di grado n − 1, è universale, non vale solo per la potenza 3”.

“Questo lo capisco: nel calcolo il termine di grado massimo si semplifica”.

“Ok. Ora, se un polinomio di grado n fosse soluzione dell'equazione ΔFn = Fn−1, vorrebbe dire che l'espressione a sinistra dell'uguale dovrebbe essere di grado n − 1, e quella a destra dell'uguale di grado n”.

“Ma questo è impossibile, no?”.

“Esatto: se due polinomi sono uguali, devono certamente avere lo stesso grado”.

“Bene, ho capito che un polinomio non può essere soluzione di quella equazione, e che, quindi, la successione di Fibonacci non è un polinomio. Questo non mi aiuta molto a capire come esprimerla in forma chiusa, però”.

“Un pochino sì, dai. Abbiamo capito che serve una espressione che rimane sufficientemente simile a sé stessa anche quando l'operatore delta agisce su di essa”.

“Ancora non vedo la soluzione. L'unica cosa che mi viene in mente è che questa roba sembra simile a un argomento che ho studiato a scuola”.

“Quale”.

“Le derivate. Ma forse mi sbaglio”.

“E invece no”.