Společná informatika

1. Automaty a jazyky

• Regulární jazyky
  • deterministický konečný automat (DFA) je pětice $A=(Q,\Sigma,\delta,q_0,F)$
    • $Q$ … konečná množina stavů
    • $\Sigma$ … konečná neprázdná množina vstupních symbolů (abeceda)
    • $\delta:Q\times\Sigma\to Q$ … přechodová funkce
    • $q_0\in Q$ … počáteční stav
    • $F\subseteq Q$ … množina koncových (přijímajících) stavů
  • jazykem rozpoznávaným (přijímaným) deterministickým konečným automatem $A=(Q,\Sigma,\delta,q_0,F)$ nazveme jazyk $L(A)=\set{w\mid w\in\Sigma^*\land\delta^*(q_0,w)\in F}$
  • slovo je přijímáno automatem $A\equiv w\in L(A)$
  • jazyk $L$ je rozpoznatelný konečným automatem $\equiv$ existuje konečný automat $A$ takový, že $L=L(A)$
  • třídu jazyků rozpoznatelných konečnými automaty označíme $\mathcal F$, nazveme regulární jazyky
  • iterační (pumping) lemma
    • nechť $L$ je regulární jazyk
    • $(\exists n\in\mathbb N)(\forall w\in L):|w|\geq n\implies w=xyz$
      • $y\neq\epsilon$
      • $|xy|\leq n$
      • $\forall k\geq 0:xy^kz\in L$
  • věta: neregularita $L_{01}=\set{0^i1^i\mid i\geq 0}$
    • předpokládejme regularitu $L_{01}$
    • vezměme $n$ z pumping lemmatu
    • zvolme $w=0^n1^n$
    • rozdělme $w=xyz$ dle pumping lemmatu
      • $|xy|\leq n$ je na začátku $w$, takže obsahuje jen nuly
      • $y\neq\epsilon$
    • z pumping lemmatu $xz\in L_{01}$, což je spor, protože $xz$ obsahuje méně nul než jedniček
  • kongruence
    • mějme konečnou abecedu $\Sigma$ a relaci ekvivalence $\sim$ na $\Sigma^*$
    • $\sim$ je pravá kongruence $\equiv(\forall u,v,w\in\Sigma^*):u\sim v\implies uw\sim vw$
    • $\sim$ je konečného indexu $\equiv$ rozklad $\Sigma^*/\sim$ má konečný počet tříd
    • třídu kongruence $\sim$ obsahující slovo $u$ značíme $[u]_\sim$ nebo $[u]$
    • příklady
      • relace „končí stejným písmenem“ je pravá kongruence
      • relace „mají stejný počet znaků“ není konečného indexu
  • Myhill-Nerodova věta
    • nechť $L$ je jazyk nad konečnou abecedou $\Sigma$
    • potom následující trzení jsou ekvivalentní:
      • $L$ je rozpoznatelný konečným automatem
      • existuje pravá kongruence $\sim$ konečného indexu nad $\Sigma^*$ tak, že $L$ je sjednocením jistých tříd rozkladu $\Sigma^*/\sim$
    • použití k důkazu neregularity
      • ukážeme pro pumpovatelný jazyk slov ve tvaru $a^+b^ic^i$ nebo $b^ic^j$
      • pro regulární $L$ musí existovat pravá kongruence konečného indexu $m$
      • mějme množinu řetězců $S=\set{ab,abb,abbb,\dots,ab^{m+1}}$
      • $|S|=m+1$, tedy nutně existují dvě slova $i\neq j$, která padnou do stejné třídy
        • $ab^i\sim ab^j$
        • tedy $ab^ic^i\sim ab^jc^i$
        • ale $ab^ic^i\in L$ a $ab^jc^i\notin L$, což je spor, takže jazyk není regulární
  • věta: jazyk $L$ je rozpoznatelný $\epsilon$NFA, právě když je $L$ regulární
    • pro libovolný $\epsilon$NFA $N$ zkonstruujeme DFA $D$ přijímající stejný jazyk jako $N$
    • nové stavy jsou $\epsilon$-uzavřené podmnožiny $Q_N$
• Deterministický a nedeterministický konečný automat
  • deterministický konečný automat (DFA) je pětice $A=(Q,\Sigma,\delta,q_0,F)$
    • $Q$ … konečná množina stavů
    • $\Sigma$ … konečná neprázdná množina vstupních symbolů (abeceda)
    • $\delta:Q\times\Sigma\to Q$ … přechodová funkce
    • $q_0\in Q$ … počáteční stav
    • $F\subseteq Q$ … množina koncových (přijímajících) stavů
  • nedeterministický konečný automat s $\epsilon$ přechody je pětice $A=(Q,\Sigma,\delta,q_0,F)$
    • $Q$ … konečná množina stavů
    • $\Sigma$ … konečná množina vstupních symbolů (abeceda)
    • $\delta:Q\times(\Sigma\cup\set{\epsilon})\to \mathcal P(Q)$ … přechodová funkce vracející podmnožinu $Q$
    • $q_0\in Q$ … počáteční stav
      • alternativa: množina počátečních stavů $S_0\subseteq Q$
    • $F\subseteq Q$ … množina koncových (přijímajících) stavů
  • $\epsilon$-uzávěr … všechny stavy, kam se z daného stavu dostaneme prázdným slovem
  • podmnožinová konstrukce
    • věta: jazyk $L$ je rozpoznatelný $\epsilon$NFA, právě když je $L$ regulární
    • pro libovolný $\epsilon$NFA $N$ zkonstruujeme DFA $D$ přijímající stejný jazyk jako $N$
    • nové stavy jsou $\epsilon$-uzavřené podmnožiny $Q_N$
      • $Q_D\subseteq\mathcal P(Q_N)$
      • $\forall S\subseteq Q_N:\epsilon\text{closure}(S)\in Q_D$
      • v $Q_D$ může být i $\emptyset$
    • počáteční stav je $\epsilon$-uzávěr $q_0$
      • $q_{D_0}=\epsilon\text{closure}(q_{N_0})$
    • přijímající stavy jsou všechny množiny obsahující nějaký přijímající stav
      • $F_D=\set{S\in Q_D: S\cap F_N\neq\emptyset}$
    • přechodová funkce sjednotí a $\epsilon$-uzavře přechody z jednotlivých stavů
      • pro $S\in Q_D,\,x\in\Sigma$ definujeme $\delta_D(S,x)=\epsilon\text{closure}\left(\bigcup_{p\in S}\delta_N(p,x)\right)$
• Regulární výrazy
  • regulární výrazy
    • $\text{RegE}(\Sigma)$ … množina všech regulárních výrazů nad konečnou neprázdnou abecedou
    • $L(\alpha)$ … hodnota regulárního výrazu $\alpha$
    • regulární výraz a jeho hodnota jsou definovány induktivně
      • základ
        • $\epsilon$ … prázdný řetězec, $L(\epsilon)=\set{\epsilon}$
        • $\emptyset$ … prázdný výraz, $L(\emptyset)=\emptyset$
        • $a$ … znak $a\in\Sigma$, $L(a)=\set{a}$
      • indukce
        • $\alpha+\beta$ … jako OR, $L(\alpha+\beta)=L(\alpha)\cup L(\beta)$
        • $\alpha\beta$ … $L(\alpha\beta)=L(\alpha)L(\beta)$
        • $\alpha^*$ … $L(\alpha^*)=L(\alpha)^*$
        • $(\alpha)$ … závorky nemění hodnotu, $L((\alpha))=L(\alpha)$
    • nejvyšší prioritu má iterace $^*$, pak zřetězení, pak sjednocení $+$
    • třída $\text{RegE}(\Sigma)$ je nejmenší třída uzavřená na uvedené operace
  • Kleeneho věta
    • každý jazyk reprezentovaný konečným automatem lze zapsat jako regulární výraz
    • každý jazyk popsaný regulárním výrazem lze zapsat jako $\epsilon$NFA
• Gramatika, jazyk generovaný gramatikou
  • formální (generativní) gramatika je čtveřice $G=(V,T,P,S)$
    • $V$ … konečná množina neterminálů (variables)
    • $T$ … neprázdná konečná množina terminálních symbolů (terminálů)
    • $S\in V$ … počáteční symbol
    • $P$ … konečná množina pravidel (produkcí) reprezentující rekurzivní definici jazyka
      • každé pravidlo má tvar $\beta A\gamma\to\omega$
        • $A\in V$
        • $\beta,\gamma,\omega\in (V\cup T)^*$
      • tj. levá strana obsahuje aspoň jeden neterminální symbol
  • jazyk $L(G)$ generovaný gramatikou $G=(V,T,P,S)$ je množina terminálních řetězců, pro které existuje derivace ze startovního symbolu $L(G)=\set{w\in T^*: S\Rightarrow_G^* w}$
  • jazyk neterminálu $A\in V$ definujeme $L(A)=\set{w\in T^*: A\Rightarrow_G^* w}$
• Zásobníkový automat, třída jazyků přijímaných zásobníkovými automaty
  • zásobníkový automat (PDA) je sedmice $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$
    • $Q$ … konečná množina stavů
    • $\Sigma$ … neprázdná konečná množina vstupních symbolů
    • $\Gamma$ … neprázdná konečná zásobníková abeceda
    • $\delta$ … přechodová funkce
      • $\delta:Q\times(\Sigma\cup\set{\epsilon})\times\Gamma\to \mathcal P_{FIN}(Q\times\Gamma^*)$
        • kde $\mathcal P_{FIN}(A)$ je množina všech konečných podmnožin množiny $A$
      • tedy $\delta(p,a,X)\ni(q,\gamma)$
        • $q$ je nový stav
        • $\gamma$ je řetězec zásobníkových symbolů, který nahradí $X$ na vrcholu zásobníku
    • $q_0\in Q$ … počáteční stav
    • $Z_0\in\Gamma$ … počáteční zásobníkový symbol
    • $F$ … množina přijímajících (koncových) stavů (může být nedefinovaná)
    • jak PDA funguje
      • je nedeterministický
      • v jednom časovém kroku
        • na vstupu přečte žádný nebo jeden symbol
        • přejde do nového stavu
        • nahradí symbol na vrchu zásobníku libovolným řetězcem (nejlevější znak bude na vrchu)
    • přechodový diagram
      • jako pro konečný automat
      • hrany popisujeme ve tvaru: vstupní znak, zásobníkový znak → push řetězec
  • jazyk přijímaný koncovým stavem je $L(P_{da})=\set{w\in\Sigma^*:(\exists q\in F)(\exists\alpha\in\Gamma^*)((q_0,w,Z_0)\vdash^*_{P_{da}}(q,\epsilon,\alpha))}$
  • jazyk přijímaný prázdným zásobníkem je $N(P_{da})=\set{w\in\Sigma^*:(\exists q\in Q)((q_0,w,Z_0)\vdash^*_{P_{da}}(q,\epsilon,\epsilon))}$
    • množina $F$ je nerelevantní, takže ji lze vynechat – pak je PDA šestice
  • lemma: od přijímajícího stavu k prázdnému zásobníku
    • na dno zásobníku přidáme špunt
    • z přijímajících stavů vedeme hranu do vypouštěcího stavu, kde zásobník vyprázdníme
  • lemma: od prázdného zásobníku ke koncovému stavu
    • na dno zásobníku přidáme špunt
    • z každého stavu uděláme přechod takový, že pokud je vidět špunt, přemístíme se do koncového stavu
  • věta: následující tvrzení jsou ekvivalentní
    • jazyk $L$ je bezkontextový, tj. generovaný bezkontextovou gramatikou
    • jazyk $L$ je přijímaný nějakým zásobníkovým automatem koncovým stavem
    • jazyk $L$ je přijímaný nějakým zásobníkovým automatem prázdným zásobníkem
  • konstrukce PDA z CFG
    • mějme gramatiku $G=(V,T,P,S)$
    • konstruujeme PDA $P=(\set{q},T,V\cup T,\delta,q,S)$
      • $\forall A\in V:\delta(q,\epsilon,A)=\set{(q,\beta)\mid (A\to \beta)\in P}$
      • $\forall a\in T:\delta(q,a,a)=\set{(q,\epsilon)}$
      • $P$ přijímá prázdným zásobníkem
    • idea
      • stavy nás nezajímají – stačí nám jeden
      • na zásobníku nedeterministicky generujeme všechny možné posloupnosti terminálů
