TI2 (Foja2) - Pardubská - Zadania 1.6.2005

1. (6b)
   Vysvetlite kódovanie TS a vzťah binárnych reťazcov a kódov TS; Čo je to univerzálny TS?
2. (10b)
   Univerzálny TS dostal na vstupe - kod(T)#w. Vieme, že časová zložitosť TS s kódom kod(T) je T(n). Aká bude časová zložitosť UTS (pri výpočte podľa prednášky) na tomto vstupe? Vysvetlite.
3. (12b)
   Napíšte MRAM pre nasledujúci problém:
   vstup: n , výstup: odmocnina n
   - Zadefinujte časovú zložitosť MRAMu pri jednotkovej a logaritmickej cene.
   - Aká je časová zložitosť - pri jednotkovej aj logaritmickej cene vami navrhnutého MRAMu? Odôvodnite.
   - Aká by -podľa simulácie z prednášky- bola časová a pamäťová zložitosť TS simulujúceho váš MRAM? Vysvetlite.
4. (10b)
   Vyslovte a dokážte Savitchovu vetu o vzťahu deterministického a nedeterministického priestoru.
5. (10b)
   Nasledujúci problém patrí do triedy NP - dokážte.
   L = {kod(G)#k | kod(G) je matica susednosti grafu G = (V,E) zapísaná po riadkoch, k je prirodzené číslo a množina vrcholov grafu G sa dá rozložiť na k disjunktných podmnožín tak, že indukované grafy tvoria úplné podgrafy.} Zadefinujte tiež triedu NP.
6. (15b)
   Napíšte definíciu pojmu NP-úplný problém a vysvetlite metódu, ako môžeme dokázať NP-úplnosť nejakého problému pomocou iného NPÚ problému. Aplikujte na problém NP-úplnosti problému 3-splniteľnosti; To, že problém SAT je NP-úplný problém, považujte za fakt.