Fórum studentů MFF UK

[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]