Humboldt-Universität zu Berlin, Institut für Informatik

Lehrstuhl für Algorithmen und Komplexität II

Vorlesung: Komplexität boolscher Funktionen

Dozenten: Prof. Johannes Köbler und Dr. Wolfgang Lindner
Termin:  VL Do 9-11 (RUD 25, IV.101) J. Köbler / W. Lindner

 Verlegt auf Do 11-13 (Rud. 4.110)
 
Zuordnung: Hauptstudium, kann mit der VL Algorithmisches Beweisen (Teil 1 oder Teil 2) zu einem Halbkurs kombiniert werden.


Inhalte und Lernziele

Die Komplexität einer boolschen Funktion wird u.a. bestimmt durch die Anzahl der Gatter, die ein Schaltkreis benötigt, um diese Funktion zu berechnen. Ein weiteres Komplexitätsmaß ist die minimale Tiefe eines solchen Schaltkreises. In der Vorlesung werden untere und obere Schranken für die Komplexität einfacher Funktionen, wie z.B. Addition und Multiplikation, bewiesen.

B. Bäßler