| Kommentar |
Kenntnis der wichtigsten Konzepte und Methoden für Algorithmenentwurf und Komplexitätsfragen, die für das Informatikstudium relevant sind, sowie Kenntnis der wichtigsten Grundlagen und Verfahren der public key Kryptographie, die für Informatiker relevant sind. |
| Literatur |
• S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press.
• O. Goldreich. P, NP, and NP-Completeness: The Basics of Complexity Theory. Cambridge University Press.
• K. Rüdiger Reischuk, Komplexitätstheorie, Teubner Verlag.
• V.V. Vazirani, Approximation Algorithms, Springer-Verlag.
• R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press.
• R.G. Downey, M.R. Fellows, Fundamentals of Parameterized Complexity, Springer-Verlag.
• Salomaa, Public-Key Cryptographie, EATCS Monographs, Springer-Verlag.
• J. Buchmann, Einführung in die Kryptographie, Springer-Verlag.
• H. Delfs, H. Knebl, Introduction to Cryptography, Springer-Verlag.
|
| Lerninhalte |
• Vollständigkeit in verschiedenen Klassen, insbesondere P, NP, PSPACE
• Parallele Algorithmen und Komplexität
• Approximative und randomisierte Algorithmen
• Das PCP-Theorem und Anwendungen
• Parametrisierte und exakte Algorithmen und Komplexitätsklassen
• Klassische Verschlüsselungsverfahren, DES
• Die Idee öffentlicher Schlüssel und das Knapsack-Problem
• Das RSA-Verfahren, Signaturen und Protokolle
• Anwendungen wie electronic banking
|
