WiSe 2019/20













Submodule number Course Type Name ECTS SWS / Exam duration
0590aB.1.24.1 Lecture (V) Höhere Algorithmik 0 4.0
0590aB.1.24.2 Practice seminar (Ü) Höhere Algorithmik 0 2.0
0590aB.1.24.3 Module exam Höhere Algorithmik 10 90 min
Qualifikationsziele: Die Studentinnen und Studenten beherrschen die gängigen Entwurfstechniken für Algorithmen und können Algorithmen mit ihrer Hilfe entwerfen. Sie können Algorithmen in Bezug auf ihren Laufzeit- und Speicherbedarf analysieren und dabei auch fortgeschrittene Analysemethoden verwenden. Sie verstehen die Theorie der NP-Vollständigkeit. Sie kennen die gängigen Komplexitätsklassen und können einfache Probleme in ihrer Komplexität einordnen.

Inhalte: Es werden Themen wie: – Wege- und Flussprobleme in Graphen; – String-Matching; – randomisierte Algorithmen; – amortisierte Analyse; – das „Master-Theorem“ zur Analyse von teile-und-herrsche-Rekursionsgleichungen; – NP-Vollständigkeit; – Approximationsalgorithmen für schwere Probleme; – zahlentheoretische Algorithmen (einschließlich RSA-Kryptosystem); – arithmetische Algorithmen und Schaltkreise sowie schnelle Fourier-Transformation behandelt.