LehreLehrveranstaltungen (Master)
Theorie Boole'scher Schaltkreise

Theorie Boole'scher Schaltkreise

  • Moduldetails

    Dozent: Prof. Dr. Heribert Vollmer

    Frequenz: zweijährlich (gerade) im Sommersemester

    Veranstaltungsart: Vorlesung und Übung (2V + 2Ü, 5 CP)

    Prüfung: mündl. Prüfung

  • Vorlesungsinhalte

    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
  • Informationen zur Prüfung

    Die Abschlussprüfung des Moduls ist eine mündliche Prüfung.

    Termin

    Die Prüfungstermine vergeben wir über eine institutsinterne Website (siehe Link unten). Achtung: Dies ersetzt nicht die Anmeldung der Prüfung im QIS.


    Anmeldung

    Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten).


    Studienleistung

    Falls Ihre Prüfungsordnung eine Studienleistung für dieses Modul vorsieht, kontaktieren Sie bitte den Dozenten.

MATERIALIEN

Alle Materialien finden Sie im Stud.IP.

PRÜFUNGSANMELDUNG

Online-Anmeldung beim Prüfungsamt
Termin für mündliche Prüfung vereinbaren