[Zk] 1.2.2011

Šlupka
Matfyz(ák|ačka) level I
Příspěvky: 39
Registrován: 7. 11. 2007 22:12
Typ studia: Informatika Bc.

[Zk] 1.2.2011

Příspěvek od Šlupka »

Zadání
Zadání
Ř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.
netsir

Re: [Zk] 1.2.2011

Příspěvek od netsir »

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.
Uživatelský avatar
hkvm
Matfyz(ák|ačka) level II
Příspěvky: 50
Registrován: 3. 6. 2008 20:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zk] 1.2.2011

Příspěvek od hkvm »

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

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“