MC - SCHEDA 8 [schede: 1 2 3 4 5 6 7 8] [indice schede]
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Matematica finita (combinazioni, complessità computazionale, ordinamento di
dati, teoria dei numeri)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Indice:
8.0 Premessa
8.1 Effetti combinatori (scelta di percorsi, moltiplicazione di matrici)
e complessità computazionale
es.1 es.2 es.3
8.2 Ricorsione. Algoritmi di ordinamento
es.4 es.5
8.3 Teoria dei numeri. Crittografia.
es.6 es.7
8.4 Commenti agli esercizi
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
===== 8.0 ==================== [inizio scheda]
In questa scheda sono affrontate, mediante alcuni esempi, aree matematiche
relativamente alle quali i rapporti col computer assumono alcune caratteri-
stiche diverse rispetto alle aree considerate in precedenza, e che in genere
sono poco presenti nel curricolo universitario di un insegnante di matemati-
ca. Il taglio della scheda sarà più "a livello adulto". Per alcuni
approfondimenti didattici che coinvolgono concetti di analisi (limite,
successioni, ...) e di probabilità e statistica (generatore di numeri
casuali, impieghi del calcolo combinatorio, analisi di dati sperimentali,...)
rinviamo ai materiali (schede di lavoro e software) "L'insegnamento della
Analisi Matematica" e "Probabilità, Statistica ed elaborazione automatica
delle informazioni".
===== 8.1 ==================== [inizio scheda]
Iniziamo affrontando direttamente alcuni esercizi.
** ES.1 *******
1) Apri (da MC) il programma QBasic PERCORSO.bas che serve per risolvere il
problema di trovare il percorso di minima percorrenza con cui si puo` passare
per un certo numero di localita`. Esamina i commenti in testa al listato del
programma ed esegui il programma. (l'istruzione DATA consente di incorporare
un file di dati all'interno del listato del programma stesso, file che viene
letto dall'istruzione READ)
2) In problemi di questo genere, in cui e` inevitabile eseguire molti calco-
li e molti confronti (una opportuna strategia puo` ridurli o facilitarli, ma
solo fino a un certo punto) e` decisivo il ruolo del computer.
Quanti sarebbero stati i percorsi possibili se vi fosse stata un'ulteriore
localita` da toccare?
E se le localita` fossero state N?
3) E` facile modificare il programma per estenderlo al caso di N localita`,
comunque si fissi N. Il tempo di calcolo, t(N), pero` cresce notevolmente
all'aumentare di N. La funzione N -> t(N) ha andamento lineare, polinomiale
o esponenziale (cioe` esistono F e G lineari/polinomiali/esponenziali t. c.
F(N) <= t(N) <= G(N)) ?
******* END es.1 ** [commenti]
** ES.2 *******
Consideriamo l'algoritmo per moltiplicare due matrici, che e` utilizzato
all'interno di Derive e del programma Matr considerati nella scheda 7.
Vogliamo esaminare come cresce il tempo di calcolo all'aumentare delle
dimensioni delle matrici. Il programma MOLTMATR.bas ci consente di fare
cio`. Apriamolo senza uscire dal QBbasic.
1) Il programma consente di misurare il tempo t(N) (in centesimi di secondi)
impiegato dal computer in uso per calcolare il prodotto tra due generiche
matrici quadrate di ordine N. Esamina dall'help le informazioni relative alla
funzione (non alla istruzione) TIMER e alla funzione RND.
2) Prova a trovare un modo per ricavare sperimentalmente qual e` l'andamento
di N -> t(N).
3) Come puoi stimare quanto valgono t(100) e t(200)?
4) Congetturato sperimentalmente l'andamento, confronta questa congettura con
quanto puoi dedurre analizzando direttamente l'algoritmo (in particolare il
sottoprogramma MOLT: -> menu Visualizza, opzione SUBs).
******* END es.2 ** [commenti]
Con un particolare computer si sono ottenuti per il programma dell'es.
precedente t: 10->6, 20->16, 25->33, 30->60, 40->125, 45->180, 50->247,
55->24, 60->423
t(20)/t(10)=3, t(40)/t(20)=7.8, t(50)/t(25)=7.5, ...
t(2N)/t(N) tende ad essere circa 8 (=2^3); ciò ci fa ritenere che l'andamen-
to sia polinomiale, di grado 3 (la parte principale è il temine di grado 3,
per cui t(N) tende a comportarsi come N^3).
Una analisi più accurata e` fattibile esaminando la pendenza di t(N):
se t(N) e` un polinomio di grado J la sua pendenza di passo h e` un polinomio
di grado J-1 (come e` facile verificare con semplici manipolazioni algebriche
per J fissato: prova a farlo).
Se calcolando ripetutamente la pendenza a partire dai dati sperimentali
prima o poi si arriva a una sequenza di dati presso che costante si puo` dire
che l'andamento e` polinomiale e se ne puo` individuare il grado; se le nuove
successioni di dati man mano ottenute continuano a crescere piu` o meno allo
stesso modo, si puo` concludere che l'andamento e` esponenziale.
** ES.3 *******
1) Entra in GRAFUN e, scelta la finestra A, introduci (Graf-PuntiCongiunti)
le coppie (N,t(N)) di cui sopra e registrale come Dat1.
Quindi esamina il punto 46 dell'help (su PEND e su XYLOG) e trasforma Dat1
in Dat2 contenente la "pendenza" di Dat1, e analogamente Dat2 in Dat3 (pen-
denza di Dat2) e Dat3 in Dat4 (pendenza di Dat3).
Trasforma anche Dat1 in Dat9 contenente il trasformato bilogaritmico di
Dat1.
Quindi rappresenta in scala automatica Dat1 nella finestra A, Dat2 in B,
Dat3 in C e Dat4 in D. Che cosa puoi dedurre dai loro andamenti?
2) Rappresenta Dat9 in D in scala automatica. Ha andamento pressocche' linea-
re: che cosa puoi dedurne?
Prova a individuare una funzione lineare F che tenda ad approssimare
questi dati.
3) Prova a dedurre da quanto trovato in 3) una approssimazione di t(N).
******* END es.3 ** [commenti]
Il problema della complessita` computazionale e` uno dei problemi piu`
attuali di ricerca (di matematici e informatici): come far fronte ai fenomeni
di "esplosione combinatoria".
Si tratta di un argomento che, anche nell'insegnamento secondario
superiore, come si può capire dagli esempi visti sopra, offre motivazioni
per la introduzione e l'uso significativo di vari concetti matematici,
occasioni per attivita` che collegano diverse aree matematiche e
informatiche, ...
===== 8.2 ==================== [inizio scheda]
Prima di proseguire leggi le voci Successioni e Calcolo Combinatorio degli
Oggetti Matematici.
** ES.4 *******
1) Definisci F(x)=x^3, G(x)=@F(x) (in Grafun @F e` il fattoriale) e H(x)=2^x
e traccia (nella finestra totale T) il grafico di F per input interi (batti
fi, invece che solo f, alla domanda "F, G, ... ?") in scala automatica tra 0
e 10 e poi, in scala invariata, quelli (per input interi) di G e H. Che cosa
puoi osservare?
2) Utilizzando il fattoriale si possono definire il coefficiente binomiale
e altre funzioni combinatorie. Vediamo come effettuare questi calcoli diret-
tamente con un linguaggio di programmazione.
Esegui ed esamina i programmi CBIN1.bas, CBIN2.bas e CBIN3.bas.
Per ciascuno cerca di individuare (sperimentalmente e teoricamente) la com-
plessita` temporale.
CBIN2.bas offre un esempio di sottoprogramma RICORSIVO.
******* END es.4 ** [commenti]
Un problema di cui e` importante valutare la complessita` temporale e` quello
dell'ordinamento dei dati (interessa l'archiviazione e la trattazione stati-
stica delle informazioni).
** ES.5 *******
1) Esamina il programma ORDIN.bas, cerca di comprendere come funzionano i tre
algoritmi di ordinamento contenuti (per minimizzazione, per inserzione,
per fusione) osservando la dimostrazione animata e analizzando i commenti dei
vari sottoprogrammi.
Valutane la complessita` computazionale, cercando di capire se i diversi
algoritmi hanno differenze di comportamento a seconda di come sono disposti
i dati (cioe` se hanno casi ottimi e pessimi).
(nel caso di dati introdotti a caso, la scelta del "seme" consente di genera-
re una particolare successione di numeri; scegliendo lo stesso seme la stessa
successione di dati puo` essere sottoposta a un altro algortimo)
2) In una situazione in cui si abbia a che fare con una grande banca di dati
in cui periodicamente vengono introdotte ulteriori quantita` di dati (e che
in tale occasione viene riordinata) quale algoritmo conviene?
(In MC e` presente anche una versione piu` bella esteticamente, ma meno
efficace per la comprensione degli algoritmi: dimordin.bas)
******* END es.5 ** [commenti]
===== 8.3 ==================== [inizio scheda]
Il computer consente di affrontare con tecniche nuove vari problemi aritmeti-
ci.
** ES.6 *******
1) Osserva ed esegui il programma TERNE.bas per generare terne pitagoriche.
L'esistenza delle terne pitagoriche ha indotto, generalizzando, ad altri
problemi, come quello noto come Ultimo Teorema di Fermat (n intero, n>2 ->
x^n+y^n=z^n non ha soluzioni tra gli interi positivi), dimostrato nel 1994.
Eulero aveva congetturato (nel 1778) piu` in generale che, se A e` intero po-
sitivo, A^N non puo` espressa come la somma di meno di N potenze di interi
positivi. Fino agli anni 60 si supponeva che questa congettura fosse vera,
e si era in cerca di una dimostrazione.
Lo sviluppo dei computer ha consentito di affrontare in modo nuovo il proble-
ma. Con un computer si possono calcolare molte somme di potenze velocemente
e si puo` o rafforzare la "supposizione" che la congettura sia vera o indi-
viduare un controesempio che ne mostri la falsita`.
Usa il programma Eulero.bas per determinare il controesempio individuato nel
1966 (riferendosi al caso N=5) ponendo fine alle ricerche di dimostrazioni
di questa versione generalizzata dell'ultimo teorema di Fermat.
2) Usa il programma Goldbach.bas, per studiare la congettura (di Goldbach)
che ogni numero pari maggiore di 2 sia la somma di due numeri primi diversi.
Il computer, finora, ha confermato questa congettura (ma non se ne ha una
dimostrazione: potrebbe prima o poi trovarsi un controesempio, anche se tutto
lascia supporre che la congettura sia vera ...)
******* END es.6 ** [commenti]
Un ultimo esempio, che mette in luce i collegamenti con i problemi di
CRITTOGRAFIA.
** ES.7 *******
Usa e analizza il programma CODSEGR.bas.
Prova a modificarlo in modo da rendere più difficile la scoperta
del procedimento di codifica.
Come potresti usare RND per una codifica più "segreta" (esamina
la funzione RANDOMIZE).
Lo studio di quali concetti matematici si presta a collegamenti con
questa problematica?
******* END es.7 ** [commenti]
===== 8.4 ==================== [inizio scheda]
**** Su alcuni quesiti: ****
** Su Es.1
Qui sotto è riprodotto Percorso.bas:
' Programma per determinare un percorso di minima percorrenza per passare
'per Torino, Como, Pavia, Brescia, Bologna partendo da e ritornando a Genova.
' Nella tabella sono indicate le distanze chilometriche, che vengono messe
'nella variabile indiciata d(.,.)
' Il percorso - che viene memorizzato nella variabile indiciata a(.) -
'viene espresso indicando le localita` con numeri: 1 per Genova, 2 per Torino,
'3 per Como, ...
PRINT
posti = 6
FOR i = 1 TO posti: FOR j = 1 TO posti
READ d(i, j)
NEXT: NEXT
' GE TO CO PV BS BO
DATA 0,170,185,125,230,295 : 'GE
DATA 170, 0,165,155,225,330 : 'TO
DATA 185,165, 0, 85,110,260 : 'CO
DATA 125,155, 85, 0,135,200 : 'PV
DATA 230,225,110,135, 0,190 : 'BS
DATA 295,330,260,200,190, 0 : 'BO
min = 100000: p = 0
i = 1
FOR j = 2 TO posti
FOR k = 2 TO posti
IF k <> j THEN
FOR l = 2 TO posti
IF l <> j AND l <> k THEN
FOR m = 2 TO posti
IF m <> j AND m <> k AND m <> l THEN
FOR n = 2 TO posti
IF n <> j AND n <> k AND n <> l AND n <> m THEN
d = d(i, j) + d(j, k) + d(k, l) + d(l, m) + d(m, n) + d(n, i)
p = p + 1
IF d <= min THEN min = d: a(1)= i: a(2)= j: a(3)= k: a(4)= l: a(5)= m: a(6)= n
END IF
NEXT
END IF
NEXT
END IF
NEXT
END IF
NEXT
NEXT
PRINT
PRINT "n.percorsi possibili ="; p
PRINT "percorso con percorrenza minima: ";
FOR i = 1 TO posti: PRINT a(i); : NEXT: PRINT a(1)
PRINT "percorrenza ="; min; "km"
Si ottiene:
n.percorsi possibili = 120
percorso con percorrenza minima: 1 4 6 5 3 2 1
percorrenza = 960 km
Il programma calcola la lunghezza di tutti i percorsi possibili, quindi
t(N) cresce come il numero di questi, ossia come N!.
N! cresce esponenzialmente. Infatti 2^(N-1) < N! = N*(N-1)*...*2*1 < N^N
(se N>2). Anzi, N! > Int(N/2) ^ Int(N/2) (se N>1): cresce più velocemente
di A^N comunque si prenda A.
(sono chiamate ESPONENZIALI le funzioni del tipo N -> h^N con hgt;1 e piu` in
generale quelle del tipo N -> G(N)^N per cui esistano K intero e hgt;1 tali
che per ogni N > k si abbia G(N) >= h)
** Su Es.2
1) Ecco MoltMatr.bas:
nmax = 60: DIM A(nmax, nmax), B(nmax, nmax)
Via:
PRINT "ordine max="; nmax
FOR i = 1 TO nmax: FOR j = 1 TO nmax: A(i, j) = RND: NEXT: NEXT
10
INPUT ; "ordine"; n
IF n > nmax THEN PRINT " -->> "; : GOTO Via
t1 = TIMER
MOLT A(), A(), B(), n, n, n
t2 = TIMER
PRINT TAB(15); FIX((t2 - t1) * 100); "(sec/100)"
GOTO 10
SUB MOLT (A(), B(), c(), m, h, n) STATIC
' c() è la matrice m*n prodotto di a() m*h per b() h*n
FOR i% = 1 TO m: FOR j% = 1 TO n
c = 0
FOR k% = 1 TO h: c = c + A(i%, k%) * B(k%, j%): NEXT
c(i%, j%) = c
NEXT j%, i%
END SUB
2) Un modo semplice per studiare l'andamento di t(n) è vedere come varia
t(n) al raddoppiare di n. Su un po' di esempi (vedi i dati riprodotti sotto)
si può osservare che tende a moltiplicarsi circa per 8. Quindi t(n) cresce
circa cubicamente. Altri metodi (riferibili ai dati riptodotti a destra,
da cui si capisce subito che l'andamento è più che lineare) sono
presentati in es.3.
ordine? 6 0 (sec/100) ordine? 10 6 (sec/100)
ordine? 12 5 (sec/100) ordine? 15 5 (sec/100)
ordine? 24 27 (sec/100) ordine? 20 16 (sec/100)
ordine? 48 219 (sec/100) ordine? 25 33 (sec/100)
ordine? 30 60 (sec/100)
ordine? 35 82 (sec/100)
ordine? 40 125 (sec/100)
ordine? 45 180 (sec/100)
ordine? 50 247 (sec/100)
ordine? 55 324 (sec/100)
ordine? 60 423 (sec/100)
3) Se per t(50) trovi ad es. 2.5 sec puoi stimare in 2.5*8= 20 sec t(100)
e in 160 sec (quasi 3 min) t(200).
4) Vengono effettuate circa m*n*h moltiplicazioni, addizioni, assegnazioni
e incrementi dei contatori. Per m=h=n=N, questo numero e` N^3.
** Su Es.3
1) Sotto sono rappresentati Dat1, Dat2, Dat3, Dat4 e Dat 9.
Si vede che al 3° passaggio alle pendenze si ottiene un grafico che
oscilla attorno a un certo valore. Le oscillazioni sono notevoli, a casua
della perdita di precisione che man mano aumenta facendo le differenze. Si
potrebbero fare prove per N maggiori per avere più cifre significative
e stime più precise. Comunque possiamo osservare che si è riusciti
ad abbattere l'andamento dei grafici. Il fenomeno dovrebbe quindi crescere
come N^h, con h pari circa a 3.
2) Se F(x) = ux^s+g(x) con g(x) infinito per x->INF di ordine inferiore,
se rappresento (Log(x),Log(y)), questa relazione, per x->INF, tende a confon-
dersi con (Log(x),Log(u)+s*Log(x)), cioe`, scrivendo X al posto di Log(x),
con (X,Log(u)+s*X), cioe` con una relazione lineare. La pendenza s e` l'espo-
nente della parte principale di F(x). Nel caso del nostro Dat9 dal grafico
si ha che s e` circa 3, a conferma dell'andamento cubico.
3) Cercando q tale che x -> q+3x approssimi il trasformato bilogaritmico,
cioe` q che approssimi Log(u), si trova (per tentativi o individuando due
punti della retta che approssima i dati - vedi figura) q = -2.8. Quindi u =
10^Log(u) = 10^-2.8 = 0.0016 = 0.002 circa.
In alternativa, compreso che l'andamento è cubico, possiamo eguagliare t(60)
ad u*60^3 e dedurne, con più precisone, u=0.00196.
Se si traccia il grafico di F si trova che i punti sperimentali sono in
buon accordo con esso. Ma una stima precisa del valore di u, ossia del
coefficiente direttivo di t(N), non è molto significativa. Un impiego dello
stesso computer in momenti diversi (a seconda di quanto esso è "impegnato")
puo' dar luogo ad andamenti diversi (ma comunque cubici, nell'ambito della
stessa sessione d'uso del programma).
** Su Es.4
1) I grafici mettono in luce il fatto gia` osservato che il fattoriale
cresce piu` velocemente di 2^N.
2) Ecco CBIN1.bas:
DEFDBL A-Z
PRINT
10 INPUT ; " n (<90)"; n: IF n <= 90 THEN GOTO 10
DIM c(n, n)
t = TIMER
FOR i = 0 TO n: c(i, 0) = 1: c(i, i) = 1: NEXT
FOR i = 2 TO n: FOR j = 1 TO i - 1
c(i, j) = c(i - 1, j - 1) + c(i - 1, j)
NEXT: NEXT
PRINT " t ="; INT((TIMER - t) * 100);
IF n < 11 THEN INPUT "stampo triangolo"; risp ELSE risp = 0: PRINT
IF risp = 1 THEN
FOR i = 0 TO n: FOR j = 0 TO i
PRINT TAB(j * 5 + 1); c(i, j);
NEXT: PRINT : NEXT
END IF
ERASE c
GOTO 10 Il triangolo (per n=10):
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
CBIN2.bas:
DECLARE SUB cbin (n!, k!, c!)
PRINT
10
INPUT "n,k"; n, k
t = TIMER
cbin n, k, c
PRINT c,
PRINT "t="; (TIMER - t) * 100
GOTO 10
SUB cbin (n, k, c)
IF k = n OR k = 0 THEN c = 1: EXIT SUB
cbin n - 1, k - 1, a
cbin n - 1, k, c
c = a + c
END SUB
CBIN3.bas:
...
SUB cbin (n, k, c)
c = 1
FOR i = 1 TO k
c = c * (n - i + 1) / i
NEXT
END SUB
Per CBIN1 (che mette in C(.,.) tutti i coefficienti binomiali) con un
particolare PC si ottiene t(44)=10, t(88)=39. Al raddoppiare di N t quadru-
plica. Quindi il tempo cresce come N^2. La cosa era del resto ovvia: i valori
calcolati crescono come l'"area" del triangolo, che ha base e altezza propor-
zionali a N, quindi come N^2. In modo piu` pedestre: gli elementi del trian-
golo sono 1+2+3+..+(N+1) = (1+N+1)*(N+1)/2 = N^2/2+...
CBIN2 calcola il coeff. bin. in modo ricorsivo: usa la stessa idea impiega-
ta in CBIN1 ma lascia al programma il calcolo dei valori: il sottoprogramma
Cbin richiama se stesso piu` volte procedendo cosi`:
1) se e` richiesto C(4,2) si predispone a calcolare C(3,1) e C(3,2)
2) per calcolare C(3,1) si predispone a calcolare C(2,0) e C(2,1)
3) C(2,0) sa che vale 1
4) per calcolare C(2,1) si predispone a calcolare C(1,0) e C(1,1)
5) C(1,0) sa che vale 1
6) C(1,1) sa che vale 1
7) quindi (con 5 e 6) calcola C(2,1) = C(1,0)+C(1,1)
8) quindi (con 3 e 7) calcola C(3,1) = C(2,0)+C(2,1)
8) per calcolare C(3,2) si predispone a calcolare C(2,1) e C(2,2)
9) per calcolare C(2,1) si predispone a calcolare C(1,0) e C(1,1)
10) C(1,0) sa che vale 1
11) C(1,1) sa che vale 1
12) quindi (con 10 e 11) calcola C(2,1)
13) C(2,2) sa che vale 1
14) quindi (con 12 e 13) calcola C(3,2)
15) quindi (con 8 e 14) calcola C(4,2)
I rientri utilizzati nella descrizione precedente danno una idea delle
chiamate di Cbin che man mano si inscatolano l'una nell'altra.
Quando il programma arriva a situazioni come 3) o 5) e 6), cioe` quando il
sottoprogramma si ferma alla riga: IF k = n OR k = 0 THEN c = 1: EXIT SUB
non procede con ulteriori chiamate, ma completa la chiamata precedente.
Completata una chiamata, i calcoli svolti al suo interno vengono dimenticati;
ad es. C(2,1) viene calcolato 2 volte, per trovare C(3,1) 3 C(3,2).
Per analizzare il comportamento temporale conviene considerare il caso peg-
giore, cioe` calcolare C(n,k) con k al "centro": quando k e` vicino a n o a
0 il sottoprogramma Cbin arriva prima ai casi di cui conosce il valore (i
casi del tipo C(i,i), corrispondenti ai lati non orizzontali del triangolo).
Si ottengono tempi che crescono sempre piu` velocemente. Il file
tempcbin.gfu contiene i tempi t(n) per il calcolo di C(n,n/2) (n pari) otte-
nuti con un particolare PC:
'coppie (n,t(n)), t(n)= tempo calcolo di C(n,n/2) con CBIN2 con un certo PC
7
10,5
12,16
14,49
16,165
18,692
20,2356
22,9068
Analizzandolo con Grafun, se ne trovo e rappresento graficamente più volte
la pendenza, osservo che non riesco ad abbatterne l'andamento. Trasformandolo
in scala semilogaritmica, ottengo un grafico che tende a essere lineare.
Quindi si tratta di una funzione esponenziale:
se f(x) = k*a^x e rappresento (x,Log(y)), cioe` (x,Log(k)+x*Log(a)),
ottengo una retta di pendenza Log(a).
Se ho messo il file in Dat1 e il suo trasformato in Dat2, rappresentati sotto
a sinistra e al centro, e metto in Dat3 la sua pendenza, rappresentata a
destra, dal grafico o esaminando Dat3 con RCL, trovo Log(a) = 0.30, da cui
a = 10^0.3 = 1.995 = (circa) 2:
Quindi il tempo cresce circa come 2^n.
La cosa poteva anche essere dedotta dalla struttura del programma:
ogni chiamata di Cbin effettua a sua volte altre due chiamate, e cosi` via
fino a che non si arriva ai casi noti (lati del triangolo). Se si prende k
al centro, la "distanza" dai lati cresce come n. Quindi le chiamate di Cbin
raddoppiano un numero di volte che cresce come n, cioe` il loro numero cresce
come 2^n.
CBIN3 calcola C(n,k) come n/1*(n-1)/2*...*(n-k+1)/k, con un numero di
operazioni che cresce come k. Nel caso pessimo (k=n) impiega un tempo che
cresce linearmente rispetto a n.
CBIN3 e` decisamente l'algoritmo piu` efficiente. CBIN1 e` utile se in-
serito in un programma in cui si devono calcolare piu` volte dei coeffi-
cienti binomiali: una volta che sono stati calcolati e memorizzati in una
variabile indiciata, nei successivi usi il tempo di accesso a un qualunque
C(i,j) sara` costante. CBIN2 e` decisamente da scartare.
** Su Es.5
SUB ORDMIN (a(), n)
FOR i = 1 TO n
MIN a(), i, n, posto
SWAP a(i), a(posto)
NEXT
END SUB
SUB MIN (a(), i, j, posto) STATIC ' a(posto)=min{a(i),...a(j)}
posto = i
FOR h = i + 1 TO j: IF a(h) < a(posto) THEN posto = h
NEXT h
END SUB
I primi passi dell'algoritmo:
1) Ricerca del minimo e suo scambio col 1° elemento
2) Ricerca del minimo a partire dal 2° elemento e suo scambio col 2° elemento
...
vvvvvvvvvvvvvvvvvvvvvv
ggggggg
sssssssssssssssssss
jjjjjjjjjj
wwwwwwwwwwwwwwwwwwwwwww
pppppppppppppppp
kkkkkkkkkkk
ccc
nnnnnnnnnnnnnn
qqqqqqqqqqqqqqqqq
uuuuuuuuuuuuuuuuuuuuu
a
mmmmmmmmmmmmm
llllllllllll
iiiiiiiii
bb
ffffff
xxxxxxxxxxxxxxxxxxxxxxxx
dddd
ooooooooooooooo
tttttttttttttttttttt
hhhhhhhh
eeeee
rrrrrrrrrrrrrrrrrr | a
ggggggg
sssssssssssssssssss
jjjjjjjjjj
wwwwwwwwwwwwwwwwwwwwwww
pppppppppppppppp
kkkkkkkkkkk
ccc
nnnnnnnnnnnnnn
qqqqqqqqqqqqqqqqq
uuuuuuuuuuuuuuuuuuuuu
vvvvvvvvvvvvvvvvvvvvvv
mmmmmmmmmmmmm
llllllllllll
iiiiiiiii
bb
ffffff
xxxxxxxxxxxxxxxxxxxxxxxx
dddd
ooooooooooooooo
tttttttttttttttttttt
hhhhhhhh
eeeee
rrrrrrrrrrrrrrrrrr |
a
bb
sssssssssssssssssss
jjjjjjjjjj
wwwwwwwwwwwwwwwwwwwwwww
pppppppppppppppp
kkkkkkkkkkk
ccc
nnnnnnnnnnnnnn
qqqqqqqqqqqqqqqqq
uuuuuuuuuuuuuuuuuuuuu
vvvvvvvvvvvvvvvvvvvvvv
mmmmmmmmmmmmm
llllllllllll
iiiiiiiii
ggggggg
ffffff
xxxxxxxxxxxxxxxxxxxxxxxx
dddd
ooooooooooooooo
tttttttttttttttttttt
hhhhhhhh
eeeee
rrrrrrrrrrrrrrrrrr |
SUB ORDINS (a(), n)
'Dopo aver ordinato {a(1),.., a(i)} ottengo un ordinamento di {a(1),.., a(i+1)
'INSERENDO a(i+1) al posto giusto: faccio retrocedere a(i+1) finché incontro
'elementi > di esso (l'avanzamento è realizzato attraverso 'scambi' di
'posto). Il primo insieme ordinato è {a(1)}_
FOR i = 2 TO n ' inserisco a(2), poi inserisco a(3), . , a(n)
FOR j = i TO 2 STEP -1 ' eventuale avanzamento di a(i)
IF a(j) >= a(j - 1) THEN j = 2 ELSE SWAP a(j), a(j - 1)
' quando non c'erano piu' scambi da fare, per uscire dal loop ho posto j%=2
NEXT
NEXT
END SUB
I primi passi dell'algoritmo:
1) Confronto il 2° elemento col 1°; se è minore lo inserisco davanti;
2) Confronto il 3° elemento con quelli che lo precedono fino a trovare un
elemento minore; lo inserico dopo questo;
3) Confronto il 4° elemento con quelli che lo precedono fino a trovare un
elemento minore; lo inserico dopo questo;
...
qqqqqqqqqqqqqqqqq
mmmmmmmmmmmmm
nnnnnnnnnnnnnn
ggggggg
hhhhhhhh
sssssssssssssssssss
a
tttttttttttttttttttt
rrrrrrrrrrrrrrrrrr
bb
jjjjjjjjjj
uuuuuuuuuuuuuuuuuuuuu
iiiiiiiii
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
ooooooooooooooo
llllllllllll
pppppppppppppppp
vvvvvvvvvvvvvvvvvvvvvv
ffffff
ccc
dddd
eeeee
kkkkkkkkkkk | mmmmmmmmmmmmm
qqqqqqqqqqqqqqqqq
nnnnnnnnnnnnnn
ggggggg
hhhhhhhh
sssssssssssssssssss
a
tttttttttttttttttttt
rrrrrrrrrrrrrrrrrr
bb
jjjjjjjjjj
uuuuuuuuuuuuuuuuuuuuu
iiiiiiiii
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
ooooooooooooooo
llllllllllll
pppppppppppppppp
vvvvvvvvvvvvvvvvvvvvvv
ffffff
ccc
dddd
eeeee
kkkkkkkkkkk |
mmmmmmmmmmmmm
nnnnnnnnnnnnnn
qqqqqqqqqqqqqqqqq
ggggggg
hhhhhhhh
sssssssssssssssssss
a
tttttttttttttttttttt
rrrrrrrrrrrrrrrrrr
bb
jjjjjjjjjj
uuuuuuuuuuuuuuuuuuuuu
iiiiiiiii
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
ooooooooooooooo
llllllllllll
pppppppppppppppp
vvvvvvvvvvvvvvvvvvvvvv
ffffff
ccc
dddd
eeeee
kkkkkkkkkkk |
SUB ORDFUS (x(), i, j)
IF i = j THEN EXIT SUB
m = (i + j) \ 2: ORDFUS x(), i, m: ORDFUS x(), m + 1, j
DIM y(j - i)
FUSIONE x(), i, m, x(), m + 1, j, y()
FOR n% = i TO j: x(n%) = y(n% - i): NEXT
ERASE y
END SUB
SUB FUSIONE (x(), i, h, y(), j, k, z())
' fusione di x(i)-x(h) e y(j)-y(k) in z(0),z(1), ...
n% = 0: s% = i: t% = j
WHILE s% <= h AND t% <= k
IF x(s%) < y(t%) THEN z(n%) = x(s%): s% = s% + 1 ELSE z(n%) = y(t%): t% = t% + 1
n% = n% + 1
WEND
FOR p% = s% TO h: z(n%) = x(p%): n% = n% + 1: NEXT
FOR p% = t% TO k: z(n%) = y(p%): n% = n% + 1: NEXT
END SUB
I primi passi dell'algoritmo:
1) Attraverso ripetuti dimezzamenti mi riconduco a confrontare due elenchi da
12, due elenchi da 6, due elenchi da 3, uno da 2 e uno da 1 elemento;
2) Ordinato l'elenco da 2 ordino quello da 1 (il che non richiede confronti);
3) Fondo i due elenchi ordinati da 2 e da 1; ottengo un elenco ordinato da 3;
...
5) Fondo i due elenchi ordinati da 2 e da 1; ottengo un nuovo elenco ordinato
da 3;
6) Fondo i due elenchi ordinati da 3; ottengo un elenco ordinato da 6;
...
12) Fondo i due elenchi ordinati da 3; ottengo un nuovo elenco ordinato da 6;
...
nnnnnnnnnnnnnn
iiiiiiiii
mmmmmmmmmmmmm
kkkkkkkkkkk
bb
eeeee
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
uuuuuuuuuuuuuuuuuuuuu
jjjjjjjjjj
tttttttttttttttttttt
ggggggg
qqqqqqqqqqqqqqqqq
a
ccc
hhhhhhhh
rrrrrrrrrrrrrrrrrr
pppppppppppppppp
ffffff
vvvvvvvvvvvvvvvvvvvvvv
sssssssssssssssssss
ooooooooooooooo
llllllllllll
dddd | iiiiiiiii
nnnnnnnnnnnnnn
mmmmmmmmmmmmm
kkkkkkkkkkk
bb
eeeee
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
uuuuuuuuuuuuuuuuuuuuu
jjjjjjjjjj
tttttttttttttttttttt
ggggggg
qqqqqqqqqqqqqqqqq
a
ccc
hhhhhhhh
rrrrrrrrrrrrrrrrrr
pppppppppppppppp
ffffff
vvvvvvvvvvvvvvvvvvvvvv
sssssssssssssssssss
ooooooooooooooo
llllllllllll
dddd |
iiiiiiiii
mmmmmmmmmmmmm
nnnnnnnnnnnnnn
kkkkkkkkkkk
bb
eeeee
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
uuuuuuuuuuuuuuuuuuuuu
jjjjjjjjjj
tttttttttttttttttttt
ggggggg
qqqqqqqqqqqqqqqqq
a
ccc
hhhhhhhh
rrrrrrrrrrrrrrrrrr
pppppppppppppppp
ffffff
vvvvvvvvvvvvvvvvvvvvvv
sssssssssssssssssss
ooooooooooooooo
llllllllllll
dddd |
...
iiiiiiiii
mmmmmmmmmmmmm
nnnnnnnnnnnnnn
bb
eeeee
kkkkkkkkkkk
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
uuuuuuuuuuuuuuuuuuuuu
jjjjjjjjjj
tttttttttttttttttttt
ggggggg
qqqqqqqqqqqqqqqqq
a
ccc
hhhhhhhh
rrrrrrrrrrrrrrrrrr
pppppppppppppppp
ffffff
vvvvvvvvvvvvvvvvvvvvvv
sssssssssssssssssss
ooooooooooooooo
llllllllllll
dddd | bb
eeeee
iiiiiiiii
kkkkkkkkkkk
mmmmmmmmmmmmm
nnnnnnnnnnnnnn
xxxxxxxxxxxxxxxxxxxxxxxx
wwwwwwwwwwwwwwwwwwwwwww
uuuuuuuuuuuuuuuuuuuuu
jjjjjjjjjj
tttttttttttttttttttt
ggggggg
qqqqqqqqqqqqqqqqq
a
ccc
hhhhhhhh
rrrrrrrrrrrrrrrrrr
pppppppppppppppp
ffffff
vvvvvvvvvvvvvvvvvvvvvv
sssssssssssssssssss
ooooooooooooooo
llllllllllll
dddd |
bb
eeeee
iiiiiiiii
kkkkkkkkkkk
mmmmmmmmmmmmm
nnnnnnnnnnnnnn
ggggggg
jjjjjjjjjj
tttttttttttttttttttt
uuuuuuuuuuuuuuuuuuuuu
wwwwwwwwwwwwwwwwwwwwwww
xxxxxxxxxxxxxxxxxxxxxxxx
qqqqqqqqqqqqqqqqq
a
ccc
hhhhhhhh
rrrrrrrrrrrrrrrrrr
pppppppppppppppp
ffffff
vvvvvvvvvvvvvvvvvvvvvv
sssssssssssssssssss
ooooooooooooooo
llllllllllll
dddd |
1) Dalle uscite sperimentali si capisce che:
MIN non ha casi ottimi/pessimi: al raddoppiare dei dati il tempo quadrupli-
ca sempre; t(N) e` un infinito di ordine 2. Teoricamente: l'algoritmo cerca
man mano il minimo di tutti di dati, dei dati dal 2^ in poi, dei dati dal 3^
in poi, ...; per cerare il minimo tra H dati fa H-1 confronti; quindi im-
piega un tempo k*N per trovare il 1^ dato, un tempo K*(N-1) per trovare il
2^, ..., cioe` in tutto k*(N + N-1 + N-2 + ...) = k/2*N^2 + ...
INS ha caso ottimo se i dati sono gia` in ordine crescente: il tempo cresce
linearmente; nel caso in cui i dati siano a caso (con distribuzione uniforme)
cresce piu` o meno quadraticamente; la crescita e` chiaramente quadratica (e
con tempi molto maggiori) nel caso in cui i dati siano decrescenti.
Questo e` anche il caso pessimo, infatti l'algortimo man mano legge un dato
e lo colloca al posto giusto rispetto ai dati letti in precedenza. Mentre se
i dati sono gia` in ordine crescente deve per ogni dato fare un solo confron-
to (lo confronta con il massimo tra i dati gia` letti e si ferma senza effet-
tuare spostamenti), se sono in ordine decrescente deve invece confrontare
ogni dato letto prima con il massimo di quelli gia` letti, poi con quello
precedente, ... e andarsi a collocare al primo posto: in modo analogo a come
si e` proceduto per MIN, si conclude che il tempo e` quadratico.
FUS, come si osserva dalle uscite, cresce in modo poco piu` che lineare in
tutti i casi. Nel caso crescente e in quello decrescente si hanno tempi leg-
germente inferiori rispetto alle distribuzioni casuali dei dati. Teoricamen-
te: come si intuisce sia dalla esecuzione animata che dalla analisi del sot-
toprogramma, l'algoritmo funziona fondendo in ordine coppie di segmenti or-
dinati di dati (dai segmenti si estrae man mano il minimo tra i due primi
elementi dei segmenti finche' uno di questi
4 9 1 3 5 2 8 viene esaurito); se i dati sono N=2^H, fon-
\ / \ / \ / | de segmenti lunghi 2, 4, 8, 16, ..., 2^H;
4 1 2 | in ognuna di queste fasi (ossia ad ogni li-
9 3 5 | vello del grafo a fianco, che se i dati fos-
\__ __/ \_ _/ sero stati 2^N sarebbe stato "simmetrico")
1 2 deve comunque fare almeno N/2 confronti e
3 5 meno di N confronti; le fasi sono H; quindi
4 8 i confronti in tutto sono tra H*N/2 e H*N;
9 / H = log2(N); quindi il tempo cresce come
\ / N*log(N) (la base non e` rilevante: log2(N),
\____ ____/ Log(N), ln(N), ... sono proporzionali).
1 Se la quantita` di dati non e` una potenza
2 di 2, il comportamento sara` intermedio tra
3 quello di due situazioni con quantita` pari
4 a una potenza di 2. Quindi in ogni caso
5 t(N) cresce come N*log(N)
8
2) Conviene ORDINS. Perché? Anche in questo caso, non esiste il modello o
la tecnica matematica migliore in assoluto. A seconda dei contesti la
strategia più efficace può cambiare.
** Su Es.6
1)
DEFDBL A-Z
max = 100
PRINT : PRINT "Terne pitagoriche (x^2+y^2=z^2; x, y <="; max; ")"
n.cifre = 15: prec.rel = 5 * 10 ^ -n.cifre
FOR x = 1 TO max: FOR y = x TO max
u = (x ^ 2 + y ^ 2) ^ .5#
GOSUB Ver.Int
IF intero = 1 THEN PRINT x; y; u, : intero = 0
NEXT: NEXT
END
Ver.Int:
IF ABS((INT(u) - u) / u) < prec.rel THEN ' parte intera inf.
intero = 1
ELSEIF ABS((INT(u + 1) - u) / u) < prec.rel THEN ' parte intera sup.
intero = 1
END IF
RETURN
Terne pitagoriche (x^2+y^2=z^2; x, y <= 100 )
3 4 5 5 12 13 6 8 10 7 24 25 8 15 17
9 12 15 9 40 41 10 24 26 11 60 61 12 16 20
12 35 37 13 84 85 14 48 50 15 20 25 15 36 39
16 30 34 16 63 65 18 24 30 18 80 82 20 21 29
20 48 52 20 99 101 21 28 35 21 72 75 24 32 40
24 45 51 24 70 74 25 60 65 27 36 45 28 45 53
28 96 100 30 40 50 30 72 78 32 60 68 33 44 55
33 56 65 35 84 91 36 48 60 36 77 85 39 52 65
39 80 89 40 42 58 40 75 85 40 96 104 42 56 70
45 60 75 48 55 73 48 64 80 48 90 102 51 68 85
54 72 90 56 90 106 57 76 95 60 63 87 60 80 100
60 91 109 63 84 105 65 72 97 66 88 110 69 92 115
72 96 120 75 100 125 80 84 116
DEFDBL A-Z
n.cifre = 15: prec.rel = 5 * 10 ^ -n.cifre
x1 = 25: x2 = 30
y1 = 81: y2 = 85
z1 = 106: z2 = 110
w1 = 131: w2 = 135
' Invece che: FOR x = 1 TO 135 : FOR y = x TO 135: FOR z = y to 135 : ...
' si sono scelti range piu` ristretti per ridurre i tempi; comunque la
' quaterna di interi x,y,z,w che si ottiene e` la prima per cui esiste u
' intero tale che x^5+y^5+z^5+w^5=u^5
PRINT "Ricerca di x,y,z,w per cui esiste u tale che x^5+y^5+z^5+w^5=u^5"
PRINT "negli intervalli:"
PRINT "x1,x2; y1,y2; z1,z2; w1,w2: "; x1; x2; " "; y1; y2; " "; z1; z2; " "; w1; w2
PRINT "Aspetta ..."
FOR x = x1 TO x2: FOR y = y1 TO y2: FOR z = z1 TO z2: FOR w = w1 TO w2
LOCATE , 1: PRINT "x,y,z,w,u"; x; y; z; w;
u = (x ^ 5 + y ^ 5 + z ^ 5 + w ^ 5) ^ .2#: GOSUB Ver.Int
IF intero = 1 THEN PRINT u: intero = 0
NEXT: NEXT: NEXT: NEXT
LOCATE , 1: PRINT SPACE$(60)
END
Ver.Int:
IF ABS((INT(u) - u) / u) < prec.rel THEN ' parte intera inf.
intero = 1
ELSEIF ABS((INT(u + 1) - u) / u) < prec.rel THEN ' parte intera sup.
intero = 1
END IF
RETURN
Ricerca di x,y,z,w per cui esiste u tale che x^5+y^5+z^5+w^5=u^5
negli intervalli:
x1,x2; y1,y2; z1,z2; w1,w2: 25 30 81 85 106 110 131 135
Aspetta ...
x,y,z,w,u 27 84 110 133 144
2)
' Programma per la verifica sperimentale della Congettura di Goldbach: ogni
' numero pari maggiore di 2 e` somma di due numeri primi diversi tra loro.
' Al momento (1997), ne' la congettura ne' la sua negazione sono state
' dimostrate
Via:
INPUT "ricerca dei numeri primi <= N; N="; max
DIM a(max): rad = SQR(max)
' lascio a(n)=0 se n e' primo (o e' 0), se no metto in a(n) un fattore primo di n
FOR fat = 2 TO rad
IF a(fat) = 0 THEN FOR i = fat * fat TO max STEP fat: a(i) = fat: NEXT
NEXT
WHILE 0 = 0
INPUT "1: elenco numeri primi, 2: fattorizzare, 3: Goldbach, 4: altro N, 5: fine"; risp
IF risp = 1 THEN
INPUT "elenco primi compresi tra h e k; h,k="; h, k
IF k > max THEN k = max: PRINT "prendo k="; max
IF h = 0 THEN h = 1
FOR i = h TO k: IF a(i) = 0 THEN PRINT i;
NEXT: PRINT
ELSEIF risp = 2 THEN
PRINT "n. da scomporre <="; max; : INPUT n
IF n > max THEN
PRINT "numero troppo grande"
ELSE
WHILE a(n) > 0: PRINT a(n): n = n / a(n): WEND
PRINT n
END IF
ELSEIF risp = 3 THEN
FOR i = 2 TO max STEP 2
v = 0
FOR j = 1 TO i - 1
IF a(j)= 0 THEN IF a(i-j)= 0 THEN PRINT i; "="; j; "+"; i-j; " # "; : j= i-1: v= 1
' se trovo la coppia di addendi pongo v=1 e esco dal ciclo ponendo j=i-1
NEXT
IF v = 0 THEN PRINT "falsa": i = max
IF i \ 100 = i / 100 THEN INPUT ; "", wwww$
NEXT: PRINT
ELSEIF risp = 4 THEN
ERASE a: GOTO Via
ELSEIF risp = 5 THEN
END
END IF
WEND
ricerca dei numeri primi <= N; N=? 1000
1: elenco numeri primi, 2: fattorizzare, 3: Goldbach, 4: altro N, 5: fine? 1
elenco primi compresi tra h e k; h,k=? 1,1000
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157
163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241
251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347
349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439
443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547
557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643
647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751
757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859
863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977
983 991 997
1: elenco numeri primi, 2: fattorizzare, 3: Goldbach, 4: altro N, 5: fine? 2
n. da scomporre <= 1000 ? 996
3
2
2
83
1: elenco numeri primi, 2: fattorizzare, 3: Goldbach, 4: altro N, 5: fine? 3
2 = 1 + 1 # 4 = 1 + 3 # 6 = 1 + 5 # 8 = 1 + 7 # 10 = 3 + 7 # 12 = 1 +
11 # 14 = 1 + 13 # 16 = 3 + 13 # 18 = 1 + 17 # 20 = 1 + 19 # 22 = 3 +
19 # 24 = 1 + 23 # 26 = 3 + 23 # 28 = 5 + 23 # 30 = 1 + 29 # 32 = 1 +
31 # 34 = 3 + 31 # 36 = 5 + 31 # 38 = 1 + 37 # 40 = 3 + 37 # 42 = 1 +
41 # 44 = 1 + 43 # 46 = 3 + 43 # 48 = 1 + 47 # 50 = 3 + 47 # 52 = 5 +
47 # 54 = 1 + 53 # 56 = 3 + 53 # 58 = 5 + 53 # 60 = 1 + 59 # 62 = 1 +
61 # 64 = 3 + 61 # 66 = 5 + 61 # 68 = 1 + 67 # 70 = 3 + 67 # 72 = 1 +
71 # 74 = 1 + 73 # 76 = 3 + 73 # 78 = 5 + 73 # 80 = 1 + 79 # 82 = 3 +
79 # 84 = 1 + 83 # 86 = 3 + 83 # 88 = 5 + 83 # 90 = 1 + 89 # 92 = 3 +
89 # 94 = 5 + 89 # 96 = 7 + 89 # 98 = 1 + 97 # 100 = 3 + 97 # 102 =
1 + 101 # 104 = 1 + 103 # 106 = 3 + 103 # 108 = 1 + 107 # 110 = 1 +
109 ...
** Su Es.7
' cod e` la codifica "segreta" dei numeri del codice ASCII
' car$ e` un carattere battuto e n.asc e` il suo numero in codice ASCII
' car.new$ e` la sua codifica segreta e n.asc.new e` il suo numero in codice ASCII
PRINT
DIM cod(255)
FOR i = 0 TO 255
cod(i) = i + 3: IF cod(i) > 255 THEN cod(i) = cod(i) - 255
NEXT
10 INPUT "1: codifica, 2: decodifica"; cosa
SELECT CASE cosa
CASE 1
INPUT"messaggio: ", a$
PRINT "codifica: ";
FOR i = 1 TO LEN(a$)
car$ = MID$(a$, i, 1): n.asc = ASC(car$): n.asc.new = cod(n.asc)
car.new$ = CHR$(n.asc.new) : PRINT car.new$;
NEXT
PRINT
CASE 2
INPUT"codifica: ", a$
PRINT "messaggio: ";
FOR i = 1 TO LEN(a$)
car$ = MID$(a$, i, 1): n.asc = ASC(car$)
FOR n.asc.new =0 TO 255: IF n.asc= cod(n.asc.new) THEN EXIT FOR
NEXT
car.new$ = CHR$(n.asc.new) : PRINT car.new$;
NEXT
PRINT
CASE ELSE
END SELECT
GOTO 10
1: codifica, 2: decodifica? 1
messaggio: non mi piace la matematica
codifica: qrq#pl#sldfh#od#pdwhpdwlfd
1: codifica, 2: decodifica? 2
codifica: qrq#pl#sldfh#od#pdwhpdwlfd
messaggio: non mi piace la matematica
Questi tipi di codifica (basati su uno slittamento del codice ascii) sono
molto facili da individuare, come lo sono anche quelli basati su una
qualunque altra scelta di una funzione bigettiva da N<256 in N<256: tenendo
conto della frequenza delle varie lettere (individuabile con una analisi
statistica), della distribuzione della lunghezze delle parole e delle frasi,
dei vincoli esistenti (in genere, in italiano, ad esempio, prima di una H ci
può essere una C, una G o uno spazio; dopo una B non ci possono essere
C, F, G, …), … non è difficile individuare i cambiamenti di "nome".
Vediamo una delle molte "complicazioni" ideabili. Si potrebbe creare una
sequenza di, ad esempio, 5 valori di "slittamento" in modo che di volta in
volta cambi la ridenominazione, ma in modo che, per chi conosce la sequenza
(che funge da chiave di lettura), sia anche possibile effettuare la
decodifica. Vedi CodSegr2.bas in MC:
...
DIM cod(4,255)
d(0)=3: d(1)=7: d(2)=1: d(3)=27: d(4)=13
FOR j=0 TO 4: FOR i = 0 TO 255
IF i < 32 OR i > 126 THEN ' non modifichiamo i caratteri "strani"
cod(j,i) = i ' ma solo lettere e segni di interpunzione
ELSE
cod(j,i) = i + d(j): IF cod(j,i) > 126 THEN cod(j,i) = cod(j,i) - 126 + 31
END IF
NEXT: NEXT
...
id = 0
...
IF id > 4 THEN id = 0
car$ = MID$(a$, i, 1): n.asc = ASC(car$): n.asc.new = cod(id,n.asc)
car.new$ = CHR$(n.asc.new) : PRINT car.new$; : id = id + 1
...
id = 0
...
IF id > 4 THEN id = 0
car$ = MID$(a$, i, 1): n.asc = ASC(car$)
FOR n.asc.new =0 TO 255: IF n.asc= cod(id,n.asc.new) THEN EXIT FOR
NEXT
car.new$ = CHR$(n.asc.new) : PRINT car.new$; : id = id + 1
...
1: codifica, 2: decodifica? 1
messaggio: non mi piace la matematica
codifica: qvo;zl'q%nfl!(n#tb0rphu%pd
1: codifica, 2: decodifica? 2
codifica: qvo;zl'q%nfl!(n#tbOrphu%pd
messaggio: non mi piace la ma4ematica
Efficacissimo è il ricorso a RND e RANDOMIZE. Possiamo scegliere un seme
(ossia un numero intero) per individuare una successione di numeri tra 0 e 1
pseudo-casuale (ossia generata da un algoritmo particolare in modo che in
apparenza i numeri si susseguano in modo casuale) mediante RANDOMIZE
(INPUT "seme"; s : RANDOMIZE s). Trasformiamo i numeri man mano generati
da RND in numeri compresi tra 0 e 93 con D = FIX(RND*94) e modifichiamo il
programma di sopra mettendo "+D" al posto di "+d(j)". Se il ricevente
conosce il "seme" può decodificare il messaggio.
Quello della crittografia è un tema che, se non ci si mette a studiare la
crittografia a fondo, a far finta di far studiare e far capire agli alunni le
tecniche più sofisticate, ma si punta a studiarne il ruolo, a collocarlo
storicamente e, soprattutto, a far ideare agli alunni (ricorrendo alle
conoscenze che già hanno, alla esplorazione degli strumenti matematici e del
software che hanno a disposizione, ...) nuovi metodi di codifica, offre
spunti e motivazioni (culturali ed "emotive") agli alunni in direzione di
diverse attività ed aree matematiche (funzioni, successioni, iniettività
e invertibilità, algortimi, aritmetica modulare, variabili casuali, ...).
[inizio scheda] [schede: 1 2 3 4 5 6 7 8] [indice schede]