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 Klausur beginnt am Mittwoch, den 22.02.2017, um 14:30 Uhr.
  • Die Nachklausur beginnt am Dienstag, den 12.09.2017, um 11:00 Uhr.
  • Die reine Prüfungszeit beträgt zwei Stunden. Erfahrungsgemäß muss mit bis zu drei Stunden bis zum Abschluss der Prüfung gerechnet werden.
  • Die Prüfungsanmeldung für die Hauptklausur ist ab sofort freigeschaltet. Studierende können sich noch bis zum 15.02.2017 über das Online-Portal anmelden und bei Bedarf bis zum 21.02.2017 von der Anmeldung zurücktreten.
  • Für Studierende, welche sich in Papierform anmelden müssen, gelten die oben genannten Fristen. Falls eine Anmeldung oder Abmeldung in Papierform erfolgt, muss die Zulassung zur Anmeldung sowie die Abmeldung bei Frau Blancani (Raum 218 im Gebäude 50.34) abgegeben 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)