Dies ist eine alte Version des Dokuments!
Lernziele
A. Datenstrukturen (Skript Kapitel 4)
- 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
B. Begriffe und Komplexität
- 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.
C. Irrgärten und Pfadfinder-Algorithmen
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. Beispielaufgabe mit Lösung (ETH)
- Wie funktioniert der A*-Algorithmus? Man muss ihn für kleine Beispiele durchführen können.
Sortieralgorithmen
- Was ist ein stabiles bzw. ein instabiles Sortierverfahren?
- Wie funktioniert Selectionsort, welche Komplexität hat er im Best- und im Worst-Case?
- Wie funktioniert Swaport, welche Komplexität hat er im Best- und im Worst-Case?
- Wie funktioniert Bubblesort, welche Komplexität hat er im Best- und im Worst-Case?
- Wie funktioniert Mergesort, welche Komplexität hat er im Best- und im Worst-Case?
Problem des Handlungsreisenden (Traveling Salesman-Problem)
- Das Problem verstehen und Anwendungen dafür kennen.
- Wie viele Touren gibt es bei n Städten theoretisch?
- Erkläre drei Algorithmen, wie man die Ausgangslösunge finden könnte (Nearest Neighbor, Random, Greedy-Algorithmus).
- Das Prinzip des Ameisen-Algorithmus verstehen und erklären können.
- Das Lösungsprinzip von 2-Opt (oder allgemein k-Opt) verstehen und erklären können.
- Was bedeutet Simulated Annealing? Wozu wird es eingesetzt?
Link zu Simulated Annealing und k-Opt: Link zu Simulated Annealing und k-Opt
Möglichkeiten für 3-Opt: Hier