Next: Über
dieses Dokument
Einführung in die Theoretische Informatik III
SS 1998
Inhaltsübersicht
-
Schaltkreise und Schaltkreiskomplexität
-
Schaltkreise und straight-line-Programme 2.1--2.2
-
Normalformen Boolescher Funktionen, Reduktion 2.3--2.4
-
Spezielle Schaltkreise 2.5
-
Präfix-Berechnungen, Addition, Subtraktion 2.6--2.8
-
Multiplikation 2.9
-
Reziproke und Division 2.10
-
Untere und obere Schranken 2.12--2.13
-
Schaltkreise für algebraische Probleme
-
Matrixmultiplikation 6.1--6.3
-
Transitive Hülle 6.4
-
Matrix-Inversion, lineare Systeme 6.5--6.6
-
Schnelle Fourier-Transformation 6.7
-
Mischen und Sortieren 6.8
-
Komplexitätsklassen
-
Sprachen und Probleme 8.1--8.3
-
Klassifikation 8.5.1--8.5.2
-
Platz-beschränkte Klassen 8.5.3--8.5.5
-
Komplementierung 8.6
-
Reduktion, vollständige Probleme 8.7--8.8
-
P-vollständige Probleme 8.9
-
NP-vollständige Probleme 8.10--8.11
-
PSPACE-vollständige Probleme 8.12
Die numerischen Angaben beziehen sich auf die entsprechenden Kapitel und
Abschnitte des Buches
J.E. Savage, Models of Computation,
Addison-Wesley 1998
Volker Strehl
Thu May 7 10:16:59 MET DST 1998