Studium



WiSe 2019/20












Dieses Modul ist importiert: 0089cA.2.1 Höhere Algorithmik
Qualifikationsziele: Die Studierenden 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.