Institute of Theoretical Informatics, Algorithm Engineering

Algorithmen II

  • Type: Vorlesung (V)
  • Semester: WS 17/18
  • Time: 16.10.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude


    17.10.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    23.10.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    24.10.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    30.10.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    06.11.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    07.11.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    13.11.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    14.11.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    20.11.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    21.11.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    27.11.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    28.11.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    04.12.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    05.12.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    11.12.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    12.12.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    18.12.2017
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    19.12.2017
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    08.01.2018
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    09.01.2018
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    15.01.2018
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    16.01.2018
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    22.01.2018
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    23.01.2018
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    29.01.2018
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    30.01.2018
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    05.02.2018
    09:45 - 11:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude

    06.02.2018
    15:45 - 17:15 wöchentlich
    30.46 Chemie, Neuer Hörsaal 30.46 Chemie-Hörsaalgebäude


  • Lecturer: Prof. Dr. Peter Sanders
  • SWS: 4
  • Lv-No.: 24079
Voraussetzungen

Siehe Modubeschreibung.

Literaturhinweise

K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox

Mehlhorn, Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie

Ahuja, Magnanti, Orlin: Network Flows

de Berg, Cheong, van Kreveld, Overmars: Computational Geometry: Algorithms and Applications

Gonzalo Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press

R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

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.

Arbeitsbelastung

Vorlesung mit 3 SWS + 1 SWS Übung.

6 LP entspricht ca. 180 Stunden

ca. 45 Std. Vorlesungsbesuch,

ca. 15 Std. Übungsbesuch,

ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter

ca. 30 Std. Prüfungsvorbereitung

Ziel

Der/die Studierende besitzt einen vertieften Einblick in die theoretischen und praktischen Aspekte der Algorithmik und kann algorithmische Probleme in verschiedenen Anwendungsgebieten identifizieren und formal formulieren. Außerdem kennt er/sie weiterführende Algorithmen und Datenstrukturen aus den Bereichen Graphenalgorithmen, Algorithmische Geometrie, String-Matching, Algebraische Algorithmen, Kombinatorische Optimierung und Algorithmen für externen Speicher.

Er/Sie kann unbekannte Algorithmen eigenständig verstehen, sie den genannten Gebieten zuordnen, sie anwenden, ihre Laufzeit bestimmen, sie beurteilen sowie geeignete Algorithmen für gegebene Anwendungen auswählen. Darüber hinaus ist der/die Studierende in der Lage, bestehende Algorithmen auf verwandte Problemstellungen zu übertragen.

Neben Algorithmen für konkrete Problemstellungen kennt der/die Studierende fortgeschrittene Techniken des algorithmischen Entwurfs. Dies umfasst parametrisierte Algorithmen, approximierende Algorithmen, Online-Algorithmen, randomisierte Algorithmen, parallele Algorithmen, lineare Programmierung, sowie Techniken des Algorithm Engenieering. Für gegebene Algorithmen kann der/die Studierende eingesetzte Techniken identifizieren und damit diese Algorithmen besser verstehen. Darüber hinaus kann er/sie für eine gegebene Problemstellung geeignete Techniken auswählen und sie nutzen, um eigene Algorithmen zu entwerfen.

Prüfung

Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung im Umfang von 120 Minuten nach § 4 Abs. 2 Nr. 1 SPO.

Klausur

Die Klausur findet am 21.02.2018 um 11.30 Uhr statt. Die Hörsaaleinteilung geben wir rechtzeitig bekannt.

Sie können sich vom 08.01.2018 bis einschließlich 14.02.2018 am Studierendenportal  für die Klausur anmelden, die Abmeldung ist bis einschließlich 20.02.2018 möglich. Für Anmeldungen in Papierform gelten dieselben Fristen, bitte geben Sie die Prüfungszulassungen im Sekretariat von Prof. Sanders ab, Gebäude 50.34, Raum 218.

test

Klausur:

Die Hauptklausur findet am 21.02.2018 um 11:30 statt. Die Bearbeitungszeit beträgt 120 Minuten.
Es darf ein doppelseitig handbeschriebenes DIN A4 Blatt mit in die Klausur genommen werden.

Skript:

Skript (Stand: 04.12.2017)

Folien:

Komplett: Folien (Stand: 01.02.2018)
Kapitel 0 (overview): Folien (Stand: 27.11.2017)
Kapitel 1 (algorithm engineering): Folien (Stand: 27.11.2017)
Kapitel 2 (randomized algorithms): Folien (Stand: 07.11.2017)
Kapitel 3 (approximation algorithms): Folien (Stand: 27.11.2017)
Kapitel 4 (stringology): Folien (Stand: 30.11.2017)
Kapitel 5 (rmq): Folien (Stand: 27.11.2017)
Kapitel 6 (bwt and succinct): Folien (Stand: 27.11.2017)
Kapitel 7 (geometric algorithms): Folien (Stand: 30.11.2017)
Kapitel 8 (range search): Folien (Stand: 30.11.2017)
Kapitel 9 (online algorithms): Folien (Stand: 08.12.2017)
Kapitel 10 (parallel algorithms): Folien (Stand: 15.12.2017)
Kapitel 11 (advanced datastructures): Folien (Stand: 18.12.2017)
Kapitel 12 (shortest path algorithms): Folien (Stand: 15.01.2018)
Kapitel 13 (dfs): Folien (Stand: 16.01.2018)
Kapitel 14 (maximum flows and matchings): Folien (Stand: 22.01.2018)
Kapitel 15 (external algorithms): Folien (Stand: 01.02.2018)

Übungen:

Übung 1: Folien (Stand: 14.11.2017)
Übung 2: Folien (Stand: 14.11.2017)
Übung 3: Folien (Stand: 08.02.2018)
Übung 4: Folien (Stand: 05.12.2017)
Übung 5: Folien (Stand: 05.12.2017)
Übung 6: Folien (Stand: 06.12.2017)
Übung 7: Folien (Stand: 20.12.2017)
Übung 8: Folien (Stand: 07.02.2018)
Übung 9: Folien (Stand: 06.02.2018)
Übung 10: Folien (Stand: 06.02.2018)
Übung 11: Folien (Stand: 06.02.2018)
Übung 12: Folien (Stand: 06.02.2018)
Übung 13: Folien (Stand: 06.02.2018)

Übungsblätter:

Übungsblatt 1: Aufgaben (Stand: 30.01.2018) Musterlösung (Stand: 08.02.2018)
Übungsblatt 2: Aufgaben (Stand: 05.12.2017) Musterlösung (Stand: 08.02.2018)
Übungsblatt 3: Aufgaben (Stand: 21.11.2017) Musterlösung (Stand: 30.11.2017)
Übungsblatt 4: Aufgaben (Stand: 16.01.2018) Musterlösung (Stand: 25.01.2018)
Übungsblatt 5: Aufgaben (Stand: 16.01.2018) Musterlösung (Stand: 25.01.2018)
Übungsblatt 6: Aufgaben (Stand: 16.01.2018) Musterlösung (Stand: 25.01.2018)
Übungsblatt 7: Aufgaben (Stand: 30.01.2018) Musterlösung (Stand: 08.02.2018)

Übersicht

Voraussetzungen

Siehe Modubeschreibung.

Literaturhinweise

K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox

Mehlhorn, Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie

Ahuja, Magnanti, Orlin: Network Flows

de Berg, Cheong, van Kreveld, Overmars: Computational Geometry: Algorithms and Applications

Gonzalo Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press

R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

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.

Arbeitsbelastung

Vorlesung mit 3 SWS + 1 SWS Übung.

6 LP entspricht ca. 180 Stunden

ca. 45 Std. Vorlesungsbesuch,

ca. 15 Std. Übungsbesuch,

ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter

ca. 30 Std. Prüfungsvorbereitung

Ziel

Der/die Studierende besitzt einen vertieften Einblick in die theoretischen und praktischen Aspekte der Algorithmik und kann algorithmische Probleme in verschiedenen Anwendungsgebieten identifizieren und formal formulieren. Außerdem kennt er/sie weiterführende Algorithmen und Datenstrukturen aus den Bereichen Graphenalgorithmen, Algorithmische Geometrie, String-Matching, Algebraische Algorithmen, Kombinatorische Optimierung und Algorithmen für externen Speicher.

Er/Sie kann unbekannte Algorithmen eigenständig verstehen, sie den genannten Gebieten zuordnen, sie anwenden, ihre Laufzeit bestimmen, sie beurteilen sowie geeignete Algorithmen für gegebene Anwendungen auswählen. Darüber hinaus ist der/die Studierende in der Lage, bestehende Algorithmen auf verwandte Problemstellungen zu übertragen.

Neben Algorithmen für konkrete Problemstellungen kennt der/die Studierende fortgeschrittene Techniken des algorithmischen Entwurfs. Dies umfasst parametrisierte Algorithmen, approximierende Algorithmen, Online-Algorithmen, randomisierte Algorithmen, parallele Algorithmen, lineare Programmierung, sowie Techniken des Algorithm Engenieering. Für gegebene Algorithmen kann der/die Studierende eingesetzte Techniken identifizieren und damit diese Algorithmen besser verstehen. Darüber hinaus kann er/sie für eine gegebene Problemstellung geeignete Techniken auswählen und sie nutzen, um eigene Algorithmen zu entwerfen.

Prüfung

Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung im Umfang von 120 Minuten nach § 4 Abs. 2 Nr. 1 SPO.