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

Kurzfassung:

Es werden grundlegende Themen aus dem Bereich der Komplexitätstheorie. 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:

• 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:

Dieses Modul wird ist kein offizieller Bestandteil einer Prüfungsordnung. Es ist insbesondere für die Umsetzung von Übergangsregelungen zur FPO 2021, bzw. dem ab dem Wintersemester 2023/24 gelesenen Modul infAAK-01a: Analyse von Algorithmen und Komplexität.

Außerdem wird das Modul im Rahmen der Anmeldung zur Teilnahme am Modul infAAK-01a: Analyse von Algorithmen und Komplexität verwendet.