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