#set text(font: "New Computer Modern", lang: "cs")
#set heading(numbering: (..numbers) => numbering("1.", ..(numbers.pos().slice(1))))

= Společná matematika

== Základy diferenciálního a integrálního počtu

=== Posloupnosti reálných čísel a jejich limity
==== definice, aritmetika limit
- *definice vlastní limity*: Posloupnost $(x_n)$ má limitu $L in RR$, když
  $ forall epsilon > 0: exists n_0 in NN : forall n : n > n_0 => |x_n - L| <= epsilon $
- *definice nevlastní limity*: Posloupnost $(x_n)$ má limitu $L = oo$, když
  $ forall H > 0: exists n_0 in NN : forall n : n > n_0 => x_n > H $
- *definice nevlastní limity*: Posloupnost $(x_n)$ má limitu $L = -oo$, když
  $ forall H < 0: exists n_0 in NN : forall n : n > n_0 => x_n < H $
- *aritmetika limit*: Nechť $(a_n)$, $(b_n)$ jsou posloupnosti s limitami $lim_(n->oo)a_n = a$ a $lim_(n->oo)b_n = b$
  - $lim_(n->oo)(a_n+b_n) = a + b$, je-li výraz definován
  - $lim_(n->oo)(a_n b_n) = a b$, je-li výraz definován
  - pokud $forall n > n_0 : b_n != 0$, pak $lim_(n->oo)(a_n/b_n) = a/b$, je-li výraz definován
==== věta o dvou policajtech, limity a uspořádání
- *věta o dvou policajtech*: Pro posloupnosti $(a_n)$, $(b_n)$ a $(c_n)$, pokud platí, že
  $ exists n_0 in NN : forall n > n_0: a_n <= b_n <= c_n $
  a
  $ lim_(n->oo) a_n = lim_(n->oo) c_n = L $
  pak
  $ lim_(n->oo) b_n = L $
- *věta o limitě a uspořádání*: Nechť $(a_n)$, $(b_n)$ jsou posloupnosti s limitami $lim_(n->oo)a_n = a$ a $lim_(n->oo)b_n = b$,
  #[#set enum(numbering: "(i)")
  + $ a < b => exists n_0 : n > n_0 => a_n < b_n $
  + $ exists n_0 : n > n_0 => a_n <= b_n => a <= b $
  ]
=== Řady
==== definice částečného součtu a součtu
- *nekonečná řada* je výraz:
  $ sum_(n=1)^oo a_n = a_1 + a_2 + a_3 + ... $
- *částečný součet řady*: Pro řadu $sum_(n=1)^oo a_n$ je $n$-tý částečný součet
  $ s_n = sum_(i=1)^n a_i $
- *definice součtu řady*: Řada $sum_(n=1)^oo x_i$ má součet $s$ a je *konvergentní*, když
  $ lim_(n->oo) sum_i^n a_i = s $
  nebo také
  $ lim_(n->oo) s_n = s $
  kde $s_n$ je částečný součet řady.
==== geometrická řada, harmonická řada
- *geometrická řada* je řada:
  $ sum_(n=0)^oo q^n $
  - součet je $1/(1-q) "pro" |q| < 1$
- *harmonická řada* je řada:
  $ sum_(n=0)^oo 1/n $
=== Reálné funkce jedné reálné proměnné
==== limita funkce v bodě
- definice, aritmetika limit
  - *okolí bodu*: Okolí bodu $U(a, delta) = (a - delta, a + delta)$
    - okolí nekonečen definujeme jako $U(+oo, delta) = (1/delta, oo)$, $U(-oo, delta) = (-oo, -1/delta)$
  - *definice limity*: Funkce $f$ má v bodě $h in RR^*$ limitu $L in RR^*$, když
    $ forall epsilon > 0: exists delta > 0 : forall x != h : d(x, h) <= delta => d(f(x), L) <= epsilon $
    u vlastních limit a analogicky s řadami u nevlastních nebo
    $ forall epsilon > 0: exists delta > 0 : forall x : x in P(h, delta) => f(x) in U(L, epsilon) $
    pro obojí díky definicím okolí pro nekonečna
  - *vztah s uspořádáním*: pro funkce $f$ a $g$ s limitami $lim_(x->oo)$
    #[#set enum(numbering: "(i)")
    + $ lim_(x->c)f(x) > lim_(x->c)g(x) => exists delta > 0 : f(x) > g(x) forall x in P(c, delta) $
    + $ exists delta > 0 : f(x) >= g(x) forall x in P(c, delta) => lim_(x->c)f(x)>=lim_(x->c)g(x) $
    + $ exists delta > 0 : f(x) <= h(x) <= g(x) forall x in P(c, delta) and lim_(x->c)f(x) = lim_(x->c)g(x) = A in RR^* => lim_(x->c)h(x) = A$ (ekv. věty o dvou policajtech)
    ]
  - *limita složené funkce*: Nechť $A, B, C in RR^*$, $lim_(x->A) g(x) = B$ a $lim_(x->B)f(x) = C$, navíc, nechť je splněna jedna z podmínek:
    #[#set math.equation(numbering: "(i)")
    - $f(B) = lim_(x->B) f(x) = C$ ($f$ je spojitá v $B$)
    nebo
    - $exists eta > 0 : B in.not g(P(A, eta))$
    ]
    pak
    $ lim_(x->A) f(g(x)) = C $
==== funkce spojité na intervalu
- *spojitost na intervalu*: Funkce je spojitá na intervalu, je-li spojitá v každém vnitřním bodu a jednostraně spojitá v mezích
- *nabývání mezihodnot*: Funkce spojitá na intervalu nabývá všech hodnot mezi mezemi intervalu
- *nabývání maxima*: Funkce spojitá na intervalu má na tomto intervalu maximální hodnotu
=== Derivace a její aplikace
==== definice a základní pravidla pro výpočet
- *definice derivace*:
  $ f'(x) = lim_(h->0) (f(x+h) - f(x))/h $
- *derivace mocniny*:
  $ (x^n)' = n x^(n-1) $
- *derivace součtu*:
  $ (f+g)'(x) = f'(x) + g'(x) $
- *derivace součinu*:
  $ (f g)'(x) = g(x) f'(x) + f(x) g'(x) $
  - (#text(blue)[Right dLeft, Left] #text(fill: rgb("#7d542c"))[dRight])
- *derivace podílu*:
  $ (f/g)'(x) = (g(x) f'(x) - f(x) g'(x))/(g^2(x)) $
  - (#text(blue)[Right dLeft, Left] #text(fill: rgb("#7d542c"))[dRight])
- *derivace gon. funkcní*: $sin'(x) = cos(x)$, $cos'(x) = -sin(x)$
- *derivace složené funkce*:
  $ (f(g(x)))' = f'(g(x)) g'(x)$
==== l’Hospitalovo pravidlo
- pro funkce $f$ a $g$ s vlastní derivací v $P(h, delta)$, pro které platí buď
  $ lim_(x->h) f(x) = lim_(x->h) g(x) = 0 $
  nebo
  $ lim_(x->h) g(x) = plus.minus oo $
  platí
  $ lim_(x->h) (f(x))/(g(x)) = lim_(x->h)(f'(h))/(g'(h)) $

==== vyšetření průběhu funkcí: extrémy, monotonie a konvexita/konkavita

- *extrémy*: $f'(x) = 0$
- *monotonie*: $f'(x) > 0$ #sym.arrow.double rostoucí, $f'(x) < 0$ #sym.arrow.double klesající
- *konvexita/konkavita*: $f''(x) > 0$ #sym.arrow.double konvexní, $f''(x) < 0$ #sym.arrow.double konkávní

==== Taylorův polynom (limitní forma)

- $ T^(f,a)_n (x) = f(a) + f'(a)(x - a) + (f''(a))/2!(x - a)^2 + ... + (f^((n))(a))/n!(x - a)^n $
- platí, že $T^((n)) = f^((n))$, $(T^(f,a)_n)' = T^(f',a)_(n-1)$

=== Integrály a jejich aplikace
==== primitivní funkce: definice a metody výpočtu
- *definice primitivní funkce*: Pokud pro funkci $f$ definovanou na reálném intervalu $(a,b) -> RR$
  existuje funkce $F: (a,b) -> RR$, jejíž derivace na intervalu $(a,b)$ je rovna $f$, $F'(x) = f(x), forall x in (a,b)$
  je funkce $F$ primitivní funkcí k funkci $f$
- *substituce*:
  $ integral f(g(x))g'(x) dif x = lr(|#block[$ y &= g(x) \ dif y &= g'(x) dif x $]|) = integral f(y) dif y \
    = F(y) + c = lr(|#block[$ y &= g(x) $]|, size: #200%) = F(g(x)) + c $
  $ integral_a^b f(g(x))g'(x) dif x = lr(|#block[$ y &= g(x) \ dif y &= g'(x) dif x \ x = a &-> y = g(a) \ x = b &-> y = g(b) $]|) = integral_(g(a))^(g(b))f(y) dif y $
- *per partes*:
  $ integral u v' = u v - integral u'v $
==== Riemannův integrál: definice, souvislost s primitivní funkcí (Newtonovým integrálem)
- *dělení intervalu*: $D = (d_1 ... d_n)$ je dělení intervalu $I = [a,b]$, pokud platí, že
  $ a = d_0 < d_2 < ... < d_n = b $
- *dolní a horní Riemannova suma*: pro funkci $f$ na intervalu $[a,b]$ a dělení $D$ tohoto intervalu na intervaly $I_1 ... I_n$:
  $ s(f, D) = sum_(i=1)^n |I_i| dot inf{f(x) | x in I_i} $
  $ S(f, D) = sum_(i=1)^n |I_i| dot sup{f(x) | x in I_i} $
- *dolní horní Riemannův integrál*: pro funkci $f$ na intervalu $[a,b]$:
  $ underline(integral_a^b) f = sup{s(f,D) | D "je dělení" [a,b]} $
  $ overline(integral_a^b) f = inf{S(f,D) | D "je dělení" [a,b]} $
- *Riemannův integrál*:
  $ underline(integral_a^b) f = overline(integral_a^b) f = integral_a^b $
- *1. základní věta analýzy*: Pro Riemannovsky integrovatelnou $f$ je a $F$:
  $ F(x) = integral_a^x f(t) dif t $
  a platí
  + $F$ je spojitá na $[a,b]$
  + v každém boďe $x in [a,b]$ existuje $F'(x) = f(x)$
  tedy: Primitivní funkce lze spočítat Riemannovským integrálem
- *2. základní věta analýzy*: Pokud je $f$ Newtonovsky i Riemannovsky integrovatelná, jsou si R. a N. integrály rovny.
==== aplikace
- odhady součtu řad (konečných i nekonečných)
  - pro neklesající $f$ na intervalu $[1,n]$
    $ sum_(k=1)^(n-1) f(k) <= integral_1^n f <= sum_(k=2)^n f(k) $
    analogicky pro nerostoucí
  - pro nerostoucí $f: [1, oo) -> [0, oo)$ řada $sum_(k=1)^oo f(k)$ konverguje, kdyžž:
    $ lim_(b->oo) integral_1^b f < oo $
