Pseudo-Booleovská optimalizace - NTIN096

• Anglický název: Pseudo-Boolean Optimization
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2019
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. RNDr. Ondřej Čepek, Ph.D.
• Třída: Informatika Mgr. - volitelný; Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika, Teoretická informatika

Anotace

čeština

Poslední úprava: 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ů.

angličtina

Poslední úprava: T_KTI (16.05.2011)

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.

Cíl předmětu

čeština

Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Podmínky zakončení předmětu

čeština

Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Literatura

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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.

Sylabus

čeština

Poslední úprava: 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.

3. Zaokrouhlování, derandomizace, lokální optima.

4. Redukce obecné optimalizace na kvadratickou.

5. Maximalizace pro posiformy.

6. Aplikace v teorii her.

7. Kvadratické optimalizace a roof-dualita.

8. Persistence a souvislost s toky v sítích.

9. Zobecnění roof-duality, hierarchie odhadů.

10. Aproximace

11. Speciální třídy.

angličtina

Poslední úprava: 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.