|
Camminare a Manhattan e... ... gli algoritmi ricorsivi |
|
|
|
Di seguito viene riportata una breve introduzione a ciascuna lezione, con una sintesi dei contenuti, degli obiettivi formativi perseguiti, dei collegamenti argomenti del programma di matematica o di fisica, ed, infine, con i riferimenti alle schede per il docente e i discenti, contenute negli allegati dell'’Unità di Lavoro. Per una descrizione maggiormente dettagliata di ciascuna lezione, si rimanda alla relativa scheda per il docente.
Lezione 1
•
riflettere sul
problema della rappresentazione e manipolazione della conoscenza; •
riconoscere
nell’algoritmo una possibile soluzione ad un dato problema. argomenti collegati: •
ordinamenti e
insiemi ben ordinati; •
problemi di
ottimizzazione, o di minimo; •
distanze
non euclidee nel piano; materiali in allegato: •
scheda
1d: descrizione
dettagliata della lezione (docente); •
scheda
1s: testo del
problema e consegne (discenti). Lezione
2
Nella seconda lezione, viene discussa una caratterizzazione dei cammini
minimi, strumento necessario per conoscere più a fondo il problema in
esame, e per giustificare i passi che porteranno ad una sua successiva
soluzione. obiettivi informatici: •
saper
operare su modelli alternativi che rappresentano le conoscenze intorno
al problema; argomenti collegati: •
algebra
vettoriale; •
gruppo delle
traslazioni del piano; materiali in allegato: •
scheda
2d: descrizione dettagliata della lezione (docente). In questa terza lezione,
dai risultati teorici precedentemente acquisiti e dalle intuizioni nate
intorno agli esempi discussi, viene derivato l'algoritmo ricorsivo che
risolve il problema “Manhattan”. obiettivi informatici: •
riconoscere
gli elementi dell’architettura di un algoritmo ricorsivo; •
saper
applicare le regole del dato algoritmo ricorsivo; •
riflettere
sul problema della terminazione dell’algoritmo. argomenti collegati: •
successioni
definite per ricorrenza. materiali in allegato: • scheda 3d: descrizione dettagliata della lezione (docente). Lezione
4
La quarta lezione, prevede
l’esecuzione di un gioco di ruolo che vede i discenti simulare in prima
persona l’algoritmo ricorsivo derivato nella precedente lezione. L’obiettivo
del gioco è quello di far riflettere sui complessi meccanismi che si nascondono
dietro la pur semplice formulazione dell’algoritmo. obiettivi informatici: •
riconoscere
nel gioco di ruolo e nelle sue regole, un modello analogo al problema dato e
all’algoritmo che lo risolve; •
riconoscere
la complessità di operazioni necessarie all’esecuzione dell’algoritmo
ricorsivo trovato; materiali in allegato: •
scheda
4d: descrizione dettagliata della lezione (docente); •
scheda
2s: regole
del gioco di ruolo, e consegne (discenti). argomenti collegati: •
il triangolo
di Pascal. La quinta lezione
è divisa in due parti. Nella prima parte il docente introduce le funzioni
ricorsive nel linguaggio Pascal, mostrando
alcuni esempi classici che illustrano come tali funzioni possano essere
utilizzate per implementare algoritmi ricorsivi. Successivamente, ha luogo
l'attività in laboratorio di informatica, in cui i vari gruppi di lavoro
formati dai discenti, realizzano un programma che permetta l’implementazione
dell'algoritmo ricorsivo soluzione del problema “Manhattan”. Tale attività
si conclude con una relazione finale. obiettivi informatici: •
conoscere la
sintassi e la semantica delle funzioni ricorsive in Pascal; • saper realizzare una funzione ricorsiva che implementi l’algoritmo sviluppato per il problema in esame; • saper utilizzare il calcolatore per studiare empiricamente un algoritmo; •
riflettere sul problema del tempo di esecuzione
dell’algoritmo. materiali in allegato: •
scheda
5d: descrizione
dettagliata della lezione (docente); •
scheda
3s: consegne
per l’attività in laboratorio (discenti); Lezione
6
La sesta lezione viene presentata la dimostrazione
del fatto che l'algoritmo ricorsivo che risolve il problema “Manhattan”
termina in un numero finito di passi, qualunque sia la condizione di partenza. obiettivi informatici: •
Saper
dimostrare la terminazione dell’algoritmo dato; •
Riconoscere
l’analogia tra la funzione definita per ricorsione e il principio di induzione; argomenti collegati: •
principio
di induzione; materiali in allegato: •
scheda
6d: descrizione
dettagliata della lezione (docente). Nella settima lezione, vengono presentati 4 nuovi problemi “ricorsivi”:
un problema di tassellazione dello spazio, un problema combinatorio, un
problema di ricerca binaria e il classico problema della Torre di Hanoi.
A conclusione della lezione, se i discenti possiedono qualche conoscenza
di calcolo combinatorio, potrebbe essere presentata la soluzione combinatoria
del problema “Manhattan” e/o una soluzione con un algoritmo iterativo
iterativo. obiettivi informatici: •
riflettere
sulla potenza dell’approccio ricorsivo per la risoluzione dei problemi di varia
natura, •
apprendere
un algoritmo di ricerca binaria. argomenti collegati: •
problemi
combinatori, calcolo combinatorio, matrici; •
partizioni di
un insieme, •
ordinamenti. materiali in allegato: •
scheda
7d: descrizione
dimostrazione alternativa al problema (docente); •
scheda
8d: carrellata di nuovi problemi ricorsivi (docente). Lezione
8 (verifica finale)
L’ultima
attività dell’Unità di Lavoro, prevede una verifica finale articolata
in due momenti distinti. La prima fase consiste in una verifica scritta,
della durata di un’ora, che vuole evidenziare le competenze che ciascun
discente ha acquisito. La consegna potrà prevedere, ad esempio, l’analisi
un algoritmo ricorsivo, la discussione del problema del raggiungimento
o no delle condizioni di terminazione, la realizzazione di un algoritmo
che generi una qualche sequenza di numeri (ad esempio i numeri di Fibonacci). Nella seconda fase, della durata di un’ora e
possibilmente contigua alla precedente, si vuole verificare le abilità
operative relative all’implementazione di un algoritmo ricorsivo e all’uso
del calcolatore per condurre un’analisi empirica di un dato algoritmo.
L’attività prevede che i discenti, divisi in gruppetti di due o tre componenti,
implementino e analizzino gli algoritmi relativi alla prima fase della
verifica, e stilino, entro il termine prestabilito, una relazione dei
risultati ottenuti con il calcolatore, che integrerà l’elaborato della
prima fase. materiali in allegato:
|