- obsahy rovinných útvarů -- použij integrál
- délka křivky
  $ integral_a^b sqrt(1 + (f'(t))^2) dif t $
- objemy a povrchy rotačních útvarů v prostoru
  $ V = pi integral_a^b f(t)^2 dif t $
  $ S = 2 pi integral_a^b f(t) sqrt(1 + (f'(t))^2) dif t $

== Algebra a lineární algebra
#let mA = math.bold("A")
#let mB = math.bold("B")
#let mI = math.bold("I")
#let m0 = math.bold("0")
#let mR = math.bold("R")
#let mD = math.bold("D")
#let vu = math.bold("u")
#let vv = math.bold("v")
#let vw = math.bold("w")
#let va = math.bold("a")
#let vb = math.bold("b")
#let v0 = math.bold("0")
=== Algebraické struktury
==== grupy a podgrupy, permutace
- *grupa*: dvojice $(G, +)$:
  + $G$ je uzavřená na $+$
  + $G$ obsahuje neutrální prvek $0: forall x: x + 0 = x$
  + pro každý prvek $x$ existuje inverzní prvek $-x$ a platí $x + (-x) = 0$
  + asociativita $+$
  + (komutativita $+$ ⇒ _Abelovská_)
- *podgrupa*: grupa $(P, +)$ je podgrupa $(G, +)$, pokud $P subset G$
- *permutace*: bijektivní zobrazení $[n] -> [n]$?
==== tělesa a speciálně konečná tělesa
- *těleso*: trojice $(T, +, dot)$
  + $T$ uzavřené na $+$ a $dot$
  + $(T, +, 0, -x)$ je Abelovská grupa
  + $(T without 0, dot, 1, x^-1)$ je Abelovská grupa
  + $dot$ distributivní vůči $+$: $forall a,b,c: a dot (b + c) = a b + a c$
- *konečné těleso*: těleso na konečné množině prvků: $ZZ_p$, kde $p$ je prvočíslo, $"GF"(n)$, kde $n$ je mocnina prvočísla
=== Soustavy lineárních rovnic
==== maticový zápis, elementární řádkové úpravy, odstupňovaný tvar matice
- soustavu:
  $ a_11x_1 + a_12x_2 + ... + a_1n x_n &= b_1\
    a_21x_1 + a_22x_2 + ... + a_2n x_n &= b_2\
    dots.v \
    a_(m 1)x_1 + a_(m 2)x_2 + ... + a_(m n) x_n &= b_m $
  zapíšeme jako
  $ mat(
      a_11, a_12, ..., a_1n, b_1;
      a_21, a_22, ..., a_2n, b_2;
      dots.v, dots.v, dots.down, dots.v, dots.v;
      a_(m 1), a_(m 2), ..., a_(m n), b_m;
    augment: #(-1)) $
- *elementární řádkové úpravy*:
  + vynásobení řádku nenulovým skalárem
  + permutace řádků
  + přičtení jednoho řádku k druhému
- *odstupňovaný tvar matice*:
  - v každém řádku $n$ je pivot index $p_n$ poslední nenulové číslice
  - pro $forall n,m$ čísla řádků platí $n < m => p_n < p_m$
==== Gaussova a Gaussova-Jordanova eliminace, popis množiny řešení
- *Gaussova eliminace*: převedení elementárními úpravami do REF
  - postupně přidáváme nuly od leva a zhora dolů
- *Gaussova-Jordanova eliminace*: převádíme do RREF
  - pivoty odečteme od všech řádků nad nimi
- *rovnice má*:
  - 0 řešení, pokud $"rank"(mA) < "rank"(mA|bold(b))$ ($b$ obsahuje pivota)
  - 1 řešení, pokud $"rank"(mA) = n$ (každý sloupec v $mA$ má pivota)
  - jinak nekonečně mnoho řešení
=== Matice
==== operace s maticemi a základní typy matic, hodnost matice
- typy matic
  - čtvercová, obdélníková
  - nulová $m0 = mat(0,...,0;dots.v, dots.down, dots.v; 0, ..., 0)$
  - jednotková $mI = mat(1, 0, ..., 0; 0, 1, ..., 0; dots.v, dots.v, dots.down, dots.v; 0, 0, ..., 1)$
  - symetrická $mA = mA^sans(T)$
- operace
  - sčítání ($+: RR^(m times n) times RR^(m times n) -> RR^(m times n)$): $(A+B)_(i j) = A_(i j) + B_(i j)$
  - násobení ($dot: RR^(m times n) times RR^(n times p) -> RR^(m times p)$): $(A B)_(i j) = sum_(k=1)^n A_(i k) dot B_(k j)  $
  - násobení skalárem?
  - transpozice $A^sans(T)$
- hodnost matice $"rank"(mA) =$ počet sloupců s pivoty v REF
==== regulární a inverzní matice
- regulární matice
  + má inverzi
  + $mA in T^(n times n): "rank"(mA) = n$
  + $mA ~~ mI$
  + $bold(A x) = v0$ má pouze triv. řešení $bold(x) = v0$
- inverzní matice $A^(-1)$
  $ mat(mA | mI) ~~ mat(mI | mA^(-1)) $
=== Vektorové prostory
==== vektorový prostor, lineární kombinace, lineární závislost a nezávislost, lineární obal, systém generátorů
- vektorový prostor $(V, +, dot)$ nad tělesem $(T, +, dot)$
  + $(V, +)$ je Abelovská grupa
  + násobení skalárem je asociativní a distributivní
  + násobení nulou a jedničkou dělá co má
- *podprostor*: neprázdná podmnožina $V$ uzavřená na $+$ a $dot$
- *lineární kombinace*: Pro vektory $vv _1 ... vv _n$ je libovolná $sum_i^n a_i vv _i$, kde $a_1 ... a_n in T$
- *lineární obal*: $"span"({vv _1 ... vv _n})$, průnik všech podprostorů, které obsahují ${vv _1...vv _n}$\
  (${vw: exists (a_1 ... a_n) : vw = sum_i^n a_i vv _i} $)
- *lineární nezávislost*: $sum_i^n a_i bold(b)_i = m0$ má pouze triviální řešení $a_1 = ... = a_n = 0$
==== Steinitzova věta o výměně, báze, dimenze, souřadnice
- *lemma o výměně*: v systému generátorů ${bold(c)_1 ... bold(c)_n}$ lze nahradit vektor $bold(c)_k$ vektorem $vv = sum_i^n a_i bold(c)_i$, pokud $a_k != 0$
- *Steinitzova věta o výměně*: pro množinu vektorů $B$ z vektorového prostoru $V$ a množinu vektorů $C$, která generuje $V$ můžeme sestrojit množinu $D$ takovou, že $|D|=|C|$, $B subset D$, $D$ generuje $V$ a $D without B subset C$
- *báze* vektorového prostoru $V$ je lineárně nezávislá množina vektorů, které generují $V$
- *dimenze* vektorového prostoru $V$ je velikost libovolné báze
- *vektor souřadnic* $[vv]_B$ vektoru $v$ v bázi $B$ obsahuje koeficienty lineární kombinace bázických vektorů $B$, která tvoří $v$
==== vektorové podprostory, zejména maticové (řádkový, sloupcový, jádro) a jejich dimenze
- *jádro* $ker(mA)$ matice $mA$ je množina řešení $bold(A x) = m0$
- *řádkový a sloupcový prostor* jsou prostory generované řádky a sloupci matice
- pro matici $mA in T^(m times n)$, $dim(ker(mA)) + "rank"(mA) = n$
- $dim(R_mA) = dim(S_mA) = "rank"(mA)$
- z toho plyne $"rank"(mA) = "rank"(mA^T)$
=== Lineární zobrazení
==== definice, maticová reprezentace lineárního zobrazení, matice složeného zobrazení
- *definice lineárního zobrazení*: $U$ a $V$ jsou vektorové prostory, $f: U -> V$ je lineární zobrazení, pokud:
  + $f(vu + vv) = f(vu) + f(vv)$
  + $f(t dot vv) = t dot f(vv)$
- *maticová reprezentace lineárního zobrazení*: $mA in T^(m times n)$, $f: T^n -> T^m$, $f(vu) = bold(A u)$
- *matice linárního zobrazení vzhledem k bazím*: $f: U->V$ k bazím $B$ a $C$ je
  $ [f]_(B,C) = mat(|,,|;[f(bold(b)_1)]_C, ..., [f(bold(b)_n)]_C;|,,|) $
  poté
  $ [f(vu)]_C = [f]_(B,C)[vu]_B $
  nebo Hladíkovsky:
  $ [f(vu)]_C = attach([f], bl: C, br: B)[vu]_B $
- *matice složeného zobrazení*: 
  - $mA in T^(m times n), mB in T^(n times p)$
  - $f: T^m -> T^n, g: T^n -> T^p$
  - $f(vu) = bold(A u), g(vu) = bold(B u)$
  - $=> g(f(u)) = bold(B A u)$
==== obraz a jádro lineárních zobrazení
- *obraz lineárního zobrazení*: pro zobrazení $f: U -> V$, ${f(vu) | u in U} subset V$
- *jádro lineárního zobrazení*: pro zobrazení $f: U -> V$, ${vu in U | f(vu) = m0}$
==== isomorfismus prostorů
- zobrazení $f: U->V$ je isomorfismus prostorů $U,V$ s bázemi $B,V$ kdyžž $[f]_(B,C)$ je regulární
=== Skalární součin
#let dotp(a, b) = $angle.l #a | #b angle.r$
==== skalární součin, norma indukovaná skalárním součinem
- *skalární součin*: $V$ nad $CC$, $dotp(a,b): V times V -> CC$
  #[
  #show "u": math.bold("u")
  #show "v": math.bold("v")
  #show "w": math.bold("w")
  + $dotp(v,v) in RR_0^+$
  + $dotp(v,v) = 0 <=> v = m0 $
  + $dotp(u,v) = overline(dotp(v,u))$
  + $dotp(u+v,w) = dotp(u,w)+dotp(v,w)$
  + $dotp(alpha v, u) = alpha dotp(v, u)$
  + $dotp(u,v) = 0 and u != v$ ⇒ vektory jsou _kolmé_
  ]
- *norma indukovaná skalárním součinem*: $||vv|| = sqrt(dotp(vv,vv))$
- $dotp(vu,vv) = ||vu|| dot ||vv|| dot cos phi $
==== Pythagorova věta, Cauchyho-Schwarzova nerovnost, trojúhelníková nerovnost
- vektory $vu, vv$ jsou *kolmé*, pokud $dotp(vu, vv)=0$
- *Cauchy-Schwarzova nerovnost*: $|dotp(vu, vv)| <= ||vu|| dot ||vv||$ (intuice: $cos phi in [-1, 1]$)
- *trojúhélníková nerovnost*: $||vu|| + ||vv|| >= ||vu+vv||$
- *Pythagorova věta*: pro kolmé vektory platí: $||vu + vv||^2 = ||vu||^2 + ||vv||^2$
==== ortonormální systémy vektorů, Fourierovy koeficienty, Gramova-Schmidtova ortogonalizace
- *ortonormální systém vektorů*: všechny vektory jsou vzájemně kolmé a délky $1$
- *Grahamova-Schmidtova ortogonalizace*: pro bázi $B$
  + $O <- {vb _1}$ odstraním $vb _1$ z $B$
  + dokud není $B$ prázdné:
    + vezmu $vb$ z $B$
    + $vb _p <-$ projekce $b$ do $O$
    + $vb _o <- vb - vb _p$
    + $O <- O union {vb _o}$
  (orto#[*norm*]alizace ještě přidávané vektory zkracuje na jednotkovou délku)
- *Fourierovy koeficienty*: pro ortonormální bázi $B = (vb _1 ... vb _n)$ prostoru $V$ a pro každý vektor $vv$ z $V$ platí:
  $ vv = dotp(vv, vb _1)vb _1 + ... + dotp(vv, vb _n)vb _n $
==== ortogonální doplněk, ortogonální projekce, projekce jako lineární zobrazení
- *ortogonální projekce*: pro vektor $vv$ a bázi $B = {vb _1, ..., vb _n}$:
  $ sum_i^n (dotp(vv, vb _i))/(||vb _i||)vb _i $
- *ortogonální doplňek*: podmnožiny $V$ prostoru $U$: $V^perp = {vu in U : forall vv in V: vu perp vv}$
- projekce je lineární zobrazení
==== ortogonální matice a jejich vlastnosti
- spíše "ortonormální"
- tvořená např. sloupci ortonormální báze
- unitární matice na $RR$
- uzavřené na součin
- $mA ^H mA = mI$ ($mA ^T mA = mI$)
- $mA ^(-1) = mA^T$
- zobrazení dané ortogonálními maticemi je isometrie
=== Determinanty
==== definice a základní vlastnosti determinantu (multiplikativnost, determinant transponované matice, vztah s regularitou a vlastními čísly)
- $S_n$ grupa permutací na množině $[n]$
- suma součinů diagonál matice vynásobených znamínkem permutace přes všechny permutace sloupců
  $ det mA = sum_(p in S_n) "sgn" p product_(i=1)^n a_(i, p(i)) $
- $det mA = det mA^T$
- permutace $p$ sloupců mění znaménko determinantu podle $"sgn"(p)$
  - to samé pro řádky
- dva stejné řádky ⇒ $det mA = 0$ (permutace lze popárovat tak, aby pro páry platilo $q = p compose (k,l)$, páry se liší pouze znaménkem a vzájemně se odečtou)
- vynásobení řádku skalárem vynásobí determinant skalárem
  $ mat(-,a,-;-,t dot b,-;-,c,-; delim: "|") = t dot mat(-,a,-;-,b,-;-,c,-; delim: "|") $
- sečteme-li řádek dvou matic lišících se o řádek, sečteme jejich determinanty
  $ mat(-,a,-;-,b_1+b_2,-;-,c,-; delim: "|") = mat(-,a,-;-,b_1,-;-,c,-; delim: "|") + mat(-,a,-;-,b_2,-;-,c,-; delim: "|") $
- přičtením $t$-násobku jednoho řádku k druhému nezměníme determinant
  $ mat(-,a,-;-,b+ t dot c,-;-,c,-; delim: "|") = mat(-,a,-;-,b,-;-,c,-; delim: "|") + overbrace(t dot mat(-,a,-;-,c,-;-,c,-; delim: "|"), = 0) $
  - dá se dělat i se sloupci ($det mA = det mA^T$)
- $det(mA mB) = det mA det mB$
  - rozložení na elementární operace
  - součet řádků nemění determinant a $mat(1,0,0;0,1,1;0,0,1; delim: "|") = 1$
  - násobení řádku skalárem násobí determinant skalárem a $mat(1,0,0;0,3,0;0,0,1; delim: "|") = 3$
- matice je singulární kdyžž $det = 0$
==== Laplaceův rozvoj determinantu
- vybereme řádek $i$:
  $ det mA = sum_(j=1) a_(i j) (-1)^(i+j) det mA^(i j) $
  kde $mA^(i j)$ je matice bez $i$-tého řádku a $j$-tého sloupce
  #[
  #let purp(content) = [#set text(purple);#content]
  $ mat(1, 2, 5; purp(2), purp(3), purp(0); 3, 5, 3; delim: "|") = purp(2) dot (-1)^(2 + 1) mat(2,5;5,3; delim: "|") + purp(3) dot (-1)^(2+2) mat(1,5;3,3; delim: "|") + purp(0) dot (-1)^(2+3) mat(1,2;3,5; delim: "|") $
  ]
==== geometrická interpretace determinantu
- znamínkový obsah rovnoběžnostěnu daného vektory ve sloupci matice
=== Vlastní čísla a vlastní vektory
==== definice, geometrický význam a základní vlastnosti vlastních čísel, charakteristický polynom, násobnost vlastních čísel
- pro $f: V->V$, *vlastní číslo* je $lambda in T: exists vv in V without m0: f(vv) = lambda vv$
- pro $f: V->V$, *vlastní vektor* je $vv in V without m0: f(vv) = lambda vv$
- množina vlastních čísel = *spektrum*
- *geometrická násobnost* $lambda$: dimenze podprostoru vlastních vektorů
- diagonální matice -- čísla na diagonále jsou $lambda$, vektory kanonické báze $(1, 0, 0...)$ jsou vlastní
- vlastní vektory jednoho $lambda$ tvoří podprostor
- vlastní vektory různých $lambda$ jsou lineárně nezávislé
- matice může mít max. $n$ vlastních čísel (max. počet podprostorů)
===== charakteristický polynom
- $p_mA (x) = det (mA - x mI)$
- kořeny $p_mA (x)$ jsou $lambda$
  - $ m0 = mA vv - lambda vv = (mA - lambda mI)v <=> mA - lambda mI "je singulární" <=> 0 = det(mA - lambda mI) = p_mA (lambda)$
  - *algebraická násobnost* $lambda$ = kolikrát lze $p_mA (x)$ beze zbytku vydělit $(x - lambda)$
==== podobnost a diagonalizovatelnost matic, spektrální rozklad
- *podobné matice* -- matice stejného zobrazení, vůči jiné bázi
  - $[f]_(B,B) = [id]_(C,B) dot [f]_(C,C) dot [id]_(B,B)$
  - jinými slovy: $mA = mR^(-1)mB mR$
  - podobné matice mají stejná $lambda$ se stejnými geometrickými a algebraickými násobnostmi
- *algebraická násobnost* $>=$ *geometrické násobnosti*
- *diagonalizovatelná matice* je podobná s diagonální maticí
  - $<=>$ vlastní vektory tvoří bázi $T^n$
- $mA^k = mR^(-1)mD^k mR$
==== symetrické matice, jejich vlastní čísla a spektrální rozklad
- pro symetrickou matici $mA$ existuje *ortogonální* $mR$ taková, že $mR^(-1)mA mR$ je diagonální
- zápis $mA = mR mD mR^T$ je *spektrální rozklad*
=== Positivně semidefinitní a positivně definitní matice
#let pd(content) = [#set text(red);#content]
#let psd(content) = [#set text(blue);#content]
Definice a vlastnosti sloučeny, rozdíly značeny: #pd[positivně definitní] a #psd[positivně semidefinitní]
==== charakterizace a vlastnosti, vztah se skalárním součinem, vlastními čísly
- *definice*: symetrická $mA$ je P(S)D, kdyžž $vv^T mA vv ""^pd(>)_psd(>=) 0$
- P(S)D ⇒  $""^#pd[kladná] _#psd[nezáporná]$ diagonála
- *Gramova matice*: $vv^T mA^T vu^T = dotp(vu, vv)$
  - pro bázi $B = (vb_1, vb_2, ..., vb_n)$, $a_(i j) = dotp(vb_i, vb_j)$
  - #pd([PD]) matice = Gramova matice nějakého $V$
- $forall lambda: lambda ""^pd(>)_psd(>=) 0$
- $exists$ #pd[regulární] matice $bold(U): bold(U)^T bold(U) = mA$
==== Choleského rozklad (znění věty a praktické použití)
- #pd[PD] ⇒ jednoznačná $bold(U) = mat(u_11, u_12, u_13; 0, u_22, u_23; 0, 0, u_33)$ s $u_(i i) > 0$, tž. $bold(U)^T bold(U) = mA$ = *Choleského rozklad*
- $u_11 = sqrt(a_11)$, dále dopočítám $a_12, a_13, ..., a_22, ...$ jednoznačně, aby vycházel součin

== Diskrétní matematika

=== Relace
- binární $R subset X times Y$, obecně $R subset X times Y times ...$
- *reflexivita*: $forall a : a R a$
- *symetrie*: $forall a,b: a R b <=> b R a$
- *antisymetrie*: $forall a,b: a != b => (a R b <=> b cancel(R) a)$
- *transitivita*: $forall a,b,c: a R b and b R c => a R c$
=== Ekvivalence a rozkladové třídy
- *ekvivalence*: symetrická, reflexivní a transitivní relace
- *rozkladové třídy*: $R[x] := {x | x R y}$
  - $R[x] = R[y] <=> R[x] inter R[y] != emptyset$
  - ${R[x]|forall x}$ jednoznačně určuje $R$
=== Částečná uspořádání
- *uspořádání*: antisymetrická, reflexivní a transitivní relace
- $x,y$ jsou *porovnatelné* $<=> x R y or y R x$
- *lineární uspořádání*: $forall x,y: x R y or y R x$ (vs. *částečné*)
- *ostré uspořádání*: (není uspořádání z definice), přidáme ireflexivitu
- základní pojmy (minimální a maximální prvky, nejmenší a největší prvky, řetězec, antiřetězec)
- *minimální*: neexistuje menší ($exists.not y: y < x$)
- *nejmenší*: je menší než všichni ostatní ($forall y: x <= y$)
- *maximální*: neexistuje větší ($exists.not y: y > x$)
- *největší*: je větší než všichni ostatní ($forall y: x >= y$)
- *řetězec*: $Y subset X: forall x,y in Y: x R y or y R x$
- *antiřetězec*: $Y subset X: forall x,y in Y: not(x R y or y R x)$
- výška a šířka částečně uspořádané množiny a věta o jejich vztahu (o dlouhém a širokém)
  - *výška*: $omega$ max. velikost řetězce
  - *šířka*: $alpha$ max. velikost antiřetězce
  - $alpha dot omega >= |X|$, $max(alpha, omega) >= sqrt(|X|)$
  - *Erdős-Szekeres*: V posloupnosti $x_1 ... x_(n^2+1)$ různých čísel $exists$ vybraná monotóní podposloupnost délky $n$
=== Funkce
- relace $f$ je funkce, pokud $f: X -> Y, forall x in X exists! y in Y: x f y: f(x) = y$
- typy funkcí (prostá, na, bijekce)
- *prostá* (injektivní) $f: forall x,y: f(x) = f(y) => x = y$
- *na* (surjektivní) $f: forall y exists x : f(x) = y$
- *biijektivní* prostá a na
- počty různých typů funkcí mezi dvěma konečnými množinami
  - *bijekce*: stejné velikosti množin, počet fcí je počet permutací, $|X|! = |Y|!$
  - *prosté*: pro každou z $X$ vybírám jednu hodnotu z $Y$ bez opakování, závisí na pořadí $|Y|^underline(|X|)$
  - *na*: pro každou z $Y$ vybíram jednu hodnotu z $X$ s opakováním, závisí na pořadí
=== Permutace a jejich základní vlastnosti (počet a pevný bod)
- *permutace*: bijekce $pi: [n] -> [n]$
- počet permutací: $n!$
- *pevný bod*: $i : pi(i) = i$
=== Kombinační čísla a vztahy mezi nimi, binomická věta a její aplikace
- *kombinační číslo*: $ binom(n, k) := n^(underline(k))/k! = (n!)/(k!(n-k)!) = (n dot (n-1) dot ... dot (n - k + 1))/(k dot (k-1) dot ... dot 1) $
- počet $k$-prvkových podmnožin množiny velikosti $n$
- $binom(n,0) = 1, binom(n,n) = 1, binom(n, 1) = n, binom(n, k) = binom(n, n-k)$
- $binom(n, k) = binom(n-1, k) + binom(n-1,k-1)$  $\#(|k| subset A) = \#(|k| subset A without {a}) + \#((|k-1| subset A without {a})) union {a}$)
- *binomická věta*: $ (x+y)^(n) = sum_(k=0)^n binom(n,k)x^(n-k)y^k $
- $2^n = (1+1)^(n) = sum_(k=0)^n binom(n,k) dot 1 dot 1$
- $0 = (1-1)^(n) = sum_(k=0)^n (-1)^(k) binom(n,k)$
=== Princip inkluze a exkluze
- *PIE*: pro množiny $A_1...A_n$
  $ lr(|union.big_(i=1)^n A_i|) = sum_(k=1)^n (-1)^(k+1) sum_(I in binom([n], k)) lr(|inter.big_(i in I) A_i|) $
- *Dk1*: $A = union.big_(i=1)^n A_i$
  - kolikrát levá a pravá $sum$ započítá libovolné $a in A$?
  - levá $L = 1$
  - pravá: $t := \#i : a in A_i$
    $ sum_(I in binom([n], k)) lr(|inter.big_(i in I) A_i inter {a}|) &= cases(
        0 "pokud" k > t,
        binom(t, k) "pokud" k <= t
      ) \
      P &= sum_(k=1)^t (-1)^(k+1) binom(t,k) \
      P &= -sum_(k=1)^t (-1)^(k) binom(t,k) \
      P &= -(sum_(k=0)^t (-1)^(k) binom(t,k) - binom(t, 0)) \
      P &= -(0 - 1) \
      P &= 1
$
- *Dk2*:
  $ c_A(x) &:= cases(0 "pokud" x in.not A, 1 "pokud" x in A) \
    1 - c_A &<-> overline(A) \
    c_A dot c_B &<-> A inter B \
    1 - (1 - c_A) dot (1 - c_B) &<-> overline(overline(A) inter overline(B)) = A union B $

    $ product_(i=0)^(n) (1 - c_i) &= sum_(k=0)^n (-1)^(k) sum_(I in binom([n], k)) product_(i in I) c_i \
      product_(i=0)^(n) (1 - c_i) &= 1 + sum_(k=1)^n (-1)^(k) sum_(I in binom([n], k)) product_(i in I) c_i \
      product_(i=0)^(n) (1 - c_i) &= 1 - sum_(k=1)^n (-1)^(k+1) sum_(I in binom([n], k)) product_(i in I) c_i \
      1 - product_(i=0)^(n) (1 - c_i) &= sum_(k=1)^n (-1)^(k+1) sum_(I in binom([n], k)) product_(i in I) c_i \

$
- použití (problém šatnářky, Eulerova funkce pro počet dělitelů, počet surjekcí)
==== problém šatnářky
- $Š_n := \#{pi: [n] -> [n] | forall i: pi(i) != i}$
- $Š_n = \#{pi: [n] -> [n]} - \#{pi: [n] -> [n]: exists i_1: pi(i_1) = i_1} + \#{pi: [n] -> [n]: exists i_1,i_2: i_1 != i_2: pi(i_1) = i_1, pi(i_2) = i_2} - ...$
- $ Š_n = sum_(k=0)^n (-1)^k binom(n,k) (n-k)! = sum_(k=0)^n (-1)^k n!/k! = n! sum_(k=0)^n (-1)^k/k! approx n!/e $
==== Eulerova funkce pro počet dělitelů
- ani náhodou
==== počet surejkcí
- $\#{f: M -> N} - \#{f: M -> N | exists n_1 : forall m in M: f(m) != n_1} + ...$
- $ sum_(k=0)^#text(red)[$n-1$] (-1)^k binom(n, k) (n-k)^m $
- #text(red)[$n-1$]: ${f: M -> N | forall m in M: f(m) in.not N} = emptyset$
=== Hallova věta o systému různých reprezentantů a její vztah k párování v bipartitním grafu
- *Hallova věta*: pro bipartitní graf $G = (V,E)$ s partitami $A, B$
  $ G "má párování velikosti" |A| <=> forall X subset.eq A : |{y in V without X : exists x in X: {x,y} in E}| >= |X| $
- princip důkazu a algoritmické aspekty (polynomiální algoritmus pro nalezení SRR) #text(red)[TODO]

== Teorie grafů

=== Základní pojmy teorie grafů
- *graf*: $G = (V,E), E subset binom(V, 2)$
- *orientovaný*: $E subset V × V$
- *isomorfismus grafů*: $G_1 = (V_1, E_1)$ a $G_2 = (V_2, E_2)$ jsou isomorfní kdyžž $ exists "bijektivní" f: V_1 -> V_2: forall u,v in V_1: {u,v} in E_1 <=> {f(u), f(v)} in E_2 $
- *podgraf*: $G_p = (V_p, E_p)$ grafu $G = (V,E)$: $V_p subset V, E_p subset E$
- *indukovaný podgraf*: $G_p = (V_p, E_p)$ grafu $G = (V,E)$: $V_p subset V, E_p = E inter binom(V, 2)$
- *okolí vrcholu*: $v$ v grafu $G = (V,E)$ je ${u in V | {u,v} in E}$
- *stupeň vrcholu*: v grafu $G = (V,E)$ $deg(v) = |{u in V | {u,v} in E}|$
- *doplněk grafu*: $overline(G) = (overline(V), overline(E))$ grafu $G = (V,E)$: $overline(V) = V, overline(E) = binom(V,2) without E$
- *bipartitní graf*: $exists L, P: L inter P = emptyset, L union P = V, forall e in E: |e inter L| = |e inter P| = 1$
=== Základní příklady grafů
- *úplný graf*: $K_n = ([n], binom([n], 2))$
- *úplný bipartitní graf*: $K_(m,n) = (L union P, {{l,p} | l in L, p in P}), |L| = m, |P| = n$
- *cesta*: $P_n ([n]_0, {{i, i+1} | 0 <= i < n})$
- *kružnice*: $C_n ([n-1]_0, {{i, i+1 mod n} | 0 <= i < n})$
=== Souvislost grafů, komponenty souvislosti, vzdálenost v grafu
- *relace dosažitelnosti*: $u ~ v$ kdyžž $exists$ cesta mezi $u$ a $v$ v grafu $G$
- *souvislý graf*: $forall u, v in V: u ~ v$
- *komponenta souvislosti*: podgraf indukovaný třídami ekvivalence $~$
- *vzdálenost*: $d(u,v)$ délka nejmenší cesty mezi $u$ a $v$
=== Stromy
- ekvivalentní charakteristiky stromů
  + souvislý acyklický
  + minimální souvislý
  + maximální acyklický
  + (*Eulerova formule*) souvislý a $|E| + 1 = |V|$
  + $forall u,v in V exists!$ cesta mezi $u$ a $v$ -- jednoznačně souvislý
- *list* = vrchol $deg(v) = 1$
- každý strom velikosti $>= 2$ má alespoň 1 list
=== Rovinné grafy
- *rovinné nakreslení*:
  - vrcholy jsou body v $RR^2$
  - hrany jsou oblouky $f: [0,1] -> RR^2$ spojitá a prostá
  - hrany nemají společný bod
  - vrcholy se nachází pouze na těch hranách, které ukončují
- *rovinný graf* má rovinné nakreslení
- *rovinný na sféře* ⟺ *rovinný* (bijekce přes polopřímky ze severního pólu (pokud je na severním pólu bod, lze sféru otočit o $ε$))
- *stěna*: oblast ohraničená hranami
  - specifické pro nakreslení, ne pro graf
=== Eulerova formule a maximální počet hran rovinného grafu (důkaz a použití)
- $v + f = e + 2$
- pro strom platí ($v + 1 = e + 2$)
- přidáním hrany přidáme i stěnu
=== Barevnost grafů
- *obarvení*: $c: V -> [k]$ t. ž. $forall {x,y} in E: c(x) != c(y)$
- *barevnost*: $chi(G) := min{k | exists c: V -> [k], c "je obarvení"}$
- vztah barevnosti a klikovosti grafu
  - *klikovost*: $omega(G) := max{k | K_k subset.eq G}$
  - $chi(K_k) = k$
  - $chi(G) >= omega(G)$
=== Hranová a vrcholová souvislost grafů
- *hranový řez*: množina $F subset E$ taková, že $(V, E without F)$ je nesouvislý
- *vrcholový řez*: množina $C subset V$ taková, že podgraf indukovaný $V without C$ je nesouvislý
- *hranová souvislost*: $k_e(G) = min{|F| ; F subset E, F "je hranový řez"}$
- *vrcholová souvislost*: $k_v(G) = cases(min{|C| ; C subset V, C "je vrcholový řez"} &"pro" G tilde.equiv.not K_n, n - 1 &"pro" G tilde.equiv K_n)$
- hranová a vrcholová verze Mengerovy věty
  - *Mengerova hranová věta*: $k_e(G) ≥ n <=> forall u, v:$ existuje $n$ hranově disjunktních cest mezi $u$ a $v$
  - *Mengerova vrcholová věta*: $k_v(G) ≥ n <=> forall u, v:$ existuje $n$ cest mezi $u$,  $v$ disjunktních až na $u$ a $v$
=== Orientované grafy, silná a slabá souvislost
- *orientovaný*: $E subset V × V$ -- hrany jsou uspořádané dvojice
- *silná souvislost*: mezi vrcholy existuje orientovaná cesta
- *slabá souvislost*: vrcholy jsou souvislé v podkladovém neorientovaném grafu
=== Toky v sítích
- *síť*: orientovaný graf (V,E), $c: E -> RR_0^+$ funkce kapacit, a vrcholy $z$ zdroj a $s$ stok
- *tok*: $f: E -> RR_0^+$
  + $forall e in E: f(e) <= c(e)$
  + $forall v in V without {z,s}: sum_(u: u v in E) f(u v) = sum_(u: u v in E) f(v u) $
  - $f^+(v) := sum_(u: u v in E) f(u v)$ -- přítok
  - $f^-(v) := sum_(u: u v in E) f(v u)$ -- odtok
  - $f^Delta(v) := f^+(v) - f^-(v)$      -- přebytek
  - jinak řečeno 2. $forall v in v without {z,s}: f^Delta(v) = 0$
- existence maximálního toku (bez důkazu)
  - v každé síti existuje právě jeden nebo nekonečně mnoho maximálních toků
    - ze dvou lze vždy vytvořit třetí zprůměrováním hran, které se liší
  - velikost maximálního toku je rovna velikosti minimálního řezu
  - v celočíselné síti je max. tok celočíselný
- princip hledání maximálního toku v síti s celočíselnými kapacitami (například pomocí Ford-Fulkersonova algoritmu)
  - viz ADS

== Pravděpodobnost a statistika
=== Pravděpodobnostní prostor, náhodné jevy, pravděpodobnost
#let samples = math.Omega
#let events = math.cal[F]
#let powerset = math.cal[P]
- *pravděpodonostní prostor*: trojice $(samples, events, P)$
  - $samples$ -- množina elementárních jevů
  - $events subset.eq powerset(samples)$ -- prostor jevů (typicky $powerset(samples)$)
    + $emptyset in events, samples in events$
    + $A in events => A^complement := samples without A in events$
    + $A_1,A_2... in events => union.big_(i=1)^oo A_i in events$
  - $P: events -> [0,1]$ -- pravděpodobnost
    + $P(samples) = 1$, $P(emptyset) = 0$
    + $P(union.big_(i=1)^oo A_i = sum_(i=1)^oo P(A_i)$ pro po dvou disjunktní $A_1,A_2... in events$
- základní pravidla pro počítání s pravděpodobností
  - $P(A) + P(A^complement) = 1$
  - $A subset.eq B => P(B without A)  = P(B) - P(A) => P(A) <= P(B)$
  - $P(A union B) = P(A) + P(B) - P(A inter B)$
  - $P(A_1 union A_2 ...) <= sum_i P(A_i)$
- nezávislost náhodných jevů, podmíněná pravděpodobnost
  - jevy $A$ a $B$ jsou nezávislé, pokud $P(A inter B) = P(A) dot P(B)$
  - $P(A | B) = P(A inter B) / P(B)$ "pravděpodobnost $A$ za předpokladu $B$"
- *Bayesův vzorec*: pro rozklad $samples = B_1 inter B_2...$
  $ P(B_j | A) = (P(A | B_j) dot P(B_j))/(sum_i P(A | B_i) dot P(B_i)) $
=== Náhodné veličiny a jejich rozdělení
- *#text(red)[(diskrétní)] náhodná veličina*: $X: samples -> RR$, pokud #text(red)[($"Im"(X)$ je spočetná)] a pro všechna $x$ z $RR$ platí:
  $ {omega in samples : X(omega) = x} in events $
==== popis pomocí funkcí
- *pravděpodobnostní funkce*: $p_X: RR -> [0,1]: p_X(x) = P({X=x})$ (pro #text(red)[d. n. v.])
- *distribuční funkce*: $F_X: RR -> [0,1]: F_X(x) := P(X <= x) = P(omega in samples: X(omega) <= x)$
  + $F_X$ je neklesající
  + $lim_(x -> -oo) F_X(x) = 0$
  + $lim_(x -> +oo) F_X(x) = 1$
  + zprava spojitá $F_X(x_+) = F_X(x)$
- *hustotní funkce:* $f_X : RR -> RR_0^+: F_X(x) = integral_(-oo)^x f_X (t) dif t$ (pokud existuje, n. v. je #text(blue)[spojitá])
  + $P(X = x) = 0 quad forall x in RR$
  + $P(a <= X <= b) = integral_a^b f_X (t) dif t quad forall a < b in RR$
  + $F_X$ je spojitá
==== střední hodnota
- *střední hodnota #text(red)[diskrétní] n. v.*: $ EE(X) = sum_(x in "Im"(X)) x dot P(X = x) $
- *střední hodnota #text(blue)[spojité] n. v.*: $ EE(X) = integral_(-oo)^(oo) x dot f_X(x) $
- linearita střední hodnoty
  - $EE(X + Y) = EE(X) + EE(Y)$
  - $EE(a dot X + b) = a EE(X) + b$
- střední hodnota součinu nezávislých veličin
  - *#text(red)[diskrétní] n. v. jsou nezávislé, pokud*: $P(X = x and Y = y) = P(X = x) P(Y = y)$
  - pro *nezávislé* #text(red)[d.] n. v. platí: $EE(X dot Y) = EE(X) dot EE(Y)$
- *Markovova nerovnost*: pro $X >= 0$ a $a in RR^+$:
  $ P(X >= a) <= EE(X)/a $
==== rozptyl
#let var = "var"
- *rozptyl:* $var(X) = EE((X - EE X)^2)$
  - $= EE(X^2) - EE(X)^2$
- vzorec pro rozptyl součtu (závislých či nezávislých veličin)
  - $var(a X + b) = a^2 var(X)$
==== práce s konkrétními rozděleními
- *geometrické* (džbánové) -- kolikrát musím dojít se džbánem pro vodu, než se ucho utrhne
  - $X ~ "Geom"(p)$ ($p$ je pravděpodobnost, že se ucho utrhne při každé výpravě pro vodu)
  - $p_X (k) = (1 - p)^(k-1) dot p$ ($(k-1)$-krát dojdu pro vodu bez utržení a jednou s utržením)
  - $EE(X) = 1/p$
  - $var(X) = (1-p)/p^2$
- *binomické* (multidžbánové) -- počet džbánů, které spotřebuji pro $n$ výprav pro vodu #footnote[vodu ve džbánu, jehož ucho se utrhlo, donesu domů (protože takový džbán se dá stále držet oběma rukama), ale je to otrava, takže si doma vezmu nový]
  - $X ~ "Binom"(n,p)$
  - $p_X(k) = binom(n,k) p^k (1 - p)^(n-k)$ ($k$-krát dojdu pro vodu a ucho utrhnu, $n-k$-krát ho neutrhnu, existuje $binom(n,k)$ způsobů, jak posloupnost takových cest mohla vypadat)
  - $EE(X) = n p$ (pokud jeden džbán vydrží v průměru $1/p$ cest, použiju $n/(1/p)$ džbánů)
  - $var(X) = n p (1-p)$
- *Poissonovo* (opravářovo) -- kolik nosičů přijde za den k opraváři nechat přilepit ucho
  - $X ~ "Pois"(lambda)$
  - $p_X(k) = lambda^k/k! e^(-lambda)$
  - $EE(X) = lambda$
  - $var(X) = lambda$
  - intuice: $lim_(n->oo) "Binom"(n, lambda/n) = "Pois"(lambda)$ (máme $n$ nosičů, kteří mají $n$-krát kvalitnější džbány)
- *standartní normální*
  - $X ~ N(0, 1)$
  - $f_X(x) = phi(x) = 1/sqrt(2 pi) e^(-x^2/2)$
  - $F_X = Phi$
  - $EE(X) = 0$, $var(X) = 1$
- *normální*
  - $X ~ N(mu, sigma)$
  - $N(mu,sigma) = N(0,1) dot sigma + mu$
  - $f_X = 1/sigma phi((x-mu)/sigma)$
  - $EE(X) = mu$, $var(X) = sigma^2$
- *exponenciální* (opravářovo čekací) -- jak dlouho čeká opravář, než dorazí další nosič
  - $X ~ "Exp"(lambda)$
  - $ f_X(x) = cases(0 &"pro" x <= 0, lambda e ^(-lambda x) &"pro" x >= 0) $
  - $ F_X(x) = cases(0 &"pro" x <= 0, 1 0 e^(-lambda x) &"pro" x >= 0) $
  - $EE(X) = 1/lambda$
  - $var(X) = 1/lambda^2$
=== Limitní věty
==== zákon velkých čísel
- stejně rozdělené $X_1...X_n$:
- $overline(X_n) = 1/n (X_1 + ... + X_n)$
- silný: $ P(lim_(x->oo) overline(X_n) = EE(X)) = 1 $
- slabý: $ lim_(x->oo) P(|overline(X_n) - EE(X)| > epsilon) = 0 $
==== centrální limitní věta
- stejně rozdělené $X_1...X_n$ s $EE(X) = mu$ a $var(X) = sigma^2$
- $ Y_n =((X_1 + ... + X_n) - n mu)/(sqrt(n) dot sigma) $
- $ lim_(n->oo) F_(Y_n) (x) = Phi(x) quad forall x in RR $
=== Bodové odhady
- alespoň jedna metoda pro jejich tvorbu
- *výběrový průměr a rozptyl*
  - $overline(X)_n = 1/n sum_i X_i $
    - konzistentní nestranný odhad $mu$
  - $overline(S)_n = 1/n sum_i (X_i - overline(X)_n)^2 $
    - konzistentní asymptoticky nestranný odhad $sigma^2$
  - $hat(S)_n = 1/(n-1) sum_i (X_i - overline(X)_n)^2 $
    - konzistentní nestranný odhad $sigma^2$
- *metoda momentů*
  - $m_r (theta) = EE(X(theta)^r)$
  - $hat(m_r) = 1/n sum_i X_i^r$
  - řešíme soustavu rovnic $m_r(theta) = hat(m_r)$ pro různá $r$
- *maximum likelihood estimate*
  - pro realizaci náhodného výběru $x = (x_1...x_n)$ vybíráme hodnotu $theta$, pro kterou je pravděpodonost tohoto výběru největší
  - maximalizujeme $L(x;theta)$ podle $theta$
    - $ L(x;theta) = cases(#text(red)[$p_X(x;theta) = product_i p_(X_i)(x_i;theta)$], #text(blue)[$f_X(x;theta) = product_i f_(X_i)(x_i;theta)$]) $
=== Intervalové odhady
- *metoda založená na aproximaci normálním rozdělením*
  - odhadujeme $N(theta, sigma^2)$, známe $sigma^2$, hledáme $theta$
    - $ overline(X) plus.minus z_(alpha/2) dot sigma/sqrt(n) $
    - $z_(alpha/2) = Phi^(-1) (1 - alpha/2)$ -- kvantilová fce $N(0, 1)$
    - při dostatečně velkém $n$ to platí díky CLV i pro libovolné rozdělení
  - odhadujeme $N(theta, sigma^2)$, neznáme $sigma^2$ ani $theta$
    - $ hat(theta) plus.minus bold(t)_(alpha/2) dot hat(S_n)/sqrt(n) $
    - $(overline(X) - mu)/(hat(S_n)/sqrt(n))$ už není normálně rozdělená n. v., ale má studentovo rozdělení s pdf $Psi_(n-1)(x)$
    - $t_(a/2) = Psi_(n-1)^(-1) (1 - alpha/2)$ -- kvantilová fce studentova rozdělení s $n-1$ stupni volnosti
=== Testování hypotéz
- základní přístup
  - *$H_0$* -- nulová hypotéza
  - *$H_1$* -- alternativní hypotéza
  - zamítáme či nezamítáme nulovou hypotézu
- chyby 1. a 2. druhu
  - *chyba 1. druhu* -- trapas (hlásíme zajímavst, i když nenastala)
  - *chyba 2. druhu* -- promarněná příležitost (nehlásíme zajímavst, i když bychom mohli)
- *hladina významnosti*
  - pravděpodobnost *chyby 1. druhu*, typicky $alpha = 0.05$

== Logika
=== Syntaxe
- znalost a práce se základními pojmy syntaxe výrokové a predikátové logiky (jazyk, otevřená a uzavřená formule, instance formule, apod.)
- *jazyk výrokové logiky* -- množina všech prvovýroků, $not, and, or, ->, <->, (,)$
- *jazyk predikátové logiky* -- signatura $angle.l cal(R), cal(F) angle.r$, (=)? , symboly volných proměnných, logické symboly
- *otevřená formule* -- neobsahuje kvantifikátory
- *uzavřená formule* -- neobsahuje volné proměnné
- *instance* -- dosazení za volnou proměnnou
- *teorie* -- libovolná spočetná (ne nutně konečná) množina výroků
- *term* -- cokoliv co nevrací bool (proměnná, funkce nebo konstanta)
==== normální tvary výrokových formulí
- *PNF* -- $(Q_1 x_1)(Q_2 x_2)...(Q_n x_n) phi$, kde $phi$ je otevřená
  - převod vytýkáním
    + $not (Q x)(phi) ~ (overline(Q)x)(not phi)$
    + $(Q x)(phi) and psi ~ (Q x)(phi and psi)$
    + $(Q x)(phi) or psi ~ (Q x)(phi or psi)$
- *CNF* -- konjunkce disjunkcí literálů $(p or not q or s) and (not r) and (not s or r)$
  - literál -- $p, not p$
  - klauzule -- disjunkce literálů
  - převod ekvivalentními úpravami
- *DNF* -- disjunkce konjunkcí literálů $(p and not q and s) or (not r) or (not s and r)$
  - převod ekvivalentními úpravami
- použití pro algoritmy (SAT, rezoluce)
  - rezoluce i SAT používají CNF
=== Sémantika
- *model teorie*
  - VL: ohodnocení prvovýroků, ve kterém platí všechny axiomy teorie
  - PL: struktura $angle.l cal(A), cal(R^A), cal(F^A) angle.r$ určující universum $cal(A)$ a implementaci relačních a funkčních symbolů, ve které platí všechny axiomy teorie
- pravdivost, lživost, nezávislost formule vzhledem k teorii
  - formule je *pravdivá*, pokud platí ve všech modelech teorie (všechna ohodnocení, které splňují teorii, splňují i formuli)
  - formule je *lživá*, pokud neplatí v žádném modelu teorie (všechna ohodnocení, které splňují teorii, nesplňují formuli)
  - formule je *nezávislá*, pokud platí v některém modelu a v jiném ne
- splnitelnost, tautologie, důsledek
  - formule je *splnitelná*, pokud není lživá
  - formule je *tautologie*, pokud je pravdivá v logice ($p or not p$)
- analýza výrokových teorií nad konečně mnoha prvovýroky
  - prostě to zanalyzuješ ne? tablem? možná?
=== Extenze teorií
- *extenze* $E$ teorie $T$ je taková teorie, ve které jsou *pravdivé* alespoň ty modely, které jsou pravdivé v $T$
  - *konzervativní* -- nemění množinu *důsledků* (pravdivých modelů) v původním jazyce (ale může přidávat nové důsledky nad novými symboly)
  - *jednnoduchá* -- nemění jazyk
- schopnost porovnat sílu teorií
  - stronk
- skolemizace
  - PNF → otevřená formule
    - $(forall x)(phi(x)) ~ phi(x)$
    - $(exists x)(phi(x)) ~ phi(c)$ (nový konstatntí symbol)
    - $(forall x)(exists y)(phi(x, y)) ~ phi(x, f(x))$ (nový funkční symbol)
=== Dokazatelnost
- pojem formálního důkazu, zamítnutí
  - *důkaz* je mechanicky ověřitelný certifikát o tom, že $phi$ platí, provedený na syntaktické úrovni
  - *zamítnutí* je důkaz sporu, protipříklad
- schopnost práce v některém z formálních dokazovacích systémů (např. tablo metoda, rezoluce, Hilbertovský kalkul)
  - tablo
    - $phi and psi space dash.em phi space dash.em  psi$
    - $phi or psi space cases(phi, psi, delim: angle.l)$
    - $(forall x) phi(x) space dash.em phi(x \/ t_i)$ -- všechny existující termy
    - $(exists x) phi(x) space dash.em phi(x \/ c_i)$ -- nový konstantní term
=== Věty o kompaktnosti a úplnosti výrokové a predikátové logiky
- znění a porozumění významu
- použití na příkladech, důsledky
- *věta o kompaktnosti*: teorie má model kdyžž každá její konečná část má model
- *větu o úplnosti* Bulínova skripta v tomto kontextu nezmiňují, v obecnosti úplnost znamená, že umíme dokázat všechná pravdivá tvrzení
=== Rozhodnutelnost
- teorie je *rekurzivně axiomatizovatelná* $arrow.double.l exists$ algoritmus ověřující axiom $phi in T$
- teorie je *rozhodnutelná*, $arrow.double.l exists$ algoritmus, $forall phi$ doběhne, ověří $T models phi$
- teorie je *částečně rozhodnutelná*, $arrow.double.l exists$ algoritmus $forall phi$ ověří $T models phi$, pro $T cancel(models) phi$ nemusí doběhnout
- teorie je *kompletní*, pokud je bezesporná a každá uzavřená formule je pravdivá nebo lživá
- RA => částečně rozhodnutelná
- RA + kompletní => rozhodnutelná
- pojem kompletnosti a její kritéria, význam pro rozhodnutelnost
  - $omega$-kategorické kritérium kompletnosti
    - ani náhodou
- příklady rozhodnutelných a nerozhodnutelných teorií
  - nerozhodnutelné - Halting problem, Hilbertův desátý problém

= Společná informatika

== Automaty a jazyky
=== Regulární jazyky
- deterministický a nedeterministický konečný automat
  - *DFA*: $(Q, Sigma, delta, q_0, F)$
    - $Q$ -- množina stavů
    - $Sigma$ -- abeceda
    - $delta: Q times Sigma -> Q$ -- přechodová fce
    - $q_0 in Q$ -- počáteční stav
    - $F subset Q$ -- množina koncových stavů
  - *NFA*: $(Q, Sigma, delta, Q_0, F)$
    - $Q$ -- množina stavů
    - $Sigma$ -- abeceda
    - $delta: Q times Sigma -> powerset(Q)$ -- přechodová fce
    - $Q_0 subset Q$ -- množina počáteční stavů
    - $F subset Q$ -- množina koncových stavů
- regulární gramatiky
  - pravá lineární $A -> omega B$, $A -> omega$, $A,B, in V, omega in T^*$
- regulární výrazy
  $epsilon.alt, emptyset, mono(a), alpha + beta, alpha beta, alpha ^*, (alpha)$
=== Bezkontextové jazyky
- bezkontextové gramatiky, jazyk generovaný gramatikou
  - $A -> omega, A in V, omega in (V union T)^*$
- zásobníkový automat, třída jazyků přijímaných zásobníkovými automaty
  - *PDA:* $(Q, Sigma, Gamma, delta, q_0, F)$
    - $Q$ -- množina stavů
    - $Sigma$ -- vstupní abeceda
    - $Gamma$ -- zásobníková abeceda
    - $delta: Q times (Sigma union {epsilon.alt}) times Gamma -> powerset(Q times Gamma^*)$ -- přechodová fce
    - $q_0 in Q$ -- počáteční stav
    - $Z_0 in Gamma$ -- počáteční zásobníkový symbol
    - $F subset Q$ -- množina koncových stavů
=== Rekurzivně spočetné jazyky
- gramatika typu 0
  - $alpha -> omega; alpha, omega in (V union T)^*$
- *Turingův stroj*: $(Q, Sigma, Gamma, delta, q_0, F)$
  - $Q$ -- množina stavů
  - $Sigma$ -- vstupní abeceda
  - $Gamma$ -- zásobníková abeceda
  - $delta: (Q without F) times Gamma -> Q times Gamma times {L,R}$ -- přechodová fce
  - $q_0 in Q$ -- počáteční stav
  - $B in Gamma without Sigma$ -- symbol prázdné pásky
  - $F subset Q$ -- množina koncových stavů
- algoritmicky nerozhodnutelné problémy
  - Halting problem/diagonální jazyk
  - PCP
=== Chomského hierarchie
- schopnost zařazení konkrétního jazyka do Chomského hierarchie (zpravidla sestrojení odpovídajícího automatu či gramatiky)

== Algoritmy a datové stuktury
=== Časová složitost algoritmů
- časová a prostorová složitost algoritmu
  - *časová složitost*: celkový počet kroků RAMu jako funkce délky vstupu $f: NN -> RR$
  - *prostorová složitost*: rozsah indexů použitých buňek paměti jako funkce délky vstupu $f: NN -> RR$
- měření velikosti dat
  - jednotková cena, neomezená čísla -- dá se hackovat prostorová složitost kódováním do jednoho čísla
  - jednotková cena, konstantou omezená velikost čísel (a tím indexovatelné paměti)
  - jednotková cena, polynomem omezená velikost čísel (a tím indexovatelné paměti)
  - logaritmická cena, neomezená čísla -- dobré, ale otrava s tím počítat
  - poměrná logaritmická cena, neomezená čísla -- cena je poměr logaritmů velikosti vstupu a čísel, pro polynomy konstantní
- složitost v nejlepším, nejhorším a průměrném případě
- asymptotická notace
  - $f in cal(O)(g) equiv exists n_0,c: forall n >= n_0 f(n) <= c g(n)$
  - $f in cal(Omega)(g) equiv exists n_0,c: forall n >= n_0 f(n) >= c g(n)$
  - $f in cal(Theta)(g) equiv f in cal(O)(g) and f in cal(Omega)(g)$
=== Třídy složitosti
- třídy P a NP
  - *P* -- třída rozhodovacích problémů řešitelných v polynomiálním čase
  - *NP* -- $L in "NP"$ kdyžž $exists K in "P", "polynom" g$, $forall x L(x) = 1 <=> exists y, |y| <= g(|x|): K(x,y) = 1$
- převoditelnost problémů, NP-těžkost a NP-úplnost
  - *převod* -- platí $A -> B$, když $exists$ funkce $f: {0,1}^* -> {0,1}^*$ taková, že $forall x: A(x) = B(f(x))$ a $f$ běží v polynomiálním čase
  - problém je *NP-těžký*, pokud na něj lze převést libovolný problém v NP
  - problém je *NP-úplný*, pokud je NP-těžký a v NP
- příklady NP-úplných problémů a převodů mezi nimi
  - SAT → 3-SAT -- přidáváme nové literály, $(alpha or beta) -> (alpha or x) and (not x or beta)$
  - 3-SAT → NzMna -- klauzule tvoří trojúhélníky, spojujeme $x$ s $not x$
  - 3-SAT → 3,3-SAT -- proměnné rozdělíme a zařídíme stejně ohodnocení kolečkem implikací
  - 3,3-SAT → 3D-párování -- proměnná se vyskytuje jen dvakrát -- cyklus KDKD, Z čouhají, lze spárovat pouze Z naproti sobě, klauzule -- KDZZZ
=== Metoda rozděl a panuj
- princip rekurzivního dělení problému na podproblémy
  - problém velikosti $n$ rozdělíme na dva podproblémy velikosti $n/2$
- výpočet složitosti pomocí rekurentních rovnic
- Master theorem (kuchařková věta) (bez důkazu)
  - $ T(n) &= a dot T(n/b) + Theta(n^c) \ &= a^(log_b n) + Theta(n^c) dot sum_(i=0)^(log_b n) (a/b^c)^i \ &= n^(log_b a) + Theta(n^c) dot sum_(i=0)^(log_b n) (a/b^c)^i $
  - $T(n) = Theta(n^c log n)$ pokud $a/b^c = 1$
  - $T(n) = Theta(n^c)$ pokud $a/b^c < 1$
  - $T(n) = Theta(n^(log_b a))$ pokud $a/b^c > 1$
- aplikace
  - Mergesort
  - násobení dlouhých čísel
    - $ x &= (A << n/2) + B \
        y &= (C << n/2) + D \
        x y &= (A C << n) + (A D << n/2) + (B C << n/2) + B D \
        (A + B)(C + D) &= A C + A D + B C + B D \
        x y &= (A C << n) + ((A + B)(C + D) - A C - B D) << n/2 + B D
    $
=== Binarní vyhledávací stromy
- *vyhledávací strom*: klíč v každém vrcholu je větší než všechny klíče levého podstromu a menší než pravého
- operace s nevyvažovanými stromy -- show, find, min, insert, delete
- *AVL strom*: rozdíl v hloubkách podstromů je max 1
=== Třídění
- primitivní třídicí algoritmy (Bubblesort, Insertsort)
- Quicksort -- pivot $p$, $<p$, $>p$, rekurze
- dolní odhad složitosti porovnávacích třídicích algoritmů
  - $n log n$
=== Grafové algoritmy
- prohledávání do šířky a do hloubky
  - *BFS*: dělá vrstvy, hledá nejkratší vzdálenost, používá frontu
  - *DFS*: zpětná hrana není nikdy most, xyyx -- dopředná/stromová, yxxy -- zpětná, yyxx -- příčná, xxyy -- nenastane
- topologické třídění orientovaných grafů
  - seřadím podle pořadí uzavírání v DFS, pořadí bude opačné
- nejkratší cesty v ohodnocených grafech (Dijkstrův a Bellmanův-Fordův algoritmus)
  - obecný relaxační algoritmus
  - *Dijkstra* -- halda vzdáleností
  - *BF* -- fronta podle pořadí otevíraných vrcholů -- může otevírat už jednou zavřené vrcholy
- minimální kostra grafu (Jarníkův a Borůvkův algoritmus)
  - *Jarníkův* -- přidáváme nejmenší hranu mezi kostrou a zbytkem grafu
  - *Borůvkův* -- začínáme s $n$ kostrami, ke každé přidáváme nejmenší hranu
  - *Kruskalův* -- začínáme s $n$ kostrami, vybíráme nejmenší hrany v celém grafu, přidáváme, netvoří-li cyklus
- toky v sítích (Ford-Fulkerson algoritmus)
  - hledáme zlepšující cesty, dostaneme maximální řez daný nasycenými cestami

== Programovací jazyky
Některé následující body definují varianty požadavků pro různé individuální volby povinně volitelných předmětů.
Vyžaduje se zvládnutí všech bodů bez označení Ⓥ a zvládnutí všech bodů s označením Ⓥ pro jeden z jazyků C\#, C++
nebo Java.
- Koncepty pro abstrakci, zapouzdření a polymorfismus.
  - související konstrukty programovacích jazyků
    - třídy, rozhraní, metody, datové položky, dědičnost, viditelnost
    - Ⓥ zapouzdření poskytované moduly v Javě
  - (dynamický) polymorfismus, statické a dynamické typování
  - jednoduchá dědičnost
    - Ⓥ virtuální a nevirtuální metody v C++ a C\#
  - vícenásobná dědičnost a její problémy
    - Ⓥ vícenásobná a virtuální dědičnost v C++
    - Ⓥ interfaces a defaultní metody v Javě
    - Ⓥ interfaces v C\#
  - implementace rozhraní (interface)
  - vhodné použití uvedených konceptů
- Primitivní a objektové typy a jejich reprezentace.
  - číselné a výčtové typy
  - Ⓥ ukazatele a reference v C++
    - *`&` je lvalue, `&&` je rvalue*
  - Ⓥ hodnotové a referenční typy v C\#
    - *value*
      - int, float, bool, char
      - struct, enum, nullable
    - *reference*
      - class, interface, record, delegate (lambda)
      - dynamic, object, string
  - Ⓥ reference, imutabilní typy a boxing v C\# a Javě
    - *boxing*: zabalení value typu do objectu
- Generické typy a funkcionální prvky (procedurálních programovacích jazyků).
  - Ⓥ šablony (templates) a statický polymorfismus v C++
  - Ⓥ generické typy v Javě a C\# (bez omezení typových parametrů)
  - Ⓥ typy reprezentující funkce v C++, C\#, nebo Javě
  - lambda funkce a funkcionální rozhraní
- Manipulace se zdroji a mechanizmy pro ošetření chyb.
  - správa životního cyklu zdrojů v případě výskytu chyb
    - Ⓥ RAII v C++
      - *Resource acquisition is initialization* -- spojuje lifetime objektu a nějakého zdroje (mutexu, paměti)
    - Ⓥ using v C\#
      - jako `with` v pythonu
    - Ⓥ try-with-resources v Javě
  - konstrukce pro obsluhu a propagaci výjimek
- Životní cyklus objektů a správa paměti.
  - alokace (alokace statická, na zásobníku, na haldě)
  - inicializace (konstruktory, volání zděděných konstruktorů)
  - destrukce (destruktory, finalizátory)
  - explicitní uvolňování objektů, reference counting, garbage collector
- Vlákna a podpora synchronizace.
  - reprezentace vláken v programovacích jazycích
  - specifikace funkce vykonávané vláknem a základní operace na vlákny
  - časově závislé chyby a mechanizmy pro synchronizaci vláken
- Implementace základních prvků objektových jazyků.
  - základní objektové koncepty v konkrétním jazyce
  - implementace a interní reprezentace primitivních typů
  - implementace a interní reprezentace složených typů a objektů
  - implementace dynamického polymorfismu (tabulka virtuálních metod)
- Nativní a interpretovaný běh, řízení překladu a sestavení programu.
  - reprezentace programu, bytecode, interpret jazyka
  - just-in-time (JIT) a ahead-of-time (AOT) překlad
  - proces sestavení programu, oddělený překlad, linkování
  - staticky a dynamicky linkované knihovny
  - běhové prostředí procesu a vazba na operační systém

== Architektura počítačů a operačních systémů
- Základní architektura počítače, reprezentace čísel, dat a programů.
  - reprezentace a přístup k datům v paměti, adresa, adresový prostor
  - ukládání jednoduchých a složených datových typů
  - základní aritmetické a logické operace
- Instrukční sada, vazba na prvky vyšších programovacích jazyků.
  - Implementovat běžné programové konstrukce vyšších jazyků (přiřazení, podmínka, cyklus, volání funkce) pomocí instrukcí procesoru
  - 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
- Podpora pro běh operačního systému.
  - privilegovaný a neprivilegovaný režim procesoru
  - jádro operačního systému
- Rozhraní periferních zařízení a jejich obsluha.
  - 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)
  - 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í
- Základní abstrakce, rozhraní a mechanizmy OS pro běh programů, sdílení prostředků a vstup/výstup.
  - neprivilegované (uživatelské) procesy
  - sdílení procesoru
    - procesy, vlákna, kontext procesu a vlákna
    - přepínání kontextu, kooperativní a preemptivní multitasking
    - plánování běhu procesů a vláken, stavy vlákna
  - sdílení paměti
    - 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
    - Na zadaném příkladu identifikovat a vysvětlit význam komponent virtuální a fyzické adresy (číslo stránky, číslo rámce, offset)
    - Pro konkrétní adresy a obsah jednoúrovňové stránkovací tabulky řešit úlohy překladu adres
    - Vysvětlit roli virtuálních adresových prostorů v ochraně paměti procesů a vláken
  - sdílení úložného prostoru
    - soubory, analogie s adresovým prostorem
    - abstrakce a rozhraní pro práci se soubory
- Paralelismus, vlákna a rozhraní pro jejich správu, synchronizace vláken.
  - časově závislé chyby (race conditions)
  - kritická sekce, vzájemné vyloučení
  - základní sychronizační primitiva, jejich rozhraní a použití
    - zámky
    - aktivní a pasivní čekání

= Systémové programování

== Architektura počítačů
- Výkonnost počítače a procesoru, metriky a omezení
  - Vyjádřit a na příkladech demonstrovat vztah mezi dobou běhu programu a metrikami na úrovni architektury (CPI, IPC)
  - Popsat vliv instrukčního mixu na hodnoty metrik CPI a IPC, identifikovat typické hodnoty CPI a IPC
    - *některé instrukce jsou rychlejší než jiné*, aritmetika typicky 1 CPI, jumpy 3 CPI, load 5 CPI, ALE, často má vliv i paralelismus
  - Formulovat Amdahlův zákon a použít ho pro odhad limitů zrychlení díky paralelismu
    - $t_("para") = t_("non-paralelizable") + t_("paralelizable")/n$
- Zpracování instrukcí procesorem, paralelismus, predikce a spekulace
  - Na diagramu datové cesty procesoru vysvětlit postup zpracování základních instrukcí (add, load, store, branch)
  - Popsat kroky vykonané procesorem pro obsluhu přerušení a obsluhu výjimek
    - *zastavení, identifikace příčiny, uložení stavu, skok na handler*
  - Na příkladu kódu popsat zřetězené zpracování (pipelining), identifikovat datové závislosti a popsat jejich řešení, odhadnout zrychlení
  - Popsat zřetězené zpracování (pipelining) za přítomnosti (také podmíněných a nepřímých) skoků, popsat a na příkladu identifikovat rozhodnutí základních prediktorů (saturating counter), popsat spekulativní vykonávání kódu a jeho vliv na výkon
  - Popsat rozdíl mezi hardware cores a hardware threads a jeho vliv na výkon
    - *core* -- více-méně oddělený procesor
    - *thread* -- vlastní kontext (virtuální registry, PC), sdílená ALU, většina ostatního
- Architektura paměťového subsystému, architektura cache
  - Použít metriky hit či miss ratio a access latency pro odhad rychlosti přístupu do paměti
  - Pro zadanou architekturu (přímo mapovaná, množinově či plně asociativní) a relevantní parametry (velikost, stupeň asociativity, victim replacement policy) cache a zadanou sekvenci přístupů do paměti určit chování cache (hit/miss, 3C model, obsazení konkrétních cache lines)
    - *CCC* -- cold, capacity, conflict
  - Diskutovat roli vrstev ve víceúrovňové architektuře cache a identifikovat obvyklé parametry vrstev
    - *L1* -- 64K (per core), *L2* -- 512K (per core or 2), *L3* -- 32M (per CPU)
- Multi-core a multi-socket systémy, koherence cache
  - Na diagramu identifikovat UMA a NUMA architektury
    - *(non-)uniform memory access*
  - Popsat záruky poskytované mechanismy cache coherence při přístupu do paměti
  - Popsat a na příkladech ilustrovat fungování cache coherence protokolů (IV, MSI, MESI)
  - Popsat a na příkladech kódu ilustrovat false sharing

== Operační systémy
- Spouštění procesů, dynamicky linkované knihovny, volací konvence
  - Použít systémové API (fork, exec, join …) pro spuštění a (počkání na) ukončení procesu
  - Použít pthread API (pthread_create, pthread_join …) pro spuštění a (počkání na) ukončení vlákna
    - ```c int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg)```
    - ```c int pthread_join(pthread_t thread, void **retval);```
  - Identifikovat statické a dynamické linkování, použít obvyklé nástroje pro vytvoření staticky a dynamicky linkovaného programu
    - `gcc -static`
  - Použít obvyklé nástroje pro identifikaci linkovaných symbolů, identifikovat externí a exportované symboly
    - `ldd <binary>`
  - Porovnat použití a režii statického a dynamického linkování
    - *statické* -- + dá se optimalizovat, - velké, když se nezoptimalizuje, musí se překompilovat při aktualizaci
    - *dynamické* -- (potenciálně) malé binárky
  - Identifikovat na ukázkách kódu pozičně závislý a pozičně nezávislý program, použít překladač pro vytvoření takového programu
    - `gcc -no-pie`
  - Identifikovat a vysvětlit použití absolutních adres pro adresaci proměnných na ukázkách kódu
  - Identifikovat a vysvětlit použití relativních adres pro adresaci proměnných na ukázkách kódu
  - Porovnat použití a režii absolutní a relativní adresace
  - Popsat obvyklé umístění argumentů, proměnných a dalších informací na zásobníku programů
  - Popsat obvyklé použití registrů procesoru uvnitř funkcí a při volání funkcí
- Paralelismus a synchronizace na multiprocesorech
  - Popsat a sestavit příklad race condition nad sdíleným čítačem s použitím interleaving sémantiky běhu programu
  - Popsat a sestavit příklad race condition nad sdíleným seznamem s použitím interleaving sémantiky běhu programu
  - Popsat sémantiku prostředků pro implementaci synchronizace na multiprocesorech (IPI, T&S, CAS, LL/SC)
    - *IPI* -- interprocessor interrupt
    - *T&S* -- test and set (atomické "zapiš hodnotu a vrať původní") (lol mělo by to být spíš set and test)
    - *CAS* -- compare and swap (atomické "zapiš hodnotu x, pokud je tam právě zapsané y")
    - *LL/SC* -- load-link/store-conditional (dvě instrukce, první načte hodnotu a druhá zapíše, pouze pokud na danou paměť nikdo od té doby nesáhl)
  - Implementovat spin lock s použitím zadaného prostředku (T&S, CAS, LL/SC)
  - Implementovat blokující zámek s použitím rozhraní futex
    - *futex* -- fast userspace mutex, atomic ints in userspace, syscalls only when needed
- Rozhraní pro synchronizaci
  - Popsat sémantiku atomických typů, bariér, zámků, semaforů, condition variables jako nástrojů pro synchronizaci
  - Použít zadaný nástroj (atomické typy, bariéry, zámky, semafory, condition variables) pro odstranění race condition v ukázkách kódu
  - Použít zadaný nástroj (atomické typy, bariéry, zámky, semafory, condition variables) pro implementaci problému producent-konzument
- Správa paměti na multiprocesorech, alokátory, garbage collection
  - Na zadaném příkladu datových struktur heap alokátoru popsat jeho funkci a odhadnout prostorovou a časovou režii
  - Na zadaném příkladu obsahu heapu demonstrovat algoritmy mark and sweep a copying garbage collection
    - *mark and sweep* -- označím a pak uklízím
    - *copying gc* -- používané objekty rovnou kopíruju do druhé půlky paměti
  - Ovládat související terminologii (heap, mutator, collector, reachability, garbage)
- Rozhraní pro práci se soubory, paměťově mapované soubory
  - Použít systémové API (open, seek, read, write, close, readv, writev, mmap) pro práci se soubory
    - *readv* / *writev* -- více sekvenčních čtení/zápisů do seznamu bufferů a velikostí (jeden syscall!)
  - Popsat interakci systému souborů a správy paměti při přístupu k souborům pomocí mapování (mmap)
    - ```c void *mmap(void addr[.length], size_t length, int prot, int flags, int fd, off_t offset);```
      - `addr` bude typicky `0`, kernel pickne
- Interní struktura základních systémů souborů
  - Vyjmenovat obvyklá metadata asociovaná se souborem
  - Na zadaném příkladu datových struktur systému souborů (FAT, inode, extent, dentry, bitmap) popsat realizaci operací se souborem (open, read, write)
- Princip komunikace mezi periferiemi a operačním systémem
  - Popsat a na příkladech kódu identifikovat jednotlivé kroky obsluhy žádosti o přerušení od zařízení
  - Popsat omezení nástrojů pro synchronizaci uvniř kódu obsluhujícího žádosti o přerušení
  - Popsat jednotlivé kroky přenosu dat mezi zařízením a pamětí při použití DMA

== Počítačové sítě
- Linková vrstva, adresace v Ethernetu
  - Vysvětlit základní vlastnosti a úkoly vrstvy síťového rozhraní
  - Vyjmenovat/identifikovat nejdůležitější položky ethernetové rámce, vysvětlit pojem MAC adresy a její význam
  - Propojovací zařízení na úrovni linkové vrstvy, přepínače (switch)
    - Popsat princip činnosti linkového rozhraní (přijímání, zpracování a odesílání rámců)
    - Popsat principy základní optimalizace síťového toku (filtrování, cílený forwarding, metoda zpětného učení)
- Síťová vrstva, adresace v IPv4 a IPv6, statické směrování, NAT
  - Vysvětlit základní vlastnosti a úkoly síťové vrstvy a její návaznost na vrstvy síťového rozhraní (hop-to-hop komunikace, přímé vs. nepřímé doručování)
  - Vymezení problému směrování (routing) a předávání (forwarding), směrovací tabulky
    - Vysvětlit na příkladu strukturu záznamů ve směrovacích tabulkách a význam jednotlivých položek
    - Na zadaném příkladu sítě (topologie, adresy, obsahy tabulek) popsat postup zpracování (doručení) konkrétního IP datagramu
  - IP adresy (v4 i v6)
    - Vysvětlit pojem IP adresa a síťová maska a jejich význam pro síťovou vrstvu (doručování datagramů)
    - Popsat způsob přidělování IP adres a speciální prostory adres (privátní adresy, multicast)
    - Popsat na konkrétním problému možnou aplikaci NA(P)T překladu a vysvětlit jeho užitečnost vs. nevýhody
    - Na příkladu dané sítě s použitím NA(P)T vysvětlit průchod datového paketu z vnitřní sítě do vnější a naopak
  - Protokol IPv4, základní vlastnosti, struktura IPv4 datagramu
    - Na příkladu identifikovat hlavní položky hlavičky (verze, time-to-live, protokol, kontrolní součet, adresy)
    - Na daném příkladu hlaviček datagramu (a konfigurace routeru) vysvětlit, jak bude datagram zpracován
    - Včetně atypických situací jako je např. zahození datagramu
    - Vysvětlit základní princip fungování nástroje traceroute
    - Popsat princip IPv4 fragmentace (s návazností na hlavičky IP datagramu) a navrhnout alespoň jeden postup, jak se fragmentaci vyhnout
  - Protokol ICMPv4, jeho účel a použití, základní typy zpráv, fungování nástroje Ping
  - Popsat protokol ARP a jeho význam pro interakci mezi síťovou a linkovou vrstvou
  - Popsat protokol DHCP (jak probíhá přidělování adres)
- Transportní vrstva, adresace v TCP a UDP, spolehlivost, řízení toku
  - Vysvětlit základní vlastnosti a úkoly transportní vrstvy a nejdůležitější protokoly a koncepty (TCP, UDP, porty)
  - Vysvětlit způsoby alokace portů, uvést příklady dobře známých portů
  - Na příkladu identifikovat a vysvětlit nejdůležitější položky UDP packetu a jejich souvislost s IP protokolem
  - Na příkladu identifikovat a vysvětlit nejdůležitější položky TCP packetu, vysvětlit souvislost tohoto paketu s přenášeným proudem dat
  - Popsat algoritmy navazování a ukončení spojení v TCP (three-way handshake)
  - Popsat princip řízení toku (flow control) a předcházení zahlcení (congestion control) v TCP, uvést konkrétní příklad, jak může dojít k zahlcení a jak se s tím TCP vypořádá
  - Vysvětlit, jak ovlivňuje dynamický překlad adres (NAPT) obsah hlaviček TCP a UDP paketů
- Aplikační rozhraní a abstrakce pro síťovou komunikaci
  - Napsat pseudo-kód části síťové aplikace (klient nebo server) řešící zadaný problém s použitím socket API (např. statický web server)
  - Na příkladu vysvětlit jednotlivé části URI/URL a jejich význam
  - Popsat princip fungování systému DNS a DNS protokolu (základní typy a význam záznamů, zóny, DNS servery, vyřizování DNS dotazů, bezpečnostní rizika)
  - Popsat jednotlivé (síťové) kroky (např. překlad doménového jména na IP adresu, navázání spojení na konkrétních portech, odeslání a příjem zpráv s konkrétním obsahem, …), které musí dobře známá síťová aplikace (prohlížeč, mailový klient, …) provést, když vykonává svou činnost (zobrazuje stránku, odesílá mail, …)
- Zabezpečení komunikace, autentizace, šifrování
  - Popsat jednoduché metody detekce poškozených bloků (kontrola parity, kontrolní součty) s uvedením konkrétních příkladů na různých vrstvách
  - Popsat principy a typy firewallů (co řeší a jak se konfigurují)
  - Na konkrétním příkladu problému (a konfigurace sítě) doporučit vhodné zabezpečení (nastavení firewallů, demilitarizovaná zóna, aplikační brány)
  - Popsat základní principy symetrického a asymetrického šifrování, význam použití certifikátů, zabezpečení síťové komunikace SSL/TLS

== Překladače
- Lexikální analýza
  - Použít regulární výraz pro definici lexikálního elementu
  - Použít stavy lexikálního analyzátoru (např. flex) pro definici složitějších lexikálních elementů (např. řetězec s escape-sekvencemi)
- Syntaktická analýza
  - Transformovat opakování a alternativy (např. v syntaktických diagramech) na bezkontextovou gramatiku
  - Zapsat gramatikou typické konstrukce programovacích jazyků
  - Odstranit nejednoznačnosti v gramatice (např. if-then-else)
  - Odstranit LL(1) konflikty v gramatice (např. levá rekurze)
- Sémantická analýza
  - Definovat pomocí atributů propojení lexikální a syntaktické analýzy
  - Použít syntetizované atributy (např. bison) pro předání mezivýsledků (např. při vyhodnocování výrazu)
  - Použít atributovou gramatiku (včetně dědičných atributů) pro řešení složitějších konstrukcí
- Mezikód
  - Zkonstruovat control-flow graf pro danou proceduru (v C++ nebo v C\#/Java)
  - Přepsat úsek zdrojového kódu (v C++ nebo v C\#/Java) do zvoleného mezikódu

== Pokročilé programovací jazyky

Některé následující body definují varianty požadavků pro různé individuální volby povinně volitelných předmětů.
Vyžaduje se zvládnutí všech bodů bez označení Ⓥ a zvládnutí všech bodů s označením Ⓥ pro jeden z jazyků C\#, C++
nebo Java. Dále tato specializace vyžaduje zvládnutí společných požadavků z informatiky v sekci Programovací jazyky
ve stejné variantě.

- Pokročilé využití generických typů a metod
  - Ⓥ Vysvětlit fungování generických typů a metod s typovým omezením (constraints) v C\# nebo Javě
  - Ⓥ Umět vhodně implementovat generické typy a metody s typovým omezením v C\# nebo Javě
  - Ⓥ Umět implementovat šablony (templates) typů a funkcí, a vhodně využít konceptu duck-typingu v C++
  - Ⓥ Využít parciální specializaci na vhodných příkladech v C++
  - Ⓥ Aplikovat perfect-forwarding a variadické šablony v C++
- Funkcionální prvky
  - Lambda výrazy, closure, a variable capture
    - Ⓥ Vysvětlit fungování type inference pro parametry a návratovou hodnotu lambda výrazů v C\#, C++ nebo Javě
    - Ⓥ Vysvětlit princip fungování a rozdíly mezi capture-by-copy, capture-by-reference, a no-capture sé- mantikami v C++
    - Na příkladu umět zvolit vhodný způsob variable capture
    - Ⓥ Vysvětlit princip fungování, výhody a nevýhody capture-by-“move-to-closure” sémantiky v C\#
    - Umět ukázat nutnost ruční emulace capture-by-value
    - Ⓥ Vysvětlit princip fungování variable capture a potřebu final nebo “effectively final” zachycených proměnných v Javě
- Paralelní a asynchronní programování
  - Vysvětlit výhody a nevýhody thread a task-based concurrency
    - Vysvětlit princip thread poolu
    - Ⓥ Vhodně využít typů Task, Task\<T\> a ThreadPool místo vláken v C\#
    - Ⓥ Vhodně využít tasků pomocí std::async místo vláken v C++
    - Ⓥ Vhodně využít exekutory a fork/join pool místo vláken v Javě
  - Ⓥ Vysvětlit koncepty future a promise a jejich využití v asynchronním programování v C\#, C++ nebo Javě
    - Ⓥ Umět implementovat a využívat asynchronní metody vracející svůj budoucí výsledek ve formě future v C\#, C++ nebo Javě
    - Ⓥ Umět implementovat asynchronní kód, který si drží informaci o slíbeném výsledku ve formě promise, a umí tento promise naplnit v C\#, C++ nebo Javě
  - Vysvětlit koncept coroutine a možnosti jeho využití
    - Vysvětlit v kontextu coroutine princip a možnosti využití kooperativního multitaskingu a vysvětlit jeho výhody a nevýhody oproti preemptivnímu multitaskingu
    - Ⓥ Umět implementovat coroutine a použít v zadaném příkladu připravenou coroutine v C++ nebo Javě
    - Ⓥ Využít iterátorových metod pro implementaci coroutines a využít takové coroutines na příkladu v C\#
      ```cs
      public IEnumerator<T> GetEnumerator() {
          for (int i = 0; i < Count; i++) {
              yield return this[i];
          }
      }

      IEnumerator IEnumerable.GetEnumerator() {
          return GetEnumerator();
      }
      ```
    - Ⓥ Využít asynchronní metody s await pro implementaci coroutines a využít takové coroutines na příkladu v C\#
  - Synchronizační primitiva
    - Definovat sémantiku a vysvětlit princip použití podmínkové proměnné, resp. monitoru
    - Ⓥ Využít podmínkové proměnné, resp. monitory, v C\#, C++ nebo Javě pro řešení základních synchro- nizačních problémů (např. producent-konzument)
      - ```cs
        lock (_obj) {
          while (unsafe_to_do_crimes) {
            Monitor.Wait(_obj);
          }

          Crimes.Do();
        }
        ```
      - ```cs
        Monitor.Enter(_obj);
        while (unsafe_to_do_crimes) {
          Monitor.Wait(_obj);
        }
        
        Crimes.Do();
        Monitor.Exit();
        ```
    - Definovat sémantiku a vysvětlit princip použití semaforu
    - Ⓥ Využít semaforů v C\#, C++ nebo Javě pro řešení základních synchronizačních problémů (např. producent-konzument)
- Významné prvky standardních knihoven a jejich aplikace
  - Základní síťování pomocí socketů
    - Ⓥ Umět implementovat klientskou aplikaci pomocí TCP socketů v C\#, C++ nebo Javě
      - ```c
        int main () {
          int server_socket = socket (AF_INET, SOCK_STREAM, 0); // always AF_INET, SOCK_DGRAM for UDP
          struct sockaddr_in server_address;
          server_address.sin_family = AF_INET;
          server_address.sin_addr.s_addr = htonl (INADDR_ANY); // 0.0.0.0
          server_address.sin_port = htons (HTTP_PORT);
          bind (server_socket, (struct sockaddr *) &server_address, sizeof (server_address));
          listen (server_socket, 0);
          while (true) {
            struct sockaddr_in client_address;
            socklen_t client_address_size = sizeof (client_address);
            int client_socket = accept (server_socket, (struct sockaddr *) &client_address, &client_address_size)
            char *page = "<HTML><BODY>Hello␣!</BODY></HTML>";
            write (client_socket, page, strlen (page));
            shutdown (client_socket, SHUT_RDWR);
            close (client_socket);
          }
        }
        ```
    - ```c
      s = socket();
      bind(s, addr, sizeof(addr));
      listen(s, 0);
      while (true) {
        accept(s, &client_addr, &caddr_size);
        /* do stuff */
        /* shutdown(s, SHUT_RDWR); */
        close(s);
      }
      ```
    - Ⓥ Umět implementovat serverovou aplikaci pomocí TCP socketů v C\#, C++ nebo Javě
    - Ⓥ Využít na jednoduchém příkladu UDP sockety pro komunikaci mezi aplikacemi v C\#, C++ nebo Javě
  - Ⓥ Využít koncept asynchronního programování v tvorbě síťových aplikací v C\#, C++ nebo Javě

== Návrh a tvorba software

=== Doporučené postupy
- Principy objektového návrhu
  - Abstrakce, zapouzdření, SOLID principy a jejich aplikace, dekompozice
    - *S* -- single responsibility
    - *O* -- open-closed -- dá se rozšiřovat bez modifikace (implement changes by adding code)
    - *L* -- Liskov substitution -- pokud umím pracovat se zvířátky, měl bych umět pracovat i s kočkou, i když nevím, co to je kočka
      - expect no more, provide no less
    - *I* -- interface segregation -- interfacy by měly být specifické
    - *D* -- dependency inversion -- závislosti by měly procházet přes abstrakce, high-level nezávisí na lowlevelu, lowlevel si definuje abstrakci, oba závisí na abstrakci (interface-implementace)
  - Předpokládá se schopnost identifikovat porušení principů v návrhu a navrhnout změny vedoucí k nápravě
- Návrh API, tříd a metod
  - Rozhraní aplikací (API) a poskytovatelů služeb (SPI), evoluce rozhraní
  - Návrh tříd, dědičnost a kompozice, immutability
  - Návrh metod, zohlednění účelu/zodpovědnosti, funkční dekompozice
  - Testovatelnost tříd a metod, návrh pro testovatelnost
- Návrhové vzory
  - *Strategy*, *Observer*, *Decorator*, *Factory*, *Adapter*, *Facade*
  - Identifikace principů objektového návrhu v návrhových vzorech
  - Struktura, záměr (intent) a aplikace základních návrhových vzorů

=== Programování v paralelním prostředí

- Paralelní programování, paměťový model.
- Atomické operace a neblokující datové struktury.

=== Nástroje pro vývoj software

- Správa verzí
  - Popsat účel a použití systémů pro správu verzí při vývoji rozsáhlého software a práci v týmech (typicky nabízené funkce těchto systémů a jejich použítí pro řešení běžných situací)
  - Popsat běžné způsoby integrace verzovacích systémů s nástroji pro správu projektů
  - Vysvětlit hlavní koncepty (lokální a vzdálené repozitáře, pracovní kopie (working copy), commit, větve)
  - Popsat a použít operace clone, pull, push, add, diff, commit, branch, merge, log, blame nástroje git
  - Popsat koncept feature branch v kontextu procesu vývoje a udržování software
  - Vysvětlit konflikty mezi verzemi, důvody vzniku a způsoby řešení
- Systémy pro sestavování software
  - Popsat hlavní účel a typicky nabízené funkce
  - Vysvětlit hlavní koncepty (cíl, závislosti, akce)
- Nástroje pro testování software
  - Popsat hlavní koncepty (test, pokrytí, jednotkové testování, integrační testování, systémové testování, black box, white box)
  - Popsat a na ukázkách kódu identifikovat typickou strukturu testu (set up, tear down, execute and validate)
  - Vysvětlit omezení běžných testovacích postupů a základní možnosti řešení
  - Popsat způsoby automatizace testování