Datalogi · Gymnasiet 2 · Datastrukturer · 2.º Período

Träd och grafer

Undersökning av icke-linjära datastrukturer som binära sökträd och grafer. Eleverna lär sig om traversering och nätverksrepresentation.

Kort sammanfattning: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.

• Skolverket Kursplaner
• DAODAT0 - 1. Algoritmer och datastrukturer
• DAODAT0 - 2. Analys av algoritmer

Om detta ämne

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.

I kursen Datalogi lär vi oss hur man navigerar (traverserar) i dessa strukturer. Vi tittar på begrepp som noder, kanter och rötter. Att förstå hur en sökning i ett balanserat träd kan vara extremt snabb jämfört med en lista är en av de viktigaste insikterna för en blivande programmerare.

Eleverna förstår dessa komplexa nätverk bäst när de får rita upp dem, bygga dem fysiskt med snören eller samarbeta för att hitta den kortaste vägen i en mänsklig graf.

Nyckelfrågor

1. Vad kännetecknar ett binärt sökträd?
2. Hur kan grafer representera sociala nätverk?
3. Vilka traverseringsmetoder finns för träd?

Se upp för dessa missuppfattningar

Vanlig missuppfattning

Att ett träd och en graf är samma sak.

Vad man ska lära ut istället

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.

Vanlig missuppfattning

Att binära träd alltid är snabba.

Vad man ska lära ut istället

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.

Idéer för aktivt lärande

Utforskande cirkel

Det mänskliga nätverket

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.

30 min·Hela klassen

Simuleringsövning

Bygg ett binärt sökträd

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.

25 min·Hela klassen

EPA (Enskilt-Par-Alla)

Sociala grafer

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.

20 min·Par

Vanliga frågor

Varför är grafer så viktiga i modern datalogi?

Grafer är grunden för nästan all modern teknologi, från Googles sökalgoritmer (PageRank) till logistiksystem och rekommendationsmotorer. De tillåter oss att modellera komplexa relationer som inte ryms i enkla tabeller.

Hur kan studentcentrerat lärande hjälpa vid undervisning om träd?

Trädstrukturer är svåra att visualisera enbart i kod. Genom att låta eleverna bygga fysiska träd med papper och penna, eller använda interaktiva simuleringar där de kan se hur noder flyttas vid radering, skapas en mental karta som gör kodningen mycket lättare.

Vad är traversering och varför finns det olika sätt?

Traversering är hur vi besöker alla noder i ett träd. Olika ordningar (in-order, pre-order, post-order) används för olika syften, som att skriva ut element i storleksordning eller kopiera ett träd.

Behöver eleverna kunna koda en graf från grunden?

Det viktigaste är att de förstår konceptet och hur man representerar en graf (t.ex. med en närhetsmatris). Att implementera en hel graf-klass kan vara överkurs, men att använda en befintlig är mycket relevant.