ZurückEsc12510
Abstract Complexity Theory
Abstrakte Komplexitätstheorie
8 LPunregelmäßigDEwird nicht mehr angeboten
Inhalte
Gödelnummerierung, Blumsches Maß, Speed-up-Theorem, Gap-Theorem, Union-Theorem, Naming-Theorem.
Lernziele
Einblick in die Grundlagen der Komplexitätstheorie. Die abstrakte Komplexitätstheorie löst sich ganz von den konkreten Aufwandsmaßen und Modellen. Sie definiert axiomatisch, welche Eigenschaften ein Maß haben soll, und leitet daraus Sätze ab, die für alle (vernünftigen) Maße gelten.
Prüfungsleistung
Prüfungsgespräch benotet
Literatur (1)
- Manuel Blum: A Machine-Independent Theory of the Complexity of Recursive Functions. J. ACM 14(2): 322-336 (1967)
Quelle: Modulbeschreibung der BTU · abgerufen 17.10.2026Original