Zkouška 2. 4. 2015

Pokračování přednášky TIN060 Algoritmy a datové struktury I
pepelik

Zkouška 2. 4. 2015

Příspěvek od pepelik »

1.) Máme 2n (po dvou různých) prvků $a_1,\dots, a_{2n}$ , které chceme rozdělit na n nejmenších a n největších. Dokažte, že poté co třídící síťí paralalně setříme prvky a_1, \dots, a_n a a_{n+1},\dots, a_{2n} postačí již k získání výsledku síť konstantní hloubky.

2.) Dokažte, že problém vrcholového pokrytí(VP) (je dán neorientovaný graf G = (E,V) a přirozené číslo k; existuje podmnožina vrcholů W volikosti nejvýše k, která pokrývá všechny hrany, tj. z každé hrany leží v množině W alespoň jeden vrchol) je NP-úplný. Pro dokázání, že je VP NP-těžký využijte některého z NP-úplných problémů probraných na přednášce (Klika, Součet podmnožiny, Splnitelnost formule v KNF, Rozvrh pro paralelní stroje, Obchodní cestující).

3) Mějme optimalizační algoritmus pro hledání vrcholového pokrytí: Dokud G má hrany vyber vrchol maximálního stupně (pokud jich je víc, vezmi libovolný), dej ho do vrcholového pokrytí a odstraň všechny hrany grafu s tímto vrcholem incidentní.
Dokažte, že algoritmus nemá (na množině všech zadání vrcholového pokrytí) poměrovou chybu \theta \le {3\over 2}.

Hinty k řešení:
1.) Stačí síť hloubky 1. Sestrojí se tak, že máme vstupy a_1,a_2,\dots,a_{2n}, které propojíme hradly následovně: první s posledním, druhý s předposledním, atd. Pak už stačí jen odůvodnit proč to funguje
2.) Převádět je potřeba na jediný grafový problém, který máme k dispozici, tedy na Kliku. Klika -> VP: Z grafu, v němž chceme hledat kiku uděláme doplňěk, v němž je nutné hledat nezávislou množinu. Doplněk nezávislé množiny je VP.
3.) Je nutné sestrojit graf, který bude uvádět protipříklad na němž uvedený alg. najde příliš velké pokrytí. Vezmeme dostatečně velký bipartitní graf (řekněme např. dvě řady vrcholů po 12 vrcholech). K jedné řadě (kterou, když vybereme do VP, tak je optimem) začneme přidávat vrcholy dost velkého stupně, aby je musel alg. vybrat dříve. než optimum. K prvním třem připojíme hranou vrchol, pak k dalším třem přidáme jeden vrchol, atd., totéž ještě zopakujeme pro čtveřice, které připojíme hranou k novému vrcholu. Postupem jsme sestrojili graf pro nějž alg. vytvoří pokrytí o 19 vrcholech, kdežto opt. je 12.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“