Si consiglia la visione dell’attività “Unisci i puntini e riproduci le figure“

Materiale

Mappe da stampare

Carta, matita, matite colorate/pennarelli, penna

Matita, matite colorate/pennarelli, penna

Età

A partire dagli 8 anni

Numero di giocatori

Per tutta la classe

Competenze acquisite

Riconoscere usi dell’informatica e delle sue tecnologie nella vita comune

Riconoscere gli elementi algoritmici in operazioni abituali della vita quotidiana

Utilizzare il ragionamento logico per spiegare il funzionamento di alcuni semplici algoritmi

Comprendere che i problemi possono essere risolti mediante la loro scomposizione in parti più piccole

Attività di introduzione ai Grafi e Teoria dei Grafi.

Legenda utile per la comprensione dei fogli presenti in questa attività:

– Area verde (A,B,C,D): rappresenta la terra ferma.
– Area azzurra: rappresenta l’acqua di un fiume.
– Striscia marrone: rappresenta un ponte di legno

Le regole generali per l’attività sono le seguenti:

• L’area Verde (A, B, C, D): è la zona in cui è possibile muoversi/sostare senza alcun problema, in tutta libertà.
• L’area Azzurra: questa zona, a causa dell’alto livello d’acqua e della forte corrente non è possibile attraversarla a nuoto, può essere attraversata solo ed esclusivamente utilizzando un ponte di legno

Questa attività può essere effettuata nuovamente a coppie, come la precedente, o se si preferisce anche singolarmente. Dopo aver letto e spiegato la legenda e le regole generali, assegnate ora la prima mappa a ogni gruppo/studente.

Vediamo chi è in grado di risolvere la seguente sfida: partendo da un punto (A, B, C, D) della mappa a vostro piacimento, trovare un qualsiasi percorso che percorra tutti e 7 i ponti di legno della mappa passando su di essi una e una sola volta (ovvero non passare su un ponte è sbagliato, passare due volte sullo stesso ponte è sbagliato; bisogna passare su tutti i ponti che vedete nella mappa, ma una volta soltanto).

Gli studenti possono utilizzare una matita o penna per tracciare il percorso; eventualmente se dopo un po’ di tentativi la mappa risulta essere troppo scarabocchiata, assegnare loro un foglio nuovo su cui provare (questo vale anche per le mappe successive).

Attenzione, questa sfida non ammette una soluzione. Senza dirlo agli studenti, lasciate loro del tempo per provare e riprovare. Se qualche gruppo/studente dice di aver terminato e essere riuscito a trovare un percorso, osservate bene la soluzione che vi propone, sicuramente ci sarà un errore.

Dopo aver lasciato trascorrere un po’ di tempo l’insegnante può riferire alla classe che effettivamente tale sfida, rispettando le regole viste in precedenza, non ammette alcuna soluzione

Assegnate ora la seconda mappa agli studenti, in questa mappa rispetto alla precedente abbiamo aggiunto un nuovo ponte in legno, che collega la costa di B con la costa di D.

Questa volta promettete agli studenti che delle soluzioni ci sono, basta trovare i punti giusti da cui partire (se si parte dal punto A si arriva sul punto C e viceversa; mentre partendo da B o D non c’è soluzione).

Vediamo chi è in grado di risolvere la sfida: partendo da un punto (A, B, C, D) della mappa a vostro piacimento, trovare un qualsiasi percorso che percorra tutti e 8 i ponti della mappa passando su di essi una e una sola volta (ovvero non passare su un ponte è sbagliato, passare due volte sullo stesso ponte è sbagliato; bisogna passare su tutti i ponti che vedete nella mappa, ma una volta soltanto).

Dopo che un gruppo/studente ha terminato il proprio lavoro, dovrà consegnare la mappa all’insegnante e mostrarle il percorso che ha usato per arrivare alla soluzione.

Il/Lo gruppo/studente che per primo arriva a una soluzione corretta è il vincitore della sfida.

Assegnate ora la terza mappa agli studenti, in questa mappa rispetto alla precedente abbiamo aggiunto un ulteriore nuovo ponte in legno, che collega la costa di A con la costa di B.

Anche questa volta promettete agli studenti che delle soluzioni ci sono, basta trovare i punti giusti da cui partire (se si parte dal punto B si arriva sul punto C e viceversa; mentre partendo da A o D non c’è soluzione).

Vediamo chi è in grado di risolvere la sfida: partendo da un punto (A, B, C, D) della mappa a vostro piacimento, trovare un qualsiasi percorso che percorra tutti e 9 i ponti della mappa passando su di essi una e una sola volta (ovvero non passare su un ponte è sbagliato, passare due volte sullo stesso ponte è sbagliato; bisogna passare su tutti i ponti che vedete nella mappa, ma una volta soltanto).

