Links und Funktionen
Sprachumschaltung
Navigationspfad
You are here: Home / Teaching / Winter 2015/16 / SAT Solving
Inhaltsbereich

SAT Solving

Lecture with Tutorial, 3+1 hours, Tu. 4-6pm, Th. 2-4pm, Johannsen
Content | Organisation | Time and Place | Material | Tutorials | Exam

News

All questions answered on Thursday, Feb 04. Please send questions to Christian.

Content

The satisfiability problem for classical propositional logic (SAT) is the canonical NP-complete problem, therefore algorithms for solving it are of essential importance for theoretical computer science, their development and study forms an entire area of research.

Recently there has been a lot of progress in this area, in theory as well as in practice. On the theoretical side, there are new algorithms for which worst-case upper bounds on the run-time can be proven, that are better than the obvious O(2n) for brute-force search. The current best such (probabilistic) algorithms have a run-time of O(1.308n) for 3-SAT and O(1.469n) for 4-SAT.

On the other hand, there are very good heuristics and implementations for the classic backtracking algorithms (DPLL), which can solve even very large inputs with hundred thousands of variables and millions of clauses in reasonably short time. These so-called SAT solvers have by now such a good performance that they are routinely used in applications for the solution of combinatorial optimization problems.

The course will treat these theoretical and practical algorithms, as well as some methods for proving lower bounds, and also some applications. The course will be held in English.

Organisation

  • Umfang: 3+1 Semesterwochenstunden
  • Vorkenntnisse: Algorithmen und Datenstrukturen und Formale Sprachen und Komplexität bzw. Theoretische Informatik für Medieninformatiker
  • Vorlesung & Übung: Dr. Jan Johannsen, Christian Neukirchen

 

Die Vorlesung wird anerkannt:

  • für Studierende im Studiengang Informatik Master für das Modul Algorithmik und Komplexität
  • für Studierende im Studiengang Medieninformatik Master für das Modul Vertiefende Themen der Informatik für Master
  • für Studierende in den Studiengängen Informatik und Medieninformatik Bachelor für das Modul Vertiefende Themen der (Medien-) Informatik
  • für Studierende mit Nebenfach Informatik nach Vereinbarung

Time and Place

Lecture / Tutorial Di, 16-18 Uhr Raum 218 (Amalienstr. 73a)
Lecture Do, 14-16 Uhr Raum 220 (Amalienstr. 73a)

Material

Literature:

U. Schöning and J. Torán, The Satisfiability Problem: Algorithms and Analyses, Lehmans 2013, ISBN 978-3865415271

Tutorials

The tutorials will be held every two weeks in the Tuesday timeslot of the course, first on October 27.

Exam

To be announced

 

 

Document Actions

Funktionsleiste