• Pumping lemma pro bezkontextové jazyky
  • lemma o vkládání (pumping) pro bezkontextové jazyky
    • nechť $L$ je bezkontextový jazyk
    • $(\exists n)(\forall w\in L):|w|\geq n\implies w=u_1u_2u_3u_4u_5$
      • $u_2u_4\neq\epsilon$
      • $|u_2u_3u_4|\leq n$
      • $\forall k\geq 0:u_1u_2^ku_3u_4^ku_5\in L$
    • poznámka: v prezentaci je ostrá nerovnost $|w|\gt n$, v jiných zdrojích neostrá
  • idea důkazu
    • vezmeme derivační strom pro $w$
    • nejdeme nejdelší cestu, na ní dva stejné neterminály
    • tyto neterminály určí dva postromy, které definují rozklad slova
    • větší podstrom můžeme posunout ($k\gt 1$) nebo nahradit menším podstromem ($k=0$)
  • příklad: $L_{012}=\set{0^i1^i2^i\mid i\geq 1}$ není bezkontextový
    • důkaz sporem – předpokládejme bezkontextovost
    • vezmeme $n$ z pumping lemmatu
    • zvolíme $w=0^n1^n2^n$
    • délka pumpovacího slova $u_2u_3u_4$ musí být nejvýše $n$, tedy vždy můžeme pumpovat maximálně dva různé symboly
    • $u_2u_4\neq\epsilon\implies$ iterací se slovo změní
    • tím se poruší rovnost symbolů
    • tedy ať už zvolíme libovolné dělení $u_1u_2u_3u_4u_5$, nové slovo nebude patřit do $L_{012}$, což je spor
• Chomského normální tvar
  • o bezkontextové gramatice $G=(V,T,P,S)$ bez zbytečných symbolů, kde jsou všechna pravidla ve tvaru $A\to BC$ nebo $A\to a$, kde $A,B,C\in V,\, a\in T$, říkáme, že je v Chomského normálním tvaru (ChNF)
  • algoritmus převodu
    • eliminujeme $\epsilon$-pravidla
      • označíme nulovatelné symboly
      • přidáme verzi pravidel bez nulovatelných symbolů
      • odstraníme $\epsilon$-pravidla
    • eliminujeme jednotková pravidla (tím nepřidáme $\epsilon$-pravidla)
      • najdeme jednotkové páry
      • přidáme odpovídající pravidla
      • odstraníme jednotková pravidla
    • eliminujeme zbytečné symboly (tím nepřidáme žádná pravidla)
      • nejdříve eliminujeme negenerující, pak nedosažitelné
    • pravé strany délky aspoň 2 předěláme na samé neterminály
    • pravé strany s aspoň třemi neterminály rozdělíme na více pravidel
• Turingův stroj
  • turingův stroj (TM) je sedmice $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$
    • $Q$ … konečná množina stavů
    • $\Sigma$ … konečná neprázdná množina vstupních symbolů
    • $\Gamma$ … konečná množina všech symbolů pro pásku
      • vždy $\Gamma\supseteq\Sigma,\,Q\cap\Gamma=\emptyset$
    • $\delta$ … (částečná) přechodová funkce
      • zobrazení $(Q-F)\times\Gamma\to Q\times\Gamma\times\set{L,R}$
      • $\delta(q,X)=(p,Y,D)$
        • $q\in (Q-F)$ … aktuální stav
        • $X\in \Gamma$ … aktuální symbol na pásce
        • $p\in Q$ … nový stav
        • $Y\in\Gamma$ … symbol pro zapsání do aktuální buňky, přepíše aktuální obsah
        • $D\in\set{L,R}$ … směr pohybu hlavy (doleva, doprava)
    • $q_0\in Q$ … počáteční stav
    • $B\in\Gamma\setminus\Sigma$ … blank = symbol pro prázdné buňky, na začátku všude kromě konečného počtu buněk se vstupem
    • $F\subseteq Q$ … množina koncových neboli přijímajících stavů
    • poznámka: někdy se nerozlišuje $\Gamma$ a $\Sigma$ a neuvádí se $B$, pak je TM pětice
  • turingův stroj $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ přijímá jazyk $L(M)=\set{w\in\Sigma^*:(\exists p\in F)(\exists \alpha,\beta\in\Gamma^*)(q_0w\vdash_M^*\alpha p\beta)}$
    • tj. množinu slov, po jejichž přečtení se dostane do koncového stavu
    • pásku nemusí uklízet (v naší definici)
  • jazyk nazveme rekurzivně spočetným, pokud je přijímán nějakým Turingovým strojem
  • říkáme, že TM $M$ rozhoduje jazyk $L$, pokud $L=L(M)$ a pro každé $w\in\Sigma^*$ stroj nad $w$ zastaví
    • jazyky rozhodnutelné TM nazýváme rekurzivní jazyky
    • rekurzivní jazyky jsou podmnožinou rekurzivně spočetných jazyků
• Algoritmicky nerozhodnutelné problémy
  • rozhodnutelný problém
    • problém … množina otázek (nebo spíše vstupů) kódovatelná řetězci nad abecedou $\Sigma$ s odpověďmi $\in\set{\text{ano},\text{ne}}$
      • pokud problém definuji jako množinu, jde o otázku, zda vstup kóduje prvek dané množiny (např. polynom s celočíselným kořenem)
    • problém je (algoritmicky) rozhodnutelný, pokud existuje TM takový, že pro každý vstup $w\in P$ TM zastaví a navíc přijme, právě když $P(w)=\text{ano}$ (tj. pro $P(w)=\text{ne}$ zastaví v nepřijímajícím stavu)
    • nerozhodnutelný problém … není rozhodnutelný
    • existuje analogie mezi rozhodnutelným problémem a rekurzivním jazykem
  • redukce problému
    • definice: redukcí problému $P_1$ na $P_2$ nazýváme algoritmus $R$, který pro každou instanci $w\in P_1$ zastaví a vydá $R(w)\in P_2$, přičemž…
      • $P_1(w)=\text{ano}\iff P_2(R(w))=\text{ano}$
      • tedy i $P_1(w)=\text{ne}\iff P_2(R(w))=\text{ne}$
    • věta: existuje-li redukce problému $P_1$ na $P_2$, pak…
      • pokud $P_1$ je nerozhodnutelný, pak je nerozhodnutelný i $P_2$
      • pokud $P_1$ není rekurzivně spočetný, pak není rekurzivně spočetný ani $P_2$
  • problém zastavení není rozhodnutelný
    • definice: instancí problému zastavení je dvojice řetězců $M,w\in\set{0,1}^*$
    • definice: problém zastavení je najít algoritmus $\text{Halt}(M,w)$, který vydá 1, právě když stroj $M$ zastaví na vstupu $w$, jinak vydá 0
    • věta: problém zastavení není rozhodnutelný
    • idea důkazu: redukujeme $L_d$ na $\text{Halt}$
  • diagonální jazyk
    • diagonální jazyk $L_d$ je definovaný jako jazyk slov $w\in\set{0,1}^*$ takových, že TM reprezentovaný jako $w$ nepřijímá slovo $w$
    • věta: $L_d$ není rekurzivně spočetný jazyk, tj. neexistuje TM přijímající $L_d$
    • idea důkazu
      • kdyby existoval TM přijímající $L_d$, spuštění takového stroje na vlastním kódu by vedlo k paradoxu
  • univerzální jazyk $L_u$ definujeme jako množinu binárních řetězců, které kódují pár $(M,w)$, kde $M$ je TM a $w\in L(M)$
  • TM přijímající $L_u$ se nazývá univerzální Turingův stroj
    • existuje
  • problém univerzálního jazyka není rozhodnutelný
    • věta: $L_u$ je rekurzivně spočetný, ale není rekurzivní
    • mohli bychom zkonstruovat TM přijímající $L_d$
  • problém prázdnosti jazyka daného TM není rozhodnutelný
• Chomského hierarchie
  • gramatiky typu 0 (rekurzivně spočetné jazyky $\mathcal L_0$)
    • pravidla v obecné formě $\alpha\to\omega$
      • $\alpha,\omega\in(V\cup T)^*$
      • $\alpha$ obsahuje neterminál
    • rekurzivně spočetný jazyk je rozpoznatelný (nějakým) Turingovým strojem
  • gramatiky typu 1 (kontextové gramatiky, jazyky $\mathcal L_1$)
    • pouze pravidla ve tvaru $\gamma A\beta\to\gamma\omega\beta$
      • $A\in V$
      • $\gamma,\beta\in(V\cup T)^*$
      • $\omega\in (V\cup T)^+$
      • jedinou výjimkou je pravidlo $S\to\epsilon$, pak se ale $S$ nevyskytuje na pravé straně žádného pravidla
    • kontextový jazyk je rozpoznatelný lineárně omezeným automatem (LBA, lineárně omezený Turingův stroj)
  • gramatiky typu 2 (bezkontextové gramatiky, jazyky $\mathcal L_2$)
    • pouze pravidla ve tvaru $A\to\omega$
      • $A\in V$
      • $\omega\in(V\cup T)^*$
    • bezkontextový jazyk je rozpoznatelný nedeterministickým zásobníkovým automatem
  • gramatiky typu 3 (regulární gramatiky / pravé lineární gramatiky, regulární jazyky $\mathcal L_3$)
    • pouze pravidla ve tvaru $A\to\omega B$ nebo $A\to\omega$
      • $A,B\in V$
      • $\omega\in T^*$
    • idea
      • každý neterminál odpovídá stavu konečného automatu
      • pravidla odpovídají přechodové funkci
    • regulární jazyk je rozpoznatelná konečným automatem
• Schopnost zařazení konkrétního jazyka do Chomského hierarchie (zpravidla sestrojení odpovídajícího automatu či gramatiky)
  • obvykle chceme jazyk zařadit co nejpřesněji – např. říct, že není regulární (dokázat pomocí iteračního lemmatu) a že je bezkontextový (sestavit CFG)
  • je regulární: sestrojíme konečný automat
  • není regulární: použijeme iterační lemma nebo Myhill-Nerodovu větu
  • je bezkontextový: sestrojíme bezkontextovou gramatiku
  • není bezkontextový: použijeme lemma o vkládání
  • kontextovostí se obvykle nezabýváme
    • lemma: jazyk $L=\set{a^ib^jc^k\mid1\leq i\leq j\leq k}$ je kontextový jazyk, není bezkontextový
  • je rekurzivně spočetný: popíšeme algoritmus
    • algoritmus pro $0^n1^n$
      • jezdíme tam a zpátky po pásce, přičemž $0$ přepíšeme na $X$, znak $1$ přepíšeme na $Y$
      • přijmeme, pokud nám jedničky a nuly dojdou ve stejnou chvíli (páska je popsaná samými $X$ a $Y$)
  • není rekurzivně spočetný (nebo případně jenom rekurzivní): dokážeme pomocí $L_d$
  • uzavřenost operací
    • regulární jazyky jsou uzavřené na množinové (sjednocení, průnik, rozdíl, doplněk) i řetězcové operace ($L{.}M,L^*,L^+,L^R,M\setminus L,L/M$), na homomorfismus a inverzní homomorfismus
      • doplněk: obrátíme „koncovost“ stavů
      • průnik, sjednocení, rozdíl
        • zkonstruujeme součinový automat $(Q_1\times Q_2,\Sigma,\delta,(q_{0_1},q_{0_2}),F)$
          • kde $\delta((p,q),x)=(\delta_1(p,x),\delta_2(q,x))$
        • průnik … $F=F_1\times F_2$
        • sjednocení … $F=(F_1\times Q_2)\cup(Q_1\times F_2)$
        • rozdíl … $F=F_1\times (Q_2-F_2)$
    • bezkontextové jazyky jsou uzavřené na sjednocení, konkatenaci, iteraci, reverzi, naopak neuzavřené na průnik (ale jsou uzavřené na průnik s regulárním jazykem)
    • uzavřenost můžeme použít k důkaz regularity nebo bezkontextovosti
    • ale můžeme ji použít i k důkazu neregularity jazyka $L$ – kdybychom aplikací uzavřených operací na jazyk $L$ a regulární jazyky dostali jazyk $L'$, který zjevně není regulární (např. $0^i1^i$)
