giovedì 3 dicembre 2020

Capacità — 9. Finalmente la codifica Morse

“Siamo pronti per un riassunto finale”.

“Oh, finalmente”.

Abbiamo ricavato questa formula ricorsiva per la lunghezza delle stringhe codificate col codice Morse:”.

N(negativo) = 0
N(0) = 1
N(1) = 0
N(t) = N(t − 2) + N(t − 4) + N(t − 5) + N(t − 7) + N(t − 8) + N(t − 10)

“Giusto”.

“Abbiamo detto che, per calcolare la capacità di un canale in cui le trasmissioni avvengono secondo una determinata codifica, dobbiamo calcolare la lunghezza delle stringhe per t che diventa sempre più grande, farne il logaritmo, e dividere tutto per t”.

“Ricordo anche questo.”.

“E, infine, abbiamo visto un metodo per risolvere un'equazione alle ricorrenze, con l'uso delle funzioni esponenziali”.

“L'abbiamo usato con i numeri di Fibonacci, mi ricordo. Si immagina che la soluzione sia un'esponenziale, si sostituisce, e si fanno tornare i conti scoprendo di quale esponenziale si tratti”.

“Di quale, o di quali: potrebbero essercene anche più di una. La formula per i numeri di Fibonacci ne contiene due, per esempio”.

“Ah, vero. Però a lungo andare, quando il numero diventa sempre più grande, ce n'è una che comanda, perché l'altra dà un contributo sempre più piccolo”.

“Sì, è così. Abbiamo un'esponenziale con esponente positivo che, a lungo andare, diventa sempre più grande, e un'esponenziale con esponente negativo che, a lungo andare, diventa sempre più trascurabile”.

“Ok. Quindi ora dovremmo risolvere quella brutta equazione alle ricorrenze per il codice Morse? Sostituendo un'esponenziale generica?”.

“Già”.

“Ma se prendo una funzione del tipo an e sostituisco, mi viene una roba complicatissima!”.

“Prova, però devi sistemare le lettere, perché questa volta abbiamo indicato con N(t) il numero di stringhe di lunghezza t. Quindi, se vuoi provare con una funzione esponenziale, deve essere del tipo N(t) = at”.

“Ah, ok, io provo. Se sostituisco at mi viene questo:”.

at = at-2 + at−4 + at−5 + at−7 + at−8 + at−10

“Giusto”.

“Ma è una cosa orribile”.

“Eh, un po'”.

“E come la risolvo?”.

“Comincia col raccogliere il termine più piccolo, at−10”.

“Giusto, e poi lo semplifico. Direi che risulti una cosa del genere:”.

a10 = a8 + a6 + a5 + a3 + a2 + 1

“Bene”.

“Ma è un'equazione di decimo grado, chi la risolve?”.

“Questo lo facciamo fare ai computer, ecco qua”.

“Ah, veh che bello. Vedo due risultati reali, uno positivo e uno negativo, e poi dei risultati complessi”.

“A noi interessa quello positivo, che sarà quello che comanda quando la lunghezza della stringa diventa sempre più lunga”.

“Dice che è circa 1.4529”.

“E quindi la nostra N(t) si comporta circa come 1.4529t, a lungo andare”.

“E adesso?”.

“E adesso ne fai il logaritmo in base 2, e dividi per t”.

“La t si semplifica, rimane log2(1.4529)”.

“Che fa circa 0.539”.

“E quindi?”.

“E quindi abbiamo fatto: la capacità di una linea che trasmette in codice Morse è di 0.539 bit per unità di tempo”.

“Che fatica”.

“Pensa che Shannon ha spiegato tutto questo in due mezze pagine di un suo famosissimo articolo”.

“Cosa?”.

“Pagina 3 e pagina 4”.

“Su quante?”.

“Cinquantacinque”.

“Aiuto!”.

venerdì 13 novembre 2020

Chi ha paura della matematica?

Che fare in un venerdì 13 del 2020?

Quattro chiacchiere sulla matematica con .mau., ospitati virtualmente dalla Biblioteca Delfini di Modena. Saremo qui oppure qui.


