Träd & grafer Flashcards
Vad är några karakteristiska drag för ett träd som datastruktur?
Ett träd har en root node (ingång).
Data lagras hierarkiskt.
Alla noder har en förälder (utom root).
Varje nod kan ha noll eller flera barn.
Noder utan barn kallas “löv”.
Ge exempel på hur träd används i olika sammanhang.
Träd används för att representera:
Linux filsystem
If-satsernas syntax i programmering
SQL-syntax för SELECT-satser
Strukturering av naturligt språk
Organisationshierarkier
Vad är ett träd inom IT?
Ett träd är en av de vanligaste abstrakta datastrukturerna inom IT. Det är en hierarkisk struktur med termer som kommer från genealogi, t.ex. root, node, parent, children och leaves.
Vilka är några användningsområden för trädstrukturer?
Träd används inom:
Filsystem
Kompilatorer (för att analysera programmeringsspråks syntax)
Naturligt språkbehandling
Organisationshierarkier
Sorteringsalgoritmer
m.m
Vilka är vanliga operationer på träd?
Skapa ett träd (create)
Lägg till en ny nod (insert)
Räkna antal noder (size)
Räkna längsta väg (height)
Sök efter en viss nod
Traversera trädet (flera sätt)
Vad är ett binärt träd?
Ett binärt träd är en typ av träd där varje nod har högst två barn. Det används ofta för sortering och parsning.
Hur ser trädet ut efter att noderna 78, 44, 101, 97, 222 har insatts?
Trädet byggs upp enligt följande struktur:
78 är root.
44 är vänster barn till 78.
101 är höger barn till 78.
97 är vänster barn till 101.
222 är höger barn till 101.
Vad gör funktionen ascending_write(node)?
Funktionen traverserar trädet in-order (vänster, root, höger) och skriver ut nodernas data i stigande ordning.
Hur fungerar insättning av noder i ett träd?
Insättningen börjar från root och jämför varje nods värde för att avgöra om den ska placeras till vänster (mindre värde) eller till höger (större värde).
Hur representeras en nod i ett träd med Python?
En nod representeras av en klass Tree med tre attribut: data, left, och right. left och right pekar på barnnoderna.
Hur ser trädet ut efter att noderna 78, 44, 101, 97, 222 har insatts?
Trädet byggs upp enligt följande struktur:
78 är root.
44 är vänster barn till 78.
101 är höger barn till 78.
97 är vänster barn till 101.
222 är höger barn till 101.
Vad består en graf av?
En graf består av:
Noder (vertices): Punkterna i grafen.
Bågar (edges): Linjer som binder samman noderna.
Vilka olika typer av grafer finns det?
Riktade grafer (directed): Bågarna har en riktning.
Oriktade grafer (undirected): Bågarna har ingen riktning.
Viktade grafer (weighted): Bågarna har vikter (kostnader) associerade med sig.
Cykliska grafer (cyclic): Grafer som innehåller cykler.
Acykliska grafer (acyclic): Grafer som inte innehåller cykler.
Hur ser en riktad graf ut?
En riktad graf är en graf där varje båge har en riktning. Exempel på en riktad graf:
Noder: A, B, C, D, E
Bågar: A → B, B → C, C → D, D → E
Hur ser en oriktad graf ut?
En oriktad graf är en graf där bågarna inte har någon riktning. Exempel på en oriktad graf:
Noder: A, B, C, D, E
Bågar: A – B, B – C, C – D, D – E
Vad är en viktad graf och hur används den?
En viktad graf är en graf där varje båge har en vikt (kostnad) associerad med sig. Exempel på användning är att representera avstånd mellan städer. Exempelgraf:
Noder: A (Alingsås), G (Göteborg), J (Jönköping), M (Malmö), S (Stockholm)
Bågar: Alingsås → Göteborg (46), Göteborg → Jönköping (154), etc.
Vad kan grafer användas till?
Grafer kan representera en mängd olika problem. Några exempel:
“Travelling Salesman” problem: Hitta den kortaste rundan som besöker varje stad en gång.
Trafiksignalproblem: Optimering av trafikflöden.
Tillverkningsindustri: Processmodulering och simulering.
Vad är “Travelling Salesman” problem?
Det är ett klassiskt optimeringsproblem där en säljare ska besöka ett antal städer, var och en exakt en gång, och återvända till startstaden på det sätt som ger den kortaste möjliga totalsträckan.
Vad handlar trafiksignalproblemet om?
Trafiksignalproblemet handlar om att använda modeller för att lösa komplexa problem som involverar trafikflöden och optimering av trafiksignaler.
Vilka metoder finns för att söka i grafer?
Djupet-först sökning (DFS): Utforskar så långt ner i grafen som möjligt innan den backar och utforskar nästa väg.
Bredden-först sökning (BFS): Utforskar alla grannar till en nod innan den går vidare till nästa nivå.
Vad är Colossal Cave?
Colossal Cave är det första textbaserade äventyrsspelet, utvecklat 1975. Det anses vara roten till äventyrsspelsgenren och involverar att utforska ett grottsystem som representeras som en graf.
Hur representeras ett grottsystem som en graf?
Ett grottsystem kan representeras som en graf där varje rum är en nod, och varje gång eller passage mellan rum är en båge. Exempelvis kan noderna representera rum och bågarna representerar möjliga vägar mellan rummen.
Hur kan ett grottsystem implementeras i Python?
Genom att skapa en Room-klass som innehåller information om rummet, dess anslutningar (norr, söder, öst, väst), rumsinformation och objekt i rummet. Dessa anslutningar kan representera bågarna i grafen.
Vilka funktioner kan användas för att manipulera ett grottsystem i Python?
Exempel på funktioner:
make_temp_dict(file): Skapar ett temporärt dictionary från filen.
create_graph(temp_dict): Skapar grafen från dictionaryt.
move(direction, location): Flyttar till en annan plats baserat på användarens kommando.
Hur fungerar huvudloopen i grottsystemets Python-implementering?
Huvudloopen körs kontinuerligt och lyssnar på användarens kommando. Baserat på kommandot kan användaren flytta runt i grottsystemet, få hjälp, eller avsluta spelet.
