Effiziente Algorithmen

Ein zentraler Aspekt bei der algorithmischen Behandlung von Problemen in der Informatik ist die Effizienz. Wie schnell bzw. kostengünstig lässt sich ein Problem lösen? Dabei wesentlich sind die Auswahl geeigneter Datenstrukturen sowie der zugehörige Algorithmenentwurf. Anschließend daran ist eine Problem- und Algorithmenanalyse unerlässlich, bei denen Korrektheit und Effizienz der verwendeten Methoden untersucht werden.

In der Vorlesung werden wichtige Klassen von Algorithmen vorgestellt und analysiert. Die StudentInnen sollen ein vertieftes Verständnis erlangen, welche Datenstrukturen für welche Fragestellungen geeignet sind. Sie sollen einen elementaren Fundus an algorithmischen Techniken erlernen, effiziente Verfahren zu entwerfen und zu analysieren. Schließlich sollen die Grenzen dieser Techniken ausgelotet werden.

Inhalt

In dieser einführenden Veranstaltung werden unterschiedliche Typen von Algorithmen und die ihnen zugrunde liegenden Datenstrukturen und Strategien untersucht. Von Bedeutung sind hierbei Korrektheitsbeweise, die Aufwandsanalyse der Algorithmen sowie der Nachweis oberer und unterer Schranken für die Laufzeit von Lösungsverfahren.

Folgende Themen werden behandelt:

  • die algorithmischen Techniken Greedy, Divide&Conquer, dynamische Programmierung
  • Methoden der Aufwandsanalyse, Rekursionsgleichungen
  • obere und untere Laufzeitschranken
  • Graphenalgorithmen: Tiefensuche, Breitensuche, kürzeste Wege, aufspannende Bäume, Flussprobleme
  • Sortierverfahren
  • Suchverfahren

Zielgruppe

  • Informatik B.Sc. und Diplom PO 2008
    Komplex Grundlagen der Informatik
    Niveaustufe 300
  • Informations- und Medientechnik M.Sc. PO 2008
    Komplex Methodische Grundlagen
    Wirtschaftsingenieurwesen M.Sc. PO 2008
    Vertiefungsrichtung Informatik
  • Modul: Link zu einer externen Seite 11450, 8 KP
  • 4 SWS VL, 2 SWS UE

Voraussetzungen

Die Kenntnis des Modells der Turingmaschine sowie der Begriffe Entscheidungsproblem und Berechenbarkeit wird empfohlen. Zu Beginn der Vorlesung werden diese kurz wiederholt.

Literatur

  • T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Algorithmen - Eine Einführung, Oldenbourg, 2. Auflage, 2007 (sehr empfehlenswert!)
  • N. Blum: Algorithmen und Datenstrukuturen, Oldenbourg, 2. Auflage, 2013
  • V. Heun: Grundlegende Algorithmen, 2. Auflage, Vieweg, 2003
  • R. Sedgewick, K. Wayne: Algorithms, 4th Edition, Addison-Wesley 2011
  • J. Kleinberg und E. Tardos: Algorithm Design, Pearson Education, 2006
  • K. Mehlhorn: Datenstrukturen und effiziente Algorithmen, 3 Bände, Teubner 1988 (englische Version: Data Structures and Algorithms)
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, 3. Auflage, Spektrum Akademischer Verlag 1996