Dopo aver provato il primo metodo, proviamo ora un secondo metodo per ricercare un elemento in una lista di elementi. E vediamo come va a finire.
1:
I due studenti che hanno il ruolo di sistema d’apertura porta e che quindi conoscono anche la password corretta, distribuiranno una scheda lettera a ognuno del gruppo dei 13 studenti disposti in piedi, la distribuzione è totalmente casuale, devono scegliere a loro piacimento 13 schede lettere tra le 26 che hanno a loro disposizione (ovviamente tra le 13 schede distribuite deve comparire anche la scheda che rappresenta la prima lettera della password).
Esempio:
Dopo la distribuzione, tutti i 13 studenti esibiranno davanti a loro la lettera assegnata.
P
R
V
G
U
H
L
F
W
O
N
C
T
Ora entra in azione l’aiutante della formica Cloe, in totale davanti si trova 13 lettere, considera la lettera che si trova a metà della lista (la lettera L) e domanda se la lettera della password che sta cercando, si trova prima/dopo rispetto alla lettera che rappresenta la metà della lista che ha a disposizione; i due studenti addetti al sistema d’apertura porta risponderanno Sì oppure No.
Se la risposta è Sì / No in base alla domanda fatta, la nostra ricerca sarà concentrata non più sull’intera lista ma solo sulla sua metà; allora gli studenti della metà lista in cui la ricerca è esclusa, rimanendo nella loro posizione, si siedono e le loro lettere vengono prese dagli studenti addetti al sistema d’apertura porta e immesse nuovamente nel plico delle lettere a loro disposizione. L’aiutante di Cloe continuerà in questo modo, ovvero facendo dimezzamenti successivi fino a rimanere con un unico elemento nella lista, quello rappresenterà la lettera cercata.
A ogni domanda effettuata, i due studenti addetti al sistema d’apertura porta segneranno alla lavagna l’effettuazione di una domanda/tentativo.
Iniziamo ora a cercare la prima lettera della password: _ (ovvero la lettera G).
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera L; la prima lettera della password si trova prima della lettera L? – Risposta: Sì –
P
R
V
G
U
H
L
F
W
O
N
C
T
Aiutante di Cloe: la lettera che rappresenta la metà della lista risultante è la lettera V (oppure G); la prima lettera della password si trova dopo della lettera V? – Risposta: Sì –
P
R
V
G
U
H
L
F
W
O
N
C
T
Aiutante di Cloe: la lettera che rappresenta la metà della lista risultante è la lettera U; la prima lettera della password si trova dopo della lettera U? – Risposta: No –
P
R
V
G
U
H
L
F
W
O
N
C
T
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera U (oppure G); la prima lettera della password si trova prima della lettera U? – Risposta: Sì –
P
R
V
G
U
H
L
F
W
O
N
C
T
G
La prima lettera della password è stata trovata (G _ _ _) dopo 4 tentativi.
2:
L’intero gruppo dei 13 studenti torna interamente in piedi; dopo aver ritirato tutte le schede lettere rimaste, ora i due studenti che hanno il ruolo di sistema d’apertura porta ridistribuiranno nuovamente una scheda lettera a ognuno del gruppo dei 13 studenti, la distribuzione è totalmente casuale, devono scegliere a loro piacimento 13 schede lettere tra le 26 che hanno a loro disposizione (ovviamente tra le 13 schede distribuite deve comparire anche la scheda che rappresenta la seconda lettera della password).
Dopo la distribuzione, tutti i 13 studenti esibiranno davanti a loro la lettera assegnata.
D
T
B
K
O
P
N
F
A
M
X
Z
I
Iniziamo ora a cercare la seconda lettera della password: _ (ovvero la lettera M).
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera N; la seconda lettera della password si trova prima della lettera N? – Risposta: No –
D
T
B
K
O
P
N
F
A
M
X
Z
I
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera M; la seconda lettera della password si trova dopo la lettera M? – Risposta: No –
D
T
B
K
O
P
N
F
A
M
X
Z
I
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera F (oppure A); la seconda lettera della password si trova dopo la lettera F? – Risposta: Sì –
D
T
B
K
O
P
N
F
A
M
X
Z
I
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera M (oppure A); la seconda lettera della password si trova prima della lettera M? – Risposta: No –
D
T
B
K
O
P
N
F
A
M
X
Z
I
M
La seconda lettera della password è stata trovata (G M _ _) dopo 4 tentativi.
3:
L’intero gruppo dei 13 studenti torna interamente in piedi; dopo aver ritirato tutte le schede lettere rimaste, ora i due studenti che hanno il ruolo di sistema d’apertura porta ridistribuiranno nuovamente una scheda lettera a ognuno del gruppo dei 13 studenti, la distribuzione è totalmente casuale, devono scegliere a loro piacimento 13 schede lettere tra le 26 che hanno a loro disposizione M (ovviamente tra le 13 schede distribuite deve comparire anche la scheda che rappresenta la terza lettera della password).
Dopo la distribuzione, tutti i 13 studenti esibiranno davanti a loro la lettera assegnata.
R
Q
I
K
L
J
S
F
B
C
V
Y
G
Iniziamo ora a cercare la terza lettera della password: _ (ovvero la lettera K).
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera S; la terza lettera della password si trova prima della lettera S? – Risposta: Sì –
R
Q
I
K
L
J
S
F
B
C
V
Z
I
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera I (oppure K); la terza lettera della password si trova dopo la lettera I? – Risposta: Sì –
R
Q
I
K
L
J
S
F
B
C
V
Z
I
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera L; la terza lettera della password si trova prima della lettera L? – Risposta: Sì –
R
Q
I
K
L
J
S
F
B
C
V
Z
I
K
La terza lettera della password è stata trovata (G M K _) dopo 3 tentativi.
4:
L’intero gruppo dei 13 studenti torna interamente in piedi; dopo aver ritirato tutte le schede lettere rimaste, ora i due studenti che hanno il ruolo di sistema d’apertura porta ridistribuiranno nuovamente una scheda lettera a ognuno del gruppo dei 13 studenti, la distribuzione è totalmente casuale, devono scegliere a loro piacimento 13 schede lettere tra le 26 che hanno a loro disposizione (ovviamente tra le 13 schede distribuite deve comparire anche la scheda che rappresenta la quarta lettera della password).
Dopo la distribuzione, tutti i 13 studenti esibiranno davanti a loro la lettera assegnata.
V
N
X
T
E
W
L
J
F
G
A
Z
D
Iniziamo ora a cercare la quarta e ultima lettera della password: _ (ovvero la lettera V).
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera L; la quarta lettera della password si trova prima della lettera L? – Risposta: Sì –
V
N
X
T
E
W
L
J
F
G
A
Z
D
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera X (oppure T); la quarta lettera della password si trova dopo la lettera X? – Risposta: No –
V
N
X
T
E
W
L
J
F
G
A
Z
D
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera N; la quarta lettera della password si trova dopo la lettera N? – Risposta: No –
V
N
X
T
E
W
L
J
F
G
A
Z
D
Aiutante di Cloe: la lettera che rappresenta la metà della lista è la lettera N (oppure V); la quarta lettera della password si trova prima della lettera N? – Risposta: Sì –
V
N
X
T
E
W
L
J
F
G
A
Z
D
V
La quarta lettera della password è stata trovata (G M K V) dopo 4 tentativi.
Password trovata! Quante briciole di pane le è costata a Cloe questo secondo metodo di ricerca? In totale le sono state sottratte 15 briciole dal suo carretto.
Ma quindi in questa semplice attività abbiamo potuto constatare che con il primo metodo di ricerca a Cloe vengono sottratte 27 briciole, mentre con il secondo metodo solamente 15! Ovviamente quello presentato sopra è solo un semplice esempio di gioco, poi sicuramente ogni bambino soprattutto nel primo metodo potrà decidere di chiamare una lettera piuttosto di un’altra.
Ma indipendentemente dalle scelte fatte, la differenza tra i due metodi si dovrebbe notare palesemente, soprattutto se ci sofferma a studiare il caso peggiore di entrambi i metodi di ricerca.
Il caso peggiore del primo metodo di ricerca utilizzato (caso in cui l’aiutante di Cloe è particolarmente sfortunato e per ogni lettera della password deve effettuare tutti i tentativi) è pari a 48 tentativi totali.
Il caso peggiore del secondo metodo di ricerca utilizzato (caso in cui l’aiutante di Cloe per ogni lettera deve arrivare fino al quarto tentativo) è pari a 16 tentativi totali.
Si può facilmente osservare che il secondo metodo converge a una soluzione in maniera regolare e più rapidamente rispetto al primo.
Conclusione – Non esiste numero che io non indovini
In conclusione, per mettere ancora più in evidenza l’enorme differenza di efficienza che è presente tra le due metodologie di ricerca che abbiamo visto con le due attività precedenti, proponiamo la seguente attività alla classe.
L’insegnante chiede alla classe di mettersi d’accordo e pensare a un numero qualsiasi da 0 a 100 e senza rivelarglielo scriverlo su un foglio di carta.
Dopo che gli studenti le hanno dato il via, usando il metodo di ricerca visto nella prima attività, l’insegnante prova a dire dei numeri a suo piacimento compresi tra 0 e 100, (a meno che non sia un insegnante particolarmente fortunato) prima di trovare il numero che hanno scelto gli studenti ci vorranno parecchi tentativi (nel caso peggiore 99).
Mentre se l’insegnante usa l’ingegno, basandosi sul metodo di ricerca visto nella seconda attività è certo che con al massimo 7 tentativi, troverà il numero che la classe ha scelto.
Non è abbastanza per convincervi? Aumentate l’intervallo dei numeri (1000 – 10000 – 100000) e vedrete che usando il secondo metodo di ricerca affrontato vi basterà giusto qualche tentativo in più rispetto ai 7 usati precedentemente per trovarlo con certezza.
ANCHE QUESTA È INFORMATICA!
Con questa semplice attività, gli studenti hanno avuto modo di osservare e esercitarsi sulle tecniche di ricerca di un elemento in una lista di elementi.
I due metodi di ricerca affrontati, sono molto utilizzati anche in Informatica e sono l’algoritmo di ricerca Sequenziale/Lineare e l’algoritmo di ricerca Dicotomica/Binaria.
In realtà, il primo metodo di ricerca che è stato affrontato era di cercare l’elemento facendo scelte successive in maniera casuale (questo per rendere l’attività più divertente) e non di seguire la sequenza esatta degli elementi presenti nella lista. Ma essendo che la password è formata da 4 lettere assolutamente casuali e quindi senza alcuna logica legata alla grammatica italiana o al significato di una parola, è facile vedere che l’efficienza nel trovare un elemento in una lista di elementi è del tutto equivalente.
Mentre il secondo metodo di ricerca si basa sul funzionamento presente nell’algoritmo di ricerca Dicotomica, in cui data una lista di elementi, facendo delle domande / confronti, si vanno a fare dimezzamenti successivi dell’intervallo di ricerca, arrivando molto presto a trovare la soluzione.
