TI2 (Pardubská) - Zadania 06.06.2005, pondelok 8:30, C

1. (12b)
   Definujte rozhodnutelny a nerozhodnutelny problem.
   Vysvetlite, ako pomocou znameho nerozhodnutelneho problemu mozme dokazat, ze iny problem je nerozhodnutelny.
   Aplikujte na problem zastavenia TS.
2. (13b)
   Univerzálny TS dostal na vstupe - kod(T)#w.
   Aka bude casova zlozitost UTS v najhorsom pripade (pri vypocte z prednasky) na tomto vstupe, ak vieme, ze
   • DTS na kazdom vstupe zastane
   • priestorove ohranicenie DTS je S(n)
   Vysvetlite.
3. (14b)
   Napiste (nie nutne uplne formalne) MRAM, ktory rozpoznava jazyk
   L = {1^kw^k4 | k patri N; w patri {2;3}^*}
   Vstup: 1,...,1,a₁,...,a_m ; a_i patri {2;3}
   Vystup:
   • 1 ak m=k*l; a₁...a_m = (a₁...a_l)^k
   • 0 inak
   • Zadefinujte casovu zlozitost MRAMu pri jednotkovej a logaritmickej cene.
   • Aka je casova a pamatova zlozitost pri jednotkovej a logaritmickej cene Vami navrhnuteho MRAMu? Odovodnite
   • Aka by - podla simulacie z prednasky - bola casova a pamatova zlozitost TS simulujuceho Vas MRAM? Vysvetlite
4. (15b)
   Dokazte, ze nasledujuci problem patri do NP.
   Vstup: G = (V;E); k patri N
   Vystup:
   • 1 - ak sa da mnozina V rozlozit na k disjunktnych mnozin V₁,...,V_k tak, ze kazdy z indukovanych podgrafov G_i = (V_i; E prienik (V_i×V_i)); i=1,...,k je alebo uplny graf, alebo jednoduchy cyklus
   • 0 inak
   Predpokladajte, ze graf je zadany maticou susednosti, riadky su oddelene oddelovacom.
5. (10b)
   Vyslovte a dokazte Savitchovu vetu o vztahu deterministickeho a nedeterministickeho priestoru.
6. (15b)
   Napíšte definiciu pojmu NP-uplny problem a vysvetlite metodu, ako mozeme dokazat NP-uplnost nejakeho problemu pomocou ineho NPU problemu. Aplikujte na problem NP-uplnosti k-kliky; to, ze problem SAT je NP-uplny problem, povazujte za fakt.