# 8.2.2010

- 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)
- Odvodte, ze funkce faktorial g(x)=x! je primitivne rekurzivni (za predpokladu, ze funkce nasobeni je PRF).
- Popiste 2-aproximacni algoritmus pro obchodniho cestujiciho s trojuhelnikovou nerovnosti, ktery pouziva minimalni kostru. Ukazte, ze skutecne dany algoritmus dosahuje zmineho aprox. pomeru.
- Ukazte, ze problem rozvrhovani je NP-uplny. (soucasti zadani byl popis problemu rozvrhovani z poznamek k cviceni)