15 | Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:- Ergebnisüberprüfung (Checkers) und Zertifizierung- Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert- Grundbegriffe des Algorithm Engineering- Effektive Umsetzung verketteter Listen- Unbeschränkte Arrays, Stapel, und Warteschlangen- Hashtabellen: mit Verkettung, linear probing, universelles Hashing- Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort- Selektion: quickselect- Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten- Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit- Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)Literaturhinweise:Algorithms and Data Structures - The Basic Toolbox, K. Mehlhorn und P. SandersSpringer 2008Weiterführende LiteraturAlgorithmen - Eine EinführungT. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein, Oldenbourg, 2007Algorithmen und DatenstrukturenT. Ottmann und P. Widmayer, Spektrum Akademischer Verlag, 2002Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, SuchenR. Sedgewick, Pearson Studium 2003Algorithm DesignJ. Kleinberg and É. Tardos, Addison Wesley, 2005Vöcking et al.Taschenbuch der Algorithmen, Springer, 2008Lehrinhalt:Dieses Modul soll Studierenden grundlegende Algorithmen und Datenstrukturen vermitteln.Die Vorlesung behandelt unter anderem:- Grundbegriffe des Algorithm Engineering- Asymptotische Algorithmenanalyse (worst case, average case, probabilistisch, amortisiert)- Datenstrukturen z. B. Arrays, Stapel, Warteschlangen und Verkettete Listen- Hashtabellen- Sortieren: vergleichsbasierte Algorithmen (z.B. quicksort, insertionsort), untere Schranken, Linearzeitalgorithmen (z.B. radixsort)- Prioritätslisten- Sortierte Folgen,Suchbäume und Selektion- Graphen (Repräsentation, Breiten-/Tiefensuche, Kürzeste Wege, Minimale Spannbäume)- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)- Geometrische Algorithmen