Algorithmik

Download der Folien und Übung aus dem Ilias.

1. Algorithmische Grundlagen
   1. Grundbegriffe aus der Algorithmik
      Übung 1: Halteproblem
2. Analyse von Algorithmen
1. Asymptotische Analyse
   Übung 2: Asymptotische Laufzeit
2. Experimentelle Analyse
3. Problemlösen durch Rekursion
4. Binäre Bäume
5. Logische Datenstrukturen (sets, tables, dictionaries, union find)
6. Dictionaries
   1. Binäre Suchbäume
   2. Balancierte Bäume
   3. B-Trees
   4. kd-Bäume
   5. Hashfunktionen und Hashtechniken
7. Priority Queues
   1. Binary Heaps
   2. Binomial-Heaps
   3. Fibonacci-Heaps
   4. Treaps
8. Dynamische Programmierung
   1. Line-Scheduling
   2. Matrix-Chain-Multiplication
   3. Theorie of Dynamic Programming
   4. The 0-1-Knapsack-Problem with Dynamic Programming
   5. Sequence Alignment in Biology
9. Graphen
   1. Eulersche Graphen
   2. Grundlagen zur Tiefen und Breitensuche
   3. Topologisches Sortieren
   4. Kürzeste Wegen durch Topologisches Sortieren
   5. Algorithmus von Dijkstra
   6. All-Pairs-Shortest-Paths
   7. Transitive Hülle in Graphen
   8. Minimum-Cost-Spanning-Tree
   9. Flüsse in Netzwerken. Die Algorithmen von Ford&Fulkerson und Dinitz
   10. Relaxierung in Graphen. Algorithmus von Bellman&Ford
10. Informierte heuristische Algorithmen
    1. Best-First-Search
    2. A*-Algorithmus