Složitost I
Vyučující: Ondřej Čepek (
web se slajdy)
Předmět má za cíl «naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti». Jedná se o přednášku se cvičeními ob týden.
Info z první přednášky
Cvičení jsou od druhého týdne.
Materiály
Staré (kompletní) slajdy na webu se neshodují se současným sylabem a budou průběžně aktualizované. Při zobrazení v OpenOffice.org jsou navíc poměrně velké části některých současných slajdů prázdné, přednášející slíbíl, že tam umístí i PDF. Update: V OOo 3.1.1 už je to v pořádku, jen je třeba mít správný (resp. špatný) font Symbol (takový co odpovídá Microsoftímu), aby se Vám zobrazily všechny symboly. Tak pozor na to.
Přehled NP-úplných úloh
Jestli máte občas trochu zmatek, jak přesně vypadá zadání které z běžných NP-úplných úloh, popletete jednu s druhou nebo nemáte spojené české a anglické názvy, pomůže vám tento přehled (používám v něm stejné legrační zkratky jako Čepek):
- TSP: obchodní cestující (travelling salesman problem) = nejkratší hamiltonovská kružnice v grafu s váhami: silně NP-úplná.
- HK: hamiltonovská kružnice (Hamiltonian cycle) = kružnice, která projde každým vrcholem právě jednou: NP-úplná.
- VP: vrcholové pokrytí (vertex cover) = (min.) množina vrchoů, každá hrana v ní má aspoň jeden vrchol: NP-úplná.
- SP: součet podmnožiny (subset sum): NP-úplná.
- SAT: splnitelnost formulí v CNF (KNF): NP-úplná.
- 3-SAT: splnitelnost kubických formulí v CNF (KNF): NP-úplná.
- NM: nezávislá množina (independent set) = (max.) množina vrcholů, žádné dva spojeny: NP-úplná.
- KL: klika (clique) = úplný podgraf, resp. odpovídající mna vrcholů indukující úplný podgraf: NP-úplná.
- 3-BG: 3-barvení grafu (graph 3-coloring): NP-úplná.
- 3-P: 3-partition = rozdělení multimnožiny celých čísel na trojice se stejným součtem: silně NP-úplná.
- (KACHL?): kachlíkování (asi je to speciální případ (s okrajem) Wang tiles/dominoes podle Hao Wanga, který to vymyslel, u tiling problem hrozí ještě záměna s jinými «teselačními» problémy): NP-úplná.
- LOUP: dva loupežníci (partition problem): NP-úplná (SP lze převést na LOUP).
- 0–1CP: 0–1 celočíselné programování : NP-úplná (SP nebo SAT lze převést na 0–1CP).
- IP: isomorfismus podgrafů (subgraph isomorphism) : NP-úplná (KL lze převést na IP).
- ?: batoh (knapsack): NP-úplná.
Pozor: Je to jen velmi orientační. Míchám optimalizační verze a rozhodovací verze a bylo by dobré pro úplnost popsat přesně vše a doplnit další souvislosti a vlastnosti problémů (asi v tabulce). Klidně se toho můžete někdo zhostit:).
