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)
    • Ří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 (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
  • Uložím jedničku, pokud jsou vrcholy spojené hranou

../Attachments/02-matice-sousednosti.png

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

../Attachments/02-seznam-sousedu.png

Reprezentace orientovaného grafu

../Attachments/02-repezentace-orientovaneho-grafu.png

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25