PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
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ů.
Poslední úprava: T_KTI (16.05.2011)
Cíl předmětu -

TBA

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

TBA

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

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.

Poslední úprava: T_KTI (16.05.2011)
Sylabus -

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.

Poslední úprava: T_KTI (16.05.2011)
 
Univerzita Karlova | Informační systém UK