Modulcode:	Inf-BoolSK
Englische Bezeichnung:	Boolean Circuits
Modulverantwortliche(r):	PD Dr. Henning Schnoor
Turnus:	unregelmäßig (WS10/11)
Präsenzzeiten:	2V 1Ü
ECTS:	4
Workload:	120 Std.
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

In der Veranstaltung werden Boolesche Schaltkreise als Berechnungsmodell vorgestellt, sowie effiziente Algorithmen für arithmetische Operationen in diesem Modell betrachtet. Weiter werden untere Schranken für bestimmte Berechnungsprobleme angegeben.

Lernziele:

Die Studierenden können in dem Schaltkreismodell Algorithmen verstehen und entwerfen, sowie deren Komplexität analysieren. Weiterhin lernen sie, für welche Berechnungsfragen es keine sehr effizienten Algorithmen geben kann.

Lehrinhalte:

• Boolesche Schaltkreise als Berechnungsmodell
• Maß für ''Effizienz'' von Schaltkreisen
• Algorithmen für arithmetische Operationen
• Untere Schranken für praktische Probleme
• Generelle obere und untere Schranken für effiziente Algorithmen

Weitere Voraussetzungen:

Prüfungsleistung:

Mündliche Modulprüfung, ggfs. mit Vorleistung durch erfolgreiche Bearbeitung von theoretischen Aufgaben.

Lehr- und Lernmethoden:

Vorlesung, Übung

Verwendbarkeit:

Wahlpflichtmodul im BSc Informatik

Literatur:

Heribert Vollmer ''Introduction to Circuit Complexity. A Uniform Approach'', Springer 1999

Verweise:

Kommentar: