Themen dieses Kurses

  • Allgemeines

  • Seminar: Entwurf und Analyse von Datenstrukturen

    Umfang:

    5 ECTS, 2 SWS

    Zeit & Ort:

    mittwochs, 14:15 - 15:45 Uhr, E40 (CIP-Pool)

    Voraussetzung:

    Algorithmen und Datenstrukturen

    Zielgruppe:

    BA Inf. und LuR-Inf. ab 2. Semester, MA Inf.

    Dozenten:

    Alexander Wolff, Philipp Kindermann, Krzysztof Fleszar

    Der erste Termin ist am 15. April 2015. An diesem Termin besprechen wir den Ablauf des Seminars und stellen die Vortragsthemen vor. Aus diesem Grund bitten wir um vollständige Anwesenheit.


    Kursinhalte

    In diesem Seminar werden ausgewählte Datenstrukturen behandelt, die dafür entworfen sind, bestimmte Anfragen effizient zu beantworten. Ein Schwerpunkt ist die Analyse von Datenstrukturen für geometrische Anfragen. Thematisch knüpft das Seminar an die Vorlesung "Algorithmen und Datenstrukturen" an.

    Lernziele

    Die TeilnehmerInnen lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen KursteilnehmerInnen in einem Vortrag zu vermitteln. Sie verfügen nach Abschluss des Kurses über Kenntnisse gängiger Datenstrukturen, wie man diese analysiert und wo man sie einsetzt.

    • Themenliste

      Thema Quelle
      1. B-Bäume [CLRS] Kap. 18
      2. Fibonacci-Heaps [CLRS] Kap. 19
      3. Datenstrukturen für disjunkte Mengen [CLRS] Kap. 21
      4. Quad-Trees [dBCvKO] Kap. 14
      5. Highway-Hierarchies [SS]
      6. Dynamische Datenstrukturen für minimale Spannbäume [CH]
      7. Randomisierte Datenstrukturen: Treaps [MR] Kap. 8.(13)
      8. Kürzeste Wege mit negativen Kantengewichten [CLRS] Kap. 24.1 & Prob. 24-1
      9. Die k kürzesten Wege [Epp] Kap. 1–2
      10. Textaufbereitung mit Tries [GT] Kap. 9.2
      11. Matrix-Kettenmultiplikation [CLRS] Kap. 15.2
      12. Matroide Greedy-Theorie [CLRS] Kap. 16.(4–5)
      13. Metaheuristiken und lokale Suche [Tal] Kap. 2.(3–4)
      14. Approximationsalgorithmen für Set Cover [CLRS] Kap. 35.3
      15. Subset Sum: Exakt und approximativ [CLRS] Kap. 35.5
      • Literatur

          • [CH] Chin & Houck (1978). Algorithms for Updating Minimal Spanning Trees. Journal of Computer and System Sciences, 16(1):333–344
          • [CLRS] Cormen, Leiserson, Rivest & Stein (2009). Introduction to Algorithms, Part V: Advanced Data Structures, dritte Ausgabe, MIT Press.
          • [dBCvKO] de Berg, Cheong, van Kreveld & Overmars (2008). Computational Geometry: Algorithms and Applications, dritte Ausgabe, Springer-Verlag.
          • [Epp] Eppstein (1998). Finding the k Shortest Paths. SIAM Journal of Computing, 28(2):652–673
          • [GT] Goodrich & Tamassia (2002). Algorithm Design – Foundations, Analysis and Internet Examples, John Wiley & Sons, Inc.
          • [MR] Motwani & Raghavan (1995). Randomized Algorithms, Cambridge University Press
          • [SS] Sanders & Schultes (2005). Highway Hierarchies Hasten Shortest Path Queries. Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05), volume 3669 of Lecture Notes on Computer Science, pages 568–579, Springer-Verlag.
          • [Tal] Talbi (2009). Metaheuristics – From Design to Implementation, John Wiley & Sons, Inc.