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.