• Příklad kontextového jazyka
  • lemma: jazyk $L=\set{a^ib^jc^k\mid1\leq i\leq j\leq k}$ je kontextový jazyk, není bezkontextový
  • pravidla
    • $S\to aSBC|aBC$ … generování symbolů $a$
    • $B\to BBC$ … množení symbolů $B$
    • $C\to CC$ … množení symbolů $C$
    • $CB\to BC$ … uspořádání symbolů $B$ a $C$ (pravidlo není kontextové, je potřeba ho upravit nadtrháváním)
    • $aB\to ab$ … začátek přepisu $B$ na $b$
    • $bB\to bb$ … pokračování přepisu $B$ na $b$
    • $bC\to bc$ … začátek přepisu $C$ na $c$
    • $cC\to cc$ … pokračování přepisu $C$ na $c$
  • je důležité, že tam chybí $cB\to cb$

2. Algoritmy a datové struktury

• Časová a prostorová složitost algoritmu
  • pro různé úlohy používáme různé parametrizace vstupu (tedy velikost vstupu může být trochu něco jiného – někdy počet čísel, někdy jejich hodnota…)
  • doba běhu pro vstup x
    • $t(x):=$ součet cen provedených instrukcí (může být $\infty$)
  • časová složitost výpočtu
    • $T(n):= \text{max}\lbrace t(x)\mid x \text{ vstup velikosti }n\rbrace$
  • prostor běhu pro vstup x
    • $s(x):=$ max. adresa – min. adresa + 1
    • máme na mysli maximální a minimální adresy navštívené během výpočtu
  • prostorová složitost výpočtu
    • $S(n):= \text{max}\lbrace s(x)\mid x \text{ vstup velikosti }n\rbrace$
  • takhle jsme definovali složitosti v nejhorším případě, někdy se může hodit i průměrný případ
• Měření velikosti dat
  • spotřebovanou paměť definujeme jako rozdíl mezi nejvyšším a nejnižším použitým indexem paměti
  • paměťová složitost pak odpovídá maximu ze spotřeby paměti přes všechny vstupy dané velikosti
  • do časové složitosti nepočítáme načtení vstupu
  • podobně do prostorové složitosti nepočítáme vstup, do nějž se nezapisuje, ani výstup, pokud se jenom zapíše a pak už se nečte (takhle se někdy definuje pracovní prostor výpočtu)
  • je potřeba omezit kapacitu paměťové buňky
    • jednotková cena instrukce – omezíme šířku slova na W bitů
    • logaritmická cena instrukce – cena odpovídá počtu bitů operandů včetně adres (je přesný, ale nepohodlný na přemýšlení o algoritmech)
    • relativní logaritmická cena instrukce – u polynomiálně velkých čísel je cena jednotková, u obrovských čísel se cena zvyšuje (tohle budeme reálně používat – i když se k tomu budeme obvykle chovat jako k jednotkové ceně instrukce)
• Složitost v nejlepším, nejhorším a průměrném případě
  • nejčastěji se používá složitost v nejhorším případě
    • složitost pro nejhorší možný vstup
  • složitost v průměrném případě dobře charakterizuje kvalitu algoritmu, ale je obtížné ji odvodit
    • průměrujeme přes všechny možné vstupy
• Asymptotická notace
  • $f\in O(g)\equiv\exists c\,\forall^*n\;f(n)\leq c\cdot g(n)$
    • $f,g:\mathbb N\to\mathbb R$
    • $\forall^*n$ … pro všechna $n$ až na konečně mnoho výjimek (existuje $n_0$ takové, že pro všechna větší $n$ už to platí)
  • $f\in \Omega(g)\equiv\exists c\,\forall^*n\;f(n)\geq c\cdot g(n)$
  • $\Theta(g):= O(g)\cap \Omega(g)$
• Třídy P a NP
  • problém $L\in \text P\equiv\exists A$ algoritmus $\exists p$ polynom takový, že $\forall x$ vstup platí, že $A(x)$ doběhne do $p(|x|)$ kroků $\land\;A(x)=L(x)$
  • problém $L\in \text{NP}\equiv\exists V\in P$ (verifikátor) $\exists g$ polynom (omezení délky certifikátů) $\forall x:L(x)=1\iff$ $\exists y$ certifikát $|y|\leq g(|x|)$ (krátký) $\land\;V(x,y)=1$ (schválený)
  • $\text P\subseteq\text{NP}$ (rovnost se neví)
• Převoditelnost problémů, NP-těžkost a NP-úplnost
  • rozhodovací problém $\equiv$ funkce $f:\set{0,1}^*\to\set{0,1}$
  • převod
    • mějme rozhodovací problémy $A,B$
    • problém $A$ je převoditelný na problém $B$ právě tehdy, když existuje funkce $f:\set{0,1}^*\to\set{0,1}^*$ taková, že $\forall\alpha\in\set{0,1}^*:A(\alpha)=B(f(\alpha))$ a $f$ lze spočítat v čase polynomiálním vzhledem k $|\alpha|$
    • značíme $A\to B$ nebo $A\leq_P B$
    • funkci $f$ říkáme převod (případně redukce)
  • vlastnosti převoditelnosti
    • je reflexivní $(A\to A)$ … $f$ je identita
    • je tranzitivní $(A\to B\land B\to C\implies A\to C)$ … když $f$ převádí $A$ na $B$ a $g$ převádí $B$ na $C$, tak $f\circ g$ převádí $A$ na $C$ (přičemž složení polynomiálně vyčíslitelných funkcí je polynomiálně vyčíslitelná funkce)
    • není antisymetrická – např. problémy „vstup má sudou délku“ a „vstup má lichou délku“ lze mezi sebou převádět oběma směry
    • existují navzájem nepřevoditelné problémy – např. mezi problémy „na každý vstup odpověz 0“ a „na každý vstup odpověz 1“ nemůže existovat převod
    • převoditelnost je částečné kvaziuspořádání na množině všech problémů
  • definice: NP-těžké a NP-úplné problémy
    • $L$ je NP-těžký $\equiv\forall K\in\text{NP}:K\to L$
    • $L$ je NP-úplný $\equiv L$ je NP-těžký $\land\;L\in\text{NP}$
  • věta: pokud $A\to B$ a $B\in \text P$, pak $A\in \text P$
  • věta: pokud $A→B$, $B\in \text{NP}$ a $A$ je NP-úplný, pak $B$ je NP-úplný
• Příklady NP-úplných problémů a převodů mezi nimi
  • logické: (CNF) SAT, 3-SAT, 3,3-SAT, obvodový SAT
  • grafové: nezávislá množina, klika, $k$-obarvitelnost (pro $k\geq 3$), hamiltonovská cesta/kružnice, 3D-párování
  • číselné: součet podmnožiny, batoh, 2 loupežníci, nulajedničkové řešení soustavy lineárních rovnic (v $\mathbb Z$)
  • popisy problémů
    • klika: existuje úplný podgraf grafu $G$ na alespoň $k$ vrcholech?
    • nezávislá množina: existuje nezávislá množina vrcholů grafu $G$ velikosti aspoň $k$?
      • množina vrcholů grafu je nezávislá $\equiv$ žádné dva vrcholy ležící v této množině nejsou spojeny hranou
    • SAT: existuje dosazení 0 a 1 za proměnné tak, aby $\psi(\dots)=1$?
      • kde $\psi$ je v CNF
    • 3-SAT: jako SAT, akorát každá klauzule formule $\psi$ obsahuje nejvýše tři literály
    • 3,3-SAT: jako 3-SAT, akorát se každá proměnná vyskytuje v maximálně třech literálech
    • 3D-párování
      • vstup: tři množiny $A,B,C$ a množina kompatibilních trojic $T\subseteq A\times B\times C$
      • výstup: existuje perfektní podmnožina trojic? tzn. existuje taková podmnožina, v níž se každý prvek množin $A,B,C$ účastní právě jedné trojice
  • převod klika ↔ nezávislá množina
    • pokud v grafu prohodíme hrany a nehrany, stane se z každé kliky nezávislá množina a naopak
    • převodní funkce zneguje hrany
  • při převodu problémů typu SAT vyrábíme ekvisplnitelnou formuli
  • SAT → 3-SAT
    • $(\alpha\lor\beta)\to(\alpha\lor\zeta)\land(\beta\lor\neg\zeta)$
    • převod funguje i naopak (viz rezoluce)
    • jak rozštípnout dlouhou klauzuli délky $\ell$?
      • $\alpha$ nechť má délku 2
      • $\beta$ nechť má délku $\ell-2$
      • po přidání $\zeta$ dostanu konjunkci klauzulí délky 3 a $\ell-1$
      • klauzuli délky $\ell-1$ štípu dál (pokud je moc dlouhá)
    • počet štípnutí je shora omezen délkou formule
    • v polynomiálním čase postupně rozštípeme všechny dlouhé klauzule při zachování splnitelnosti
  • 3-SAT → 3,3-SAT
    • nechť $x$ je proměnná s $k\gt 3$ výskyty
    • pro každý výskyt si pořídíme nové proměnné $x_1,\dots,x_k$
    • ekvivalenci všech $x_i$ zajistíme řetězcem implikací
      • $x_1\implies x_2$
      • $x_2\implies x_3$
      • $\quad\vdots$
      • $x_k\implies x_1$
    • každá proměnná $x_i$ se tudíž vyskytne třikrát
  • 3,3-SAT* … navíc každý literál max. 2×
    • použijeme předchozí algoritmus pro všechny proměnné s $k \geq 3$ výskyty
  • 3-SAT → nezávislá množina
    • pro každou z $k$ klauzulí formule vytvoříme trojúhelník a jeho vrcholům přiřadíme literály klauzule
      • pokud klauzule obsahuje méně než tři literály, tak přebývající vrcholy smažeme
    • spojíme hranami všechny dvojice konfliktních literálů
    • v takovém grafu existuje nezávislá množina velikosti alespoň $k$ právě tehdy, když je formule splnitelná
      • máme-li splňující ohodnocení, můžeme z každé klauzule vybrat jeden pravdivý literál – ty umístíme do nezávislé množiny
      • máme-li nezávislou množinu velikosti $k$, vybereme literály odpovídající těmto vrcholům a podle nich nastavíme odpovídající proměnné
        • v nezávislé množině velikosti $k$ nemůžou být dva vrcholy ze stejného trojúhelníku – tedy z každého trojúhelníku (klauzule) bude v množině právě jeden vrchol
        • v nezávislé množině nemohou být dva vrcholy s opačnými literály, protože takové vrcholy jsou spojeny hranou
  • nezávislá množina → 3-SAT
    • každému vrcholu odpovídá jedna proměnná (pokud je proměnná ohodnocena jedničkou, vrchol náleží do nezávislé množiny)
    • pro každou hranu přidáme klauzuli $(\neg x_i\lor\neg x_j)$, která zajistí, že obě proměnné nebudou splněny zároveň
    • chceme nezávislou množinu velikosti $k$, takže musíme vrcholy v množině spočítat
      • pořídíme si tabulku (pomocí jiných proměnných $y_{ij}$)
      • vynutíme, aby v každém sloupci byla maximálně jedna jednička a v každém řádku právě jedna jednička
    • propojíme proměnné $x_j$ a $y_{ij}$ pomocí implikace $x_{ij}\to x_j$
• Metoda rozděl a panuj: princip rekurzivního dělení problému na podproblémy
  • problém rekurzivně dělíme na menší a menší podproblémy, dokud nedojdeme k problému konstantní velikosti, který umíme vyřešit triviálně
  • problémy v jedné úrovni dělení na sobě musí být nezávislé
