[Zap] 8.2.2010

[jirka_v]

1. Predpokladejte, ze M je TS s obousmerne nekonecnou paskou. Popiste, jak z M vytvorite TS s jednosmerne nekonecnou paskou, ktery "dela totez" co M.
(stacil slovni popis bez instrukci)

2. Odvodte, ze funkce faktorial g(x)=x! je primitivne rekurzivni (za predpokladu, ze funkce nasobeni je PRF).

3. Popiste 2-aproximacni algoritmus pro obchodniho cestujiciho s trojuhelnikovou nerovnosti, ktery pouziva minimalni kostru. Ukazte, ze skutecne dany algoritmus dosahuje zmineho aprox. pomeru.

4. Ukazte, ze problem rozvrhovani je NP-uplny.
(soucasti zadani byl popis problemu rozvrhovani z poznamek k cviceni)

Pro ziskani zapoctu je treba vyresit 3 priklady.