Aggiornamento: fino a che rimane, ecco qua la ripresa:




martedì 3 novembre 2020

Capacità — 8. ·-· ·· -·-· --- ·-· ·-· · -· --·· ·

“Ho fatto i compiti, dopo la pausa estiva”.

“Incredibile, non succede mai”.

“Eheh. Mi sono fatto uno schema con tutte le possibili stringhe in codice Morse, a partire dalla lunghezza 1 fino alla lunghezza 10”.

“Però”.

“Guarda qua, ho proceduto partendo dalla lunghezza 1, e ho colorato di rosso ogni nuovo simbolo aggiunto in testa a quelli vecchi:”.


Lunghezza 1:


Non ci sono simboli.

N(1) = 0. 


Lunghezza 2:

P

N(2) = 1. 



Lunghezza 3:

Non ci sono simboli. 

N(3) = 0. 



Lunghezza 4:

PP, L

N(4) = N(4 − 2) + 1 = N(2) + 1 = 1 + 1 = 2. 



Lunghezza 5:

PS

N(5) = N(5 − 2) + N(5 − 4) + 1 = N(3) + N(1) + 1 = 0 + 0 + 1 = 1. 



Lunghezza 6:

PPP, PL, LP

N(6) = N(6 − 2) + N(6 − 4) + N(6 − 5) = N(4) + N(2) + N(1) = 2 + 1 + 0 = 3. 



Lunghezza 7:

PPS, PSP, LS

N(7) = N(7 − 2) + N(7 − 4) + N(7 − 5) + 1 = N(5) + N(3) + N(2) + 1= 1 + 0 + 1 + 0 = 3. 



Lunghezza 8:

PPPP, PPL, PLP, LPP, LL, PV

N(8) = N(8 − 2) + N(8 − 4) + N(8 − 5) + N(8 − 7) + 1 = N(6) + N(4) + N(3) + N(1) + 1 = 3 + 2 + 0 + 0 + 1 = 6. 



Lunghezza 9:

PPPS, PPSP, PLS, LPS, PSPP, PSL, LSP

N(9) = N(9 − 2) + N(9 − 4) + N(9 − 5) + N(9 − 7) + N(9 − 8) = N(7) + N(5) + N(4) + N(2) + N(1) = 3 + 1 + 2 + 1 + 0 = 7. 



Lunghezza 10:

PPPPP, PPPL, PPLP, PLPP, PLL, PPV, LPPP, LPL, LLP, PSPS, PVP, LV

N(10) = N(10 − 2) + N(10 − 4) + N(10 − 5) + N(10 − 7) + N(10 − 8) + 1 = N(8) + N(6) + N(5) + N(3) + N(2) + 1 = 6 + 3 + 1 + 0 + 1 + 1 = 12. 

“Ma che meraviglia!”.

“E direi di potermi fermare qua, giusto?”.

“Esatto: hai esaurito tutti i finali primitivi, perché con la lunghezza 10 hai potuto inserire anche l'ultimo, LV, e da ora in poi basta l'equazione generale per ricorrenze, che ora puoi scrivere in modo generico. Prova a scrivere la formula per N(t)”.

“Ormai la so a memoria:”.

N(t) = N(t − 2) + N(t − 4) + N(t − 5) + N(t − 7) + N(t − 8) + N(t − 10)

“Perfetto”.

“Però questa equazione vale solo dalla lunghezza 10 in poi, prima ci sono dei casi particolari”.

“Vero. Però c'è un trucchetto per non scrivere troppi casi particolari: hai notato che devi aggiungere 1 ogni volta che entra in gioco un finale primitivo nuovo, e questo succede quando la lunghezza della trasmissione è uguale alla lunghezza del finale nuovo”.

“Uhm, non so se ho capito”.

“Prendi l'ultimo calcolo, quello del numero di stringhe di lunghezza 10”.

“Ok. Alla fine ho dovuto aggiungere +1 perché c'era l'ultimo finale di lunghezza 10 da aggiungere”.

“Esatto. Se applichi la formula generale, quel +1 è in corrispondenza di N(10 − 10), cioè N(0)”.

“Vero”.

“E allora noi definiamo N(0) = 1”.

“Ah. E come facciamo con le lunghezze minori di 10? In quel caso dovrei calcolare N per numeri negativi”.

“Vorrà dire che definiamo che N(negativo) = 0”.

“Ma si può?”.

“Certo. Siamo matematici, possiamo fare tutto”.

“Benissimo”.

“Ed ecco quindi come riassumere l'equazione alle ricorrenze che calcola le lunghezze di tutte le possibili stringhe in linguaggio Morse”.

N(negativo) = 0
N(0) = 1
N(1) = 0
N(t) = N(t − 2) + N(t − 4) + N(t − 5) + N(t − 7) + N(t − 8) + N(t − 10)

“Fine?”.

“Fine”.

“E cosa ce ne facciamo?”.

“Calcoliamo la legge generale in forma non ricorsiva, per poi calcolare la capacità di un canale Morse”.

“La legge generale? E ci si riesce?”.

“Più o meno… Ma a noi non interessa la legge generale in forma esatta, ci interessa il suo comportamento quando la lunghezza delle trasmissioni diventa sempre più lunga. Ricordi quando abbiamo calcolato la capacità di un lucchetto da bicicletta?”.

“Sì, ricordo. Però alla fine si poteva ridurre tutto al calcolo del logaritmo in base 2 di 10, qui invece mi sembra tutto molto più complicato”.

“Vero. Nel caso del lucchetto ogni messaggio era una cifra da 0 a 10, non c'erano variabilità nella lunghezza, qui invece sì. Quello che dobbiamo fare è recuperare il metodo utilizzato allora mediante la rappresentazione ad albero: dobbiamo considerare N(t) con t sempre più grande, calcolare il suo logaritmo, e dividere tutto per t. Insomma, la formula è log2(N(t))/t, con t che cresce sempre più”.

“Mi sembra comunque complicato”.

“Sì, il problema è il calcolo di N(t). Ma noi abbiamo già visto un metodo generale per le equazioni alle ricorrenze”.

“Ma quando?”.

“Quando abbiamo trovato una formula chiusa per la successione di Fibonacci”.

“Oh”.

mercoledì 14 ottobre 2020

Carnevale della matematica #143

Benvenuti al Carnevale della Matematica numero 143, un Carnevale che usa la parola gerrymandering per ben due volte.

143, un numero che risolve il problema di Waring per le settime potenze: ogni numero naturale è la somma di al più 143 settime potenze. Compito per casa, di cui non ho trovato soluzione: trovare un numero naturale che è necessariamente uguale alla somma di 143 potenze.

143 indicherebbe anche che sono passati quasi dodici anni dal primo Carnevale, ma in realtà il dodicesimo compleanno è già passato da qualche mese, visto che ci sono state alcune pause estive negli ultimi anni. Manca un mese al numero 144, un bel quadrato, che ci permette di calcolare 143 come 144 − 1 = (12 − 1)×(12 + 1) = 11×13. I fattori 11 e 13 generano l'immortale verso della poesia Gaussiana all'alba allegro e la seguente cellula melodica:

Ora, ecco alcune proprietà del numero 143. Anzi, di alcuni numeri 143:

Il numero 143 di Tex Willer si intitola La cella della morte.

Quello di Dylan Dog si intitola Apocalisse.

Nathan Never ci porta nei cieli, con Sfida nello spazio.

Alan Ford rimane nei cieli, più o meno, con Il nuovo Superciuk.

Martin Mystere ci presenta Casanova.

Zagor è All'ultimo sangue.

Mister No è sempre in viaggio, questa volta con La spedizione scomparsa.

Julia indaga su Una storia in frantumi.

Detective Conan indaga anche lui su La verità tra le lacrime.

Amazing Spiderman, fa portare dall'aria il nome del suo nemico mensile: E il vento urla: Cyclone!

I Vendicatori, infine, si tuffano Nell'abisso del tempo.

Da tutto ciò si evince che il tema di questo mese è Viaggi, anche interstellari, eros, thanatos, Bacco e Venere, e drammi vari. Per la prima volta nella storia del carnevale, il tema è stato perfettamente rispettato da tutti i partecipanti.

