Alberi

Da aptiva.
Versione delle 16:38, 6 mag 2015, autore: Savino (Discussione | contributi)

(diff) ← Versione meno recente | Versione attuale (diff) | Versione più recente → (diff)

TITOLO: Alberi


FINALITA': introduzione alla struttura dati albero, alle sue realizzazioni e alle sue visite


OBIETTIVI:

 Elementari: memorizzare i termini utilizzati in letteratura, quali: radice, padre, figlio, foglia, altezza
             classificare i tipi di realizzazioni in base alla struttura del nodo
 Intermedi: Descrivere le istruzioni che compongono lo pseudocodice degli algoritmi di visita in profondità e in ampiezza
 Superiori Convergenti: realizzare l'implementazione degli algoritmi di visita in linguaggio C
 Superiori Divergenti: implementare nuovi algoritmi, a partire da quelli di visita, che forniscano informazioni sulla 
struttura dell'albero (esempio la sua altezza)

PREREQUISITI TEMATICI/DISCIPLINARI:

-Prodotto Cartesiano
-Conoscenza della struttura dati array
-La notazione asintotica O grande
-I paradigmi di programmazione ricorsivi e iterativi
-Conoscenze di programmazione in linguaggio C

STRATEGIE E METODOLOGIE DIDATTICHE


Alberi si, alberi no? Ovviamente non siamo stati catapultati nel bel mezzo di una agguerrita discussione tra ambientalisti e costruttori “affamati” di superfici edificabili. Gli alberi trattati in questa sede sono quelli informatici. Però come i loro omonimi del regno vegetale sono spesso al centro di discussioni tra docenti d'informatica delle superiori. Se per le strutture dati quali liste, pile, code ci si “strappa le vesti” se non sono parte del bagaglio irrinunciabile degli insegnamenti informatici della scuole superiore per gli alberi non si può dire lo stesso. Alcuni docenti li trovano un argomento di “nicchia” che debba essere lasciato solo a coloro che proseguiranno gli studi universitari in corsi d'Informatica e di Ingegneria Informatica. Altri li considerano imprescindibili anche per gli studenti delle superiori e li trattano in modo esaustivo anche dal punto di vista matematico. La mia scelta didattica è quella che debbano essere trattati in modo diverso a secondo del tipo di istituto. Non credo debbano essere trattati in un istituto commerciale o se ne ha il tempo e gli studenti in grado di apprezzarli li si può trattare senza però scendere troppo in particolari. Ad esempio potrebbero essere trattati a livello teorico gli algoritmi di visita in pseudocodice senza una loro implementazione in un linguaggio di programmazione. Cosa diversa per un Istituto Tecnico Industriale ad indirizzo informatico o in un liceo tecnologico. Nel qual caso potrebbe essere interessante non solo illustrare in modo approfondito gli algoritmi di visita in pseudocodice ma anche stimolare gli studenti a rielaborare gli stessi in un linguaggio di programmazione a loro scelta, probabilmente C oppure Java a seconda del curricolo intrapreso. Dopo questa premessa quindi ho individuato come “utenza” dell’attività didattica sugli Alberi la classe quarta di un Istituto Tecnico Industriale ad indirizzo Informatico.

L’organizzazione delle lezioni
Penserei di organizzare le lezioni come segue:

  • Le prime due ore potrebbero essere dedicate ad introdurre in modo informale gli alberi e la loro terminologia. La metologia potrebbe essere: lezione frontale tramite l’uso della LIM o tramite la lavagna d’ardesia. Per iniziare la lezione, in mezzo alla lavagna o alla LIM, il solo titolo della lezione: ALBERI. Di solito c’è sempre lo spiritoso del gruppo e l’assist è troppo invitante perchè non lo utilizzi: “Ma Prof abbiamo sbagliato ora? Questa non è la lezione di scienze”. Sghignazzo generale. Bene è lo spunto che volevo per far partire la mia “chiaccherata” informale sugli alberi. Primo spunto di riflessione è quello di chiedere agli studenti se vi siano degli esempi della realtà, non riconducibili in prima istanza all’ambito informatico e neanche al regno vegetale, in cui abbiano sentito parlare, di alberi. Mi aspetto che almeno di albero genealocico abbiano sentito parlare, magari qualche d’uno porta come esempio l’organizzazione dei tornei di calcio e di tennis. Da questo prendo spunto per iniziare la formalizzare del concetto di relazione gerarchica tra dati. Successivamente cerco di stimolare gli studenti nel ricordare casi concreti di alberi che dovrebbero avere già incontrato nel loro percorso di studi informatici quali: l’albero delle chiamate ricorsive e l’organizzazione del file system. Da questo prendo spunto per completare la formalizzazione degli alberi e della loro terminologia usata in letteratura per caratterizzarli. Questa è un insieme di termini botanici, matematici e di parentela.

DEFINIZIONI: un albero è costituito da una coppia di insiemi N ed A, in simboli T = (N, A), dove N è un insieme di nodi e A è un sottoinsieme del prodotto cartesiano N×N di coppie di nodi (in simboli A⊆N×N) chiamati archi. Dal punto di vista didattico ho preferito questa definizione perché mi permette nelle lezioni sui grafi di far vedere come gli alberi ne sono un loro caso particolare. In ogni albero, esiste un nodo particolare chiamato radice che è l’unico senza genitori. Tutti gli altri ne posseggono uno che da luogo ad una relazione genitore figlio. Un nodo può avere 0 più figli. Il numero dei sui figli viene chiamato grado del nodo. Un nodo che non ha figli si chiama foglia. Continuando nell’esempio dell’albero genealocico ovviamente una foglia è dove la dinastia si interrompe. I nodi che non sono la radice e che non sono foglie vengono definiti nodi interni. In matematica si insegna che dare delle definizioni di entità dicendo cosa non sono è poco corretto. In questo caso però è mi è sembrato opportuno utilizzarla perchè la ritengo la più semplice. Spesso bisogna scendere a compromessi rinunciando a un pò di rigore formale in cambio di semplicità di linguaggio e concettuale.

Albero.jpg

Il livello a cui si trova un nodo è il numero di archi da percorrere per raggiungerlo partendo dalla radice. Ad esempio nella figura disegnata alla lavagna il nodo E si trova al secondo livello perché per raggiungerlo a partire dalla radice A dobbiamo percorrere i due archi (A, B) e (B, E). Analogamente per F, G, H, I ed L che si trovano tutti al secondo livello. Inoltre, in analogia con le relazioni di parentela, nodi allo stesso livello e con lo stesso genitore vengono definiti fratelli. Nel disegno alla lavagna i nodi E, F, G sono tutti allo stesso livello e hanno tutti lo stesso genitore B e quindi sono classificati come fratelli. Inoltre viene definita altezza la massima profondità a cui possiamo trovare una foglia. Nel disegno della lavagna le foglie sono tutte al secondo livello per cui il massimo livello a cui possiamo trovare una foglia è il secondo che quindi è l’altezza dell’albero. Infine un albero in cui tutte le foglie si trovano alla stesso livello viene detto completo. L’albero rappresentato alla lavagna è completo. Se per esempio il nodo D non avesse figli l’albero non sarebbe completo in quanto D diverrebbe foglia ma al livello uno. Il tempo rimanente nelle due ore previste di lezione verrebbe utilizzato per rafforzare questi concetti tramite esempi con alberi di diversa tipologia.

  • Le due ore successive penserei di organizzarle come segue: prima un breve ripasso facendo ripetere, ad un allievo alla lavagna, la terminologia affrontata nella lezione precedente. Successivamente la lezione proseguirebbe con l’obiettivo di formalizzare insieme agli studenti il tipo di dato Albero e le sue operazioni. Questa attività viene seguita da una erogata in modalità trasmissiva, alla lavagna d’ardesia o alla LIM, in cui vengono mostrate alcune delle rappresentazione degli alberi nella memoria dei calcolatori.

Il tipo di dato Albero L’obiettivo come detto è quello di riuscire a fare in modo che siano gli studenti stessi a estrapolare le principali operazioni che la struttura albero possiede. L’idea è quella di formare dei piccoli gruppi eterogenei composti al massimo di quattro elementi. Credo che però se lasciati al solo intuito l’ostacolo che debbano superare sia troppo arduo per cui penso sia opportuno fornire loro una specifica che possa guidarli in modo tale da abituarli anche ad un processo di analisi e progettazione che sicuramente incontreranno nella loro vita professionale.

La specifica potrebbe essere la seguente: “Si progetti una struttura dati che permetta di determinare: il padre di ogni nodo, i figli di ogni nodo e che inoltre consenta di aggiungere e di rimuovere un nodo”

Il pericolo con un specifica come quella riportata sopra è che sia troppo guidata verso la soluzione che ho in mente io impedendo così agli studenti di essere creativi. All’opposto usarne una troppo generica rischia di creare un ostacolo tale da scoraggiare gli studenti che così rinunciano a proporre un loro modello. L’unica considerazione ulteriore che posso fare è che solo i riscontri in aula mi possano fornire quelle informazioni utili a capire se la strada intrapresa è quella corretta.

Dopo aver lasciato i gruppi lavorare in autonomia per circa mezz’ora viene fatto il punto della situazione sulle specifiche elaborate dai vari gruppi. Mi aspetto che più o meno tutti i gruppi siano riusciti vista la specifica abbastanza ridotta ad individuare le quattro operazioni: padre(), figli(), inserisciNodo() e cancellaNodo(). Se qualche gruppo non fosse giunto a nessuna soluzione oppure ad usa soluzione parziale allora sarà necessario un lavoro mirato da parte del docente. E’ comunque richiesta una formalizzazione collettiva per uniformare il nome delle funzioni in modo da evitare la Babele delle interfacce. Alla fine di questa formalizzazione lo pseudocodice della struttura albero potrebbe essere la seguente:

tipoDato Albero:
dati:
//Da definire
operazioni:

  padre(nodo n)
figli(nodo n)
inserisciNodo(nodo n)
cancellaNodo(nodo n)

fine tipoDato

Ovviamente resta da definire la struttura del tipo di dato nodo che dipende da come viene rappresentato l’albero in memoria, argomento questo, del preseguo della lezione.

Le rappresentazioni degli alberi
WORK IN PROGRESS


BIBLIOGRAFIA
Demetrescu C., Finocchi I., Italiano G. F., Algoritmi e strutture dati, Milano, McGraw-Hill, 2004

Strumenti personali
Namespace

Varianti
Azioni
Navigazione
Strumenti