Dopo che un gruppo/studente ha terminato il proprio lavoro, dovrà consegnare il foglio all’insegnante e mostrarle il percorso che ha usato per arrivare alla soluzione.

Il/Lo gruppo/studente che per primo arriva a una soluzione corretta è il vincitore della sfida.

• Mappa 1: non presenta soluzioni.
• Mappa 2: presenta soluzioni solo se si parte dalla costa A (arrivando su C) oppure partendo dalla costa C (arrivando su A).
• Mappa 3: presenta soluzioni solo se si parte dalla costa B (arrivando su C) oppure partendo dalla costa C (arrivando su B).

Ora, utilizzando di nuovo la terza mappa, (magari dandone una nuova dato che quella in loro possesso sarà pasticciata), proporre ora agli studenti la seguente sfida: abbiamo la possibilità di costruire solo più un ulteriore ponte in legno nella nostra mappa, lo possiamo costruire dove vogliamo, a patto che colleghi due coste.

Domanda:

Dove bisogna posizionare il decimo ponte all’interno della mappa, affinché sia possibile risolvere la sfida ovvero attraversare tutti i 10 ponti una e una sola volta indipendentemente dal punto di partenza? Ovvero che io parta da A oppure B oppure C oppure D riesca sempre ad attraversarli tutti passandoci sopra una e una sola volta? Vediamo chi è in grado di risolvere la sfida.

Quest’ultima attività è più complessa delle precedenti, lasciate loro del tempo; (nel caso in cui nessun studente sembra arrivarci, provate a dare il seguente suggerimento: un lato del nuovo ponte che vogliamo aggiungere deve appoggiare sulla costa C, ora trovate voi l’altra costa su cui far appoggiare il ponte).

Dopo che un gruppo/studente ha terminato il proprio lavoro, dovrà consegnare la mappa all’insegnante e mostrarle dove ha posizionato il decimo ponte e farle vedere che ora effettivamente partendo da qualsiasi parte (A, B, C, D) della mappa si riesce sempre a risolvere la sfida.

Il/Lo gruppo/studente che per primo arriva a una soluzione corretta è il vincitore della sfida.

Una possibile soluzione all’ultima sfida è presentata di seguito, ovvero posizionare il ponte in modo tale che metta in collegamento la costa di B con la costa di C (quello indicato dalla freccia), un possibile percorso è suggerito dalla numerazione inserita. Ovviamente sono possibili diverse soluzioni.

Terminate le prime due attività, il gruppo/studenti che avranno vinto almeno una sfida di tutte quelle viste in precedenza, otterranno delle golose caramelle.

Le due attività appena viste, sono utili per andare a introdurre un concetto fondamentale in informatica ovvero la Teoria dei Grafi che è la disciplina che si occupa dello studio dei Grafi. In informatica un Grafo è formato da un insieme di elementi detti Vertici o Nodi che possono essere collegati tra di loro da linee chiamate Archi o Lati. Graficamente i Vertici/Nodi sono rappresentati con dei cerchi con dentro un nome, che può anche essere una semplicissima lettera o numero; mentre gli Archi/Lati sono delle linee che mettono in collegamento due vertici e delle volte sopra hanno un numero che indica il costo che si ha se lo si percorre. Il numero di archi che confluiscono in un vertice viene chiamato Grado del Vertice.

Nella teoria dei grafi troviamo il seguente enunciato di Eulero:

Un qualsiasi grafo è percorribile se e solo se ha tutti i vertici di grado pari, oppure se solo due di essi sono di grado dispari; inoltre se ci troviamo nel secondo caso per poterlo precorrere è necessario partire da uno di essi e al termine del percorso ci ritroveremo sull’altro vertice dispari.

Questo significa che un grafo che ha:

• Tutti i Vertici di grado pari è sempre percorribile indipendentemente dal vertice da cui si parte.
• Due soli Vertici di grado dispari e tutti gli altri di grado pari è percorribile a patto che si parta da uno dei due vertici di grado dispari e al termine si arriverà sull’altro vertice di grado dispari.
• Tutti i Vertici di grado dispari oppure tre o più vertici di grado dispari non è mai percorribile indipendentemente dal vertice da cui si decide di partire.

In questa attività dove trovo tutto questo?

• Vertici/Nodi: sono l’area verde, ovvero A, B, C, D
• Archi/Lati: sono i ponti di legno

Perché nel nostro mondo innumerevoli situazioni possono essere modellate tramite il loro utilizzo. Esempio: la progettazione delle connessioni di una rete informatica, la progettazione di rotte di navi o aerei, la progettazione di come posizionare le strade in una città, la progettazione della copertura di una rete di trasporti pubblici (metropolitana, pullman, treni), nei giochi (come abbiamo appena visto) e in tantissimi altri contesti.