Vorlesung: Schaltkreiskomplexität
Dozent: Prof. Johannes
Köbler
Übung: Prof. Johannes
Köbler
| Termine: |
VL VL UE |
Di Do Do |
13-15 13-15 15-17 |
RUD 26, 1'308 RUD 26, 1'308 RUD 26, 1'307 |
J. Köbler J. Köbler J. Köbler |
Inhalte und Lernziele
Thema der Vorlesung ist die Berechnung boolescher Funktionen durch kombinatorische Schaltkreise. Ein Schaltkreis ist ein gerichteter azyklischer Graph, in dessen Knoten (Gatter) boolesche Operationen (z.B. Und, Oder, Nicht) ausgewertet werden. Wir werden Schaltkreise für grundlegende Funktionen (Addition, Multiplikation, Sortieren usw.) konstruieren. Dabei wird sich neben der Größe (Anzahl der benutzten Gatter) auch die Schaltkreistiefe (maximale Pfadlänge) als ein aussagekräftiges Komplexitätsmaß erweisen. Schaltkreisfamilien bilden ein wichtiges Berechnungsmodell für parallele Komplexitätsklassen. Analog zur NP-Vollständigkeit wurde eine Theorie der P-Vollständigkeit entwickelt, um nicht parallelisierbare Probleme identifizieren zu können.Empfohlene Literatur
- H. Vollmer, Introduction to Circuit Complexity, Springer Verlag, 1999.
Aufgabenblätter
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9