Společná informatika

• 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ý 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
  • $\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

• 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 (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ů

• 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

• 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 (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ů

• 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ý

• 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

• 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$)

• 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$

• 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

• 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)

• 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

• $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)$

• 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í)

• 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ý

• 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$

• 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é

• 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ě)

• 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$

• 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$

• 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)$

• 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 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)$

• 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)

• 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)$

• 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í 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é 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í

• 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)$

• 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)$

• 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

• 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

• 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ě

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?

• 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)

• smart pointery
• raw pointery
• reference (const, rvalue)

• 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)

• 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);

• 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

• 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

• 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)

• 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 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

• 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;