MRAM Flashcards
Čo je (M)RAM?
RAM - Random Access Machine, teda priamy prístup do pamäte, M značí či pripúšťa násobenie.
Čo obsahuj MRAM?
Program + Dátová štruktúra (pamäť)
MRAM je model počítača akého typu?
Von Neumanovského, obsahuje pamäť, program, čítač inštrukcií
Čo je pamäť?
Pole registrov, v ktorých sa nachádzajú čísla. Pritom (viac na str. 87)
Čo je vstup?
Konečná postupnosť celých čísel, ktorú čítame zľava doprava. Predpokladáme jednosmerné čítanie
Čo je výstup?
Konečná postupnosť celých čísel, ktorú vypisujeme zľava doprava.
Čo je program?
Konečná postupnosť inštrukcií, ktoré sú tvorené celočíselným návestím a inštrukciou
Aké označenia inštrukcií používame?
str. 88
Aké tri adresné módy poznáme?
- 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
Aké inštrukcie, aj s operandmi poznáme?
str. 88
Ako sa vieme pozerať na RAM?
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
Ako vieme definovať zložitosť? Aký je problém s klasickým definovaním?
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
Aká je to jednotková cena?
str. 89
Aká je to logaritmická cena?
str. 89
Aké inštrukcie naviac obsahuje MRAM oproti RAM?
DIV, MULT
Ako to je so zložitosťou a výpočtovou silou pri MRAM oproti RAM?
str. 89
Opíš vzťah časovej zložitosti medzi TS a (M)RAM, aj s dôkazom “ekvivalencie”
str. 90
Dokáž: ku každému (M)RAMu existuje ekvivalentný TS
str. 92
Prečo nie je MRAM s jednotkovou cenou rozumne definovaný model?
Lebo prechod z MRAM s jedn. cenou na TS spôsobí exponenciálny nárast zložitosti
Definuj polynomiálnu redukciu modelu M na N
str. 94
Definuj kedy sú modely M, N polynomiálne ekvivalentné
Ak je M pol. redukovateľný na N a naopak
Definuj prvú počítačovú triedu
Tie výpočtové modely, kt. sú polynomiálne ekvivalentné viacpáskovým DTS
Aké modely patria napr. do prvej počítačovej triedy?
RAM, MRAM s log. cenou, jedno/viacpáskový DTS
Ako vieme dokázať že je problém polynomiálnej zložitosti?
Stačí nám nájsť polynomiálny algoritmus na jednom z modelov 1. PC triedy
Ako vieme dokázať, že pre problém neexistuje algoritmus polynomiálnej zložitosti?
Stačí ak vyargumenujeme jeho neexistenciu na niektorom z modelov 1. PC triedy
