Lernziele

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? Link
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 ein Beispiel und eine konkrete Situation erklären können. Video von S. Lague

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?

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