Kučera 23.1.2017
Napsal: 24. 1. 2017 14:16
Zkouška vypadala podobně jako minule.
Písemka:
Hinty:
Písemka:
- Definujeme problém zastavení na prvočíslech.
Instance: Turingův stroj zadaný kódem
Otázka: Existuje prvočíslo takové, že
Rozhodněte, zda tento problém a jeho doplněk jsou (částečně) rozhodnutelné. Svojí odpověď zdůvodněte. - Definujeme problém omezené paměti.
Instance: Turingův stroj zadaný kódem, slovo a algoritmicky vyčíslitelná funkce
Otázka: Vystačí si při výpočtu nad vstupem s pamětí ?
Ukažte, že tento problém je rozhodnutelný. - Definujeme problém čtyřlisté kostry.
Instance: Graf
Otázka: Existuje kostra grafu , 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.
Hinty:
- Problém je částečně rozhodnutelný, ale nikoliv rozhodnutelný. Důkaz vyplývá z Riceovy věty.
- Je třeba použít lemma o inkluzi , pak pustit a odmítnout, když překročí vymezenou paměť nebo běží příliš dlouho..
- Šla na to převést Hamiltonovská cesta (na kterou jde převést Hamiltonovská kružnice).