“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.
P
N(2) = 1.
Lunghezza 3:
Non ci sono simboli.
Non ci sono simboli.
N(3) = 0.
Lunghezza 4:
PP, L
N(4) = N(4 − 2) + 1 = N(2) + 1 = 1 + 1 = 2.
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.
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.
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.
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.
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.
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”.
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”.
Nessun commento:
Posta un commento