Terminológia

Question 1

Čo konkrétne je výpočtový model?

Answer 1

Turingov stroj s 1 vstupnou a k pracovnými páskami, pričom na vstupnú nevie zapisovať

Question 2

Ako nazývame aj náš výpočtový model?

Answer 2

TS s oddeleným vstupom

Question 3

Definuj DTS s časovou zložitosťou T(n)

Answer 3

na každom vstupe dĺžky n spraví maximálne T(n) krokov

Question 4

Definuj DTS s pamäťou S(n)

Answer 4

na každom vstupe dĺžky n použije na každej pracovnej páske maximálne S(n) políčok

Question 5

Ako definujeme zložitosť pri NTS?

Answer 5

Rovnako ako DTS, ale že každý výpočet musí byť tak ohraničený (každá vetva)

Question 6

Definuj DTIME(T(n))

Answer 6

Trieda JAZYKOV akc. DTS v čase T(n)

Question 7

Definuj NTIME(T(n))

Answer 7

Trieda jazykov akc. NTS v čase T(n)

Question 8

Definuj DSPACE(S(n))

Answer 8

Trieda jazykov akc. DTS v priestore S(n)

Question 9

Definuj NSPACE(S(n))

Answer 9

Trieda jazykov akc. NTS v priestore S(n)

Question 10

Definuj P, NP

Answer 10

zjednotenie DTIME(n^k) pre všetky k, resp. NTIME

Question 11

Definuj DLOG, NLOG

Answer 11

DSPACE(log n) resp. NSPACE(log n)

Question 12

Definuj PSPACE, NPSPACE

Answer 12

zjednotenie DSPACE(n^k) pre všetky k, resp. NSPACE

Question 13

Definuj EXP, NEXP

Answer 13

zjednotenie DTIME(2^(n^k)) pre všetky k, resp. NTIME

Question 14

Ako označujeme mieru zložitosti pí v modeli M pre vstup dĺžky n, ak máme mieru zložitosti X

Answer 14

X_pi^M(n) (pridaj asi obrázok)

Question 15

Definuj páskovo konštruovateľnú funkciu f

Answer 15

Ex. DTS kt. pre vstupné slovo w na jednej z pások použije presne f(|w|) políčok, na všetkých ostatných nanajvýš f(|w|)

Question 16

Definuj časovo konštruovateľnú funkciu f

Answer 16

Ex. DTS kt. pre vstupné slovo w spraví presne f(|w|) krokov