[Zk] 1.2.2011
Napsal: 2. 2. 2011 00:18
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.