[Zk] 1.2.2011
-
- 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
1.
- to je zřejmé, takže podle Riceovy věty určitě množina není rekurzivní. Podle úlohy 2 se dá tipnout, že rekurzivně spočetná bude .
K této množině naleznu charakteristickou funkci, například následující:
Tato funkce je ČRF a zastaví se právě tehdy, pokud obsahuje liché číslo
2.
Stačí vygenerovat postupně všechny čtveřice a pro každou čtveřici pokud , tak vypíšeme .
3.
Pokud je převoditelná, tak platí , tž. .
Důkaz sporem, nechť je převoditelná a nechť taková existuje.
Podle věty o rekurzi: , tž.
neboli
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. , vyberu dva vrcholy x, y, které jsou spojeny hranou.
Vytvořím graf
Na tento graf zavolám hledání kostry s . Pokud ji najde, tak musí být v podobě hamiltonovské cesty z vrcholu do vrcholu . A ta existuje, právě tehdy, když v grafu 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.
Re: [Zk] 1.2.2011
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.
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.
- 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
Já udělal ten převod na HC a jen napsal, že HK ≤p HC bylo na cvičení, uznáno bez řečí