Zk 20.1.2016

ntin

Zk 20.1.2016

Příspěvek od ntin »

Zkouskova pisemka, verze A
  1. 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?
  2. Rozhodnete, zda plati:
    NSPACE($\sqrt{n}$) \subset SPACE($n \log n$)
    Mozne odpovedi jsou ano/ne/neni znamo. Sve rozhodnuti zduvodnete.
  3. 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 G_1 = (V_1, E_1) a G_2 = (V_2, E_2), prirozene cislo $k \ge 0$
    Otazka: Existuji mnoziny hran E'_1 \subseteq E_1 a E'_2 \subseteq E_2, |E_1'| = |E_2'| \ge k, pro nez jsou grafy G_1 = (V_1, E_1') a G_2 = (V_2, E_2') izomorfni (tj. stejne az na prejmenovani vrcholu)?
Odpovědět

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