Kučera 23.1.2017

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Kučera 23.1.2017

Kučera 23.1.2017

od CiTrus » 24. 1. 2017 14:16

Zkouška vypadala podobně jako minule.

Písemka:
  1. Definujeme problém zastavení na prvočíslech.
    Instance: Turingův stroj M zadaný kódem
    Otázka: Existuje prvočíslo p takové, že M(p)\downarrow
    Rozhodněte, zda tento problém a jeho doplněk jsou (částečně) rozhodnutelné. Svojí odpověď zdůvodněte.
  2. Definujeme problém omezené paměti.
    Instance: Turingův stroj M zadaný kódem, slovo x\in\Sigma^* a algoritmicky vyčíslitelná funkce f:\Sigma^*\rightarrow\mathbb{N}
    Otázka: Vystačí si M při výpočtu nad vstupem x s pamětí f(x)?
    Ukažte, že tento problém je rozhodnutelný.
  3. Definujeme problém čtyřlisté kostry.
    Instance: Graf G=(V,E)
    Otázka: Existuje kostra grafu G, která má právě 4 listy?
    Ukažte, že problém je NP-úplný. Můžete použít převod z některého z problémů probíraných na přednášce.
Na písemku byla hodina, při odevzdání se přidělovaly sloty na ústní část po půlhodinách. Po příchodu se losovaly otázky ze seznamu, který je volně k dispozici na webu předmětu. Já jsem dostal NP-úplnost kachlíkování.

Hinty:
  1. Problém je částečně rozhodnutelný, ale nikoliv rozhodnutelný. Důkaz vyplývá z Riceovy věty.
  2. Je třeba použít lemma o inkluzi NSPACE(f(n))\subseteq TIME(2^{c_Lf(n)}), pak pustit M(x) a odmítnout, když překročí vymezenou paměť nebo běží příliš dlouho..
  3. Šla na to převést Hamiltonovská cesta (na kterou jde převést Hamiltonovská kružnice).

Nahoru