Lernziele

• Was ist eine Datenstruktur verglichen mit einem Datentyp?
• Die folgenden Datenstrukturen sollten verstanden werden:
  • Liste (Array)
  • Verkettete Liste
  • Stack (Stapel) und Queue (Warteschlange)
  • Graphen
  • Baum also Spezialfall des Graphen
  • Heap als Spezialfall von einem Baum

• Was ist ein Algorithmus?
• Was versteht man unter der Komplexität eines Algorithmus? Für welche Dinge wird die Komplexität angegeben?
• Was sagt die O-Notation für einen Algorithmus aus (Landau-Notation mit dem grossen O)?
• Beispiele angeben können für die verschiedenen Komplexitätsklassen.

Irrgärten erstellen und lösen

• Den Graphen zu einem Irrgarten aufzeichnen können und zu einem Graphen den Irrgarten zeichnen können.
• Unterschied zwischen einem perfekten (oder Standard-) Irrgarten und einem „normalen“ Irrgarten kennen.
• Wie kann man einen Irrgarten erstellen mithilfe des DFS-Algorithmus? Warum und wofür ist hier ein Stack als Datenstruktur ideal?
• Wie funktionieren die Algorithmen „Random-Mouse“, „Hand-on-Wall“, DFS, BFS?
• Welche Algorithmen produzieren den kürzesten Weg?

Allgemeine Pfadfinder-Algorithmen

• Wie funktioniert der Dijkstra-Algorithmus? Man muss ihn für kleine Beispiele durchführen können.
• Wie funktioniert der A*-Algorithmus? Man muss ihn für kleine Beispiele durchführen können.

• Nearest Neighbor, Random, Greedy-Algorithmus verstehen, um die Ausgangslösung zu finden.