====== 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? [[https://www.algosome.com/articles/maze-generation-depth-first.html| 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. [[https://ethz.ch/content/dam/ethz/special-interest/baug/ivt/ivt-dam/studies/transport-planning/exercises/2019/u1-musterloesung.pdf|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. [[https://www.youtube.com/watch?v=-L-WgKMFuhE|Video von S. Lague]]

=== 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: [[https://youtu.be/SC5CX8drAtU|Link zu Simulated Annealing und k-Opt]] 

Möglichkeiten für 3-Opt: [[https://www.researchgate.net/profile/Kamran-Zamanifar/publication/251985406/figure/fig2/AS:393200561868801@1470757727174/opt-move-seven-distinct-tour-are-obtained-from-original-tour-We-use-X-X-1-replace-of.png|Hier]]