Theorie Boole'scher Schaltkreise

Dozent: Prof. Dr. Heribert Vollmer

Frequenz: zweijährlich (gerade) im Sommersemester

Veranstaltungsart: Vorlesung, Übung und Seminar (2V + 1Ü + 2S, 7 CP)

Prüfung: mündl. Prüfung

Das Modul vermittelt vertiefte Kenntnisse über das theoretische Schaltkreismodell. Nach erfolgreichem Abschluss der LV können die Studierenden algorithmische Probleme hinsichtlich ihrer Schaltkreiskomplexität analysieren. Sie beurteilen Konsequenzen von oberen und unteren Schranken im Schaltkreismodell. Sie entwickeln Boole'sche Schaltkreise für neue algorithmische Probleme.

Inhalt:

In dieser Vorlesung werden wir das Berechnungsmodell der Boole'schen Schaltkreise untersuchen. Boole'sche Schaltkreise sind gerichtete azyklische Graphen, in deren Knoten (Gattern) Boole'sche Funktionen (etwa Und, Oder, Nicht) ausgewertet werden. Wir werden verschiedene grundlegende Funktionen (Addition, Multiplikation, Sortieren, etc.) untersuchen und Schaltkreise konstruieren, die diese mit möglichst wenig Gattern oder mit möglichst geringen Pfadlängen zwischen Eingabe und Ausgabe realisieren.

Gliederung:

• Boole’sche Schaltkreise und ihre Komplexitätsmaße
• Schaltkreise für grundlegende Funktionen (Addition, Multiplikation, Threshold)
• Reduktionen
• Reduktionen zwischen grundlegenden Funktionen (iterierte Addition, Multiplikation, Sortieren, iterierte Multiplikation)
• TC0 vs. NC1
• Untere Schranken für allgemeine Schaltkreise (Parity, Threshold)
• Probabilistische Schaltkreise
• Schaltkreise mit MOD-Gattern
• Untere Schranken für AC0(p)
• Schaltkreise und Polynome
• Der Satz von Smolensky