Kučera 23.1.2017

Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 22. 6. 2014 14:05
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Kučera 23.1.2017

Příspěvek od CiTrus »

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).
Odpovědět

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