02 Výpočetní model RAM
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Výpočetní model RAM
Random Access Machine
- Paměť - potenciálně neomezené pole buněk, v každé lze skladovat libovolně velké celé číslo
- Program - konečná posloupnost sekvenčně prováděných instrukcí
- Aritmeticko-logické instrukce
- Obvykle 2 vstupní parametry
- Přímá konstanta
- Přímo adresované paměťová buňka
- Nepřímo adresované paměťová buňka (obsah buňky použiji jako adresu)
- Obvykle 2 vstupní parametry
- Řídící instrukce - skoky, podmíněné skoky, halt …
Vstup a výstup - ponechán ve stejném paměťovém poli
# Složitost programu
- Velikost vstupu - počet paměťových buněk, které zabírá
- Časová složitost programu - nejpomalejší možný průběh našeho programu pro libovolný vstup délky $N$ (vyberu ten, který je nejdelší)
- Paměťová složitost programu - nejvyšší počet použitých paměťových buněk (vyberu ten nejhorší)
# Reprezentace grafu v modelu
# Matice sousednosti
- Graf v 2D matici $n\cdot n$
- Uložím jedničku, pokud jsou vrcholy spojené hranou
# Seznam sousedů
- Lépe paměťově úspornější
- Ukládám seznam sousedů (např. spoják - datová struktura) pro každý vrchol
- Paměťová spotřeba $O(n+n)$
Reprezentace orientovaného grafu
