od ntin » 20. 1. 2016 17:56
Zkouskova pisemka, verze A
-
Ukazte, ze nasledujici problem neni algoritmicky rozhodnutelny. Rozhodnete, zda je castecne rozhodnutelny. Sve rozhodnuti zduvodnete.
Pouziti druhe pasky
Instance: Dvoupaskovy Turinguv stroj M (dany svym kodem)
Otazka: Existuje vstup x takovy, ze M zapise nejaky znak na druhou pasku pri vypoctu nad vstupem x?
-
Rozhodnete, zda plati:
Mozne odpovedi jsou ano/ne/neni znamo. Sve rozhodnuti zduvodnete.
-
S pomoci nektereho z problemu Kachlikovani, Splnitelnost, 3-Splnitelnost, Vrcholove pokryti, Trojrozmerne parovani, Hamiltonovska kruznice, Obchodni cestujici nebo Loupeznici ukazte, ze nasledujici problem je NP-uplny:
Nejvetsi spolecny podgraf
Instance: Grafy a , prirozene cislo
Otazka: Existuji mnoziny hran a , , pro nez jsou grafy a izomorfni (tj. stejne az na prejmenovani vrcholu)?
[b]Zkouskova pisemka, verze A[/b]
[list=1]
[*]
Ukazte, ze nasledujici problem neni algoritmicky rozhodnutelny. Rozhodnete, zda je castecne rozhodnutelny. Sve rozhodnuti zduvodnete.
[u]Pouziti druhe pasky[/u]
[i]Instance:[/i] Dvoupaskovy Turinguv stroj M (dany svym kodem)
[i]Otazka:[/i] Existuje vstup x takovy, ze M zapise nejaky znak na druhou pasku pri vypoctu nad vstupem x?
[/*]
[*]
Rozhodnete, zda plati:
[latex]NSPACE($\sqrt{n}$) \subset SPACE($n \log n$)[/latex]
Mozne odpovedi jsou ano/ne/neni znamo. Sve rozhodnuti zduvodnete.
[/*]
[*]
S pomoci nektereho z problemu Kachlikovani, Splnitelnost, 3-Splnitelnost, Vrcholove pokryti, Trojrozmerne parovani, Hamiltonovska kruznice, Obchodni cestujici nebo Loupeznici ukazte, ze nasledujici problem je NP-uplny:
[u]Nejvetsi spolecny podgraf[/u]
[i]Instance:[/i] Grafy [latex]G_1 = (V_1, E_1)[/latex] a [latex]G_2 = (V_2, E_2)[/latex], prirozene cislo [latex]$k \ge 0$[/latex]
[i]Otazka:[/i] Existuji mnoziny hran [latex]E'_1 \subseteq E_1[/latex] a [latex]E'_2 \subseteq E_2[/latex], [latex]|E_1'| = |E_2'| \ge k[/latex], pro nez jsou grafy [latex]G_1 = (V_1, E_1')[/latex] a [latex]G_2 = (V_2, E_2')[/latex] izomorfni (tj. stejne az na prejmenovani vrcholu)?
[/*]
[/list]