Idéer för aktivt lärande
Träd och grafer tar oss från linjära strukturer till nätverk och hierarkier. Binära sökträd är centrala för att förstå hur datorer snabbt kan hitta information i stora databaser, medan grafer är oumbärliga för att modellera allt från sociala nätverk till rutter i GPS-appar. Detta moment tränar elevernas förmåga att tänka i flera dimensioner.
Aktivitet 01
Eleverna skapar en graf i klassrummet genom att hålla i snören som representerar kopplingar (kanter) mellan varandra (noder). De ska sedan försöka skicka ett meddelande från en sida till en annan med så få hopp som möjligt.
Vad kännetecknar ett binärt sökträd?
Aktivitet 02
Eleverna får lappar med slumpmässiga tal och ska ställa sig i en trädformation. Varje ny elev måste jämföra sitt tal med 'roten' och gå till vänster eller höger tills de hittar sin plats. Detta visar hur trädet växer och hur sökning fungerar.
Hur kan grafer representera sociala nätverk?
Aktivitet 03
Eleverna analyserar hur en plattform som LinkedIn eller Facebook använder grafer för att föreslå 'vänner du kanske känner'. De diskuterar i par hur algoritmen kan hitta kopplingar i andra eller tredje led.
Vilka traverseringsmetoder finns för träd?
Några anteckningar om att undervisa detta avsnitt
Se upp för dessa missuppfattningar
Att ett träd och en graf är samma sak.
Förklara att ett träd är en speciell typ av graf utan cykler och med en rot. Genom att rita exempel på grafer med cirklar ser eleverna när en struktur slutar vara ett träd.
Att binära träd alltid är snabba.
Visa vad som händer om man lägger in tal i storleksordning (trädet blir en lång lista). Diskussioner om 'balanserade träd' hjälper eleverna att förstå vikten av trädets form.
Metoder som används i denna översikt
Listor och arrayer
Studie av linjära datastrukturer som arrayer och länkade listor. Eleverna undersöker hur data lagras i minnet och hur man itererar över dem.
8 methodologies
Stackar och köer
Introduktion till LIFO- och FIFO-principerna genom stackar och köer. Praktiska tillämpningar som ångra-funktioner och utskriftsköer diskuteras.
8 methodologies