Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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

Skript (1. bis 5. Woche)