MRAM

Question 1

Čo je (M)RAM?

Answer 1

RAM - Random Access Machine, teda priamy prístup do pamäte, M značí či pripúšťa násobenie.

Question 2

Čo obsahuj MRAM?

Answer 2

Program + Dátová štruktúra (pamäť)

Question 3

MRAM je model počítača akého typu?

Answer 3

Von Neumanovského, obsahuje pamäť, program, čítač inštrukcií

Question 4

Čo je pamäť?

Answer 4

Pole registrov, v ktorých sa nachádzajú čísla. Pritom (viac na str. 87)

Question 5

Čo je vstup?

Answer 5

Konečná postupnosť celých čísel, ktorú čítame zľava doprava. Predpokladáme jednosmerné čítanie

Question 6

Čo je výstup?

Answer 6

Konečná postupnosť celých čísel, ktorú vypisujeme zľava doprava.

Question 7

Čo je program?

Answer 7

Konečná postupnosť inštrukcií, ktoré sú tvorené celočíselným návestím a inštrukciou

Question 8

Aké označenia inštrukcií používame?

Answer 8

str. 88

Question 9

Aké tri adresné módy poznáme?

Answer 9

• Ak x je číslo j, adresujeme obsah R(j)
• Ak x je *j, adresujeme obsah registra s číslom v R(j)
• Ak x je =j pracujeme priamo s číslom j

Question 10

Aké inštrukcie, aj s operandmi poznáme?

Answer 10

str. 88

Question 11

Ako sa vieme pozerať na RAM?

Answer 11

2 spôsoby: ako RAM kt. počíta funkciu s oborom hodnôt, alebo RAM kt. dáva ako výsledok viacero čísel. Viac info str. 88

Question 12

Ako vieme definovať zložitosť? Aký je problém s klasickým definovaním?

Answer 12

Keďže máme nekonečný register, nevieme použiť ako čas počet vykonaných inštrukcií a ako pamäť počet použitých registrov.
Poznáme teda jednotkovú a logaritmickú cenu

Question 13

Aká je to jednotková cena?

Answer 13

str. 89

Question 14

Aká je to logaritmická cena?

Answer 14

str. 89

Question 15

Aké inštrukcie naviac obsahuje MRAM oproti RAM?

Answer 15

DIV, MULT

Question 16

Ako to je so zložitosťou a výpočtovou silou pri MRAM oproti RAM?

Answer 16

str. 89

Question 17

Opíš vzťah časovej zložitosti medzi TS a (M)RAM, aj s dôkazom “ekvivalencie”

Answer 17

str. 90

Question 18

Dokáž: ku každému (M)RAMu existuje ekvivalentný TS

Answer 18

str. 92

Question 19

Prečo nie je MRAM s jednotkovou cenou rozumne definovaný model?

Answer 19

Lebo prechod z MRAM s jedn. cenou na TS spôsobí exponenciálny nárast zložitosti

Question 20

Definuj polynomiálnu redukciu modelu M na N

Answer 20

str. 94

Question 21

Definuj kedy sú modely M, N polynomiálne ekvivalentné

Answer 21

Ak je M pol. redukovateľný na N a naopak

Question 22

Definuj prvú počítačovú triedu

Answer 22

Tie výpočtové modely, kt. sú polynomiálne ekvivalentné viacpáskovým DTS

Question 23

Aké modely patria napr. do prvej počítačovej triedy?

Answer 23

RAM, MRAM s log. cenou, jedno/viacpáskový DTS

Question 24

Ako vieme dokázať že je problém polynomiálnej zložitosti?

Answer 24

Stačí nám nájsť polynomiálny algoritmus na jednom z modelov 1. PC triedy

Question 25

Ako vieme dokázať, že pre problém neexistuje algoritmus polynomiálnej zložitosti?

Answer 25

Stačí ak vyargumenujeme jeho neexistenciu na niektorom z modelov 1. PC triedy