Algorithmen II

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.

Klausur am 19.09.2025

Die Prüfung findet am Freitag, den 19.09.2025, um 8.00 Uhr statt. Die Hörsaaleinteilung veröffentlichen wir rechtzeitig.

Wichtig! Eine direkte Anmeldung über das Studierendenportal ist leider nicht möglich. Wenn Sie das Modul Algorithmen II vor dem 01.04.2025 in Ihrem Prüfungsplan ausgewählt hatten, schreiben Sie bitte an den Informatik-Studiengangservice beratung-informatik does-not-exist.informatik kit edu mit CC an blancani@kit.edu, dort erhalten Sie weitere Infos zur Anmeldung.

Die unten genannten Fristen und sonstigen Infos gelten weiterhin, wir möchten Sie aber darum bitten, sich möglichst zeitnah anzumelden.

Hier die An-/Abmeldedaten:

Anmeldebeginn:  21.06.2025 (0.00 Uhr)
Anmeldeschluss: 11.09.2025 (23.59 Uhr)
Abmeldeschluss: 19.09.2025 (7.59 Uhr)

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.

Fragen rund um das Thema Nachteilsausgleich klären Sie bitte unverzüglich.

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

Klausur am 11.03.2025

Die Ergebnisse sind online im Campus-System einsehbar.  Den Lösungsvorschlag und die Statistik finden Sie hier. Die Klausureinsicht findet am 07.05.2025 von 11.30 bis 12.30 Uhr in Raum 236 im Gebäude 50.34 statt, bitte kommen Sie bis spätestens 12.00 Uhr zur Einsicht und bringen Sie bitte Ihren Studierendenausweis mit.