Si consiglia la visione delle attività “La stanza cinese“, “Un robot su Marte” e “La parata dei pinguini” .

Si consiglia la visione dell’attività del gruppo Bebras “Mi dia il resto!” reperibile qui: Bebras dell’informatica — Quesiti d’esempio

Materiale

Archelino di Huch & Games©

Età

A partire dagli 8 anni

Numero di giocatori

Attività per tutta la classe

Attività individuale

Competenze acquisite

Obiettivi di apprendimento al termine della classe terza della scuola primaria

Ambito dati e informazione
O-P3-D-2. Definire l’interpretazione degli oggetti utilizzati per rappresentare l’informazione (legenda)

Attività per spiegare i problemi di soddisfacimento dei vincoli (noti anche come CSP) e i problemi di ricerca in uno spazio degli stati (si tratta di algoritmi introdotti nel capitolo “Risoluzione di problemi”, siccome sono legati all’Intelligenza Artificiale).

Questa attività farà uso delle istruzioni già presenti all’interno del gioco. Andremo ad analizzare alcuni compiti passo per passo.

L’arca può contenere fino a 7 esseri viventi: 1 persona, Noè e 6 animali. Noè dovrà sempre essere messo sulla punta dell’arca girato in modo che osservi gli altri sei posti liberi. Siccome abbiamo sei posti liberi sull’arca e sei animali da posizionare su di essa non rischiamo di lasciare degli animali a terra. Ogni posto sull’arca può ospitare uno qualsiasi dei sei animali, e ogni animale può guardare verso la punta o la coda dell’arca.

La figura 1 e 2 ci mostrano due possibili disposizioni degli animali sull’arca. Nella figura 1 al primo posto abbiamo l’ippopotamo che guarda verso Noè, nella figura 2 abbiamo la zebra che guarda verso la coda dell’arca. Se facciamo una foto all’arca e osserviamo l’immagine appena scattata siamo in grado di dire quale animale ha preso posizione nei posti a sedere numerati dall’1 al 6, verso chi sta guardando, o se il posto è ancora vuoto.

La descrizione della foto prende il nome di stato. La figura 1 indica uno stato, la figura 2 ne rappresenta un altro. Se volessimo provare a scattare le foto di tutte le disposizioni possibili degli animali nei 6 posti a sedere otterremo tantissime foto. Questo gruppo di foto appena scattate prenderebbe il nome di insieme degli stati possibili.

Nella figura 4 (mostrata di seguito) ci vengono dati due suggerimenti per sistemare gli animali sull’arca, che dovranno essere rispettati per poter rendere contenti gli animali.

Se seguiamo il primo suggerimento e andiamo a posizionare il panda nel primo posto, la zebra nel secondo posto e il leone nel terzo posto e scattiamo una foto per vedere lo stato attuale, vedremo che i posti da assegnare sono solo più quelli numerati 4,5 e 6, i primi 3 sono già occupati. Possiamo vedere quindi i suggerimenti come dei vincoli.

In informatica la risoluzione di questi problemi prende il nome di problemi di soddisfacimento dei vincoli, CSP (dall’inglese: constraint satisfaction problem).

I CSP sono definiti da:

• un insieme di vincoli;
• un insieme di variabili.

I vincoli nel nostro caso abbiamo detto che corrispondono ai suggerimenti che ci vengono forniti, l’insieme delle variabili è rappresentato dai 6 posti a sedere.

Trovare la soluzione ad un CSP significa assegnare dei valori alle variabili in modo tale che non venga violato alcun vincolo. A noi persone è sufficiente osservare i suggerimenti per capire come trovare la soluzione a questi CSP, ma per un computer è tutta un’altra storia!

Possiamo formulare un CSP come un problema di ricerca in uno spazio degli stati. In un problema di ricerca in uno spazio degli stati si inizia a partire da uno stato iniziale che corrisponde allo stato in cui non abbiamo ancora fatto nessun assegnamento, sull’arca è presente soltanto Noè.

Esempio di un problema di ricerca in uno spazio degli stati con la figura 14:

Dopo aver assegnato dei valori a tutte le variabili controlleremo se tutti i vincoli sono stati rispettati:

1. il primo vincolo è rispettato poiché gli animali sono inseriti nella posizione che ci viene indicata;
2. anche il secondo vincolo è rispettato poiché il panda può parlare con il canguro.

Abbiamo trovato la soluzione! Gli animali sono ora tutti contenti.