Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Boolean Functions and Their Applications - NAIL021

Title:	Booleovské funkce a jejich aplikace
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2020
Semester:	winter
E-Credits:	3
Hours per week, examination:	winter s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time
Additional information:	http://ktiml.mff.cuni.cz/~cepek/vyuka.html

Guarantor:	prof. RNDr. Ondřej Čepek, Ph.D.
Class:	Informatika Mgr. - Teoretická informatika
Classification:	Informatics > Theoretical Computer Science
Is pre-requisite for:	NTIN094, NTIN093

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

Last update: T_KTI (10.04.2001)

This course is suitable for all undergraduate and doctoral students who have acquired at least basic knowledge of mathematical logic, graph theory, and complexity of algorithms. The course covers several areas of interesting problems centerted around Boolean functions. Although the course is mostly theoretical, it includes examples of applications of the covered theory (e.g. in artificial intelligence and relational databases). One of the goals of this course is to provide the students with interesting research topics, which may be suitable for their master thesis.

Aim of the course -

Last update: prof. RNDr. Ondřej Čepek, Ph.D. (12.06.2019)

The aim of this course is to introduce to the students the foundations of Boolean function theory and perhaps also suggest possible topics for a master theses.

Course completion requirements -

Last update: prof. RNDr. Ondřej Čepek, Ph.D. (26.09.2020)

There is only an oral exam. The subject of the exam can be anything covered in the course (including all proofs, of course). If the school is closed due to state regulations the exam will be administered online (via Zoom).

Literature - Czech

Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)

Y.Crama, P.L.Hammer, Boolean Functions - Theory, Algorithms, and Applications. Cambridge University Press, 2011.

Requirements to the exam - Czech

Last update: prof. RNDr. Ondřej Čepek, Ph.D. (12.06.2019)

Zkouška je pouze ústní, předmětem zkoušky může být cokoli z probrané látky (pochopitelně včetně důkazů).

Syllabus -

Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)

1) Introduction to Boolean functions.

literals, logic operators, Boolean formulae and funkctions

normal forms (DNF, CNF) and their properties

2) Implicants, consequents, resolution (consensus) and its completeness

3) Monotone functions and their basic properties

2) Regular functions.

relative strength of variables, properties of regular functions

recognition and dualization of regular functions

3) Threshold functions.

properties, characterization, and recognition of threshold functions

4) Satisfiability of Boolean formulae

NP-completeness of SAT and 3-SAT

classes of formulae with polynomial time SAT: quadratic, Horn and q-Horn functions

5) Minimal representation of Boolean functions.

proofs of NP-completeness for some known classes

cases solvable in polynomial time: acyclic and quasi-acyclic functions