Vorlesung über "Modelle Boolscher Formeln - Strukturen und Algorithmen"

Die Vorlesung "Modelle Boolscher Formeln - Strukturen und Algorithmen" untersucht neuere Ansätze zur Lösung des als NP-schwer bekannten Problems Modelle Boolescher Formeln zu bestimmen. Diese auch als SAT-Problem bekannte Thematik bildet den algorithmischen Kern von Problemen mit höchster praktischer Relevanz: Testen von Chips, Aufbau von Expertensystemen oder Lösung komplexer Konfigurationsprobleme. Insbesondere randomisierte Verfahren liefern hier oft sehr schnell gute Lösungen.

Obwohl keine Spezialkentnisse erwartet werden, Grundstudiumskenntnisse in Informatik sind ausreichend, richtet sich die Veranstaltung an StudentInnen, die Interesse haben möglichst schnell forschungsnah zu arbeiten.

Termine

Dienstags 13.30-15.00 Uhr im Seminarraum 616, Pohlighaus.

Literatur

• U. Schöning, Algorithmik (Kap 11), Spektrum Verlag, 2001
• Emo Welzl, Boolean Satisfiability - Combinatorics and Algorithms, Skript ETH Zürich, 2005