Modulcode:	infAAK-01a
Englische Bezeichnung:	Analysing algorithms and complexity
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	jedes Jahr im SS (SS23 SS24 SS25)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-A (BSc Inf (21)) BSc-WInf-WP-Inf (BSc WInf (21)) MSc-WInf-WP-Inf (MSc WInf (21))
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Das Modul behandelt grundlegende Themen aus dem Bereich der effizienten Algorithmen und der Komplexitätstheorie. Dabei werden zentrale Techniken des Algorithmenentwurfs und der Analyse studiert. Konkret behandelt das Modul die Methoden Divide-and-Conquer, dynamische Programmierung, Greedy-Verfahren, Worst Case, Average Case sowie randomisierte Algorithmen und amortisierte Analyse. Diese Techniken werden angewandt, um grundlegende algorithmische Probleme zu lösen und die Korrektheit der Algorithmen zu beweisen. Des Weiteren werden Grenzen der Algorithmik mit Hilfe der Komplexitätstheorie aufgezeigt, Klassen P und NP, vorgestellt und Reduktionen zwischen Entscheidungsproblemen behandelt. Als Ausblick werden approximative Algorithmen zur Lösung schwerer Optimierungsprobleme vorgestellt.

Lernziele:

Die Studierenden können:

• Laufzeitanalyse von Algorithmen (Best, Worst und Average Case) bestimmen
• algorithmischen Methoden (Divide and Conquer, dynamische

Programmierung, Greedy Algorithmen, Augmentierungen) zur Lösung von Problemen anwenden

• die Korrektheit von Algorithmen beweisen
• Graphalgorithmen entwickln und analysieren
• randomisierten Algorithmen analysieren
• verstehen die Komplexität von Problemen (Klassen P, NP, NP-Vollständigkeit, ETH)

und können Reduktionen zwischen Problemen durchführen

• approximative Algorithmen entwickeln und analysieren

Lehrinhalte:

Weitere Voraussetzungen:

Einführung in die Algorithmik, Mathematik für Informatik A und B

Prüfungsleistung:

Am Ende des Semester wird eine schriftliche Klausur geschrieben. Zum Bestehen der Veranstaltung muss die Klausur bestanden werden. Die Endnote des Moduls ist die Klausurnote.

Die Klausurzulassung wird Ihnen nur erteilt, falls Sie uns überzeugt haben, dass Sie die Klausur auch bestehen können. Deshalb knüpfen wir die Zulassung zur Modulprüfung an folgende Bedingungen:

Sie dürfen in den Hausaufgaben in höchstens drei Aufgabenserien weniger als 40 Prozent der Punkte erreichen, die Sie durch die Aufgaben erreichen können.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Klaus Jansen, und Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, Walter de Gruyter, 2008.

Norbert Blum: Algorithmen und Datenstrukturen: eine anwendungsorientierte Einführung, Oldenbourg 2004.

Thomas H. Cormen, Charles E. Leiserson, und Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, Boston: MIT Press Vol 3, 2009.

Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders: Algorithmen und Datenstrukturen - Die Grundwerkzeuge, Springer Vieweg 2014.

Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen, Teubner 2005.

Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen, Springer Vieweg 2017.

Robert Sedgewick: Algorithms in Java, Parts 1-4, 3rd ed., Addison-Wesley, 2002.

Verweise:

Kommentar: