← zpět

Stack a heap, teorie grafů

Lekce 07

Počítač a vykonávání programu

Stack a heap

Hlavní rozdíly zásobníku a haldy jsou dva, přičemž jeden je důsledkem druhého. Způsob, jakým se k datům přistupuje, se liší. To zapříčiňuje odlišný čas přístupu k datům.

int main()
{
  char *pismena_heap; // proměnná `pismena_heap` typu `char*`
                      // (tedy pointer na (nejspíše) seznam znaků)
                      // alokovaná NA STACKU

  bool tautologie = true; // proměnná typu `bool` alokovaná na
                          // STACKU

  if (tautologie)
  {
    char pismena_stack[100];  // proměnná o velikosti
                              // 100*sizeof(char), tedy 100 bytů
                              // alokovaná na STACKU

    pismena_heap = new char[100]; // 100 bytů alokovaných na HEAPU,
                                  // pointer na data na haldě
                                  // se uloží do `pismena_heap`
                                  // na STACK
  } // zde končí if, `pismena_stack` nikde později není využívaná,
    // je tedy odstraněna ze STACKU (ne garb. coll., ale instrukcí,
    // které napsal překladač)
} // zde končí celý program. kdyby tady nekončil, zapomněli bychom
  // dealokovat `pismena_heap`, vznikl by memory leak.

Poté, co program skončí, je jedno, jestli jsme paměť zapomněli dealokovat, operační systém ji odstraní sám. To neznamená, že bychom to měli dělat.

# řetězce jsou mutable, jsou předávany referencí
a = [1,2,3,4]

b = a

b.append(5)

print(id(a))
print(id(b))
# tyto dvě vytisknutí vypíší stejnou ID

print(b)
print(a)
# vypíše to stejné, protože pole je předáváno referencí

# typ `int` je immutable, při každé změně se vytvoří nový
# objekt na haldě. ano, v Pythonu je VŠE na haldě.
c = 5

d = c

d += 1

print(c) # 5
print(d) # 6

Základy teorie grafů

Uvažme následující situace:

Všechny tyto situace mají jedno společné - to, o čem pojednávají, se dá nazvat jako "objekty o kterých mluvíme" a "vztahy, které mezi nimi jsou".

Objekty, o kterých pojednáváme, nazýváme vrcholy, vztahy mezi nimi hrany.

Formálně je graf $G$ dvojice $(V, E)$. Množina $V$ je množina vrcholů, zatímco $E$ množina neuspořádaných dvojic $\set{u, v}$, kde $u,v \in V$. Pro komfort píšeme místo $\set{u,v}$ jen $uv$.

Pokud nahradíme neuspořádané dvojice v množině $E$ uspořádanými, z obyčejného grafu se stane graf orientovaný.

Pokud chceme přidat ohodnocení hran, můžeme závest i funkci $h: E \to M$, kde $M$ je množina, ze které ohodnocení bereme. Tato funkce tedy přiřazuje hranám nějaké ohodnocení.

Teď trocha terminologie:

O stupních platí jedno pěkné tvrzení. Říká se mu princip sudosti a říká, že se součet stupňů všech vrcholů rovná dvojnásobku počtu hran.

Z jednoho do druhého vrcholu můžeme dojít několika způsoby. Pokud vybereme jakoukoli posloupnost hran, říkáme této posloupnosti sled. Pokud se ve sledu neopakují hrany, této posloupnosti říkáme tah. Pokud se vrcholy neopakují, řekneme, že jde o cestu.

To, že lze z každého vrcholu dojít do každého jiného po cestě neznamená, že spolu vrcholy sousedí.

Slovo cesta je v teorii grafů dvojznačné. Jednak nám může říkat po jaké trase se vydat, abychom došli z jednoho vrcholu do druhého. Tato trasa nám ale také tvoří samostatný graf. Tento graf je jistě podgrafem grafu původního.

Dalším takovým typem grafu je kružnice, která má vrcholy $v_1,v_2,...,v_n$ a platí, že mezi $v_i$ a $v_{i+1}$ vede hrana. Musí ale také vést hrana mezi $v_n$ a $v_1$.

Pokud nemá graf jako podgraf kružnici, získává tím poměrně zajímavé vlastnosti. Říkáme jim stromy a platí, že

Více si o grafech můžete přečíst zde.