• Metoda rozděl a panuj: výpočet složitosti pomocí rekurentních rovnic
  • vyjádříme složitost algoritmu (tedy $T(n)$) pomocí složitosti podproblému, tím dostaneme rekurzivní rovnici
  • do rovnice můžeme postupně dosazovat a vypozorovat nějaký obecný vzorec – chceme dojít až k $T(1)$
  • nebo můžeme rovnou použít Master theorem
  • případně ze složitosti $i$-té úrovně můžeme odvodit složitost celého algoritmu (součtem přes všechny úrovně)
• Master theorem (kuchařková věta) – bez důkazu
  • uvažujeme rekurzivní algoritmus, který vstup rozloží na $a$ podproblémů velikosti $n/b$ a z jejich výsledků složí celkovou odpověď v čase $\Theta(n^c)$
  • věta: rekurentní rovnice $T(n)=a\cdot T(n/b)+\Theta(n^c),\;T(1)=1$ má pro konstanty $a\in\set{1,2,\dots},\,b\in(1,\infty),\,c\in[0,\infty)$ řešení…
    • $T(n)=\Theta(n^c\log n)$, pokud $a/b^c=1$
    • $T(n)=\Theta(n^c)$, pokud $a/b^c\lt 1$
    • $T(n)=\Theta(n^{\log_b a})$, pokud $a/b^c\gt 1$
• Metoda rozděl a panuj: aplikace (Mergesort, násobení dlouhých čísel)
  • Mergesort
    • na vstupu posloupnost
    • pokud je délka posloupnosti menší rovna jedné, mergesort vrátí vstup
    • jinak vrátí merge(mergesort(první polovina vstupu), mergesort(druhá polovina vstupu)), kde merge slévá dvě poloviční setříděné posloupnosti v lineárním čase
    • čas $\Theta(n\log n)$
      • v každém z $\log n$ pater (lineárně) sléváme kousky posloupnosti
      • v každém patře se kousky sečtou na $n$
  • násobení $n$-ciferných čísel v čase $O(n^{\log_23})$
    • Karacubovo násobení
    • násobíme dvě $n$-ciferná čísla $x,y$ v soustavě o základu $z$
    • cifry obou čísel rozdělíme na dvě poloviny
      • $x=a\cdot z^{n/2}+b$
      • $y=c\cdot z^{n/2}+d$
    • pak $x\cdot y=(a\cdot z^{n/2}+b)(c\cdot z^{n/2}+d)=ac\cdot z^{n}+(ad+bc)\cdot z^{n/2}+bd$
    • $(ad+bc)$ lze vyjádřit jako $(a+b)(c+d)-ac-bd$
    • takže stačí 3 násobení
    • $T(n)=3\cdot T(n/2)+cn$
    • časová složitost podproblému na vrstvě a počet podproblémů
      • 1. vrstva $\quad n\quad1$
      • 2. vrstva $\quad\frac n2\quad3$
      • $i$-tá vrstva $\quad \frac {n}{2^i}\quad 3^i$
      • poslední vrstva $\quad 1\quad 3^{\log_2 n}$
    • $T(n)=\sum_{i=0}^{\log_2 n}n\cdot(3/2)^i\in\Theta(n\cdot (3/2)^{\log_2n})$, což lze převést na $\Theta(n^{\log_23})$
    • podle Master theorem $a=3,\,b=2,\,c=1$
• Definice (binárního) vyhledávacího stromu
  • BVS je binární strom, jehož každému vrcholu $v$ přiřadíme unikátní klíč $k(v)$ z univerza. Přitom musí pro každý vrchol $v$ platit:
    • kdykoliv $a\in L(v)$, pak $k(a)\lt k(v)$
    • kdykoliv $b\in R(v)$, pak $k(b)\gt k(v)$
• Operace s nevyvažovanými binárními vyhledávacími stromy
  • Find: „binární vyhledávání“ (porovnávám s vrcholem – podle toho se zanořím do jednoho z podstromů nebo vrátím hodnotu vrcholu, případně $\emptyset$, pokud se nemám kam zanořit)
  • Insert: vložím vrchol tam, kde bych ho našel, kdyby ve stromu byl (pokud tam je, tak nic nedělám)
  • Delete: vrchol najdeme a smažeme; pokud má jednoho syna, tak ho připojíme pod otce smazaného vrcholu; pokud má dva syny, nejdříve nalezneme nejlevější vrchol v pravém podstromu a s tím ho prohodíme (fungovalo by to i symetricky)
• AVL stromy (definice)
  • AVL strom = hloubkově vyvážený strom
  • pro každý jeho vrchol platí $|h(L(v))-h(R(v))|\leq1$
  • tedy hloubka levého a pravého podstromu se liší nejvýše o jedna
  • věta: AVL strom na $n$ vrcholech má hloubku $\Theta(\log n)$
• Primitivní třídicí algoritmy (Bubblesort, Insertsort)
  • BubbleSort = výměna dvou prvků
    • procházíme pole zleva doprava
    • bereme dvojice prvků, které jsou v poli vedle sebe – pokud jsou ve špatném pořadí, tak je prohodíme
    • pokud jsme během jednoho průchodu provedli aspoň jedno prohození, musíme pole projít znova (jinak algoritmus končí)
  • InsertSort = zařazení prvku mezi již setříděné
    • rozdělíme pole na setříděnou a nesetříděnou část (na začátku je nesetříděná část prázdná)
    • postupně bereme prvky z nesetříděné části a zařazujeme je na správné místo v setříděné části (najdeme vhodné místo, setříděné prvky vpravo posuneme napravo, do vzniklého místa vložíme aktuální prvek)
• Quicksort
  • určíme pivota, rozdělíme na prvky menší rovny a větší rovny
  • algoritmus $\mathrm{QuickSort}(X)$
    • pokud $n\leq 1$: vrátíme vstup
    • zvolíme pivota $p$
    • rozdělíme $x_1,\dots,x_n$ podle $p$ na $L,S,P$
    • $L\leftarrow \text{QuickSort}(L)$
    • $P\leftarrow \text{QuickSort}(P)$
    • vrátíme $L,S,P$
  • věta: QuickSort s náhodnou volbou pivota má časovou složitost se střední hodnotou $\Theta(n\log n)$
  • částečné zdůvodnění průměrné složitosti
    • s pravděpodobností $\frac12$ bude náhodně vybraný pivot v prostředních dvou čtvrtinách setříděné posloupnosti („skoromedián“)
    • střední hodnota počtu pokusů, než zvolíme skoromedián, je podle lemmatu o džbánu rovna $2$ (to se schová do konstanty)
    • když jsme zvolili skoromedián, tak se problém zmenšil na $\frac34$
  • složitost v nejhorším případě je $\Theta(n^2)$
• Dolní odhad složitosti porovnávacích třídicích algoritmů
  • uvažujeme strom algoritmu – jeho listy odpovídají možným výsledkům
  • větvení v rozhodovacím stromě budou odpovídat jednotlivým porovnáním
  • listů musí být $n!$
  • hloubka stromu musí být aspoň $\log_2n!\geq \log_2 n^{\frac n2}=\frac n2 \log n$
  • každý každý porovnávací třídicí algoritmus musí mít složitost $\in\Omega(n\log n)$
• Prohledávání grafu do šířky a do hloubky
  • prohledávání do šířky (BFS)
    • zpracování určitého vrcholu = odeberu ho z fronty, podívám se na sousední vrcholy a pokud jsou nenavštívené, tak je označím jako otevřené a přidám je do fronty ke zpracování, zpracovávaný vrchol zavřu
    • algoritmus začíná přidáním prvního vrcholu do fronty (to je ten vrchol, ze kterého graf prohledáváme)
    • algoritmus končí, jakmile je fronta prázdná
    • složitost $\Theta(n+m)$
    • BFS najde cestu s nejmenším počtem hran (z výchozího vrcholu do libovolného vrcholu grafu) – tedy lze použít k hledání nejkratší cesty v grafech s jednotkovými hranami
  • prohledávání do hloubky (DFS)
    • lze implementovat rekurzí nebo jako BFS se zásobníkem místo fronty
    • na začátku jsou všechny vrcholy neviděné
    • DFS(v):
      • stav(v) ← otevřený
      • pro vw $\in E$
        • pokud stav(w) = neviděný
          • DFS(w)
      • stav(v) ← zavřený
    • DFS spouštíme z nějaké vrcholu – navštívíme všechny vrcholy z něj dosažitelné
    • opakované DFS – algoritmus nespouštíme pouze pro jeden určitý vrchol, ale pro všechny (neviděné) vrcholy grafu → projdeme všechny komponenty souvislosti
      • stejného efektu lze docílit přidáním jednoho superzdroje, který bude připojen ke všem vrcholům grafu
    • složitost $\Theta(n+m)$
• Topologické třídění orientovaných grafů
  • topologické uspořádání grafu $G=(V,E)$ je lineární uspořádání $\leq$ na $V$ takové, že $\forall uv\in E: u\leq v$
    • může jich být víc
  • konstrukce topologického uspořádání
    • postupným odtrháváním zdrojů (vezmeme libovolný vrchol, jdeme proti šipkám do zdroje, tento zdroj umístíme do uspořádání a odtrhneme ho z grafu) – to je ale složité na efektivní implementaci
    • opakované DFS opouští (zavírá) vrcholy v pořadí opačném topologickému uspořádání
• Nejkratší cesty v ohodnocených grafech (Dijkstrův a Bellmanův-Fordův algoritmus)
  • Dijkstra
    • hledání nejkratších cest z daného vrcholu do všech vrcholů grafu
    • je to v podstatě BFS s budíky (s prioritní frontou)
    • funguje pro kladné reálné délky hran
    • začínáme od nějakého vrcholu $v_0$ (otevřeme ho a jeho ohodnocení $h(v_0)$ nastavíme na nulu)
      • ostatní vrcholy $v$ mají ohodnocení $h(v)=+\infty$
    • dokud existují nějaké otevřené vrcholy, vybereme z nich ten, jehož $h(v)$ je nejmenší (ten zavřeme) a všechny jeho následníky otevřeme a jejich $h(w)$ snížíme na $h(v)+l(v,w)$
    • ukládáme předchůdce vrcholů, aby se cesta dala rekonstruovat
    • pozorování: každý vrchol zavřeme pouze jednou
    • pokud nejmenší $h(v)$ hledáme pokaždé znova, tak to má složitost $\Theta(n^2)$
    • cena operací
      • ExtractMin … $T_X$
      • Insert … $T_I$
      • Decrease … $T_D$
    • složitost Dijkstra je $O(n\cdot T_I+m\cdot T_D + n\cdot T_X)$
      • vkládáme každý vrchol
      • decrease se provádí nejvýše jednou za každou hranu
      • extractujeme každý vrchol
    • při použití binární haldy jsou všechny tři operace $O(\log n)$, z čehož vyplývá složitost Dijkstra $O((n+m)\log n)$
      • lepší (asymptoticky) je zvolit $d$-regulární haldu, kde $d=m/n$
      • ještě lepší je Fibonacciho halda
  • Bellman-Ford
    • relaxační algoritmus (je to třída algoritmů, liší se tím, jak vybírají otevřené vrcholy – patří tam i Dijkstra, který vybírá ty nejlevnější)
    • vrcholy ukládá do fronty (takže jako Dijkstra, akorát nebere nejlevnější, ale nejstarší)
    • funguje pro grafy bez záporných cyklů
    • obecný relaxační algoritmus
      • vstup: graf $G$, počáteční vrchol $v_0$
      • na začátku jsou všechny vrcholy nenalezené, jejich ohodnocení je nekonečné, jejich předchůdci jsou nedefinováni
      • stav počátečního vrcholu nastavíme na otevřený, jeho ohodnocení na nulu
      • dokud existují otevřené vrcholy
        • vezmu nějaký otevřený vrchol $v$ (v Bellmanově-Fordově algoritmu beru ten nejstarší ve frontě)
        • pro všechny jeho následníky $w$ provedu relaxaci, tzn.:
          • pokud $h(w)\gt h(v)+l(v,w)$
            • $h(w)\leftarrow h(v)+l(v,w)$
            • stav(w) $\leftarrow$ otevřený
            • $P(w)\leftarrow v$
          • stav(v) $\leftarrow$ uzavřený
      • výstup: ohodnocení vrcholů $h$ a pole předchůdců
    • Bellmanův-Fordův algoritmus má fáze
      • $F_0:=$ otevření $v_0$
      • $F_i:=$ zavírání vrcholů otevřených v $F_{i-1}$ a otevírání jejich následníků
    • invariant: na konci fáze $F_i$ odpovídá $h(v)$ délce nejkratšího $v_0v$-sledu o nejvýše $i$ hranách
    • z toho vyplývá složitost $\Theta(n\cdot m)$
