[Zk] 1.2.2011

img003.jpg

Řešení
1.

$S eq\emptyset , S eq\mathbb{N}$ - to je zřejmé, takže podle Riceovy věty určitě množina $S$ není rekurzivní. Podle úlohy 2 se dá tipnout, že rekurzivně spočetná bude $\overline{S}$.

$$\overline{S}=\{x | W_x\ obsahuje\ liché\ číslo \}$$

K této množině naleznu charakteristickou funkci, například následující:
$$\psi(x) = (\exists<y,z,s>)(\varphi_{x,s}(y)\downarrow=2z+1)$$
Tato funkce je ČRF a zastaví se právě tehdy, pokud $W_x$ obsahuje liché číslo

2.

Stačí vygenerovat postupně všechny čtveřice $<y,z,s,x>$ a pro každou čtveřici pokud $(\varphi_{x,s}(y)\downarrow=2z+1)$, tak vypíšeme $x$.

3.

Pokud je převoditelná, tak platí $\exists ORF f$, tž. $\forall x : x \in A \Leftrightarrow f(x) \in \overline{A}$.

Důkaz sporem, nechť je převoditelná a nechť taková $f$ existuje.

Podle věty o rekurzi: $\exists n$, tž. $\varphi_n \simeq \varphi_{f(n)}$

neboli

$$n \in A \Rightarrow f(n) \in A \Rightarrow f(n) ot \in \overline{A}$$

Což je spor.

4.

Úloha 4 je dle mého primitivní, jen se to musí rozepsat a to se mi nechce, myslím, že každý po zamyšlení tento algoritmus musí vymyslet.

5.

Vyřeším pomocí té kostry problém HK. $G=(V,E)$, vyberu dva vrcholy x, y, které jsou spojeny hranou.

Vytvořím graf $G^{'}=(V \cup \{x^{'}, y^{'} \}, (E \backslash \{(x,y)\}) \cup \{ (x,x^{'}), (y, y^{'}) \})$

Na tento graf $G^{'}$ zavolám hledání kostry s $k = 2$. Pokud ji najde, tak musí být v podobě hamiltonovské cesty z vrcholu $x^{'}$ do vrcholu $x^{'}$. A ta existuje, právě tehdy, když v grafu $G$ existuje HK (odeberu ty přidané vrcholy z HC a spojím odebranou hranou).

Takže úloha je NP-těžká, že je NP je zřejmé, takže je NP-úplná.

Ústní část
Jelikož jsem měl z písemné 5/5, tak jsem si losoval z každého okruhu dvakrát a pak jsem si vybral vyhovující otázku. Lidi co měli 4/5 si vylosovali dvě otázky a pak z jednoho okruhu mohli losovat ještě jednou a vybrat si. 3/5 žádnou tuhle možnost nemají, 2/5 a méně nepostupují. Čas ústní se určoval podle toho jak kdo rychle odevzdal, první šel ve 12:15, pak v 15ti minutových intervalech další lidi.

Skončil jsem na otázkách

• Věta o rekurzi s důkazem

• NP-úplnost 3DM (převod ze splnitelnosti)

Zkouška pohodová, ale musí člověk umět i něco říct, nejen napsat. Což jsem měl u věty o rekurzi trošku problém, napsané jsem to měl správně, chápal jsem to, ale číst ty písmenka mi dělalo trošku problém, ale myšlenku jsem vysvětlil :) 3DM jsem měl trochu jiný důkaz než má v materiálech, tak chvíli mé řešení zkoumal, vyptával se a nakonec jsem ho přesvědčil, že to funguje (bylo to správně, jen on byl zvyklý na svůj důkaz). Celkově za jedna.

Attachments:

• img003.jpg

K úloze 5 dodám, že podle Kučery ten převod měl bejt HAM -> HC -> Kostra s om. st. Převod HC na kostru s omezeným stupněm je zřejmý, graf obsahuje HC právě když obsahuje kostru s max. st. 2. Převod HAM -> HC se ale musí dělat trochu jinak, než je popsáno výše. Postup výše podle mě není převod HAM na HC, ale HAM obsahující hranu (x, y) na HC. Při použití na graf G = ({a, b, c, d}, {(a, c), (a, d), (b, c), (b, d), (c, d)}) a vybrané vrcholy c, d totiž selže - graf G obsahuje HK, ale graf G' vytvořený podle G neobsahuje HC.

Převod HAM -> HC se dělá tak, že se vybere libovolný vrchol x grafu G, do grafu G' se přidá vrchol x' a hrany {(x', y) | (x, y) e E(G)}. Intuitivně to je zkopírování/rozdvojení libovolného vrcholu s tím, že kopie je spojena se stejnými vrcholy, jako originál. Na vrcholy x a x' se připojí nové vrcholy y a y', které zaručí, že pokud je v G' HC, pak tato cesta začíná v y, jde do x, poté projde všechny vrcholy původního grafu a nakonec vejde do x' a v y' skončí. Je vidět, že v grafu G existuje HK právě když v G' existuje HC - když z nalezené cesty odstřihneme y a y' získáme cestu z x do x', což je v grafu G cesta z x do x, tedy HK.

Já udělal ten převod na HC a jen napsal, že HK ≤_p HC bylo na cvičení, uznáno bez řečí ;-)