(Boolesche Funktionen: Algorithmen und Komplexität)

PD Dr.rer.nat.habil. Karl-Heinz Niggl

Vorlesung im Sommersemester 2006 (3V + 1Ü)

Mittwoch, 13.00 - 14.30 Uhr , K2002A
Donnerstag , 11.00 - 12.30 Uhr , HU 129

Inhalt:

Die Realisierung von Schaltungen für strukturierte oder unstrukturierte Boolesche Funktionen ist die Basis für die Konstruktion digitaler Rechner. Die Vorlesung bespricht -- aus theoretischer Sicht -- Verfahren zur Konstruktion und Manipulation von Darstellungen Boolescher Funktionen und komplexitätstheoretische Grenzen solcher Konstruktionen.

Konkrete Themen:

• Boolesche Funktionen und ihre klassichen Darstellungsformen
• Kennzeichnung von Basen für Boolesche Funktionen
• Boolesche Algebren und Funktionen über Booleschen Algebren
• Der Stonesche Darstellungssatz und Repräsentierbarkeit
• Minimalpolynome für Boolesche Funktionen: Berechnung und Komplexität
• Schaltkreise und Komplexitätsklassen für Schaltkreisfamilien
• Schaltkreise für grundlegende Funktionen (z. B. Arithmetik)
• Ordered Binary Decision Diagrams (OBDDs): eine state-of-the-art-Datenstruktur zur Darstellung, Manipulation und Verifikation von Booleschen Funktionen

Boolesche Algebren

Induktive Definition

Grundbegriffe

Anmoderation

Übungsblatt 3

Übungsblatt 2

Übungsblatt 1