Čtení: 2× 60 minHodnotí se: zápočtový test (30 b, zápočet od 10 b)

5 Nácvičné testy

Po přečtení umíš

zkusit si formát 4 úloh za 30 bodů v čase
vědět, ve kterém pořadí úlohy řešit
najít si slabinu ještě před testem

Délka testu v materiálech není. Počítej s tím, že máš 60 minut. Pište na papír bez dívání do skript, teprve pak si otevři řešení a obodujte se.

Doporučené pořadí v testu: nejdřív úlohy 2 a 3, které mají pevnou kostru, pak 1, nakonec 4. Na 10 bodů stačí dvě úlohy za 6 bodů, i neúplné úlohy ale dávají body, takže začni každou.

5.1 Test A

Cvičení 5.2 (Úloha 1, 6 b)

Sestroj dvoupáskový deterministický Turingův stroj pro $\{0^n 1^{2n} \mid n \ge 0\}$ v čase $O(n)$ .

Řešení

Fáze: zkopíruj nuly, pak za každou nulu přečti dvě jedničky.

δ(q0, ♯, ♯) = (qA, ♯, ♯, •, •)
δ(q0, 0, ♯) = (q1, 0, 0, →, →)
δ(q1, 0, ♯) = (q1, 0, 0, →, →)
δ(q1, 1, ♯) = (q2, 1, ♯, •, ←)
δ(q2, 1, 0) = (q3, 1, 0, →, •)
δ(q3, 1, 0) = (q2, 1, 0, →, ←)
δ(q2, ♯, ♯) = (qA, ♯, ♯, •, •)

Neuvedený přechod znamená zamítnutí. Hlava 1 jde jen doprava, čas je $O(n)$ .

Body: 2 za nápad, 3 za přechody, 1 za čas.

Cvičení 5.3 (Úloha 2, 6 b)

Máš orákulum „má $G$ vrcholové pokrytí velikosti nejvýše $k$ ?“. Najdi nejmenší pokrytí.

Řešení

Binárně najdi nejmenší $k$ .
Pro každý vrchol $v$ : je-li odpověď na $(G - v, k - 1)$ ANO, dej $v$ do pokrytí, smaž ho a sniž $k$ . Jinak jdi dál.

Vrchol s odpovědí NE není v žádném nejmenším pokrytí, takže jeho hrany pokryjí sousedé. Dotazů je $n + O(\log n)$ .

Cvičení 5.4 (Úloha 3, 6 b)

Máš $n$ zkoušek, $t$ termínů, kapacitu $c$ zkoušek na termín a dvojice zkoušek v konfliktu. Zapiš jako ILP.

Řešení

$x_{e,t} \in \{0, 1\}$ znamená, že zkouška $e$ je v termínu $t$ .

$\sum_t x_{e,t} = 1$ pro každou zkoušku.
$x_{e,t} + x_{f,t} \le 1$ pro konflikt $\{e, f\}$ a každý termín.
$\sum_e x_{e,t} \le c$ pro každý termín.

Cvičení 5.5 (Úloha 4, 12 b)

Dokaž, že Dominating Set je NP-úplný.

Řešení

Celý důkaz je v kapitole o redukcích. Bodování: 2 za NP, 3 za konstrukci, 1 za polynomiálnost, 2 za ⇒, 4 za ⇐.

5.2 Test B

Cvičení 5.6 (Úloha 1, 6 b)

Sestroj dvoupáskový nedeterministický stroj pro $\{ww \mid w \in \{0,1\}^*\}$ v čase $O(n)$ .

Řešení

Hádáme střed: kopíruj na druhou pásku, v libovolné chvíli přejdi na převinutí a pak porovnávej.

δ(q0, ♯, ♯) = (qA, ♯, ♯, •, •)
δ(q0, s, ♯) = (qc, s, s, →, →)
δ(qc, s, ♯) ∋ (qc, s, s, →, →)     ještě kopíruj
δ(qc, s, ♯) ∋ (qb, s, ♯, •, ←)     tady je střed
δ(qb, s, t) = (qb, s, t, •, ←)     převiň druhou pásku
δ(qb, s, ♯) = (qe, s, ♯, •, →)
δ(qe, s, s) = (qe, s, s, →, →)     porovnej
δ(qe, ♯, ♯) = (qA, ♯, ♯, •, •)

Každá větev má nejvýš $2n + 2$ kroků, takže čas je $O(n)$ .

Cvičení 5.7 (Úloha 2, 6 b)

Máš orákulum pro splnitelnost CNF. Najdi splňující ohodnocení.

Řešení

Nejdřív ověř, že je formule splnitelná. Pro $i = 1, \dots, n$ přidej $(x_i)$ . Pokud je výsledek splnitelný, klauzuli nech. Jinak ji vyměň za $(\neg x_i)$ . Dotazů je $n + 1$ .

Cvičení 5.8 (Úloha 3, 6 b)

Zapiš jako SAT, zda má $G$ kliku velikosti $k$ .

Řešení

$x_{i,v}$ znamená, že $i$ -tý člen kliky je $v$ .

$\bigvee_v x_{i,v}$ pro každé $i$ .
$(\neg x_{i,u} \vee \neg x_{j,v})$ pro $i < j$ a každé $u, v$ , kde $u = v$ nebo $\{u, v\} \notin E$ .

Cvičení 5.9 (Úloha 4, 12 b)

Dokaž, že Partition je NP-úplný (lze čísla rozdělit na dvě části se stejným součtem?). Víš, že Subset Sum je NP-úplný.

Řešení

NP: certifikát je podmnožina, sečteme ji.

Konstrukce. Máme $a_1, \dots, a_n$ se součtem $S$ a cíl $T$ , kde $T \le S$ . Přidej číslo $y = |S - 2T|$ .

Polynomiálnost. Jedno číslo navíc se stejným počtem bitů.

Případ $2T \le S$ , tedy $y = S - 2T$ . Celkový součet je $2S - 2T$ a každá část má $S - T$ .

⇒ Podmnožina se součtem $T$ spolu s $y$ dá $T + S - 2T = S - T$ .

⇐ Část obsahující $y$ má součet $S - T$ , takže její zbytek má součet $S - T - y = T$ .

Případ $2T > S$ , tedy $y = 2T - S$ . Celkový součet je $2T$ a každá část má $T$ .

⇒ Podmnožina se součtem $T$ je jedna část, zbytek s $y$ je druhá.

⇐ Část bez $y$ má součet $T$ .

5.3 Co dál podle výsledku

Body	Co to znamená
Pod 10	Vrať se k Self-redukci a Modelování, to je nejrychlejších 12 bodů.
10–17	Zápočet máš. Doplň si Turingovy stroje.
18 a víc	Zbytek času dej redukcím, přijdou i u ústní zkoušky.

Kapitolu mám prostudovanou