Pravdepodobnostné algoritmy

Question 1

Opíš načo sú dobré pravdepodobnostné algoritmy

Answer 1

str. 65

Question 2

Čo robí procedúra brand?

Answer 2

Náhodne vráti 0/1, obe s pr. 0.5

Question 3

Ako vieme pomocou brand vygenerovať náhodné číslo?

Answer 3

m-krát zavolám brand, budem brať výsledok ako m-bitové číslo

Question 4

Definuj pravdepodobnosť akceptovania/zamietania

Answer 4

str. 66

Question 5

Definuj chybu pravd. algoritmus

Answer 5

str. 66

Question 6

Definuj časovú zložitosť pravd. alg. A

Answer 6

Je T(n), ak A vykoná v každom výpočte na každom vstupe dĺžky n najviac T(n) krokov

Question 7

Ako vieme spraviť algoritmus, ktorý spustíme viackrát a na základe toho odpovieme? Aká je jeho chyba?

Answer 7

str. 66

Question 8

Vyslov a dokáž vetu o vylepšovaní

Answer 8

Str. 67

Question 9

Poriadne prečítaj dôsledok 7.2

Answer 9

str. 68

Question 10

Vyslov vetu o volaní pomocou brand a dokáž ju, aj s faktom o počte chybných výpočtov

Answer 10

str. 68

Question 11

Definuj pravdepodobnostný turingov stroj

Answer 11

str. 70

Question 12

Definuj BPP

Answer 12

Trieda jazykov, ktoré môžeme akceptovať pravd. TS v pol. čase s chybou 0≤e<1/2 (70)

Question 13

Aký je vzťah PSPACE, P, BPP?

Answer 13

P ⊆ BPP ⊆ PSPACE. Dôkaz str. 70

Question 14

Uveď príklady pravdepodobnostných algoritmov

Answer 14

Výpočet určitého integrálu, výpočet čísla pí, testovanie veľkých prvočísel, pravdepodobnostné generovanie prvočísel

Question 15

Definuj RSA, ako funguje, všetko o tom

Answer 15

str. 73

Question 16

Opíš algoritmy modulárnej aritmetiky

Answer 16

str. 75

Question 17

Ako vieme vypočítať určitý integrál?

Answer 17

str. 70

Question 18

Ako vieme vypočítať číslo pí?

Answer 18

str. 71

Question 19

Ako vieme testovať veľké prvočísla?

Answer 19

str. 72

Question 20

Ako vieme pravdepodobnostne generovať veľké prvočísla?

Answer 20

str. 73

Question 21

Ako vieme nájsť NSD?

Answer 21

76

Question 22

Definuj triedu RP

Answer 22

ak pre L existuje pravdepodobnostný polynomiálny aloritmus A taký, že ak x ∈ L, potom A akceptuje x s pravdepodobnosťou ≥ 1/2 a ak x !∈ L, potom A zamietne x s pravdepodobnosťou 1 (t.j., A sa v takomto prípade nikdy nemýli).

Question 23

Definuj ZP-pravdepodobnostný algoritmus A

Answer 23

môže výpočet skončiť s výsledkom „akceptuj“, „zamietni“ alebo „neviem“, pričom každý výpočet na každom vstupe musí skončiť práve s jedným z týchto troch výsledkov.

Question 24

Kedy patrí jazyk L do triedy ZPP?

Answer 24

ak pre L existuje ZP-pravdepodobnostný polynomiálny aloritmus A, ktorého žiadny výpočet na žiadnom vstupe neskončí s chybným výsledkom (t.j., pravdepodobnosť toho, že A akceptuje x !∈ L [zamietne x ∈ L] je 0) a pre každý vstup x platí, že pravdepodobnosť toho, že výpočet A na x skončí s výsledkom „neviem“ je ≤ 1/2