Algorithmen II

Klausur am 14.03.2024

Die Prüfung findet am Donnerstag, den 14.03.2024, um 8.00 Uhr statt.

Hier die An-/Abmeldedaten:
Anmeldebeginn:  16.01.2024
Anmeldeschluss: 10.03.2024
Abmeldeschluss: 13.03.2024

Eine Abmeldung am Klausurtag ist nur noch im Hörsaal möglich.

Diese Fristen gelten auch für Anmeldungen in Papierform, bitte schreiben Sie frühzeitig an Anja Blancani (blancani does-not-exist.kit edu), falls Sie eine Prüfungszulassung abgeben müssen.

Bitte melden Sie sich unbedingt an, eine Teilnahme ohne Anmeldung kostet Zeit und verursacht erheblichen Aufwand.

Die Hörsaaleinteilung geben wir rechtzeitig bekannt.

Die Bearbeitungszeit beträgt 120 Minuten. Es darf ein doppelseitig handbeschriebenes DIN-A4-Blatt mit in die Klausur genommen werden.

 


 

Aktuelles

  • 06.12.2023: Wegen widersprüchlicher Aussagen zum Fortschritt der Vorlesung: Die Vorlesungen der KWen 48 und 49 haben Kapitel 6 (Randomisierte Algorithmen) und Kapitel 8 (Approximationsalgorithmen) vollständig behandelt. Die Vorlesung am 11.12. wird also das Kapitel 7 (Externe Algorithmen) behandeln.
  • 11.12.2023: Wegen Krankheit wird die heutige Vorlesung in Vertretung das Kapitel 9 behandeln.
  • 16.01.2024: Die Vorlesungsfolien und Folien für die Übung vom 15./16.01. können temporär hier (Vorlesung, Übung, Übung (Fortsetzung)) heruntergeladen werden.
  • 22.01.2024: Die Altklausuren mit Musterlösung befinden sich hier. Unseres Wissens nach gibt es bei der Fachschaft umgebrochene Versionen zum Üben, in denen Aufgabenstellung und Lösung getrennt sind.

Skript

Skript (Stand: 13.09.2023)

Folien

Komplett: Folien (Stand: 30.10.2023)

Kapitel 0 (overview): Folien (Stand: 24.10.2023)
Kapitel 1 (algorithm engineering): Folien (Stand: 30.10.2023)
Kapitel 2 (advanced datastructures): Folien (Stand: 30.10.2023)
Kapitel 3 (shortest path algorithms): Folien (Stand: 14.11.2023)
Kapitel 4 (dfs): Folien (Stand: 14.11.2023)
Kapitel 5 (maximum flows and matchings): Folien (Stand: 21.11.2023)
Kapitel 6 (randomized algorithms): Folien (Stand: 28.11.2023)
Kapitel 7 (external algorithms): Folien (Stand: 19.12.2023)
Kapitel 8 (approximation algorithms): Folien (Stand: 04.12.2023)
Kapitel 9 (fixed parameter algorithms): Folien (Stand: 11.12.2023)
Kapitel 10 (parallel algorithms): Folien (Stand: 11.12.2023)
Kapitel 12 (geometric algorithms): Folien (Stand: 22.01.2024)
Kapitel 13 (online algorithms): Folien (Stand: 29.01.2024)
Kapitel 14 (stringology 1): Folien (Stand: 08.01.2024)
Kapitel 15 (stringology 2): Folien (Stand: 09.01.2024)
Kapitel 16 (stringology 3): Folien (Stand: 17.01.2024)

Übungen

Übung 1: Folien (Stand: 31.10.2023) Handout (Stand: 31.10.2023)
Übung 2: Folien (Stand: 07.11.2023) Handout (Stand: 07.11.2023)
Übung 3: Folien (Stand: 14.11.2023) Handout (Stand: 14.11.2023)
Übung 4: Folien (Stand: 21.11.2023) Handout (Stand: 21.11.2023)
Übung 5: Folien (Stand: 31.10.2023) Handout (Stand: 31.10.2023)
Übung 6: Folien (Stand: 05.12.2023) Handout (Stand: 05.12.2023)
Übung 7: Folien (Stand: 12.12.2023) Handout (Stand: 12.12.2023)
Übung 8: Folien (Stand: 19.12.2023) Handout (Stand: 19.12.2023)
Übung 9: Folien (Stand: 18.01.2024) Handout (Stand: 18.01.2024)
Übung 10: Folien (Stand: 30.01.2024) Handout (Stand: 30.01.2024)
Übung 11: Folien (Stand: 30.01.2024) Handout (Stand: 30.01.2024)
Übung 12: Folien (Stand: 07.02.2024) Handout (Stand: 07.02.2024)
Übung 13: Folien (Stand: 13.02.2024) Handout (Stand: 13.02.2024)

Übungsblätter

Übungsblatt 1: Aufgaben (Stand: 01.02.2024) Musterlösung (Stand: 01.02.2024)
Übungsblatt 2: Aufgaben (Stand: 14.11.2023) Musterlösung (Stand: 24.11.2023)
Übungsblatt 3: Aufgaben (Stand: 01.02.2024) Musterlösung (Stand: 01.02.2024)
Übungsblatt 4: Aufgaben (Stand: 01.02.2024) Musterlösung (Stand: 01.02.2024)
Übungsblatt 5: Aufgaben (Stand: 19.01.2024) Musterlösung (Stand: 19.01.2024)
Übungsblatt 6: Aufgaben (Stand: 15.02.2024) Musterlösung (Stand: 15.02.2024)

Beschreibung

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.

Vortragssprache Deutsch
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.