Zk 20.1.2016
Napsal: 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)?