Prima di passare all'elenco dei contributi, l'annuncio del prossimo Carnevale: il numero 144 uscirà il 14 novembre e sarà ospitato dai Maddmaths!.

Il primo contributo arrivato è quello di Leonardo Petrillo, che sul Tamburo Riparato ha introdotto, nel modo più semplice possibile, un effetto particolare che può avvenire nel mondo degli atomi: l'effetto Auger. Un “viaggio forzato” degli elettroni negli atomi sottoposti ad alcune condizioni particolari. Per far ciò, viene fatta una breve premessa sull'effetto fotoelettrico e sulla struttura elettronica dei metalli. Il tutto si conclude in musica con uno splendido brano di musica classica sempre inerente al tema dei viaggi. 

Annalisa Santi, ben attenta alle tassative prescrizioni sul tema, si chiede, nel suo post dal titolo Volo Air Canada 143 e le unità di misura: chissà se a proposito di viaggi interstellari o drammi esso volesse forse far riferimento al Cosmos 143, un satellite artificiale russo o al volo Air Canada 143? A lei ha ricordato proprio il volo Air Canada 143, un volo di linea della compagnia aerea canadese Air Canada in servizio tra Montréal ed Edmonton che il 23 luglio 1983 effettuò un drammatico atterraggio di emergenza e sfiorata una vera tragedia legata proprio a un errore dovuto alla variazione delle unità di misura adottate, kilogrammo e libbra. Ma si parla anche di Corsari e di Gilberto Govi… decisamente voli pindarici!

.mau. apparentemente non ha rispettato il tema del Carnevale, ma vediamo: sulle Notiziole ha scritto una serie notevole di quizzini, ed è noto che se uno non riesce a risolverli è un dramma: 


Poi ha recensito vari libri, e si sa che i libri possono fare viaggiare tanto: 

- Two Trains Leave Paris di Taylor Marie Frey e Mike Wesolowski, un testo di matematica di base con un approccio piuttosto peculiare ma carino 

- The Truth about Archie and Pye di Jonathan Pinnock, un giallo matematico che non gli è per nulla piaciuto. 

- Caos, spunti sulla teoria del caos pensati da Stefano Marmi e resi interessanti da Marco Malvaldi. Se non cercate i racconti del BarLume va molto bene. 

