Úvod

Question 1

Čo je výpočtový model?

Answer 1

Turingov stroj

Question 2

Aký je rozdiel medzi Monte Carlo a Las Vegas alg.?

Answer 2

Monte Carlo dáva rýchlo pravdepodobne správnu odpoveď, Las Vegas správnu pravdepodobne rýchlo

Question 3

Čo je problém?

Answer 3

Množina vstupov, výstupov a vzťah medzi nimi (vstupno-výstupné podmienky)

Question 4

Aký algoritmus je asymptoticky optimálny?

Answer 4

Asymptoticky neexistuje nič lepšie

Question 5

Ako vieme simulovať viacpáskový stroj na 1 páske?

Answer 5

Stačí použiť viacstopú pracovnú pásku. (Jedna možnosť je mať na každej stope zaznačenú aj pozíciu hlavy, druhá možnosť je posúvať jednotlivé stopy tak, aby boli všetky hlavy stále nad tým istým políčkom.) Uvedomte si, že simulácia jedného kroku pôvodného TS nám môže trvať až S(n) krokov, keďže musíme prejsť celú pásku a nájsť všetky simulované hlavy. (Resp. kS(n) krokov, lebo musíme poposúvať jednotlivé pásky.)

Question 6

Aká bude časová zložitosť pri redukcii k pások na jednu?

Answer 6

Budeme mať T^2(n) pre T(n) pôvodný.