Unplugged

Lezione 3

Far lavorare i computer - gli Algoritmi (I parte)

Obiettivi

Questa lezione è dedicata agli algoritmi in generale: si sperimenta in che cosa consistono, come sia possibile ordinare e ricercare le informazioni nel minor tempo possibile, adoperando tre diversi tipi di ricerca: lineare, binaria e hash.

Attività

Le attività partono dal gioco della battaglia navale eseguito in tre diverse modalità fino ad arrivare ad una riflessione sul funzionamento di uno scanner di codici a barre relativi a prodotti di un supermercato:

Battaglia navale: un gioco a ricerca lineare;
Battaglia navale: un gioco a ricerca binaria;
Battaglia navale: un gioco a ricerca hash;
Riflessione: lo scanner di un supermercato (search key, chiave di ricerca).

Che cos'è un algoritmo?

Un algoritmo è un insieme di istruzioni preparato per completare un lavoro.

Ai computer si richiede spesso di cercare informazioni all'interno di grandi moli di dati; per eseguire questo lavoro essi necessitano di metodi veloci ed efficienti. Esistono vari metodi di ricerca di informazioni, tra cui i più usati sono:

ricerca lineare;
ricerca binaria;
ricerca hash ("mischiare").

1. Battaglia navale: un gioco a ricerca lineare (foglio 1A e 1B)

Obiettivo

Indovinare dov'è la nave del compagno; saper rispondere alle osservazioni.

Istruzioni

Organizzatevi in coppie; uno di voi ha il foglio 1A, l'altro l'1B. Non mostrate il vostro foglio al compagno!
Entrambi cerchiate una delle 26 navi della parte alta del foglio e dite al compagno il numero. Quella sarà la vostra nave.
Adesso prendetevi tutto il tempo per indovinare dove si trova la nave del compagno: a turni uno dice la lettera della nave (da A a Z) e il compagno comunica il numero della nave che corrisponde a quella lettera nel suo schema. Se il numero corrisponde alla nave scelta dal compagno, la nave è affondata se no è acqua. Usate lo schema nella parte bassa del foglio per barrare le varie navi ad ogni tentativo.
Di quanti colpi avete bisogno per localizzare la nave del compagno? Questo è il vostro punteggio di gioco: VINCE CHI HA MENO PUNTI.

Osservazioni

Quale valore potrebbe avere il punteggio minimo e massimo?

2. Battaglia navale: un gioco a ricerca binaria (foglio 2A e 2B)

Obiettivo

Indovinare dov'è la nave del compagno; saper rispondere all'osservazione n.3.

Istruzioni

Le istruzioni per questa versione del gioco sono le stesse di quella precedente tranne che I NUMERI DELLE NAVI SONO IN ORDINE ASCENDENTE (dal più piccolo al più grande).

Organizzatevi in coppie; uno di voi ha il foglio 2A, l'altro l'2B. Non mostrate il vostro foglio al compagno!
Entrambi cerchiate una delle 26 navi della parte alta del foglio e dite al compagno il numero. Quella sarà la vostra nave.
Adesso prendetevi tutto il tempo per indovinare dove si trova la nave del compagno: a turni uno dice la lettera della nave (da A a Z) e il compagno comunica il numero della nave che corrisponde a quella lettera nel suo schema. Se il numero corrisponde alla nave scelta dal compagno, la nave è affondata se no è acqua. Usate lo schema nella parte bassa del foglio per barrare le varie navi ad ogni tentativo.
Di quanti colpi avete bisogno per localizzare la nave del compagno? Questo è il vostro punteggio d igioco: VINCE CHI HA MENO PUNTI.

Osservazioni

Qale strategia hanno usato coloro che hanno fatto meno punti?
Quale nave dovreste scegliere per prima? Quale posizione si dovrebbe scegliere successivamente?
Se si applica questa strategia, qual è il numero MASSIMO di colpi NECESSARIO per colpire la nave?

3. Battaglia navale: un gioco a ricerca hash ("mischiare") (foglio 3A e 3B)

Obiettivo

Trovare la colonna (da 0 a 9) in cui si trova la nave; saper rispondere all'osservazione n.1 e n.2.

Istruzioni

Si prende un foglio come nei giochi precedenti dicendo al compagno il numero della nave scelta.
In questo gioco troverete la colonna (da 0 a 9) in cui si trova la nave scelta dal compagno. Per far ciò occorre semplicemente SOMMARE LE CIFRE DEL NUMERO DELLA NAVE. L'ultima cifra della somma identifica la colonna. Per esempio, per localizzare la nave 2345 occorre sommare 2+3+4+5, il cui risultato è 14. L'ultima cifra è 4, perciò la nave deve essere nella quarta colonna. Una volta identificata la colonna occorre trovare quale nave della colonna è quella giusta.
Giocate usando questa nuova strategia. Si può sfruttare il medesimo foglio per molte volte, basta scegliere la nave da colonne diverse.

Osservazioni

Quali navi sono molto semplici da trovare? Quali navi sono più difficili da trovare?
Quale tra queste strategie di ricerca viste è la più veloce? Perchè?

4. Riflessione: lo scanner di un supermercato (search key, chiave di ricerca)

Si supponga che un supermercato abbia 10000 prodotti differenti sugli scaffali; ogni prodotto è memorizzato nel computer di cassa del supermercato con un codice a barre. Il codice a barre (il prodotto da ricercare) viene definito search key, chiave di ricerca).

Ammettiamo che, quando un codice a barre viene scansionato, il computer adoperi un millesimo di secondo per dare un'occhiata ad ogni prodotto:

quanti secondi occorrerebbero al computer per trovare il prodotto corrispondente con un metodo di ricerca lineare?
quanti secondi gli occorrerebbero invece per trovare il prodotto con un metodo di ricerca binaria? In questo caso, tieni conto del fatto che gli basterebbero 14 soli tentativi.
come dovrebbe essere organizzata la ricerca hash per trovare il prodotto ancora più rapidamente?

Ricerca binaria: come funziona

Google Sites

Report abuse