• Minimální kostra grafu (Jarníkův a Borůvkův algoritmus)
  • lemma
    • nechť $G$ je graf opatřený unikátními vahami, $R$ nějaký jeho elementární řez a $e$ nejlehčí hrana tohoto řezu
    • pak $e$ leží v každé minimální kostře grafu $G$
  • klasický Jarník
    • hladový algoritmus
    • na začátku máme strom $T$, který obsahuje vrchol $v_0$ (libovolný) a žádné hrany
    • vezmeme nejlehčí hranu vedoucí mezi stromem $T$ a zbytkem grafu – tu přidáme do stromu
      • opakujeme, dokud takové hrany existují
    • složitost $O(n\cdot m)$
  • Jarník podle Dijkstry
    • udržuju si haldu aktivních hran – to jsou hrany v aktuálním řezu
    • do stromu $T$ vždycky přidávám minimum z haldy
    • když zjistím, že mám dvě aktivní hrany, které vedou do jednoho vrcholu mimo $T$, tak tu těžší zahodím
    • s haldou složitost $O(m\log n)$
      • protože $n\log n$ se díky souvislosti grafu vejde do $m\log n$
  • Borůvkův algoritmus
    • paralelní verze Jarníkova algoritmu
    • na začátku $T$ obsahuje izolované vrcholy grafu
    • dokud $T$ není souvislý:
      • rozložíme $T$ na komponenty souvislosti
      • pro každou komponentu najdeme nejlehčí hranu mezi komponentou a zbytkem vrcholů a přidáme ji do $T$
    • složitost
      • rozklad na komponenty v $O(n+m)$, ale taky $O(m)$ díky souvislosti
      • nalezení nejlehčích hran v $O(m)$
      • algoritmus se zastaví po nejvýše $\lfloor\log n\rfloor$ iteracích
      • z toho plyne složitost $O(m\log n)$
• Toky v sítích (Ford-Fulkerson algoritmus)
  • cesta je nenasycená $\equiv$ žádná její hrana není nasycená / všechny mají kladné rezervy
  • algoritmus
    • iterujeme, dokud existuje nenasycená cesta ze zdroje do stoku
    • spočítáme rezervu celé cesty (minimum přes rezervy hran cesty)
    • pro každou hranu upravíme tok – v protisměru odečteme co nejvíc, zbytek přičteme po směru
  • pro celočíselné kapacity vrátí celočíselný tok
  • racionální kapacity převedeme na celočíselné
  • pro iracionální kapacity se může rozbít
  • lemma: pokud se algoritmus zastaví, vydá maximální tok
  • věta: pro každou síť s racionálními kapacitami se Fordův-Fulkersonův algoritmus zastaví a vydá maximální tok a minimální řez
    • vzhledem k operacím, které algoritmus provádí, nemůže z celých čísel vytvořit necelá
  • důsledek: velikost maximálního toku je rovna kapacitě minimálního řezu
  • důsledek: síť s celočíselnými kapacitami má aspoň jeden z maximálních toků celočíselný a Fordův-Fulkersonův algoritmus takový tok najde

3. Programovací jazyky

• Abstrakce, zapouzdření, polymorfismus – související konstrukty programovacích jazyků (třídy, rozhraní, metody, datové položky, dědičnost, viditelnost)
  • v C# i v C++ jsou třídy (class) i struktury (struct)
    • deklarace musí být v C++ zakončena středníkem
    • v C++ to neovlivňuje způsob uložení a předávání, v C# jsou struktury hodnotového typu
  • rozhraní (interface) v C#
    • konvence psát na začátek názvu I
    • dovnitř se píšou metody / method-like věci (třeba props), nesmí tam být fields
    • jeden řádek může být např. public int m(int a, int b);
    • dříve muselo být všechno public, dneska je dobré tam to public explicitně psát (i když defaultně je pořád všechno public)
    • názvy parametrů metod v interfacu slouží k dokumentaci
    • nemůže existovat instance interfacu, pouze proměnná s typem interfacu (ta může být nullable)
    • class Kachna : IPostovniZvire {…}
    • IPostovniZvire zvire1 = new Kachna();
    • třída může implementovat víc interfaců
    • rozhraní může dědit od jiného rozhraní
  • v C++ můžeme rozhraní definovat pomocí dědičnosti (obvykle virtuální)
  • v C++ můžu při dědění definovat viditelnost
  • viditelnost v C# – některá klíčová slova
    • public – přístup není omezen
    • private – přístup je omezen na kód v daném typu
      • C# podporuje vnořené typy – takže kód ve vnořeném typu má taky přístup k private položkám typu, v němž je vnořen
    • protected – přístup je omezen na daný typ a typy, které z něj dědí
  • výchozí viditelnost – private ve třídě, public v interfacu
  • C#: abstract method vs. interface
    • vynucení kontraktu – interface ho vynucuje hned
    • veřejný kontrakt – abstraktní metody můžou být protected
    • slib rozšiřitelnosti – u virtuální metody je to opt-out (pomocí sealed), u interfaců opt-in (musím znova říct, že implementuju interface)
    • data – u interfaců nelze (kvůli vícenásobné dědičnosti)
    • vícenásobná dědičnost – nelze u abstraktních metod
• (Dynamický) polymorfismus, statické a dynamické typování
  • statické typování
    • proměnné mají pevně dané typy známé při kompilaci
    • je jasné, jaké metody podporují
    • dobře se provádí statická analýza kódu, lze hlásit chybná volání metod apod.
  • dynamické typování
    • typy proměnných nejsou pevně definované, určují se za běhu
    • volání chybné metody selže až za běhu
    • tzv. duck typing
    • v C# lze aktivovat klíčovým slovem dynamic
    • za jistou formu dynamického typování lze považovat i používání obecných rozhraní nebo rodičovských typů (např. object)
  • statický polymorfismus se implementuje tak, že přetížíme metodu nebo operátor nebo že zakryjeme rodičovskou metodu
  • dynamický polymorfismus funguje pomocí virtuálních metod
  • při volání interfacové metody je důležité, která třída ji implementuje
    • koncept virtuálních metod s interfacy přímo nesouvisí, ale požadavek interfacu můžeme uspokojit virtuální metodou
    • poznámka: interfacová metoda se dá implementovat explicitně
• Vícenásobná dědičnost a její problémy (vícenásobná a virtuální dědičnost v C++, interfaces v C#)
  • diamantový problém – pokud mají moji rodiče společného rodiče a já volám jeho metodu, kterou oba implementují, jaká metoda se má volat?
• Číselné a výčtové typy
  • enum se v C# definuje třeba takto: enum Season { Spring, Summer, Autumn, Winter }
    • když za Season napíšu : ushort, tak se místo intu použije ushort
    • můžu nadefinovat hodnoty jednotlivých možností
  • v C# jsou tyto číselné typy: byte, sbyte, decimal, double, float, int, uint, nint, nuint, long, ulong, short, ushort
    • nint a nuint mají nativní velikost (64 nebo 32 bitů, podle platformy)
• Ukazatele a reference v C++
  • smart pointery
  • raw pointery
  • reference (const, rvalue)
• Hodnotové a referenční typy v C#
  • základní dělení všech typů
    • pointery – jsou ošklivé, nebudeme se o nich bavit
    • hodnotové typy – alokované na místě (s výjimkami)
      • enums
      • structures
        • simple types (Int32, Int64, Double, Boolean, Char, …)
        • nullables
        • user defined structures (struct)
    • referenční typy – alokované na spravované (managed) haldě
      • classes (e.g. strings)
      • interfaces
      • arrays
      • delegates
  • halda je garbage-collectovaná (GC), funguje chytřeji než v Pythonu, není potřeba reference counter, ale používá se graf dosažitelnosti
  • overhead u každého objektu na haldě (má typicky 16 B)
    • syncblock – kvůli práci s více vlákny (u jednovláknových programů zbytečný), má 8 B, skládá se ze dvou částí:
      • lock
        • owner thread + counter (kvůli rekurzivnímu zamykání)
        • waiting threads list – nějaký férový seznam (nebo fronta, na tom nesejde)
      • condition variable
        • sleeping threads list
    • pointer na typ (zjednodušeně řečeno)
      • třída System.Type, má instance na GC haldě
      • každý datový typ odpovídá jedné instanci třídy
    • na referenčních proměnných jde volat .GetType()
  • co může být v proměnné
    • hodnota (u hodnotových typů)
      • velikost odpovídá velikosti datového typu
      • u struktur lze použít new, které nic nealokuje, ale zavolá konstruktor
    • reference (u referenčních typů)
      • je tam uložená adresa, takže velikost odpovídá velikosti adres
      • adresa vede na GC haldu
      • adresa ukazuje na celý objekt
      • explicitní alokace pomocí new
      • tu adresu nelze zjistit (zčásti proto, že GC objekty na haldě někdy přesouvá, proto se adresa může měnit)
• Pokročilé prvky syntaxe C#
  • vícerozměrná pole
    • zubatá (jagged)
      • pole polí
        • int[][] a = new int[2][];
        • a[0] = new int[3];
        • a[1] = new int[4];
        • int x = a[0][1];
      • jako v Javě
      • nevýhoda: každé pole má svůj vlastní overhead
    • obdélníková (rectangular)
      • mezi hranaté závorky napíšu jednu nebo více čárek
      • int[,] a = new int[2, 3];
      • int x = a[0, 1];
      • jako v C/C++
    • jagged jsou obecně rychlejší (cca 2×)
      • ale pokud už s každou naindexovanou položkou pole budu provádět nějaký výpočet, tak tam nebude velký rozdíl v rychlosti
    • obdélníková jsou paměťově úspornější (v určitých situacích), lépe se zapisují
  • indexer je vlastně speciální property
    • public T this[int i] { get { return arr[i]; } set { arr[i] = value; } } }
  • nullable value types mají vlastnost bool HasValue a taky T Value
  • přetěžování operátorů
    • public static Fraction operator *(Fraction left, Fraction right) => new Fraction(left.numerator * right.numerator, left.denominator * right.denominator);
  • přetížení konverze
    • public static implicit operator byte(Digit d) => d.digit;
    • public static explicit operator Digit(byte b) => new Digit(b);
