(Plan) Oberseminar

Fortgeschrittene Algorithmen und Datenstrukturen

Motivation und Abgrenzung:

Abstrakten Datentypen wie Folge und total geordnete Menge sind einfach zu spezifizieren und (deswegen!) sehr nützlich. Zur ihrer Anwendung benötigt man aber konkrete Implementierungen. Die einfachsten davon (Bsp: einfach verkettete Liste, AVL-balancierter Suchbaum) werden im ersten und zweiten Semester behandelt. Danach verweist man auf effizientere, aber kompliziertere Implementierungen in Standardbibliothken, ohne diese im Detail zu analysieren. Genau das wollen wir in diesem Oberseminar an einigen Beispielen nachholen und dabei auch Anwendungen fortgeschrittener Programmiertechniken erleben.

Wir wollen jedoch keine Algorithmen und Datenstrukturen betrachten, die für spezielle Anwendungsbereiche angepaßt sind, denn das geschieht schon in den jeweiligen Spezialvorlesungen.

Im Seminar sollen für jede Datenstruktur jeweils eine wissenschaftliche Primärquelle zitiert werden sowie eine Implementierung. Deren Quelltext soll auf eigenem Rechner kompiliert, benutzt und ggf. verändert werden.

Themen:

• Datenstrukturen für
  • Folgen (2/3/4-Bäume, Data.Sequence),
  • Mengen (größenbalancierte Bäume, Data.Set),
  • Mengen von Zahlen (Patricia Tries, Data.IntSet)
  • Prioritätswarteschlangen (Bsp: Braun trees)
• Algorithmen
  • minimum comparison selection, merging, sorting
  • Sortiernetzwerke
  • Sortieren bei sequentiellem Zugriff (tape merging, sorting)
• Methoden und Programmier-Techniken
  • Trennung von Spezifikation und Implementierung durch Schnittstellen (interfaces, Typeklassen)
  • Korrektheit (Struktur-Invarianten) durch starke Typen
  • eigenschaftsbasiertes Testen
  • maximale und amortisierte Komplexität
  • Laufzeit- und Speichermessungen (profiling)
  • Programmablaufsteuerung über Bedarfsauswertung (Streams, Iteratoren)

Quellen:

• Donald Knuth: The Art Of Computer Programming, Band 3 (1973, 1998) https://www-cs-faculty.stanford.edu/~knuth/taocp.html
• Chris Okasaki: Purely Functional Data Structures (1999) https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/
• Beiträge der Kategorie Functional Pearls aus Journal of Functional Programming https://www.cambridge.org/core/journals/journal-of-functional-programming/article-type-collections/functional-pearls
• Quelltexte von Datenstruktur-Bibliotheken und dort angegebene Quellen, Beispiele:
  • java.util.Collections (Josh Bloch, Neil Gafter et al., 1995–) https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/Collections.java,
  • Assorted concrete container types (Daan Leijen et al., 2002–) https://hackage.haskell.org/package/containers

Seminar-Organisation

• eine Konsultation 3 Wochen vor Vortragstermin
• eine Woche vor Vortrag:
  • Zusammenfassung (1 Seiten Text, mit Quellen) an alle anderen Teilnehmer
  • Foliensatz (Arbeitsstand) an Seminarleiter, dieser gibt weiter an zwei anonyme TN, diese schreiben Kurz-Gutachten
• Präsentation und Diskussion im Seminar
• ggf. Überarbeitung bis max. 1 Woche nach Vortrag
• Kurz-Gutachten für zwei andere Vorträge

allgemeines zur Bewertung von Oberseminaren