Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2011/12 / Effiziente Funktionale Datenstrukturen


Inhaltsbereich

Effiziente Funktionale Datenstrukturen

Seminar

Aktuelles

  • Alle Vortragenden vom 14.3. können ihre Folien und ihre Ausarbeitung bis zum 28.3. über UniWorX abgeben.
  • Das Seminar findet am 14.3. im Raum 027, Oettingenstr. 67 statt.
  • Alle Vortragenden vom 29.2. können ihre Folien und ihre Ausarbeitung bis zum 14.3. über UniWorX abgeben.
  • Alle Teilnehmer werden gebeten, sich bei UniWorX zum Seminar anzumelden.

 


Inhalt

In diesem Seminar geht es um die Entwicklung von Datenstrukturen, welche kein destruktives Update unterstützen, d.h. Daten können nach ihrer Erzeugung nicht mehr verändert werden, die aber dennoch zur Implementierung effizienter Algorithmen verwendet werden können. Solche Datenstrukturen sind in der funktionalen Programmierung nützlich, in der man oft versucht ohne eine destruktive Veränderung von Daten auszukommen. Mit der zunehmenden Wichtigkeit der parallelen Datenverarbeitung spielen funktionale Datenstrukturen auch in der imperativen Programmierung, z.B. in Java, eine wichtiger werdende Rolle. Funktionalen Datenstrukturen werden hier verwendet, da sie die Handhabung von Nebenläufigkeit erleichtern.

Das Seminar folgt dem Buch

Chris Okasaki
Purely functional data structures
Cambridge University Press, 1998
ISBN 0-521-66350-4

ggf. angereichert um Originalarbeiten.

Das Seminar richtet sich an alle Studenten der Informatik und Medieninformatik, d.h. Studenten der jeweiligen Bachelor-, Master- oder Diplomstudiengänge. Da die Anforderungen für Seminare in den jeweiligen Studienordnungen variieren, wird auch die erforderliche Prüfungsleistung je nach Studiengang angepasst.


Organisation

Anforderungen

  • Vortrag: 30-45 Minuten
  • Ausarbeitung zum Thema
    • Bei einzeln bearbeiteten Kapiteln: 7000-14000 Zeichen
    • Bei zu zweit bearbeiteten Kapiteln: Eine gemeinsame Ausarbeitung mit 14000-20000 Zeichen, in welcher der jeweilige Eigenanteil klar gekennzeichnet ist; oder wahlweise zwei einzelne Ausarbeitungen mit jeweils 7000-14000 Zeichen.
    • Bei Master- und Diplomstudenten werden die Anforderungen mit den Betreuern abgesprochen.

    Zeitplan

    • bis spätestens 4 Wochen vor dem Vortrag: Besprechung mit dem Betreuer zum Thema
    • bis spätestens 2 Wochen vor dem Vortrag: Besprechung eines Entwurfs der Vortragsfolien und evtl. der Ausarbeitung
    • bis spätestens 1 Tag vor dem Vortrag: Vorabversion der Ausarbeitung ins Netz stellen
    • bis spätestens 2 Wochen nach dem Vortrag: Abgabe der Endversion der Ausarbeitung


    Zeit und Ort

    Seminar: Mittwoch, 29. Februar 2012, 10 - 18 Uhr und Mittwoch, 14. März 2012, 10 - 18 Uhr

     


    Planung

    Mittwoch 29.2.

    • Kapitel 3: Some Familiar Data Structures in a Functional Setting
      • Weiß
      • Betreuer: Martin Hofmann
    • Kapitel 4: Lazy Evaluation
      • Seebauer
      • Betreuer: Martin Hofmann
    • Kapitel 5: Fundamentals of Amortization
      • Freitag, Bernhard
      • Betreuer: Steffen Jost
      • Folien
    • Kapitel 6: Amortization and Persistence via Lazy Evaluation
      • Borutta, Lacek
      • Betreuer: Steffen Jost
    • Kapitel 7: Eliminating Amortization (abgesagt)
      • Vortrag abgesagt
      • Betreuer: Steffen Jost
    • Kapitel 8: Lazy Rebuilding
      • Brunner, Straub
      • Betreuer: Ulrich Schöpp
      • Folien: Brunner, Straub

    Mittwoch 14.3

    • Kapitel 9: Numerical Representations
      • Mircheva, Dickhaut
      • Betreuer: Ulrich Schöpp
    • Kapitel 10: Data-Structural Bootstrapping
      • Schmidbartl
      • Betreuer: Andreas Abel
    • Kapitel 11: Implicit Recursive Slowdown
      • Brückner
      • Betreuer: Andreas Abel
    • New catenable and non-catenable deques
      • Barth (Bachelor), Senjak (Diplom)
      • Betreuer: Andreas Abel
    • The String B-Tree: A New Data Structure for String Search in External Memory and its Applications
      • Peetz, Liebhart
      • Betreuer: Martin Hofmann
    • Persistent Union Find
      • Franz, Gabor
      • Betreuer: Steffen Jost
    • Finger Trees
      • Kettelhoit
      • Betreuer: Ulrich Schöpp
    • Suffix Trees, Suffix Arrays
      • Kaltenbacher, Novoseltsev
      • Betreuer: Martin Hofmann

     

    Artikelaktionen


    Funktionsleiste