MI-PAA
- Konfigurační proménné:
- je jich konečný počet
- nabývají konečného počtu hodnot -> možných ohodnocení je konečný počet
- lze s jejich pomocí vyjádřit řešení (všechna, platná, optimální)
- NPO problémy z kompendia:
- Dynamické programování
- Dynamické programování - dekompozice podle kapacity batohu (Autor: Petr Fišer a Jan Schmidt)
- Dynamické programování - dekompozice podle ceny (Autor: Petr Fišer a Jan Schmidt)
- Vyplňování matice (DP - cena)
- pseudopolynomiální složitost (n * M nebo n * C)
- Teorie - vysvětlena trochu jinak než na eduxu
- FPTAS
- výpočet chyby
- Odvození chyby v sekci 5: http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf (lokální kopie) - 16.11.2015
- Postup: určete si pro každou instanci počet bitů, které můžete zanedbat v závislosti na zvolené chybě -> Nejprve volím chybu a z ní vypočítám počet bitů k zanedbání - NE NAOPAK!
- Zmenšení přesnosti - bitový posun (FPTAS)
- B&B
- Nejhůře jako hrubá síla
- Tŕídy složitosti
- Třídy problémů: P, NP, co-NP, NPH, NPC, co-NPC umět zařadit problém do třídy
- přeformulovat verzi problému z jedné třídy tak, aby patřil do třídy druhé
- Převod SAT na 3SAT
- Princip: http://www-verimag.imag.fr/~duclos/teaching/inf242/SAT-3SAT-and-other-red.pdf (lokální kopie) - 5.11.2015
- Příklad CNF
- Je formule splnitelná? = NPC
- Je formule tautologie? (je vždy 1?) = P
- Je formule kontradikce? (tedy nemůže být splněná) = co-NPC
- Stav
- Konfigurační proměnné
- Vnitřní proměnné algoritmu
- pojem se váže ke konkrétnímu algoritmu
- Pro nás - konf. proměnné jsou plně určené
- Prohledávací prostor
- Pro nás - obsahuje i "stavy", kde není plně určené ohodnocení konf. proměnných
- Stavový prostor
- množina stavů (konf. proměnné jsou určené!)
- operátory - hrana v grafu představujícím stavový prostor je aplikace operátoru = operace
- Požadujeme
- Souvislost - existuje tah z libovolného stavu do libovolného jiného.
- je-li tah minimální, existuje k němu tah inverzní "podobné" délky
- Příklady
- Batoh: seznam věcí + přidání/odebrání věci
- TSP: pořadí měst + dvojzáměna
- Dlaždičkování čtvercové sítě obdélníky: souřadnice obdélníku + zmenšení/zvétšení obdélníku
- Pohyb stavovým prostorem
- Jen přes stavy splňující omezující podmínky -> komplikované operace
- I přes stavy nespňující omezující podmínky -> jednoduché operace; nutná penalizace
- Ilustrace pohybu stavovým prostorem
- Cvičení 6