Modulcode:	infAAK_A-01a
Englische Bezeichnung:	Analysing algorithms and complexity
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:

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.

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

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.