Algorithmen II

  • Typ: Vorlesung (V)
  • Lehrstuhl: KIT-Fakultäten - KIT-Fakultät für Informatik - Institut für Theoretische Informatik - ITI Sanders
  • Semester: WS 20/21
  • Zeit: 02.11.2020
    10:00 - 11:30 wöchentlich


    03.11.2020
    16:00 - 17:30 wöchentlich

    09.11.2020
    10:00 - 11:30 wöchentlich

    10.11.2020
    16:00 - 17:30 wöchentlich

    16.11.2020
    10:00 - 11:30 wöchentlich

    17.11.2020
    16:00 - 17:30 wöchentlich

    23.11.2020
    10:00 - 11:30 wöchentlich

    24.11.2020
    16:00 - 17:30 wöchentlich

    30.11.2020
    10:00 - 11:30 wöchentlich

    01.12.2020
    16:00 - 17:30 wöchentlich

    07.12.2020
    10:00 - 11:30 wöchentlich

    08.12.2020
    16:00 - 17:30 wöchentlich

    14.12.2020
    10:00 - 11:30 wöchentlich

    15.12.2020
    16:00 - 17:30 wöchentlich

    21.12.2020
    10:00 - 11:30 wöchentlich

    22.12.2020
    16:00 - 17:30 wöchentlich

    11.01.2021
    10:00 - 11:30 wöchentlich

    12.01.2021
    16:00 - 17:30 wöchentlich

    18.01.2021
    10:00 - 11:30 wöchentlich

    19.01.2021
    16:00 - 17:30 wöchentlich

    25.01.2021
    10:00 - 11:30 wöchentlich

    26.01.2021
    16:00 - 17:30 wöchentlich

    01.02.2021
    10:00 - 11:30 wöchentlich

    02.02.2021
    16:00 - 17:30 wöchentlich

    08.02.2021
    10:00 - 11:30 wöchentlich

    09.02.2021
    16:00 - 17:30 wöchentlich

    15.02.2021
    10:00 - 11:30 wöchentlich

    16.02.2021
    16:00 - 17:30 wöchentlich


  • Dozent: Prof. Dr. Peter Sanders
    Tobias Heuer
    Daniel Seemaier
  • SWS: 4
  • LVNr.: 24079
  • Hinweis: Online
Inhalt

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.

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.

VortragsspracheDeutsch
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.

Organisatorisches

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

Arbeitsaufwand

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

Voraussetzungen

Siehe Modubeschreibung.