Home | english  | Impressum | Sitemap | KIT

Algorithmen II

Algorithmen II
Typ: Vorlesung (V)
Semester: WS 16/17
Ort:

Dienstags, 30.46 Hörsaal Neue Chemie

Mittwochs, 50.35 Hörsaal am Fasanengarten

Zeit:

Dienstag und Mittwoch 15:45-17:15 wöchentlich

Beginn: 18.10.2016
Dozent:

Prof.Dr. Peter Sanders
Dr. Simon Gog
Dr. Christian Schulz
Michael Axtmann

SWS: 4
LVNr.: 24079
Prüfung:

Klausur

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 Nachklausur beginnt am Dienstag, den 12.09.2017, um 11:00 Uhr, die Hörsaaleinteilung geben wir noch bekannt. Sie können sich ab 07.07.2017 und bis einschließlich 05.09.2017 am Studierendenportal für die Prüfung anmelden, die Abmeldung ist bis einschließlich 11.09.2017 möglich. Für Anmeldungen in Papierform gelten dieselben Fristen, bitte geben Sie die Prüfungszulassungen im Sekretariat von Prof. Sanders ab (Geb. 50.34, Raum 218). Am Prüfungstag können Sie sich nur noch in dem Hörsaal, in den Sie eingeteilt wurden, bei der Aufsicht abmelden.

 

  • Die reine Prüfungszeit beträgt zwei Stunden. Erfahrungsgemäß muss mit bis zu drei Stunden bis zum Abschluss der Prüfung gerechnet werden.
  • Als Hilfsmittel ist nur ein DIN-A4 Blatt mit Ihren handschriftlichen Notizen zugelassen. Hierbei besteht ein DIN-A4 Blatt aus einer Vorderseite und einer Rückseite!

 

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)
Kapitel 0: Folien (Stand: 31.01.2017)
Kapitel 1: Folien (Stand: 31.01.2017)
Kapitel 2: Folien (Stand: 13.02.2017)
Kapitel 3: Folien (Stand: 31.01.2017)
Kapitel 4: Folien (Stand: 31.01.2017)
Kapitel 5: Folien (Stand: 31.01.2017)
Kapitel 6: Folien (Stand: 08.02.2017)
Kapitel 7: Folien (Stand: 31.01.2017)
Kapitel 8: Folien (Stand: 13.02.2017)
Kapitel 9: Folien (Stand: 31.01.2017)
Kapitel 10: Folien (Stand: 31.01.2017)
Kapitel 11: Folien (Stand: 16.02.2017)
Kapitel 12: Folien (Stand: 13.02.2017)
Kapitel 13: Folien (Stand: 31.01.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)

Ergänzendes Material:

KaHIP BFS: Download (Stand: 27.10.2016)
Folien Burrows Wheeler Transformation: Download (Stand: 11.01.2017)
Compressed Text Indexing: Download (Stand: 31.01.2017)