# [Zk] 1.2.2011 <{ForumPost(poster="Šlupka", timestamp=2011-02-02 00:18:27)}> 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)(\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 $$ 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](/Forum%20archiv/Attachments/3886_365812bd4353921a2b347ae73c0de2b5)* <{/ForumPost}> <{ForumPost(poster="netsir", timestamp=2011-02-02 11:32:16)}> 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. <{/ForumPost}> <{ForumPost(poster="hkvm", timestamp=2011-02-02 11:59:20)}> Já udělal ten převod na HC a jen napsal, že HK ≤p HC bylo na cvičení, uznáno bez řečí ;-) <{/ForumPost}>