Algorithmen II

Allgemeines

 

Aktuelles

  • 8. September 2016: Vorlesungsseite angelegt
  • 17. Oktober 2016: Skript und Vorlesungsfolien sind online
  • 19. Oktober 2016: Update Kapitel 2
  • 9. November 2016: Link zu Straßennetzwerken in Übungsblatt 1 korrigiert
  • 9. November 2016: Am Mittwoch, dem 16. November, findet ausschließlich Übung statt. Am Anfang werden wir die Übung von heute abschließen.
  • 16. Dezember: Korrektur der Folien von der Übung 9. Die Präfixsummeneinträge für "große Elemente" wurden korrigiert.
  • 11. Januar: Die Vorlesung am Dienstag, dem 17. Januar, fällt aus. Dafür wird am 18. Januar keine Übung gehalten, sondern 90 Minuten Vorlesung stattfinden.
  • 19. Januar: Die Prüfungsanmeldung ist ab sofort freigeschaltet.
  • 26. Januar: Die Vorlesung am Mittwoch, dem 1. Februar, fällt aus.
  • 2. Fabruar: Als Hilfsmittel ist nur ein DIN-A4 Blatt mit Ihren handschriftlichen Notizen zugelassen.
  • 13. Februar: Folien zu den Kapiteln "Fortgeschrittene Datenstrukturen" und "Approximationsalgorithmen" in die Folien mit allen Kapiteln eingefügt. Bisher waren diese beiden Kapitel ausschließlich als separates Kapitel auf der Website verfügbar.
  • 13. Februar: Update Kapitel 12. Korrektur im Pseudocode zur Berechnung der kleinsten einschließenden Kugel
  • 16. Februar: Korrektur der Musterlösung vom Übungsblatt 6 Aufgabe 3 und der Vorlesungsfolien. In beidem Fällen wurde die Entropie einer Zeichenkette falsch angegeben.
  • 20. Februar: Kurrektur der Musterlösung vom Übungsblatt 4 Aufgabe 3c.
  • 20. Februar: Kurrektur der Musterlösung vom Übungsblatt 5 Aufgabe 9c.
  • 20. Februar: Kurrektur der Musterlösung vom Übungsblatt 7 Aufgabe 7.

 

Klausur

  • Die Ergebnisse der Nachklausur vom 12.09.2017 sind nun online.

 

Lehrinhalt

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt.

 

Mitschnitt der Vorlesung

Die Aufzeichnung der Vorlesungen und Übungen sind hier zu finden.

Externe Applets

Links zu String-Algorithmen

Vorlesungsmaterial

Die Folien der Vorlesung werden nach Kapiteln getrennt online verfügbar sein. Außerdem wird ein Skript angeboten, welches die Themen, die nicht von Algorithms and Data Structures abgedeckt sind, kurz behandelt.

Literaturhinweise

  • K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox
  • K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing  Topic: Algorithm Engineering, Flows, Geometrie
  • R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows
  • M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications
  • G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press
  • R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Klausur am 22.02.2017 um 14.30 Uhr

Hörsaaleinteilung

A bis Fl     Benz, Raum 110, Geb. 10.21
Fr bis Kl    Daimler, Raum 301, Geb. 10.21
Ko bis N    Neue Chemie, Raum 001, Geb. 30.46
O bis Z     Audimax Geb. 30.95

Skript

Skript (Stand: 16.09.2016)

Folien

Komplett: Folien (Stand: 16.02.2017)

Übungen

Übung 0: Folien (Stand: 23.12.2016)
Übung 1: Folien (Stand: 23.12.2016)
Übung 2: Folien (Stand: 23.12.2016)
Übung 3: Folien (Stand: 23.12.2016)
Übung 4: Folien (Stand: 23.12.2016)
Übung 5: Folien (Stand: 23.12.2016)
Übung 6: Folien (Stand: 23.12.2016)
Übung 7: Folien (Stand: 23.12.2016)
Übung 8: Folien (Stand: 23.12.2016)
Übung 9: Folien (Stand: 23.12.2016)
Übung 10: Folien (Stand: 23.12.2016)
Übung 11: Folien (Stand: 11.01.2017)
Übung 12: Folien (Stand: 25.01.2017)
Übung 13: Folien (Stand: 31.01.2017)
Übung 14: Folien (Stand: 14.02.2017)

Übungsblätter

Übungsblatt 1: Aufgaben (Stand: 08.11.2016) Musterlösung (Stand: 08.11.2016)
Übungsblatt 2: Aufgaben (Stand: 21.11.2016) Musterlösung (Stand: 18.11.2016)
Übungsblatt 3: Aufgaben (Stand: 30.11.2016) Musterlösung (Stand: 30.11.2016)
Übungsblatt 4: Aufgaben (Stand: 08.12.2016) Musterlösung (Stand: 20.02.2017)
Übungsblatt 5: Aufgaben (Stand: 21.12.2016) Musterlösung (Stand: 21.02.2017)
Übungsblatt 6: Aufgaben (Stand: 16.02.2017) Musterlösung (Stand: 21.02.2017)
Übungsblatt 7: Aufgaben (Stand: 16.02.2017) Musterlösung (Stand: 20.02.2017)