- Introduzione alla filosofia matematica di Bertrand Russell; fondamenti della matematica (di giusto cent'anni fa). Solo per amanti di Bertie. 

- I giochi matematici di PhiQuadro di Sandro Campigotto: problemi matematici per liceali (e non solo) con ambientazioni molto peculiari. 

- A History of π di Petr Beckmann: per farvi scoprire che i matematici possono anche non essere persone asettiche. 


C'è poi l'obituary di John Barrow, sempre in tema di drammi. 

Sul Post c'è la recensione del libro La luce e il tempo, di Guido Corbò, una bella introduzione alla teoria della relatività che usa la matematica ma senza mai superare le conoscenze della terza media (sì, almeno per la relatività ristretta è possibile!). E se non è un viaggio interstellare questo… 

C'è poi un post scriptum: Non prendete sempre alla lettera i numeri. È vero che non si possono confrontare i dati sui contagi Covid di adesso con quelli di fine marzo, ma questo non significa che possiamo stare tranquilli. 

Ed ecco i Maddmaths!; Roberto Natalini finge di disinteressarsi all'importante tema di questo mese, ma non ci riesce. 

Il libro di Leonardo — Comics&Science – The Fibonacci Issue. Giovedì 8 ottobre, all’interno dell’Internet Festival di Pisa, è stato presentato in anteprima il nuovo albo Comics&Science, The Fibonacci Issue, contenente tra l’altro la storia “Il libro di Leonardo” scritta e disegnata da Claudia Flandoli. Questo è certamente un viaggio. 

Presentazione di Archimede 2/2020.  È uscito il n. 2/2020 della rivista Archimede. Ecco il sommario del direttore Roberto Natalini: “Sono stati mesi per molti versi drammatici, sicuramente inediti. La quarantena, le difficoltà della didattica, l’incertezza su cosa ci aspetterà dopo l’estate. Noi siamo andati avanti, cercando di preparare un numero della rivista che fosse interessante e ricco di spunti. Apriamo con un articolo di modellistica matematica di Pierandrea Vergallo e Michele Zanatta che ci parlano dell’equazione di Gompertz e di come si usi nell’analisi della crescita dei tumori (l’articolo è liberamente accessibile sul sito Mondadori). A seguire, Lorenzo Meneghini ci propone una passeggiata tra progressioni geometriche, triangoli rettangoli e connessioni con il rapporto aureo. Argomenti tipicamente abbastanza scollegati, ma che posso diventare oggetto di un laboratorio stimolante. Infine Anna Maria Dallai e Marta Ciappelli ci parlano di tabelline, e di come sia possibile impostare un programma di lavoro basato su una loro interpretazione geometrica. Per la rubrica Scuole superiori, Guliana Massotti ci parla della geometria dello spazio. I disegni del fumetto «Le avventure matematiche di Dory e Berty», in cui si parla del teorema di Talete in termini molto originali, sono di Claudia Flandoli, che firma la sua seconda copertina di Archimede (dell’altra si parla qui), l’idea narrativa e i testi di Alice Manieri.” E non dimentichiamo le soluzioni dei giochi di Archimede Enigmistica, apparsi nei numeri precedenti e la nuova rubrica “A colpo d’occhio” tenuta da Roberto Zanasi (sono io, sì). Provate a guardare e commentare la sua ultima proposta. Direi che anche questo sia un viaggio bello lungo.


Dialogo sui numeri primi. Alessandro Zaccagnini ci propone un suo “Dialogo sui numeri primi”, un esercizio di stile in cui cercherà di parlare dei numeri primi in modo interessante senza usare formule, o quasi. Nel dialogo, che qui presentiamo a puntate, o meglio “giornate”, troveremo tre personaggi presi a prestito da Galileo: Salviati, che è un copernicano (un teorico dei numeri analitico), Sagredo, che è un patrizio (un matematico di un altro settore), e Simplicio, che è un tolemaico (un dilettante). 

  • Giornata prima, nella quale si discute della natura dei numeri primi.
  • Giornata seconda, nella quale si discutono i metodi per distinguere i numeri primi dai numeri composti.  

Numeri primi e dialoghi: eros, o dramma, a seconda di come uno si pone nei confronti della teoria dei numeri. 

Nobel in fisica 2020: vince anche il matematico Roger Penrose. Il Premio Nobel in fisica 2020 è stato assegnato pochi minuti fa a tre scienziati: Roger Penrose e, in compartecipazione, Reinhard Genzel e Andrea Ghez.  
Finalmente Roger Penrose. Nei giorni scorsi è stato annunciato che Roger Penrose è uno dei tre vincitori del premio Nobel per la fisica 2020. Raccogliamo qui una serie di ricordi di Michele Emmer, che ha conosciuto Penrose e con cui ha collaborato in passato. 
Qui si festeggia un nobel, e dove si festeggia Bacco non manca di presentarsi. 

Precarietà e Covid 19: la proposta della EWM per sostenere le giovani scienziate. Il 24 agosto si è tenuto un meeting zoom dal titolo EWM and the corona crisis. Elisabetta Strickland (Gruppo di lavoro della EWM per il Covid-19) ha partecipato ed ha scritto per noi un resoconto della riunione pieno di idee e proposte. Torniamo seri per un momento: precarietà e malattie sono drammi veri, il sostegno alla scienza è cosa buona, e quello alle scienziate, spesso messe da parte, è cosa ottima. 

Come nascono il vento, le nuvole e le perturbazioni. In questa nuova puntata della rubrica Esperienze Transdisciplinari di Matematica, Gianluigi Boccalon ci presenta un percorso che ha sperimentato alcuni anni fa in alcune sue classi di scuola secondaria di primo grado, alla scoperta delle basi della meteorologia, provando come sua abitudine ad abbattere i confini disciplinari tra fisica, geografia, chimica e matematica. Sembra fatto apposta per commentare l'episodio dell'Uomo Ragno con Cyclone.

Quadrati, rettangoli e nastri di Moebius: la congettura di Toepliz. A maggio di quest’anno, Joshua E. Green e Andrew Lobb hanno compiuto un interessante passo avanti nella dimostrazione della Congettura di Toepliz. In questo articolo Alberto Saracco cerca di fare il punto della situazione. Viaggi non ancora terminati, insomma.

Olimpiadi Internazionali di Matematica: Italia sesta al mondo. La sessantunesima Olimpiade Internazionale di Matematica ha avuto luogo in questi giorni in un formato inedito: programmata a luglio a San Pietroburgo, in Russia, e in un primo momento posticipata a settembre, di fronte al fatto che sarebbe stato molto difficile per molti concorrenti raggiungere la sede prevista, è stata trasformata in gara distribuita in tutto il mondo, in modo che potessero partecipare il maggior numero possibile di ragazze e ragazzi. Vediamo com'è andata. Questi sono ancora viaggi, che sarebbero stati fisici se la pandemia non si fosse messa in mezzo. 

L'improbabile non è impossibile. Inizia la nuova rubrica “La lente matematica” che sarà tenuta da Marco Menale. Brevi testi per guardare da vicino le cose con l’occhio del matematico. L'occhio del matematico, si sa, lavora bene in presenza di caffeina e di alcool. Di solito non contemporaneamente, ma non è detto. 

Mathematical Graffiti #3 – Sophie Germain, ovvero… Antoine-August Le Blanc. Terzo appuntamento con la rubrica di Stefano Pisani. “Dietro un grande uomo, c’è sempre una grande donna”. Questa frase, attribuita solitamente a Virginia Woolf, potrebbe attagliarsi perfettamente alla vicenda di Sophie Germain – solo che, nel suo caso, donna e uomo coincidevano. Sophie Germain (1771-1831) è stata una grande matematica, fisica e filosofa francese. Lo spirito riformatore della rivoluzione francese permeò le sue coraggiose scelte di vita. La frase "uomo e donna coincidevano" racchiude una storia notevole, di quando le donne erano considerate indegne di certi studi. Scegliete voi quale dei temi del Carnevale si adatta meglio a questa situazione. 

Ricordo di Vaughan F. R. Jones (1952 – 2020). Nei giorni scorsi è venuto a mancare all’età di 67 anni il matematico neozelandese Vaughan Jones, vincitore tra l’altro della Medaglia Fields nel 1990. Vi proponiamo un ricordo di Roberto Longo. Un secondo ricordo di una persona che non c'è più, in questo Carnevale. 

Un matematico prestato alla Disney. Alberto Saracco ci propone i video della serie “Un matematico prestato alla Disney“, in cui fa divulgazione della matematica traendo spunto da storie di paperi e topi. 

Puntata 19: La casa in 4D — L’ipercubo. In questa puntata, prendendo spunto dalla casa in 4D costruita da Archimede Pitagorico, ci parla dell’ipercubo. 

Puntata 20: Sindaco, che passione! – La matematica delle elezioni. In questa puntata, prendendo spunto dalla lotta elettorale tra Paperino e Gastone in Sindaco, che passione!, ci parla della matematica elettorale, e in particolare del gerrymandering

Puntata 21: Paperin Palladio e la missione architettonica – Aritmetica modulare. In questa puntata, prendendo spunto dal teorema di Arturo Dentato e dal numero 42 nella storia di Paperin Palladio, di Roberto Gagnor e Valerio Held, ci parla delle somme di tre cubi e dell’aritmetica modulare.

Puntata 22: Paperoga prof. per caso – Numeri primi. In questa puntata, prendendo spunto dalle bizzarre idee di Paperoga (Prof. per caso) sui numeri ci parlerà dell’infinità dei numeri primi. 

E qui c'è poco da dire, dato che il tema del Carnevale viene dai fumetti. 


Ora tocca a Davide Passaro, che scrive su Math is in the Air

Iniziamo con l'articolo di Pasquale Napolitano dal titolo: "Come vola un aereo: la resistenza spiegata tra paradossi e strati limite". Ancora viaggi. 

Rilanciamo con un articolo di Enrico De Giuli che tratta una "vexata quaestio" ovvero: "Che cosa è la matematica?".  E per rispondere a questa domanda, ognuno può fare riferimento al tema del Carnevale che preferisce (o anche a tutti i temi insieme, volendo).

Terminiamo con una interessante intervista ad Alessio Farcomeni, professore ordinario di statistica all'università di Tor Vergata. Il sottotitolo dell'intervista è molto indicativo ed è il seguente: "La statistica e le sue infinite possibilità applicative". La statistica: per qualche matematico è eros, per qualcun altro è thanatos. 


Passiamo a Paolo Alessandrini, che in questo mese si è dedicato a Gianni Rodari. 

"Matematica per pigri" Ovvero la matematica è una costruzione mentale che può anche fare a meno della realtà, e come tale è perfetta per i pigri, per gli amanti del gioco e della fantasia, e quindi per scrittori come Gianni Rodari. 

"Misure" Una questione matematica molto cara a Rodari è il concetto di misurazione, che viene utilizzato non sopprimendo completamente lo spirito scientifico e razionale, ma sovrapponendovi i colori della fantasia per creare una "nuova logica". 

"Derivabilità" "Il paese senza punta", una delle "Favole al telefono", offre una ghiotta occasione per parlare di continuità, derivabilità e frattali. Quelli di fantasia sono tra i viaggi più divertenti, in fondo.


Ora eccoci ai Rudi Mathematici, che come al solito chiudono il Carnevale (e in questo come al solito non si veda né un tentativo di metterli all'ultimo posto, né di riservar loro un posto d'onore: semplicemente, sono quasi sempre in ritardo): 

Buon compleanno Marie-Jean è un compleanno (ma va?). Dedicato al rivoluzionario Condorcet, in origine si intitolava “Il respiro della locomotiva”, e inizia con una dettagliata analisi di una delle canzoni più famose dei Jethro Tull, pensa te. Jethro Tull e locomotive: senza dubbio si viaggia. 

Poi c’è questo “Tsunami”, che è un Paraphernalia, e che è in grado di scatenare davvero catastrofi e solitoni. Sta a vedere che può starci davvero, in tema, stavolta… 

Meno drammatico, ma con un discreto impatto sui lettori e solutori, abbiamo poi questo “Indovinello dei Pellegrini”, che ovviamente fa parte della serie “Gli Allegri Monaci di Riddlewell”, e c’è poco da fare: se un monastero ha la parole “riddle” nel nome, si capisce subito come vada a finire la messa. I pellegrini viaggiano per definizione, no? 

L’improbabile titolo “Cura dimagrante con tartine” preannuncia il post istituzionale del blog, deputato alla soluzione del problema pubblicato su “Le Scienze” di Settembre. Un commento dal portavoce dei Rudi: è notevole non solo per la nostra sublime maestria di eccezionale intrattenimento matematico, ma anche per una topica niente male che abbiamo preso. È sempre più difficile, dopo tanti anni, nascondere la nostra spudorata cialtronaggine. Si parla di tartine, oltre che di errori baricentrici, e cos'è una tartina senza la bevanda preferita da Bacco?

C’è poi “Ney-pat-ko-no”, e il nome dice tutto, no? Perché perdersi in ulteriori spiegazioni? E perché spiegare quale dei vari temi di questo Carnevale è stato rispettato? Basta cliccare sul link e andarsi a leggere le ultime righe del post dal titolo misterioso, dove è tutto spiegato. 

Fortuna ha voluto che di compleanni, questo mese, ce ne fossero ben due. Concludiamo dunque il Carnevale, tracciando una simbolica linea di confine, con “Buon compleanno Claude!”, che  parla del non troppo noto Bachet de Méziriac, e che a suo tempo, sulla prestigiosa rivista Rudi Mathematici, si intitolava “Confini”. E i confini, beh, son lì per rendere difficile la vita a chi vuole viaggiare. Ma, ogni tanto bisognerebbe ricordarlo, i confini sono sempre e soltanto fittizi.

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