• Reference, imutabilní typy a boxing v C#
  • boxing
    • každý hodnotový typ je potomkem objectu
    • tedy do proměnné typu object musí jít přiřadit proměnnou hodnotového typu
    • při takovém přiřazení se provádí boxing – je to implicitní alokace na GC haldě, alokuje se tam instance hodnotového typu (bude tam standardní overhead)
      • pozor: v Javě jsou dva různé typy, int (hodnotový) a Integer (referenční) – v C# je to ten samý typ System.Int32
    • co můžu dělat s proměnnou typu object?
      • můžu volat ToString()
    • unboxing – hodnotový typ alokovaný na haldě uložený referencí se uloží jako hodnota
    • není vhodné používat object pro slabé typování – vlastně takhle implementujeme duck typing
    • když potřebujeme hodnotový typ předávat referencí, tak object nedává smysl, vhodnější je použít jednoduchou třídu
  • imutabilní typy
    • do fieldu označeného jako readonly lze zapisovat pouze v konstruktoru (a při inicializaci apod.)
    • případně u vlastností můžeme schovat setter – pak budou taky readonly
    • strukturu můžeme celou označit jako readonly
  • reference
    • hodí se pro snazší manipulaci s hodnotovými proměnnými (abychom je všude nemuseli předávat hodnotou a abychom mohli z funkce vracet víc hodnot než jednu)
      • u referenčních typů obvykle nedává smysl používat tracking referenci
      • výjimečným případem, kdy to smysl dává, je třeba zvětšení pole – vyrobím nové pole, položky překopíruju a do tracking reference přiřadím nové pole
    • používají se tzv. tracking reference
    • klíčové slovo ref – používá se u parametrů funkcí, uvádí se dvakrát, v hlavičce funkce i při volání
    • když používám ref, tak proměnná musí být inicializovaná (aby se z ní dalo číst)
    • proto se u výstupních parametrů funkcí používá klíčové slovo out – na úrovni CIL kódu je to to samé, ale nevyžaduje to, aby proměnné byly inicializované
      • uvnitř funkce s výstupními parametry se s nimi zachází jako s neinicializovanými (dá se z nich číst až po prvním zápisu)
      • před standardním ukončením funkce s výstupními parametry se do každého z nich musí alespoň jednou zapsat
      • pokud funkce skončí výjimkou, tak se do výstupních parametrů zapsat nemusí, ale to není problém, protože catch blok nemůže spoléhat na inicializaci v try bloku
      • pokud proměnnou deklaruju nad try/catch, v try bloku ji inicializuji a v catch bloku vyhodím výjimku dál (pomocí throw;), tak pod try/catch můžu proměnnou považovat za inicializovanou
      • pokud napíšu if (int.Parse(s, out int x)), tak se proměnná deklaruje před ifem
    • klíčové slovo in … proměnná uvnitř funkce funguje jako readonly (podobně celá struktura funguje jako readonly)
      • při volání funkce se dá volat i hodnotově bez klíčového slova
      • in má smysl u výkonnostních optimalizací hodnotových typů (typicky u počítačových her)
    • místo in se dá použít taky ref readonly – je to něco velmi podobného
    • tracking reference se dají používat i jinde (nejen jako parametry funkcí) – je lepší je moc nepoužívat
• Šablony (templates) a statický polymorfismus v C++
  • např. template<typename T> const T& max(const T& a, const T& b) { return a < b ? b : a; }
    • templatovaná funkce
    • v C# třeba pomocí generické metody a omezení na IComparable
• Generické typy v C# (bez omezení typových parametrů)
  • class GenericList<T> { }
  • při vytvoření instance je potřeba uvést typový parametr (při volání generických metod to není potřeba)
• Typy reprezentující funkce v C++, C#
  • v C# se používají delegáti
    • pomocí klíčového slova delegate definujeme nový delegátní typ: public delegate void Callback(string message);
    • za předpokladu, že někde existuje DelegateMethod s jedním parametrem typu string, která vrací void, tak můžeme provést přiřazení Callback handler = DelegateMethod;
      • kdybychom chtěli vynutit vytvoření nové instance delegáta, tak bychom použili syntaxi Callback handler = new Callback(DelegateMethod);
    • pak ji můžeme použít: handler("Hello World");
    • k viditelnosti: můžu mít public metodu, která vrací delegáta, který ukazuje na private statickou metodu
    • delegáti můžou ukazovat i na instanční metody
      • v delegátu jsou dva ukazatele – na funkci a na this
        • u statických metod je tam null
      • stále platí, že delegáti jsou immutable – to konkrétní this je tam navždy
      • u struktur – do this se zkopíruje struktura (zaboxuje se)
    • delegáti můžou být generičtí
    • u delegátů se dává suffix Delegate
    • občas mi jde čistě o parametry – je mi úplně jedno, co ten delegát dělá
      • bylo by zbytečné pro každou takovou metodu deklarovat delegáta
      • proto existuje spousta předdefinovaných delegátů
        • Action<…>(…) → void
        • Func<…, TResult>(…) → TResult
        • Predicate<T>(T obj) → bool
      • pozor na přehlednost – typicky je lepší používat silně typované delegáty
    • var funguje i pro delegáty
  • v C++ je víc způsobů, jak pracovat s funkcemi
    • templates
    • function pointers
    • std::function
• Lambda funkce a funkcionální rozhraní
  • lambda funkce v C# se píšou jako (input-parameters) => expression nebo (input-parameters) => { <sequence-of-statements> }
  • můžou být statické
    • např. static x => x + 1
  • pokud nejsou statické, můžou zachytávat proměnné z kontextu (provádí se zachycení podobné capture by reference v C++)
  • lambda funkce jsou přiřaditelné do proměnných typu delegát
• Správa životního cyklu zdrojů v případě výskytu chyb – RAII v C++, using v C#, obsluha a propagace výjimek
  • RAII … Resource Acquisition is Initialization
    • zdroje, které třída používá, by se měly pořídit v konstruktoru a uvolnit v destruktoru, aby to bylo bezpečné
    • lock & unlock → lock_guard
    • new & delete → smart pointers
    • pokud chceme ohraničit část kódu, kde má být zámek zamčený (nebo soubor otevřený), tak ji uzavřeme do složených závorek
  • v C# pomocí usingu
    • using (var f1 = new FileStream("...")) { ... }
    • je to syntaktická zkratka pro try & finally, přičemž ve finally bloku se volá Dispose na hodnotě výrazu v závorce
  • výjimky
    • vyhazují se pomocí throw new Ex();, kde Ex je nějaký typ výjimky (konstruktor může mít parametr – třeba nějakou zprávu)
    • zachycují/zpracovávají se pomocí try-catch-finally bloku
    • catch bloků může být víc pro různé typy výjimek
    • v catch bloku můžeme tu stejnou výjimku vyhodit znova pomocí throw;
• Alokace (alokace statická, na zásobníku, na haldě)
  • statická alokace se provádí už během kompilace, týká se proměnných, které mají být k dispozici během celého běhu programu
  • alokace na zásobník se děje při volání funkcí – lokální proměnné se takto alokují a po doběhnutí funkce se zase smažou
    • je to rychlejší než alokace na haldě, ale na (volacím) zásobníku je méně místa než na haldě
    • opravdu to funguje jako zásobník (FIFO)
    • velikost alokované paměti je známá během kompilace
  • dynamickou alokaci na haldě použijeme v situacích, kdy nám první dva přístupy nestačí
    • potřebujeme sdílet objekty nějak napříč / potřebujeme polymorfismus a nestačí nám reference (v C++)
    • potřebujeme alokovat hodně paměti
    • alokovanou paměť je nutné ručně dealokovat (smart pointers tohle řeší)
  • v C# jsou všechny instance referenčních typů (a jejich fieldy) na haldě
• Inicializace (konstruktory, volání zděděných konstruktorů)
  • v C# je konstruktor označen viditelností a názvem třídy, volá se s new
  • volání rodičovského konstruktoru zajišťuje klíčové slovo base
    • public B(params1) : base(params2) {
    • není to optional, rodičovský konstruktor se volá pokaždé (defaultně bez parametrů)
  • konstruktor předka se vždy volá před konstruktorem potomka
  • v C++ je syntaxe velmi podobná, akorát místo base píšeme přímo název rodičovské třídy
• Destrukce (destruktory, finalizátory)
  • v C# se finalizátory používají k explicitnímu uvolňování unmanaged zdrojů (ve specifických use-casech)
  • v C++ se destruktory používají častěji, nejtypičtější to je, pokud potřebujeme mít pod kontrolou vytváření kopií objektu apod. (viz rule of five)
  • rodičovské třídy v C++ by měly mít virtuální destruktor (stačí prázdný)
• Explicitní uvolňování objektů, reference counting, garbage collector
  • v C++ se na haldě alokuje pomocí new, pak je nutné objekt smazat pomocí delete (právě jednou)
    • alternativou jsou smart pointers
      • unique_ptr dealokuje, jakmile dochází se smazání pointeru (proměnná vypadne ze scopu)
      • shared_ptr umožňuje ukazovat na jeden objekt z více míst, počítá reference – dealokuje, jakmile je referencí nula
        • může být problém s cyklickými referencemi, proto se někdy používá weak_ptr
    • v C se k podobnému účelu používá malloc a free
  • v C# je halda garbage collectovaná
    • garbage collector se pouští podle toho, zda je potřeba uvolnit paměť
    • fungují tam tři generace (vrstvy) objektů
    • vytváří se graf objektů, aby bylo jasné, které jsou používané a které je možné smazat
    • po smazání se zbylé objekty na haldě přeskupují (tzv. heap compacting)
    • GC má dva módy – workstation a server (v server módu běží GC na více vláknech)
• Reprezentace vláken v programovacích jazycích
  • v C# je ve jmenném prostoru System.Threading třída Thread, která obvykle reprezentuje jedno vlákno
  • ale vyrobení vlákna je drahé, takže může být užitečnější použít ThreadPool
• Specifikace funkce vykonávané vláknem a základní operace nad vlákny
  • v C# můžeme vytvořit instanci třídy Thread
  • instanci předáváme delegáta, ten může být bez parametrů nebo s jedním parametrem typu object
  • vlákno spustíme pomocí volání Start()
  • pokud v nějaký moment chceme počkat, než doběhne, můžeme použít Join()
• Časově závislé chyby (race condition) a mechanismy pro synchronizaci vláken
  • race condition nastává, když je výsledek operace závislý na pořadí, v jakém se provedou události, jejichž pořadí nemáme pod kontrolou
  • nejjednodušší řešení je mutual exclusion – k tomu se používá zámek
    • Monitor.Enter(obj) zamkne zámek na daném objektu (nebo pasivně čeká, dokud se neodemkne)
    • Monitor.Exit(obj) odemkne zámek
    • existuje syntaktická zkratka lock(obj) { … }, na začátku bloku se volá Enter, na konci se volá Exit
    • zámek si v syncblocku ukládá referenci na vlákno, které ho vlastní (jinak je tam null)
    • pokud ho zamkneme ze stejného vlákna několikrát, musíme ho několikrát odemknout (k tomu má počítadlo)
  • syncblock má každá referenční proměnná
    • co budeme zamykat?
    • chceme mít jistotu, že nám to nezamkne nikdo jiný proti naší vůli
    • tedy pokud zamykáme například nějakou naši vlastní implementaci seznamu, dává smysl, aby ta třída měla soukromý field typu object, který bude sloužit jenom jako zámek
    • neměli bychom používat lock (this)
  • součástí syncblocku je taky seznam čekajících vláken určený pro tzv. condition variable
    • vlákna čekají na to, až se s objektem něco stane
      • třeba až se ve frontě objeví nějaké položky
      • tuhle podmínku je vhodné někam poznamenat, třeba do komentáře, je to ta „condition variable“
    • když vlákno vidí, že je fronta prázdná, tak se pomocí Monitor.Wait(obj) zařadí do seznamu
    • jakmile se do fronty zařadí další položka, fronta může čekající vlákna notifikovat pomocí Monitor.Pulse(obj) nebo Monitor.PulseAll(obj)
    • aby se dal použít Wait, Pulse nebo PulseAll, musí být obalený v lock bloku (pro stejný objekt) – jinak to vyhodí výjimku
  • dalším synchronizačním primitivem je semafor, používá se k tomu, aby s objektem najednou mohlo pracovat jen omezené množství vláken
• Implementace dynamického polymorfismu (tabulka virtuálních metod)
  • každý typ s virtuálními metodami má tabulku virtuálních metod (VMT), ta se při dědění kopíruje (a prodlužuje), u overridnutých virtuálních metod se změní odkaz na implementaci
  • takže to, která implementace se reálně zavolá, závisí na třídě, jejíž instanci jsme vytvořili (nehledě na typ)
• Nativní a interpretovaný běh, reprezentace programu, bytecode, interpret jazyka, just-in-time (JIT) a ahead-of-time (AOT) překlad
  • nativní běh – zdrojový kód se přeloží a vznikne program, který lze přímo spustit
  • interpretovaný běh – zdrojový kód je zpracováván interpretem jazyka
  • C++
    • zdrojáky .cpp, jeden po druhém je překládáme, vznikají object fily .obj (nebo .o), tam je přímo strojový kód
      • ty se linkerem zpracují do jednoho .exe souboru
    • strojový kód typicky cílí na konkrétní platformu
    • kdybych chtěl, aby program běžel na jiné platformě, vezmu zdrojový kód a celý ho znova přeložím
    • 64bitové Windows podporují 32bitové programy
    • uživatelé musí vědět, jakou verzi programu si mají vybrat
    • knihovny
      • překladač programu používá hlavičkové soubory knihoven
  • Apple
    • Apple 6502 → Motorola 68000 (32bit) → IBM PowerPC (32bit) → Intel x86 (32bit) → Intel x64 (64bit) → Apple M1/M2 (ARM64, 64bit)
    • vymysleli fat binary (universal executable) – jeden spustitelný soubor, v něm je více verzí programu najednou
    • řeší to problém zpětné kompatibility, ne dopředné
  • C#
    • soubory .cs
    • .csproj, předává se build systému dotnetu, ten pustí C# compiler csc.exe (dnes css.dll)
    • vypadne z toho executable, uvnitř je CIL kód (common intermediate language)
    • ke spuštění programu potřebujeme CLR (common language runtime), obvykle je tam JIT (just-in-time) překladač, ten zajišťuje překlad a spuštění pro konkrétní platformu
      • alternativou bylo vykonávat CIL instrukce pomocí běhové podpory, ale to je hrozně pomalé
    • CLR … virtual machine (VM)
    • CIL kód … managed/řízený kód
    • dotnet executable soubor … assembly
    • Java to má podobně
      • Java intermediate language = Java bytecode
    • všechny programovací jazyky dotnetu se překládají do CIL kódu
    • optimalizace dělá až JIT
      • ale má na to omezený čas, aby se program spustil dostatečně rychle
    • JIT používá překlad po metodách
    • ale dá se použít AOT (ahead of time) překlad – takže pak v .exe souboru je nejen assembly (ten se použije pro nepodporované platformy), ale taky přímo strojový kód, který tak může být efektivnější
      • některé věci tam nefungují
• Proces sestavení programu, oddělený překlad, linkování, staticky a dynamicky linkované knihovny
  • sestavení programu
    • preprocesor
    • kompilátor (překladač)
    • assembler
    • linker
  • knihovna – statická nebo dynamická sada binárek
  • linking – spojení binárek do jedné
  • loader – načte program do paměti
  • knihovna se linkuje do souboru .lib (statická knihovna)
    • lidi už pak používají přímo hlavičkový soubor a statickou zkompilovanou knihovnu
    • pokud je knihovna statická, použije ji linker, pokud je dynamická, použije ji až loader
  • v C# se o tohle všechno stará CLR (tedy .NET runtime), viz výše
    • používají se dynamicky linkované knihovny (DLL)
• Běhové prostředí procesu a vazba na operační systém
  • program vs. proces (proces je spuštěný program, entita operačního systému)
  • operační systém zajišťuje, aby měl proces k dispozici virtuální paměť, aby mohl přistupovat k souborům na disku, k periferiím apod.
  • v C# je běhovým prostředím CLR
• Návrhové vzory
  • decorator
    • chceme nějaký objekt obalit, přidat mu funkce
    • dekorátor obvykle přijímá původní objekt v konstruktoru
    • má stejné rozhraní jako původní objekt
  • adapter
    • převádí rozhraní jedné třídy na rozhraní jiné třídy
    • abychom instanci jiné třídy mohli použít tam, kde bychom normálně potřebovali instanci té původní třídy
  • factory
    • vyrábí instance objektů (typicky podle zadaných parametrů může vyrábět instance různých objektů)
    • nebo může mít factory těch vyráběcích metod více (objekty, které padají z různých metod, spolu typicky nějak souvisí)
    • pokud jsou vyráběcí metody virtuální a můžeme definovat různé factory třídy, které vyrábějí různé typy objektů, tak se tomu říká abstract factory
  • visitor
    • uvažujeme potomky A, B, C třídy Base
    • chceme pro každého potomka umět definovat speciální operaci, která se na něm má provést (a pak to chceme umět případně i nějak rozšiřovat)
    • mohli bychom použít switch (obj) { case Type t: something(t); }, ale to není objektové ;)
    • místo toho nadefinujeme rozhraní (nebo abstraktní typ) pro visitora, bude obsahovat metody VisitA, VisitB a VisitC (metody se nemusí lišit názvy, stačí, když se liší typem parametrů – jako parametr přijímají ten objekt typu A, B nebo C)
    • třída Base pak bude mít abstraktní metodu Accept(Visitor v), kterou musí implementovat každý potomek
    • implementace v potomkovi A vypadá tak, že se volá v.VisitA(this);
    • použití
      • máme konkrétního visitora vis1 a chceme ho použít na objekt obj (který je typu A, B nebo C)
      • zavoláme obj.Accept(vis1);

