Algorithms II

For news and information about the exam, visit the German version of this page.

 

Below, you'll find the current lecture slides in the form they are used in the lecture this year (password in the Ilias course). These slides are mostly in German. For slides in English we refer to the slides on the page from the WS20/21 (same password). Please note that the slides from the WS20/21 may differ slightly from the current slides in some places.

Klausur am 22.09.2023

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

Hier die An-/Abmeldedaten:
Anmeldebeginn:  11.07.2023
Anmeldeschluss: 17.09.2023
Abmeldeschluss: 21.09.2023
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. Eine Abmeldung ist am Klausurtag nur noch im entsprechenden Hörsaal möglich.

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

Altklausuren gibt es auf unserer Homepage oder einige auch ausgedruckt/zum Download bei der Fachschaft.

 

Klausur am 16.03.2023

Die Prüfung findet am Donnerstag, den 16.03.2023, um 11.30 Uhr statt. Hier die An-/Abmeldedaten:

Anmeldebeginn:   17.12.2022
Anmeldeschluss: 12.03.2023
Abmeldeschluss: 15.03.2023

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

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

Informationen zu etwaigen weiteren Regelungen werden hier veröffentlicht, die Hörsaaleinteilung geben wir rechtzeitig bekannt.

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.