od CiTrus » 24. 1. 2017 14:16
Zkouška vypadala podobně jako minule.
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.
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:
- 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).
Zkouška vypadala podobně jako minule.
Písemka:
[list=1]
[*] Definujeme problém zastavení na prvočíslech.
[b]Instance:[/b] Turingův stroj [latex]M[/latex] zadaný kódem
[b]Otázka:[/b] Existuje prvočíslo [latex]p[/latex] takové, že [latex]M(p)\downarrow[/latex]
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.
[b]Instance:[/b] Turingův stroj [latex]M[/latex] zadaný kódem, slovo [latex]x\in\Sigma^*[/latex] a algoritmicky vyčíslitelná funkce [latex]f:\Sigma^*\rightarrow\mathbb{N}[/latex]
[b]Otázka:[/b] Vystačí si [latex]M[/latex] při výpočtu nad vstupem [latex]x[/latex] s pamětí [latex]f(x)[/latex]?
Ukažte, že tento problém je rozhodnutelný.
[*] Definujeme problém čtyřlisté kostry.
[b]Instance:[/b] Graf [latex]G=(V,E)[/latex]
[b]Otázka:[/b] Existuje kostra grafu [latex]G[/latex], 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.[/list]
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í.
[line][/line]
Hinty:
[list=1]
[*] 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 [latex]NSPACE(f(n))\subseteq TIME(2^{c_Lf(n)})[/latex], pak pustit [latex]M(x)[/latex] 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).[/list]