4. Architektura počítačů a operačních systémů

• Základní architektura počítače, reprezentace čísel, dat a programů
  • Harvardská architektura počítače
    • CPU – procesor, vykonává příkazy
    • kódová paměť (code memory) – uložení informací o příkazech
    • komunikační linka – umožňuje, aby procesor četl data z paměti
      • v základním počítači CPU nemusí zapisovat do kódové paměti, do ní se zapisuje nějak z venku
    • datová paměť (data memory) – CPU z ní čte a zapisuje do ní data
      • data se ukládají do proměnných
    • k procesoru jsou dále připojena vstupně-výstupní zařízení – I/O, periferie
  • von Neumannova architektura
    • operační paměť, kde je obojí – v jedné části kód programu, v jiné části data programu
    • zajistíme, aby IP (instruction pointer, jinak také PC, program counter) obsahoval adresy z určitého rozsahu a aby adresy proměnných byly zase z jiného rozsahu
    • je to hardwarově komplikovanější na implementaci, ale přináší to spoustu výhod
    • lze zařídit, aby IP ukazoval na začátek přeloženého programu
    • potenciální zranitelnost, pokud útočník do dat určených ke čtení uloží spustitelné byty a zařídí jejich spuštění
    • operační paměť bude volatile – RAM
      • potřebujeme jiné magické zařízení, které do RAM zkopíruje počáteční program z non-volatile paměti
• Reprezentace a přístup k datům v paměti, adresa, adresový prostor
  • data i programy reprezentujeme binárně
  • každému bytu v paměti přiřadíme adresu (n-bit unsigned), definujeme si paměťový adresový prostor
  • u 256bytové paměti budeme mít 8bitový adresový prostor (0 až 255 $\dots 2^8-1$)
  • 32bitový adresový prostor stačí pro 4 GB paměti, pro větší paměť už potřebujeme 64 bitů
• Ukládání jednoduchých a složených datových typů
  • jednoduché datové typy
    • čísla se ukládají ve dvojkové soustavě
    • znaménková čísla se ukládají ve dvojkovém doplňku
      • kladná čísla jako unsigned
      • záporná čísla jsou negace absolutní hodnoty plus 1
      • rozsah –128 až 127
      • nefunguje porovnání mezi kladnými a zápornými čísly – procesor musí podporovat znaménkové porovnání
      • MSb určuje znaménko
      • nejběžněji používaná implementace záporných čísel
    • čísla s plovoucí desetinnou čárkou (floating-point) se reprezentují takto: $\text{value}=(-1)^{\text{sign}}\cdot\text{significand}\cdot 2^{\text{exponent}-\text{bias}}$
    • číslo se naseká na byty a pak se ukládá v paměti, pořadí uložení bytů je dáno endianitou (little-endian vs. big-endian)
    • text se ukládá pomocí kódování, základní znaky používají ASCII, dále se obvykle používá Unicode
  • složené datové typy
    • moderní procesory vyžadují, aby byla data v paměti zarovnaná podle jejich velikosti
    • např. 4bajtový int musí mít adresu zarovnanou na 4 (dělitelnou čtyřmi)
    • celá struktura (struct) je zarovnaná na největší datový typ dostupný na CPU (např. 16B)
    • některé jazyky přehazují položky ve struktuře, aby se eliminovalo volné místo
    • sizeof vrátí velikost včetně těch mezer
• Implementovat běžné programové konstrukce vyšších jazyků (přiřazení, podmínka, cyklus, volání funkce) pomocí instrukcí procesoru
  • nacvičit
• Zapsat běžnou konstrukci vyššího jazyka (přiřazení, podmínka, cyklus, volání funkce), která odpovídá zadané sekvenci (vysvětlených) instrukcí procesoru
  • nacvičit
• Podpora pro běh operačního systému – privilegovaný a neprivilegovaný režim procesoru, jádro operačního systému
  • režimy procesoru (bývá jich několik, ale nejdůležitější jsou dva)
  • uživatelský režim (neprivilegovaný)
    • přístupný všem aplikacím
    • omezený přístup ke zdrojům (systémovým registrům, instrukcím)
  • kernel mode (privilegovaný)
    • je používán operačním systémem nebo jeho částí
    • má plný přístup ke zdrojům
  • přechod mezi režimy je jasně definovaný – je pouze omezené množství způsobů, jak přepnout z uživatelského do kernel režimu (aby bylo možné vyhodnotit, zda je to záměr, nebo chyba)
    • syscall = volání systémového API
    • tenká vrstva nad OS zajišťuje syscally
  • např. k vypsání textu do konzole je potřeba, abychom se přepnuli do kernel módu a zpátky (zrychluje se to použitím bufferu)
  • jádro OS zajišťuje inicializaci hardwaru, následně řeší správu prostředků a spouštění/obsluhu programů
  • podle velikosti jádra OS se rozlišují architektury
    • monolitická
      • obslužná vrstva, jejím prostřednictvím se volají interní funkce
      • takhle funguje linuxový kernel
      • zranitelnost – programy v jádře mohou dělat cokoliv
      • původně byly součásti jádra pevně nastavené od instalaci
        • problém – při připojení klávesnice chceme nainstalovat driver zařízení → dnes lze obsah jádra měnit
    • vrstvená
      • každá vrstva má svoje rozhraní
      • každá vrstva může používat jenom vrstvu přímo pod ní (její rozhraní)
    • mikrokernel
      • většina služeb se z kernel space vystrčí do user space, jsou tam jako jednotlivé moduly, ty komunikují bez sebou a s jádrem
      • je to rozšiřitelné, spolehlivé (jednotlivé služby lze v případě chyby restartovat) a bezpečné, ale poměrně pomalé
      • takhle fungují Windows
        • mají ještě hardwarovou abstrakční vrstvu, takže mikrokernel je přenositelný
        • služby běží v kernel režimu (což je v rozporu s filozofií mikrokernel)
• Popsat roli řadiče zařízení při programem řízené obsluze zařízení (PIO), pro zadané adresy a funkce vstupních a výstupních portů implementovat programem řízenou obsluhu zadaného zařízení (myš, disk)
  • implementaci nacvičit
  • řadič zařízení (controller) – HW součástka, komunikuje se zařízením nějakým protokolem
  • ovladač zařízení (driver) – SW komponenta, součást operačního systému, realizuje komunikaci s řadičem, poskytuje operačnímu systému jednotné komunikační rozhraní
  • operační systém pak zařízení zprostředkovává běžícímu programu/procesu (a uživateli)
