Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

VZaV - 3ZIMA > Zložitostné triedy > Flashcards

Zložitostné triedy Flashcards

1
Q

Aké funkcie sú “slušné”?

A

Páskovo, resp. časovo konštruovateľné

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Ako zapisujeme binárne DTS M s jednou pracovnou páskou?

A

<M>, presný tvar na str. 5
</M>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Čo potrebujeme na vyjadrenie hierarchie priestoru?

A

Jazyk, ktorý sa s menšou pamäťou riešiť nedá a väčšia mu stačí

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Konštantný multiplikatívny nárast pamäte výpočtovú silu TS …

A

nezvyšuje, dôkaz pomocou simulácie viacpáskového na 1 páske

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Vyslov a dokáž vetu o pamäťovej hierarchii

A

Str. 6
Znenie: Nech log(n) ≤ S1(n) = o(S2(n)), kde S2(n) je páskovo konštruovateľná. Potom DSPACE(S1(n)) ⊂ DSPACE(S2(n))
Dôkaz str. 6

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Aký je to prefixný kód TS M?

A

Reťazec tvaru 1*<M>. Je zrejmé, že existuje DTS, kt. rozhoduje či reťazec z 0 a 1 je alebo nie je prefixným kódom nejakého TS (aký? ako na to?)</M>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Prečo nám stačí vo vete o pamäťovej hierarchii dokázať, že L(M1) != L(M2)?

A

IDK, nájdi to

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Vďaka čomu vieme, že hierarchia pamäťovej zložitosti je nekonečná?

A

S(n)=2^2^2^2…^2 a veta o pam. hierarchii (pozri str. 8)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Vyslov a dokáž vetu o časovej hierarchii

A

Nech n ≤ T1(n)=o(T2(n)/log T1(n)), kde T2(n) je čas. konštruovateľná. Potom DTIME(T1(n)) ⊂ DTIME(T2(n)). Dôkaz podobne ako pam. hierarchia, keď tak pozri str. 8

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Ako sa mení zložitosť pri prechode od k-páskového TS na jednopáskový?

A

Pamäťová sa zachováva a časová narastie kvadraticky

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Vyslov vetu o prechode z k-páskového TS na 2 pásky, a dokáž

A

Ku každému k-páskovému T(n)-časovo ohraničenému TS Tk ex. ekv. dvojpáskový O(Tk(n)log Tk(n)) časovo ohraničený TS T2.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Dokáž, prečo je stroj po prechode na 2 pásky tak časovo ohraničený, ako je povedané vo vete

A

str. 9-10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Čo vieme použiť na dolný odhad na priestor a na čas?

A

Čas - prechodová postupnosť
Priestor - prechodová matica

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Aký aspoň priestor potrebujú neregulárne jazyky?

A

log log n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Čo je suprémum, infímum f?

A

limita najnižšej hornej, najvyššej dolnej hranice postupnosti f(n), f(n+1),…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Definuj prechodovú post. medzi i a i+1 políčkom

A

Majme jednopáskový TS, s jednosmerne nekonečnou čítacou prepisovacou hlavou zároveň, kt. najprv zmení stav a potom pohne hlavou.

fixovaný výpočet, nejaké i => postupnosť stavov, v ktorých stroj prechádza hranicu medzi i a i+1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Ako označujeme prechodovú postupnosť medzi i a i+1 políčkom?

A

pp(i)

18
Q

Vyslov lemu o rovnakej prechodovej postupnosti a teda akceptovaní iného slova, dokáž ju

A

Nech w=w1w2…wn je akc. jednopáskovým TS T a nech prechodová post. pp(i) je rovnaká ako pp(j) (i<j). Potom T akc. aj slovo w1w2…wiw(j+1)…wn
Strana 11

19
Q

Vyslov inú podobu lemy o rovnakých pp

A

v=a1a2…an, u=b1b2…bm akc. 1páskovým TS T a pp medzi ai, ai+1 je rovnaká ako bj,bj+1. Potom T akc. aj slovo a1a2…aibj+1…bm, resp. b1b2…bjai+1…an

20
Q

Ak T je T(n) časovo ohraničený, potom súčet dĺžok pp je najviac … (a dokáž prečo)

A

T(n), lebo spraví dokopy max T(n) krokov

21
Q

Dokáž vetu 3.8 na str. 12 (wcw^R) (dolný odhad na čas)

A

str. 12

22
Q

Pre TS s jednou vstupnou a jednou pamäťovou páskou je stav pamäte daný čím?

A

Obsahom pamäťovej pásky, polohou hlavy na pamäťovej páske, stavom konečnostavovej riadiacej jednotky

