Anmerkung: Diese Liste wird derzeit überarbeitet und erhebt daher keinen Anspruch auf Vollständigkeit.
Bachelorarbeit
Kompakte Kodierungen monotoner boolescher
Funktionen
Autor: David Goergen (Mai 2008)
Eine boolesche Funktion ist monoton, wenn sie sich durch einen kombinatorischen Schaltkreis darstellen lässt, der ausschließlich UND- und ODER-Gatter verwendet. Monotone boolesche Funktionen spielen eine wichtige Rolle in der Komplexitätstheorie und treten in einer Reihe von Anwendungsproblemen auf.
Ziel dieser Arbeit ist es, eine monotone boolesche Funktion, die etwa durch einen Schaltkreis oder ein propositionales Logikprogramm gegeben ist, kompakt zu kodieren, d.h. einen Schaltkreis zu finden, der die Funktion unter Verwendung möglichst weniger Gatter berechnet. Weiterhin soll die Anwendung solcher kompakter Kodierungen auf die Berechnung von Relaxierungsheuristiken in der Handlungsplanung und auf Line-of-Sight-Algorithmen in diskreten 2D-Welten untersucht werden.
