Boolesche Funktionen: Algorithmen und Komplexität

Wintersemester 2009/2010
Univ.-Prof. Dr. M. Dietzfelbinger

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

Beginn: 13.10. 2009, 13:00 Uhr

Hörer: Studierende der Informatik (Diplom) im Hauptstudium,Teil des Schwerpunkt-/ Ergänzungskomplexes "Theoretische Informatik"

Studierende der Informatik (M.Sc.), als Teil des Vertiefungungsgebietes "Algorithmik und Komplexität"

Inhalte

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

Konkrete Themen:

• - Boolesche Funktionen und Boolesche Formeln
• - Schaltkreise und Straight-Line-Programme
• - Komplexitätsklassen für Boolesche Funktionen
  
  
• - Minimierung zweistufiger Schaltkreise (Ermittlung der Primimplikanten, Aufbau eines Minimalpolynoms)
  
  
• - Konstruktion von Additionsschaltkreisen (Fischer-Ladner)
• - Konstruktion von Multiplikationsschaltkreisen (Karatsuba)
• - Konstruktion von Divisionsschaltkreisen
  
• - Schaltkreise für die (diskrete) schnelle Fouriertransformation

• - Ordered Binary Decision Diagrams: Datenstruktur für Boolesche Funktionen
• - Minimierung und Reduktion
• - OBDD -Synthese
• - Beispiele für minimierte OBDDs: Addition, Speicheradressierung, Multiplikation u.a.
• - Schaltkreisverifikation mit OBDDs
• - Analyse sequentieller Systeme (Schaltwerke) mit OBDDs
  

Termine

• Vorlesung
• Dienstag, 13:00-14:30 Uhr, Sr Bi 13
• Donnerstag, 9:00-10:30 Uhr, Sr Bi 13
  

Kriterien für den Scheinerhalt

Scheinerwerb (Diplom): Fachgespräch, 20 Min., 4SWS

Prüfung (M.Sc.): Mündl. Prüfung, 20 Min., 5LP

Literatur und Links

Literatur wird in der Vorlesung genannt.

Materialien und Übungsblätter

Den Teilnehmern wird ein Script zur Verfügung gestellt.

Skript-Download

Übungen:

Übungsblätter werden nach Bedarf ausgegeben und besprochen.Eigenständige Bearbeitung von Übungsaufgaben und Vortrag dazu ergibt Bonuspunkte für Fachgespräch/Scheinerwerb (Notenverbesserung)

Übungsblatt 1, korrigiert am 29.10.2009

Übungsblatt 2

Übungsblatt 3