PD Dr. rer. nat. K.-H. Niggl

(Sprechzeiten: Mittwoch, 11- 13 Uhr)

Vorlesung im SS 2005 (3V + 1Ü)
Mittwoch: 17:00- 18:30 Uhr, Raum ZHS 010
Donnerstag: 9:00- 10:30 Uhr, Raum ZHS 013

ACHTUNG !!

Als Ersatz für die Vorlesung am 4.5.2005 findet am Freitag, dem 27.5.2005 um 11:00-12:30 Uhr eine Ersatzvorlesung im Raum Curiebau Sr 113 statt!

Beginn: Donnerstag, den 6. April

Inhalt:

Die Realisierung von Schaltungen für strukturierte oderunstrukturierte Boolesche Funktionen ist die Basis für die Konstruktiondigitaler Rechner. Diese Vorlesung bespricht -aus theoretischerSicht- Verfahren zur Konstruktion und Manipulation von Darstellungen Boolescher Funktionen und komplextheoretische Grenzen solcher Konstruktionen.

Konkrete Themen:

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

Hörer: Studierende der Informatik und Mathematik im Hauptstudium

Scheinerwerb: Fachgespräch

Dokumente zur Vorlesung

Asymptotische Notation und wichtige o-Klassen

Boolesche Algebren
Rechenregeln, Satz von Stone und Repräsentierbarkeit

"Anmoderation"

Primimplikanten und Minimalpolynome
Der Algorithmus QC von Quine/McClusky

Berechnung des Primimplikatenpolynoms
Die Algorithmen BM (Baummethode), IK (Iterierter Konsensus) und DP (Doppeltes Produkt)

Übungsblätter

Übungsblatt 1

Übungsblatt 2

Übungsblatt 3
(Besprechung: 19.5.05)

Übungsblatt 4
(Besprechung am 2.6.05)

Übungsblatt 5