23
Q

Ak je L(n) pásková zložitosť TS, tak počet rôznych stavov pamäte je … (horný odhad)

A

L(n)st^L(n) kde t je mohutnosť páskovej abecedy, s počet stavov

24
Q

Čo je to prechodová matica?

A

str 14

25
Q

Vyslov a dokáž vetu o rovnakej prechodovej matici pre 2 slová

A

str 14

26
Q

Vyslov a dokáž vetu 3.10 o dolnom odhade na pamäť

A

str 15

27
Q

Ako vieme jednoducho simulovať NTS na DTS?

A

Prehľadávanie stromu výpočtu do šírky, na jednu pásku ukladáme konf. NTS v kt. môže byť v čase i, na druhú generujeme dosiahnuteľné v čase i+1

28
Q

Aká je zložitosť jednoduchej simulácie ak zložitosť NTS je T(n)≥n a S(n)≥log n? Aj dokáž

A

čas - O(T(n)S(n)d^T(n)) kde d je maximum počtu vetvení NTS
priestor - O(S(n)d^T(n))

teda exponenciálna
dôkaz na 16

29
Q

Vyslov a dokáž Savitchovu vetu

A

Nech S(n)≥log(n) je páskovo konštruovateľná, potom NSPACE(S(n))⊆DPSACE(S^2(n))

dôkaz 17

30
Q

Aký je vzťah DTIME, NTIME, DSPACE? veta 3.12

A

DTIME(T(n)) ⊆ NTIME (T(n)) ⊆ DSPACE(T(n)), prvá inklúzia jasná, druhá na str. 18

31
Q

Aký je vzťah DSPACE, NSPACE a DTIME? Dokáž (veta 3.13)

A

DSPACE(S(n)) ⊆ NSPACE(S(n)) ⊆ zjednotenie c DTIME(c^(logn+S(n))) pre každú páskovo konštruovateľnú S(n) str 18 dole

32
Q

Koľko rôznych konfigurácii môže nadobudnúť NTS s pam. zl. S(n), q stavmi, t symbolmi a k páskami?

A

(n+2)q[(S(n)+1)t^S(n)]^k, čo je menej ako d^(log(n)+S(n)) pre vhodnú konšt. d

33
Q

Dokáž, že DLOG⊆NLOG⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP⊆NEXP

A

str 19, NSPACE(logn) ⊆ P vyplýva z vety 3.13, NP ⊆ PSPACE je dôsledkom vety 3.12, PSPACE = NPSPACE je dôsledkom Savitchovej vety a NPSPACE ⊆ EXP vyplýva z z vety 3.13.

34
Q

Dokáž: Ak NSPACE(n^4) ⊆ NSPACE(n^3), potom NSPACE(n^20) ⊆ NSPACE(n^15).

A

str. 19

35
Q

Vyslov Translačnú lemu a ideu dôkazu

A

Nech S1(n), S2(n) a f(n) sú páskovo konštruovateľné funkcie, S2(n) ≥ n, f(n) ≥ n. Potom platí:

ak NSPACE(S1(n)) ⊆ NSPACE(S2(n)) potom NSPACE(S1(f(n))) ⊆ NSPACE(S2(f(n)))

idea dôkazu: ako tvrdenie 3.1

36
Q

Dokáž: NSPACE(n3) je vlastná podmnožina NSPACE(n4).

A

str. 20

37
Q

Dokáž (predpoklad vety o medzere): Existuje rekurzívna funkcia S(n) ≥ n, pre ktorú: DSPACE(S(n)) = DSPACE(2^S(n)).

A

str. 21

38
Q

Vyslov a dokáž vetu o medzere

A

Pre každú rekurzívnu funkciu g(n) ≥ n existuje rekurzívna funkcia S(n) ≥ n taká, že platí:
DSPACE(S(n)) = DSPACE(g(S(n))).

39
Q

Vyslov a dokáž speedup theorem

A

Pre každú rekurzívnu funkciu f(n) ≥ n^2 existuje rekurzívny jazyk L taký, že pre ľubovoľný T-stroj M akceptujúci L v čase T(n) existuje T-stroj M′ tiež akceptujúci L, v čase T′(n) tak, že f(T′(n)) ≤ T(n) pre skoro všetky n.

40
Q

Vyslov a dokáž Immerman-Szelepcsényiho vetu

A

Nech funkcia f(n) je konštruovateľná, pričom f(n) ≥ logn. Potom trieda NSPACE(f(n)) je uzavretá na komplement.

Dôkaz str. 22

VZaV - 3ZIMA (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions