# 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 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 { }` - 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 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) => { }` - 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