Datalogi · Gymnasiet 1 · Datastrukturer och abstraktion · 4.º Período

Träd och grafer

En översikt av hierarkiska och nätverksbaserade datastrukturer. Eleverna utforskar binära träd och enkla grafer för att representera komplexa relationer.

Kort sammanfattning:Träd och grafer representerar mer komplexa, icke-linjära relationer mellan data. I Datalogi 1 får eleverna en introduktion till hur hierarkier (träd) och nätverk (grafer) fungerar. Detta är grunden för att förstå allt från filsystem och HTML-strukturer till sociala nätverk och GPS-navigering.

• Skolverket Kursplaner
• Skolverket DAODAT01: Avancerade datastrukturer.
• Skolverket DAODAT01: Träd- och grafstrukturer.

Om detta ämne

Träd och grafer representerar mer komplexa, icke-linjära relationer mellan data. I Datalogi 1 får eleverna en introduktion till hur hierarkier (träd) och nätverk (grafer) fungerar. Detta är grunden för att förstå allt från filsystem och HTML-strukturer till sociala nätverk och GPS-navigering.

Eleverna lär sig begrepp som noder, kanter, rötter och löv. Fokus ligger på att förstå hur dessa strukturer kan användas för att organisera information effektivt, till exempel genom binära sökträd som snabbar upp sökningar. Kursplanen betonar användningen av avancerade datastrukturer för att lösa komplexa problem. Genom att rita och bygga egna nätverk får eleverna en visuell och praktisk förståelse för hur sammankopplad data fungerar.

Nyckelfrågor

1. Vad är en nod och en kant i en graf?
2. Hur fungerar ett binärt sökträd?
3. Hur kan grafer användas för att hitta den kortaste vägen?

Se upp för dessa missuppfattningar

Vanlig missuppfattning

Att ett träd kan ha cykler (loopar).

Vad man ska lära ut istället

Elever blandar ofta ihop träd och grafer. Genom att visa att ett träd alltid har en tydlig hierarki uppifrån och ner, medan en graf kan vara helt sammanflätad, blir den strukturella skillnaden tydlig.

Vanlig missuppfattning

Att noder i en graf måste vara fysiska platser.

Vad man ska lära ut istället

Många tror att grafer bara handlar om kartor. Genom att använda exempel som 'vänner på Facebook' eller 'länkar mellan webbsidor' förstår de att noder kan representera vad som helst.

Idéer för aktivt lärande

Utforskande cirkel

Släktträd och filsystem

Eleverna får i uppdrag att rita upp strukturen på sin egen dators mappar eller ett fiktivt släktträd. De ska identifiera rot-noden, föräldra-noder och barn-noder för att förstå hierarkin.

40 min·Smågrupper

Simuleringsövning

Kortaste vägen i klassrummet

Eleverna skapar en mänsklig graf där de är noder och håller i snören (kanter) med olika längder (vikter). De ska sedan samarbeta för att hitta den snabbaste vägen mellan två elever i nätverket.

45 min·Hela klassen

EPA (Enskilt-Par-Alla)

Binära sökträd

Eleverna får en serie tal och ska individuellt rita hur de placeras i ett binärt sökträd. De jämför sina träd i par och diskuterar varför ordningen man lägger till talen spelar roll för trädets form.

30 min·Par

Vanliga frågor

Vad är skillnaden mellan ett träd och en graf?

Ett träd är en typ av graf som är hierarkisk, har en rot och saknar cykler (man kan inte gå runt i cirklar). En graf är mer generell och kan ha noder som är kopplade till varandra på vilket sätt som helst, inklusive loopar.

Varför används binära sökträd?

De används för att lagra data så att det går mycket snabbt att hitta, lägga till eller ta bort värden. Genom att alltid ha mindre värden till vänster och större till höger kan man halvera sökområdet i varje steg, precis som vid binärsökning.

Hur kan aktivt lärande hjälpa eleverna att förstå grafer?

Grafer är visuella till sin natur. Genom att låta eleverna fysiskt bygga nätverk med garn eller rita dem på stora papper, ser de sambanden mellan noder och kanter tydligare. Det gör det lättare att förstå algoritmer för t.ex. ruttplanering när de ser vägarna framför sig.

Vad är en 'viktad' graf?

I en viktad graf har varje kant ett värde (en vikt), till exempel avståndet mellan två städer eller tiden det tar att skicka data. Detta är avgörande för att kunna räkna ut den mest effektiva vägen genom ett nätverk.