This course is suitable for all master and doctoral students who have acquired at least basic knowledge
of mathematical logic, graph theory, network flows, and complexity of algorithms. The course covers several
areas of interesting problems centerted around Pseudo-Boolean functions. A particular emphasis will be given
to applications of Pseudo-Boolean functions to solving hard optimization problems.
Last update: T_KTI (16.05.2011)
Tato přednáška je vhodná pro všechny studenty magisterského studia a doktorandy, kteří mají alespoň
základní znalosti z matematické logiky, teorie grafů, toků v sítích a složitosti algoritmů. Přednáška pokrývá
několik oblastí zajímavých problémů soustředěných okolo pseudo-boolovských funkcí, zejména se zaměřením na
aplikace pseudo-boolovských funkcí při řešení těžkých optimalizačních problémů.
Aim of the course -
Last update: RNDr. Jan Hric (07.06.2019)
TBA
Last update: RNDr. Jan Hric (07.06.2019)
TBA
Course completion requirements -
Last update: RNDr. Jan Hric (07.06.2019)
TBA
Last update: RNDr. Jan Hric (07.06.2019)
TBA
Literature -
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)
Selected papers from journals, which are relevant for the covered materiál, in particular from Discrete Applied Mathematics and from
Annals of Mathematics and Artificial Intelligence.
Last update: T_KTI (16.05.2011)
Vybrané články z časopisů které jsou relevantní pro probíranou látku, zejména z Discrete Applied Mathematics a Annals of Mathematics and Artificial Intelligence.
Syllabus -
Last update: T_KTI (16.05.2011)
1. Basic definitions and notation, examples of optimization problems which can be formulated as Pseudo-Boolean minimization or maximization.
2. Representations of Pseudo-Boolean functions (multi=linear polynomials, posiforms) and transformations between them.
3. Rounding, derandomization, local optima.
4. Reductions of general optimization to quadratic one.
5. Posiform maximization.
6. Applications to game theory.
7. Quadratic optimization and roof duality.
8. Persistency and the connection to network flows.
9. Generalizations of roof duality, hierarchy of bounds.
10. Aproximations.
11. Special classes.
Last update: T_KTI (16.05.2011)
1. Zavedení nutných pojmů a značení, příklady optimalizačních problémů, které lze formulovat jako minimalizaci nebo maximalizaci pseudo-booleovské funkce.
2. Reprezentace pseudo-booleovských funkcí (multilineární polynomy, posiformy) a převody mezi nimi.