Kučera 23.1.2017

Kučera 23.1.2017

Příspěvekod 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).
Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
 
Příspěvky: 19
Registrován: 22. 6. 2014 13:05
Bydliště: Praha
Typ studia: Informatika Mgr.
Login do SIS: manekp

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník