??. 1.2017 IB107   Vyčíslitelnost a složitost Cas: 90 minut
Jméno: Místnost: Souřadnice:
l%sti   i_l jj ľ I učo   i_l jj ľ j_i i_l j_i ľ jj c j_j ľ" j_i ľ j_i    body   c j_i ll j_i ľ jj
Oblast strojově snímatelných informaci. Své UCO vyplňte zleva
dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. 11 U A C. □ !Í □ □ '\ □ □
Nadefinujte: Task 1
15 bodů
1. (5b) Polynomiální verifikátor
2. (5b) Párující funkce
3. (5b) Standardní numerace vyčíslitelných funkcí (pomocí standardní numerace while-programů)
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
??. 1.2017 IB107   Vyčíslitelnost a složitost Cas: 90 minut
Jméno: Místnost: Souřadnice:
2
l%sti   i_l 'j ^h^a učo   i_l 'j ľ j_i i_l j_i ľ jj c j_j ľ" j_i ľ j_i    body   c j_i ll j_i ľ jj
Oblast strojově snímatelných informaci. Své UCO vyplňte zleva
dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. 11 U A C. □ !Í □ □ '\ □ □
Ukažte, že množina I = {i \ fa není injektivní} je rekurzivně spočetná. Task 2
20 bodů
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
??.1.2017
IB107   Vyčíslitelnost a složitost
Čas: 90 minut
Jméno: Místnost: Souřadnice:
3
l%sti   i_l jj ^h^J učo   i_l jj ľ j_i i_l j_i ľ jj c j_j ľ" j_i ľ j_i    body   c j_i ll j_i ľ jj
Oblast strojově snímatelných informaci. Své UCO vyplňte zleva
dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. 11 U A C. □ !Í □ □ '\ □ □
Ukažte, že problém rozhodnout zda daný graf obsahuje kubickou kostru, je NP- Task 3
úplný. 25 bodů
Kubická kostra (definice): Mějme neorientovaný (souvislý) graf G. Kubická kostra grafu G je jeho kostra, která má vrcholy stupně nejvýše 3 (stupeň vrcholu v kostře, v grafu G může být libovolný).
Související problém: Hamiltonovská cesta v grafu G je taková cesta, která prochází každým vcholem právě jednou. Rozhodnout, zda daný graf obsahuje Hamiltonovskou cestu, je NP-úplný.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.