LEA

Effiziente Algorithmen und Datenstrukturen II

  • Dozent:

    Dr. Riko Jacob
  • Modul:
    IN2004
  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
    Vertiefende Vorlesung im Gebiet Algorithmen
  • Zeit und Ort:
    Dienstag, 10:15-11:45, MI HS 2
    Donnerstag, 10:15-11:45, MI 03.11.18 (Ausweichraum 00.13.009A)
  • Übung:
    2 SWS Übung zur Vorlesung
    Übungsleitung: Matthias Baumgart
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • ECTS: 8 Punkte
  • Voraussetzungen:
    Stoff des Informatik Grundstudiums
    Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
  • Empfehlenswert für:
    Erweiterte Kenntnisse im Bereich Algorithmen
  • Folien:
    Max-Flow / Min-Cut / Min-Cost-Flow

    21. April bis 4. Juni

    Pattern Matching: KMP

    9. Juni

    Boyer-Moore

    16. Juni

    Suffix-Trees: Ukkonens Algorithmus

    18. Juni (V. Heun, pp 218-226)

    Suffix-Trees: McCreight's Algorithmus

    23. Juni (Crochemore / Rytter 'Text Algorithms', pp 81-87)

    Suffix-Trees: Anwendungen

    25. Juni (Gusfield 'Algorithms on Strings, Trees, and Sequences', Chapter 7)

    Suffix-Array: Effiziente Suche

    30. Juni (Gusfield 'Algorithms on Strings, Trees, and Sequences', Chapter 7.14)

    Suffix-Array: Linearzeit Konstruktion

    2. Juli "Linear Work Suffix Array Construction" Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt, Journal of the ACM, Vol. 53, No. 6, November 2006, pp. 918-936. http://doi.acm.org/10.1145/1217856.1217858

    LCP-Array: Linearzeit Konstruktion

    7. Juli "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications" Kasai, Lee, Arimura, Arikawa, and Park Combinatorial Pattern Matching, Springer LNCS 2089 http://dx.doi.org/10.1007/3-540-48194-X_17

    Lowest / Nearest Common Ancestor

    9. Juli "Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment" Alstrup, Gavoille, Kaplan, and Rauhe Theory of Computing Systems, 2004 http://dx.doi.org/10.1007/s00224-004-1155-5

    van Emde Boas Priority Queue

    13. Juli "Design and Implementation of an Efficient Priority Queue" van Emde Boas, Kaas, and Zijlstra Mathematical Systems Theory 10, 1977 http://dx.doi.org/10.1007/BF01683268 und Mehlhorn "Sorting and Searching" Springer ISBN 3-540-13302-X

  • Literatur:
    Die Inhalte der Vorlesung werden in wesentlichen Teilen durch folgende Bücher und Artikel abgedeckt:
    1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.
      The design and analysis of computer algorithms.
      Addison-Wesley Publishing Company: Reading (MA), 1974
    2. Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin.
      Network flows --- Theory, algorithms, and applications.
      Prentice-Hall: Englewood Cliffs, NJ, 1993
    3. Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
      Introduction to Algorithms.
      2. Auflage, The MIT Press, Cambridge, MA, 2001.
    4. Dan Gusfield
      Algorithms on Strings, Trees, and Sequences
      Cambridge University Press, 1999, TUM-Bibliothek Signatur: BIO 110f 2001A 16544 .
    5. Volker Heun
      Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
      2. Auflage, Vieweg: Braunschweig-Wiesbaden, 2003
    6. Donald E. Knuth
      The art of computer programming. Vol. 1: Fundamental algorithms.
      3. Auflage, Addison-Wesley Publishing Company: Reading (MA), 1997
    7. Christos H. Papadimitriou, Kenneth Steiglitz.
      Combinatorial optimization: Algorithms and complexity.
      Prentice-Hall, Englewood Cliffs, NJ, 1982.
    8. Steven S. Skiena.
      The Algorithm Design Manual.
      Springer-Verlag, New York, 1998.
    9. Robert E. Tarjan.
      Data Structures and Network Algorithms.
      CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983.