Über dieses Dokument

Einführung in die Theoretische Informatik III
SS 1998
Inhaltsübersicht

• Schaltkreise und Schaltkreiskomplexität
1. Schaltkreise und straight-line-Programme 2.1--2.2
2.  Normalformen Boolescher Funktionen, Reduktion 2.3--2.4
3.  Spezielle Schaltkreise 2.5
4.  Präfix-Berechnungen, Addition, Subtraktion 2.6--2.8
5.  Multiplikation 2.9
6.  Reziproke und Division 2.10
7.  Untere und obere Schranken 2.12--2.13
• Schaltkreise für algebraische Probleme
1. Matrixmultiplikation 6.1--6.3
2.  Transitive Hülle 6.4
3.  Matrix-Inversion, lineare Systeme 6.5--6.6
4.  Schnelle Fourier-Transformation 6.7
5.  Mischen und Sortieren 6.8
• Komplexitätsklassen
1. Sprachen und Probleme 8.1--8.3
2.  Klassifikation 8.5.1--8.5.2
3.  Platz-beschränkte Klassen 8.5.3--8.5.5
4.  Komplementierung 8.6
5.  Reduktion, vollständige Probleme 8.7--8.8
6.  P-vollständige Probleme 8.9
7.  NP-vollständige Probleme 8.10--8.11
8.  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

• Über dieses Dokument ...

Thu May 7 10:16:59 MET DST 1998