KIT | KIT-Bibliothek | Impressum | Datenschutz

Serie: Algorithmen I, Vorlesung, SS 2019

Autor Sinz, Carsten Iser, Markus
Genre Vorlesung
Beschreibung 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. Sanders Springer 2008 Weiterführende Literatur Algorithmen - Eine Einführung T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein Oldenbourg, 2007 Algorithmen und Datenstrukturen T. Ottmann und P. Widmayer Spektrum Akademischer Verlag, 2002 Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen R. Sedgewick Pearson Studium 2003 Algorithm Design J. Kleinberg and É. Tardos Addison Wesley, 2005 Vöcking et al. Taschenbuch der Algorithmen Springer, 2008
Fachgebiete Informatik (inf) (DDC 004)
DOI 10.5445/DIVA/2019-C10
Reichweite Veröffentlichung im Internet
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Series Landing Page