PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
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 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. 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 -
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ů.
Cíl předmětu -
Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Literatura -
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.

Sylabus -
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.

 
Univerzita Karlova | Informační systém UK