SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Algorithmic Aspects of Boolean Functions and Parameterized Complexity - NTIN099
Title in English: Algoritmické aspekty booleovských funkcí a parametrizovaná složitost
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2015 to 2018
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: RNDr. Petr Kučera, Ph.D.
Class: Informatika Mgr. - volitelný
Informatika Mgr. - Teoretická informatika
Classification: Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
The purpose of this lecture is to present several algorithms for Boolean functions, especially for the satisfiability problem. The lecture also contains an introduction to fixed-parameter algorithms and parameterized complexity theory. Exponential algorithms for SAT and MaxSAT. Parameterized complexity and fixed-parameter algorithms for SAT and MaxSAT. Approximation and search algorithms for MaxSAT.
Course completion requirements -
Last update: RNDr. Petr Kučera, Ph.D. (10.06.2019)

The lecture is completed with an oral exam from the topics covered by the lectures. In case of a small number of students the exam can be substituted with a presentation of an article from the area covered by the lecture.

Literature -
Last update: T_KTI (27.02.2014)

A. Biere, M. Heule, H. van Maaren, T. Walsh (Eds.). Handbook of Satisfiability, in: Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, 2009, pp. 131-153

Niedermeier, Rolf. Invitation to fixed-parameter algorithms. Vol. 3. Oxford: Oxford University Press, 2006

Flum, Jörg, and Martin Grohe. Parameterized complexity theory. Vol. 3. Heidelberg: Springer, 2006

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
  • Exponential algorithms for k-SAT and general SAT
  • Introduction to parameterized complexity, examples from the graph theory
  • Fixed-parameter algorithms for SAT based on backdoor sets
  • Algorithms for SAT parameterized with treewidth
  • Algorithms for SAT parameterized with a deficiency of a formula
  • Kernelization of MaxSAT and parameterization of MaxSAT
  • MaxSAT algorithms based on branch & bound
  • Approximation algorithms for MaxSAT

Charles University | Information system of Charles University |