Vorlesung
Kombinatorische Algorithmen

Sommersemester 2006
Prof. Stefan Felsner

LV-Nr.: 0230 L 253
Di 10-12, MA 642
Do 10-12, MA 142

Inhalt:

Kombinatorische Algorithmen sind, im weiteren Sinn, Algorithmen die auf diskreten, endlichen mathematischen Strukturen operieren. Der Schwerpunkt der Vorlesung wird bei Algorithmen zur Konstruktion, Abzählung und Auflistung von kombinatorischen Objekten liegen. Zusätzlich werden einige Datenstrukturen, Algorithmen auf Strings sowie randomisierte und geometrische Algorithmen behandelt.

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik (ab 4. Semester) und der Informatik (Hauptstudium).
       Diese Vorlesung ist Teil des Studienschwerpunkts Diskrete Strukturen

Übungen:

Di 14-16
MA 142

Scheinbedingungen

Am Anfang jeder Übung gibt es eine Liste, in der alle die Aufgaben ankreuzen, die sie so weit bearbeitet haben, dass sie ihre Lösungen den anderen Teilnehmern in dieser Übung an der Tafel vorführen können. Für den Erwerb des Scheins müssen mind. 66% aller relevanten Aufgaben angekreuzt werden. Auf jedem Blatt ist die relevante Aufgabenanzahl des Blattes vermerkt. Diese Zahl kann auch maximal für dieses Blatt gewertet werden. Kann eine angekreuzte Aufgabe gar nicht oder nur unzureichend vorgeführt werden, so werden alle zu diesem Termin angekreuzten Aufgaben nicht gewertet.

Übungsblätter

Die ps-Quellen der Übungsblätter gibt es hier sobald sie vorliegen (das kann auch schon vor der offiziellen Ausgabe sein). Die bearbeiteten Aufgaben werden während der Übung vorgerechnet und besprochen.
  1. Übungsblatt [ps]

  2. Übungsblatt [ps]

  3. Übungsblatt [ps]

  4. Übungsblatt [ps]

  5. Übungsblatt [ps]

  6. Übungsblatt [ps]

  7. Übungsblatt [ps]

  8. Übungsblatt [ps]

  9. Übungsblatt [ps]

Literatur:

Als Literatur verwende und empfehle ich:
  • Donald E. Knuth: The Art of Computer Programming
    • Volume 3: Sorting and Searching
    • Volume 4, Pre-Fascicle 0b: Boolean Basics
    • Volume 4, Fascicle 2: Generating All Tuples and Permutations
    • Volume 4, Fascicle 3: Generating All Combinations and Partitions
    • Volume 4, Pre-Fascicle 4a: Generating All Trees
  • Herbert S. Wilf: Combinatorial Algorithms An Update
  • Dan Gusfield: Algorithms on Strings, Trees and Sequences
  • Robert E. Tarjan: Data Structures and Network Algorithms
  • Martin Aigner: Combinatorial Search
  • R. Motwani und P. Raghavan: Randomized Algorithms
Zuletzt bearbeitet 18. April 2006