• Popsat roli přerušení při programem řízené obsluze zařízení (PIO), na úrovni vykonávání instrukcí popsat reakci procesoru (hardware) a operačního systému (software) na žádost o přerušení
  • komunikace se zařízeními
    • polling – CPU se aktivně ptá na změnu stavu zařízení (pomalé, dnes už se nepoužívá)
    • přerušení – řadič vyšle signál, že je operace hotová, a přeruší chod procesoru (ale pořád musím kopírovat data, což je pomalé)
    • DMA (Direct Memory Access) – přenos dat ze zařízení do paměti probíhá hardwarově bez účasti procesoru, až pak se provede přerušení; funkce scatter/gather umožňuje využívat nesouvislé části paměti
  • typy přerušení
    • externí – hardwarové pomocí IRQ pinu, lze ho zamaskovat (deaktivovat – pomocí registru)
    • (hardwarová) výjimka – nastal problém s instrukcemi → procesor vyvolá přerušení a nechá na OS, aby situaci vyřešil
      • výjimka typu trap se volá po instrukci, např. dělení nulou
      • u výjimek typu fault se procesor vrátí na stav před instrukcí, nechám OS, aby problém opravil, a potom instrukci pustím znova
    • softwarové – speciální instrukce
  • jak funguje přerušení
    • CPU zjistí zdroj přerušení, získá adresu handleru (kdo přerušení zpracuje – je fixní nebo se použije tabulka)
    • proud instrukcí je přerušen, CPU začne vykonávat instrukce handleru (obvykle se přepne do privilegovaného režimu, protože handler je součástí kernelu)
    • handler uloží stav CPU
    • handler udělá něco užitečného
    • handler obnoví stav CPU
    • CPU pokračuje v původním proudu instrukcí
• Neprivilegované (uživatelské) procesy
  • k prostředkům přistupují skrze operační systém (ten pak využívá ovladače apod.)
  • mají k dispozici virtuální paměť
• Procesy, vlákna, kontext procesu a vlákna
  • program
    • pasivní soubor na disku
    • loader – vezme program a načte ho do paměti
    • někde v hlavičce programu je informace o tom, kde program (výkon instrukcí) začíná
  • proces
    • instance programu vytvořená operačním systémem
    • je to datová struktura uvnitř operačního systému, v níž jsou uložené různá data, která daný program potřebuje
    • vlastní: kód, prostor v paměti, další prostředky
  • vlákno (thread)
    • místo uvnitř procesu, kde se vykonávají instrukce
    • kontext procesoru – datová struktura, ve které jsou uložené registry procesoru, pokud dané vlákno zrovna neběží
    • vlastní: pozici v kódu (program counter / instruction pointer), svůj zásobník, stav procesoru
  • fiber
    • lightweight vlákno
    • nemá celý kontext
    • scheduling se dělá kooperativně (jednotlivé fibery se vzájemně vyměňují v běhu)
• Přepínání kontextu, kooperativní a preemptivní multitasking
  • scheduler – část operačního systému, používá schedulingové algoritmy k přidělení zdrojů (jader) jednotkám
  • když se přeruší vykonávání vlákna, provede se context switch – kontext procesoru (registry včetně PC) se uloží
  • multitasking
    • cooperative – všechny procesy kooperují, předávají si řízení
    • preemptive – každé vlákno dostane od scheduleru svůj time slice; jakmile čas vyprší, dojde k přerušení
  • jinými slovy
    • při kooperativním multitaskingu musí proces dobrovolně předat řízení (yield)
    • při preemptivním multitaskingu plánovač proces prostě přeruší, jakmile mu dojde čas
• Plánování běhu procesů a vláken, stavy vlákna
  • stavy vlákna
    • created
    • ready
    • running
    • blocked
    • terminated (zombie)
  • scheduler – část operačního systému, používá schedulingové algoritmy k přidělení zdrojů (jader) jednotkám
  • real-time scheduling: real-time proces má čas, kdy se má spustit, a čas, do kdy má skončit (hard deadline – nemá smysl pokračovat, soft deadline – má smysl pokračovat ve výpočtu)
  • priorita – vázaná na proces
    • je dvousložková – při spuštění se přiděluje statická priorita (podle uživatele), dynamická priorita se v časových intervalech pravidelně zvyšuje všem ready vláknům (po spuštění se dynamická priorita sníží na nula); celková priorita je daná součtem
  • kooperativní algoritmy
    • first come, first serve (FCFS)
      • FIFO řada, procesy se vykonávají v pořadí, ve kterém přišly
    • shortest job first
      • musí být známý očekávaný čas běhu
    • longest job first
  • preemptivní algoritmy
    • round robin
      • jako FCFS
      • když vlákno trvá moc dlouho, tak se zařadí na konec fronty
    • multilevel feedback-queue
      • každá fronta má jinak dlouhý time slice
      • první (horní) ho má kratší, ty pod ní ho mají delší
      • když vlákno trvá moc dlouho, tak se zařadí na konec nižší fronty
      • když se vlákno brzo zablokuje, tak se zařadí na konec vyšší fronty
    • completely fair scheduler (CFS)
      • používá červeno-černý strom
• Vysvětlit rozdíl mezi virtuální a fyzickou adresou a identifikovat, zda se v zadaném kontextu či fragmentu kódu používá virtuální nebo fyzická adresa
  • instrukce procesoru pracují s virtuálními adresami
  • operační paměť má fyzické adresy
  • hardwarově je implementován převodní mechanismus
    • musí vyhodnotit, jestli existuje převod
    • zajistí přepočet, pokud existuje
    • tyto kroky musí být extrémně rychlé
  • existují dva mechanismy – segmentace (už se nepoužívá) a stránkování
  • MMU = Memory Management Unit, provádí převod
  • převod paměti je transparentní
  • výhody konceptu
    • větší adresový prostor – abych mohl spustit proces s většími požadavky na paměť
    • bezpečnost – aby si procesy navzájem nemohly koukat do paměti, každý má vlastní mapování; to je dnes ten hlavní důvod
• Na zadaném příkladu identifikovat a vysvětlit význam komponent virtuální a fyzické adresy (číslo stránky, číslo rámce, offset)
  • virtuální adresový prostor (VAS) je rozdělen na stejné části (stránky, jejich velikost odpovídá mocninám dvojky)
  • fyzický adresový prostor (PAS) je rozdělen na stejné části (rámce, framy, mají stejnou velikost jako stránky)
  • VAS je jednorozměrný, instrukce pracují s jedním číslem
  • page table (stránkovací tabulka)
    • zajišťuje překlad adres
    • je to pole stránek (indexované číslem stránky)
    • každý záznam obsahuje číslo framu a atributy
    • je tam jednička/nula – aby se dalo určit, jestli stránka fyzicky existuje
    • v případě chyby – page fault
  • virtuální adresa se navenek jeví jako jedno číslo, ale protože velikost stránky je mocnina dvojky, tak část binárního čísla odpovídá číslu stránky a část offsetu
    • offset je u virtuální i fyzické adresy stejný, tedy se překládá jenom prefix odpovídající stránce (přeloží se na číslo rámce)
  • když mi dojde fyzická paměť, tak nějakou stránku uložím na disk – je to obvykle méně dat, než by to bylo při výpadku segmentu (segmenty měly různé velikosti, stránky jsou všechny stejně velké)
• Pro konkrétní adresy a obsah jednoúrovňové stránkovací tabulky řešit úlohy překladu adres
  • ukázkový příklad:
    • 32bitová virtuální adresa
    • posledních 12 bitů určuje offset
    • prvních 20 bitů určuje stránku, použiju je k indexaci do stránkovací tabulky
    • dozvím se číslo rámce dat
    • k číslu rámce připojím offset
    • dostanu 32bitovou fyzickou adresu
• Vysvětlit roli virtuálních adresových prostorů v ochraně paměti procesů a vláken
  • proces má vlastní virtuální adresový prostor, takže se nemůže stát, že by sahal na paměť ostatních procesů
  • ale vlákna stejného procesu virtuální adresový prostor sdílejí
  • někdy naopak chceme, aby různé procesy mohly sdílet nějaké místo v paměti – dá se zařídit, aby konkrétní virtuální adresy různých procesů ukazovaly na stejné místo do fyzické paměti
• Sdílení úložného prostoru – soubory, analogie s adresovým prostorem; abstrakce a rozhraní pro práci se soubory
  • soubor
    • jednotka organizace dat, kolekce souvisejících informací
    • jádro OS nerozumí formátům souborů
    • soubory se typicky neukládají v paměti, ale na perzistentním úložišti
    • soubor je chápán jako unikátní číslo – kvůli lidem mají soubory jméno a cestu (aby v souborech nebyl chaos)
      • analogie s adresovým prostorem – cestu souboru je nutné přeložit (jako se virtuální adresa překládá na fyzickou)
    • některé části názvu souboru (počáteční tečka, přípona) mají speciální význam (ale přípona souboru nemusí souviset s reálným formátem souboru)
    • operace se soubory – vyčištění cache, změna atributů, vytvoření, smazání
    • file handle – číslo specifické pro proces, odkazuje na konkrétní soubor (stdin, stdout, stderr mají handles 0, 1, 2)
  • buffering
    • cachování sektorů disku (když disk čtu po bajtech, první se načítá z cache, všechny ostatní v daném sektoru už se pak načítají z cache)
    • existuje několik úrovní cache (systémová, runtime)
    • sekvenční vs. náhodný přístup
  • alternativy – memory mapping, asynchronní přístup souborům
  • adresář
    • kolekce souborů
    • význam – rychlejší hledání souboru, lepší navigace pro uživatele, logické seskupení souborů
    • obvykle reprezentován jako soubor
    • někdy v něm můžou být uloženy některé atributy jeho souborů
    • obvykle existuje kořenový adresář
    • operace – vytvořit, smazat, přejmenovat, najít název, vypsat soubory
  • ukládání souborů
    • tradiční úložiště
      • na sekundárním nebo externím úložišti
      • file system in RAM (pro dočasné soubory)
    • síťové úložiště – soubory se tváří, jako by byly na disku, ale přitom jsou uloženy někde jinde na síti
    • virtuální soubory – např. /dev/null
  • file links
    • links (hard links)
      • více adresářových záznamů odkazuje na stejný fyzický soubor
      • většina operací je transparentních
      • šetří místo, ale může dělat problémy (smazání hardlinku nesmí smazat fyzický soubor – takže OS musí počítat odkazy na daný soubor)
    • symlinks (soft links)
      • symlinky jsou speciální soubory, v nichž je uložená cesta jiného souboru
  • file system
    • řeší překlad jmen, správu datových bloků, správu dat souborů
    • pro file system je jednotkou jeden blok, blok je určitý počet sektorů
    • řeší abstrakci práce se soubory a adresáři
    • může být lokální (FAT, NTFS) nebo síťový (NFS, CIFS/SMB)
• Časově závislé chyby (race conditions)
  • více vláken přistupuje ke sdílenému prostředku
  • to vede k tomu, že výsledek výpočtu závisí na plánování operačního systému nebo na chování procesoru
  • takový výsledek je k ničemu
  • řešila by to atomizace read-modify-write operace
  • jak to vyřešit?
    • definuju kritickou sekci
    • pomocí synchronizačního primitiva zajistím, že v kritické sekci je jenom jedno vlákno
• Kritická sekce, vzájemné vyloučení
  • kritická sekce – (nejmenší) kus zdrojového kódu, kde dochází k přístupu ke sdílenému prostředku, který nesmí používat víc procesů najedou
  • vzájemné vyloučení (mutex) – jednoduchý algoritmus (synchronizační primitivum) zajišťující, že do kritické sekce nevstoupí víc vláken/procesů najednou
    • je to vlastně zámek (ale zámek se obvykle týká vláken, kdežto mutex se vztahuje na procesy)
    • pokud je mutex zamčený nějakým procesem, jiný proces nemůže sdílený prostředek používat
    • umožňuje vícenásobné zamčení tím stejným procesem (pak je nezbytný stejný počet odemčení)
• Základní synchronizační primitiva, jejich rozhraní a použití – aktivní a pasivní čekání, zámky
  • aktivní a pasivní/blokující synchronizační primitiva
    • aktivní vykonávají instrukce a pořád koukají do kritické sekce, jestli tam můžou
    • pasivní/blokující jsou zablokovány, dokud není přístup povolen
  • hardwarová podpora – atomické instrukce test-and-set (TSL), compare-and-swap (CAS)
  • primitiva
    • spin-lock – aktivní čekání pomocí TSL/CAS, ideální pro krátké čekání
    • semafor – counter a fronta čekajících vláken, atomické operace UP a DOWN
    • mutex – semafor s počítadlem rovným jedné (umožňuje vstup jednoho vlákna do kritické sekce v danou chvíli), atomické operace LOCK a UNLOCK
    • barrier – několik vláken se v jednu chvíli setká u stejné bariéry