Please be advised: Due to maintenance work on the BRZ-SAP system, some services will only be available to a limited extent in TISS from Friday, June 28, 2024 17:00 up to and including Sunday, June 30, 2024. Please accept our apologies for any inconvenience.

184.090 SAT Solving
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2015S, VU, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Aim of course

  • Knowledge about theory and proof procedures for propositional logic and quantified propositional logic
  • Knowledge about applications like planning
  • Practical knowledge about proof systems (like minisat or depQBF)

Didactic Procedure

  • Lecture
  • Processing of simple exercises by students (e.g., complete a proof presented in the lecture).
  • Preparation as home work or in small working groups (for 10 to 15 minutes) during the lecture
  • Short presentation and discussion of solutions and results.
  • Short oral presentation of relevant papers including a short written review.

Subject of course

  • Syntax, semantic, etc. for the mentioned logics proof
  • Procedures for these logics especially for quantified Boolean formulas
  • New developments like, e.g., solver in non-normal form, circuits, certificates and their extraction from proofs etc.
  • Practical work with selected provers and implementations (e.g., preprocessors).
  • A more detailed presentation of the content of the summer term will be presented in the first lecture

Additional information

Limit 20 students (entry test if necessary; details follow)

ECTS breakdown

  • 18h: 9 lectures a 2h
  • 15h: 3 ex sheets a 5 ex; including preparation of a solution in pdf)
  •  6h: ex presentation
  •  8h: reading a research paper (in teams of 2 students)
  • 12h: preparation of paper presentation
  •   7h: presentation (10 teams, 3 presentations in a 2h slot)
  •   8h:preparation for final exam
  •  1h: final exam

 Attention: The dates dor the exams are from last year. They will be discussed in the first lecture "Vorbesprechung"

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Mon13:00 - 16:0011.05.2015Theresianumgasse HS 2 SAT Solving und Erweiterungen
Mon13:00 - 16:0018.05.2015Theresianumgasse HS 1 - MWB SAT Solving und Erweiterungen
Mon09:00 - 12:0001.06.2015 meeting room Menger (at the institute)SAT Solving und Erweiterungen
Mon09:00 - 12:0008.06.2015 meeting room Menger (at the institute)SAT Solving und Erweiterungen

Examination modalities

written and oral

Course registration

Not necessary

Curricula

Study CodeObligationSemesterPrecon.Info
066 931 Computational Intelligence Mandatory elective
066 937 Software Engineering & Internet Computing Mandatory elective
066 938 Computer Engineering Mandatory elective
881 Computer Sciences Mandatory elective

Literature

Current literature like journal articles, articles from the Handbook of Satisfiability, etc. will be discussed during the lecture.

Previous knowledge

1) Propositional and predicate logic

   a) Syntax, normal forms and normal form translations

   b) Semantics, evaluation of a given formula with respect to a given interpretation, the concept of logical    consequence (entailment) also under theories, Translation of  validity, entailment, equivalence and satisfiablity problems into each other, proof procedures (beeing able to apply tableau, sequent  systems or NK)

2) Ability to construct simple proofs

   a) Induction proofs (for simple examples

   b) Simple proofs of run-time or space estimations (Example: Show that the time complexity of breadth first search with a fixed branching degree b and depth d is in O(b^d). I expect a formally correct proof  including explanations (e.g., for the O-notation).

The previous knowledeg had been taught in the course "Theoretischer Informatik und
Logik" (TIL),  "formalen Methoden der Informatik" (FMINF), "Algorithmen und Datenstrukturen" and
math lectures from the beginning of our bachelor studies.  For a part of the knowledge about logic,
  the slides of TIL and from the block Satisfiability (SAT) of FMINF  (http://www.logic.at/lvas/fminf/) could be helpfull.

Miscellaneous

Language

English