# Společná matematika

## 1. Základy diferenciálního a integrálního počtu

- Posloupnosti reálných čísel a jejich limity (definice)
	- posloupnost s hodnotami v množině $M$ je zobrazení z $\mathbb N$ do $M$
	- nechť $(a_n)$ je reálná posloupnost a $L \in \mathbb R^*$
	- pokud $(\forall\varepsilon\gt 0)(\exists n_0\in\mathbb N):(n\geq n_0\implies |a_n-L|\lt\varepsilon)$, píšeme, že $\lim a_n=L$ nebo $\lim_{n\to\infty}a_n=L$ nebo $a_n\to L$, a řekneme, že posloupnost $(a_n)$ má limitu $L$
	- pro $L\in \mathbb R$ mluvíme o vlastní limitě a pro $L=\pm\infty$ o limitě nevlastní
	- posloupnost, která má vlastní limitu, konverguje (pokud ji nemá, tak diverguje)
	- každá posloupnost reálných čísel má nejvýše jednu limitu
- Aritmetika limit
	- nechť $(a_n),(b_n)$ jsou posloupnosti reálných čísel takové, že $\lim a_n=a$ a $\lim b_n=b$
	- pak…
		- $\lim\,(a_n+b_n)=a+b$
		- $\lim\,(a_nb_n)=ab$
		- pokud $b_n\neq 0$ pro každé $n\gt 0$, pak $\lim\,(a_n/b_n)=a/b$
	- to vše platí za předpokladu, že je výraz na pravé straně definován
		- neurčité výrazy (nejsou definované): součet nekonečen s různými znaménky, součin nekonečna s nulou, podíl nekonečen, dělení reálného čísla nulou
	- pokud je $(a_n)$ omezená a $(b_n)$ konverguje k nule, pak $\lim\,(a_nb_n)=0$
		- tzn. limita $(a_n)$ nemusí existovat
- Limity a uspořádání
	- nechť $(a_n),(b_n)$ jsou posloupnosti reálných čísel takové, že mají limity $\lim a_n=a$ a $\lim b_n=b$
	- když $a\lt b$, tak existuje $n_0$, že $n\gt n_0\implies a_n\lt b_n$
	- a naopak, když $a_n\leq b_n$ pro každé $n\gt n_0$, pak $a\leq b$
	- poznámka: může se stát, že $\forall n:a_n\lt b_n$, ale $\lim a_n=\lim b_n$
		- např. uvažujme $a_n=1-\frac1n\lt b_n=1$, přičemž $\lim a_n=\lim b_n=1$
- Věta o dvou policajtech
	- nechť posloupnosti $(a_n),(b_n),(c_n)\subseteq\mathbb R$ splňují
		- $\lim a_n=\lim b_n=a\in\mathbb R$
		- $\forall n\gt n_0:a_n\leq c_n\leq b_n$
	- pak $(c_n)$ konverguje a $\lim c_n=a$
	- platí to i pro nevlastní limity – tam nám stačí jeden policajt
- Součet řady a částečný součet řady
	- nekonečná řada (reálných čísel) je výraz $$\sum_{n=1}^\infty a_n=a_1+a_2+a_3+\dots$$
		- kde $(a_n)_{n\geq 1}$ je posloupnost reálných čísel
	- ($n$-tý) částečný součet řady se značí $s_n$ a je to součet jejích prvních $n$ členů ($s_n=a_1+a_2+\dots+a_n$)
	- pokud existuje vlastní limita posloupnosti $(s_n)$ částečných součtů dané řady, mluvíme o *konvergentní* řadě a limita $\lim s_n$ je jejím *součtem*
	- pokud $\lim s_n$ neexistuje nebo je nevlastní, je daná řada *divergentní*
- Geometrická řada, harmonická řada
	- geometrická řada
		- $\sum_{n=0}^\infty q^n=1+q+q^2+q^3+\dots$
		- $q\in\mathbb R$ je parametr zvaný *kvocient*
		- pro součet geometrické řady platí $$\sum_{n=0}^\infty q^n=\begin{cases}\frac1{1-q} &-1\lt q\lt1\\ +\infty &q\geq 1\\\text{neexistuje}&q\leq -1\end{cases}$$
		- vyplývá to ze vzorce pro částečný součet $s_n=\frac{q^n-1}{q-1}$
	- harmonická řada
		- $\sum_{n=1}^\infty\frac 1n=1+\frac12+\frac13+\dots$
		- diverguje, přestože její prvky konvergují k nule
	- pro řady tvaru $\sum_{n=1}^\infty\frac1{n^s}$ obecně platí, že konvergují pro $s\gt 1$ a divergují pro $s\leq 1$
- Limita funkce v bodě: definice, aritmetika limit
	- okolí bodu je interval $U(a,\delta)=(a-\delta,a+\delta)$
		- okolí nekonečen definujeme jako $U(+\infty,\delta)=(1/\delta,+\infty)$, podobně pro $-\infty$
		- definujeme také pravé okolí bodu $U^+(a,\delta)=[a,a+\delta)$, podobně levé okolí $U^-$
		- prstencová okolí bodu $a\in\mathbb R$ definujeme jako obyčejná okolí s vyjmutým bodem $a$, značí se jako $P(a,\delta)$ apod.
	- řekneme, že funkce $f$ má v bodě $a\in\mathbb R^*$ limitu $A\in\mathbb R$, když $(\forall\varepsilon\gt 0)(\exists\delta\gt 0):x\in P(a,\delta)\implies f(x)\in U(A,\varepsilon)$
		- zapisujeme $\lim_{x\to a}f(x)=A$
		- poznámka: limita funkce $f$ v bodě $a$ nezávisí na její hodnota v $a$, funkce $f$ dokonce ani nemusí být v $a$ definovaná
		- pokud místo prstencového okolí $P$ použijeme pravé prstencové okolí $P^+$, dostaneme definici limity zprava, značí se $\lim_{x\to a^+}f(x)$
			- obdobně lze definovat limitu zleva
			- pokud $\lim_{x\to a^+}f(x)=\lim_{x\to a^-}f(x)=A$, pak $\lim_{x\to a}f(x)=A$
			- naopak pokud jsou limity zprava a zleva různé, limita neexistuje
		- podobně jako u posloupnosti – pokud limita funkce existuje, je jednoznačně určena
		- limitu funkce lze rovněž definovat pomocí posloupnosti
	- aritmetika limit
		- nechť $a,A,B\in\mathbb R^*$, nechť $f,g$ jsou funkce definované na nějakém prstencovém okolí $P(a,\delta)$ bodu $a$, nechť platí $\lim_{x\to a}f(x)=A$ a $\lim_{x\to a}g(x)=B$
		- pak platí $\lim_{x\to a}f(x)+g(x)=A+B$, je-li tento součet definován
		- $\lim_{x\to a}f(x)g(x)=AB$, je-li tento součin definován
		- pokud je $g(x)$ nenulová na nějakém prstencovém okolí bodu $a$, pak $\lim_{x\to a}f(x)/g(x)=A/B$, je-li tento podíl definován
- Limita funkce v bodě: vztah s uspořádáním
	- nechť $c\in\mathbb R^*$ a funkce $f,g,h$ jsou definované na prstencovém okolí bodu $c$
	- mají-li $f,g$ v bodě $c$ limitu a $\lim_{x\to c}f(x)\gt\lim_{x\to c}g(x)$, pak existuje $\delta\gt 0$ takové, že $f(x)\gt g(x)$ pro každé $x\in P(c,\delta)$
	- existuje-li $\delta\gt 0$ takové, že $f(x)\geq g(x)$ pro každé $x\in P(c,\delta)$, a mají-li funkce $f,g$ limitu v bodě $c$, potom $\lim_{x\to c}f(x)\geq g(x)$
	- existuje-li $\delta\gt 0$ takové, že $f(x)\leq h(x)\leq g(x)$ pro každé $x\in P(c,\delta)$ a $\lim_{x\to c}f(x)=\lim_{x\to c}g(x)=A\in\mathbb R^*$ potom i $\lim_{x\to c}h(x)=A$
		- v podstatě dva policajti
- Limita funkce v bodě: limita složené funkce
	- nechť $A,B,C\in\mathbb R^*$, nechť $g(x)$ je funkce splňující $\lim_{x\to A}g(x)=B$ a nechť $f(x)$ je funkce splňující $\lim_{x\to B}f(x)=C$
	- navíc nechť je splněna aspoň jedna z následujících podmínek
		- $f(x)$ je spojitá v $B$
		- na nějakém prstencovém okolí bodu $A$ funkce $g(x)$ nenabývá hodnotu $B$
	- potom $\lim_{x\to A}f(g(x))=C$
- Spojitost a spojitost na intervalu
	- řekneme, že funkce $f$ je v bodě $a\in\mathbb R$ spojitá, pokud $\lim_{x\to a}f(x)=f(a)$
		- spojitost zprava/zleva definujeme pomocí jednostranných limit
	- funkce je spojitá na intervalu, pokud je spojitá v každém vnitřním bodu a pokud je (odpovídajícím způsobem) jednostranně spojitá v každém krajním bodu
	- funkce může být v daném bodě buď spojitá, nebo nespojitá, nebo nedefinovaná
- Funkce spojité na intervalu: nabývání mezihodnot
	- nechť $a\lt b$ jsou reálná čísla
	- nechť $f:[a,b]\to\mathbb R$ je na intervalu $[a,b]$ spojitá
	- označme $m=\min\set{f(a),f(b)}$ a $M=\max\set{f(a),f(b)}$
	- pak každé reálné číslo z intervalu $[m,M]$ je hodnotou funkce $f$ (pro každé $y\in[m,M]$ existuje $x\in[a,b]$ takové, že $f(x)=y$)
- Funkce spojité na intervalu: nabývání maxima
	- nechť $a\leq b$ jsou reálná čísla
	- nechť $f:[a,b]\to\mathbb R$ je spojitá funkce
	- potom $f$ nabývá na intervalu $[a,b]$ svého maxima (i minima)
- Derivace – definice a základní pravidla pro výpočet
	- nechť $f:M\to\mathbb R$, $b\in M$ a $U(b,\delta)\subseteq M$ pro nějaké $\delta\gt 0$
	- derivace funkce $f$ v bodě $b$ je limita $$f'(b):=\lim_{h\to 0}\frac{f(b+h)-f(b)}{h}=\lim_{x\to b}\frac{f(x)-f(b)}{x-b}$$
	- také můžeme mít derivaci zprava/zleva, pak je limita jednostranná
	- derivace buď existuje vlastní, nebo existuje nevlastní, nebo neexistuje
	- pokud má $f$ v $b$ vlastní derivaci, říkáme, že $f$ je v $b$ diferencovatelná
	- pro pravidla derivací viz libovolnou vhodnou tabulku, některá složitější jsou [v přípravě na zápočtový test](../semestr2/matematicka-analyza1/zapoctovy-test.md)
- L'Hospitalovo pravidlo
	- nechť $a\in\mathbb R^*$, nechť funkce $f,g:P(a,\delta)\to\mathbb R$ mají na $P(a,\delta)$ vlastní derivaci a nechť $g'(x)\neq 0$ na $P(a,\delta)$
	- pokud $\lim_{x\to a}f(x)=\lim_{x\to a}g(x)=0$ a $\lim_{x\to a}f'(x)/g'(x)=A\in\mathbb R^*$, pak i $\lim_{x\to a}f(x)/g(x)=A$
	- pokud $\lim_{x\to a} |g(x)|=+\infty$ a $\lim_{x\to a}f'(x)/g'(x)=A\in\mathbb R^*$, pak i $\lim_{x\to a}f(x)/g(x)=A$
- Vyšetření průběhu funkcí: extrémy, monotonie a konvexita/konkavita
	- extrémy
		- pokud má funkce $f$ v bodě $a$ nenulovou derivaci $f'(a)\neq 0$, pak $f$ v $a$ nenabývá lokální extrém
		- tedy pokud má $f$ lokální extrém bodě $a$, tak buď $f'(a)=0$, nebo $f'(a)$ neexistuje
		- pozor, funkce může mít globální extrém v krajním bodě uzavřeného intervalu
	- monotonie
		- uvažujeme interval s kladnou délkou a spojitou funkci $f$ s derivací v každém vnitřním bodě intervalu
		- pokud na vnitřku intervalu platí $f'\gt 0$, je $f$ na daném intervalu rostoucí
		- pokud $f'\geq 0$, pak je neklesající
		- pokud $f'\lt 0$, pak je klesající
		- pokud $f'\leq 0$, pak je nerostoucí
		- pokud $f'=0$, pak je konstantní
	- konvexita/konkavita
		- zjednodušená definice: funkce $f$ je na intervalu $(a,b)$ konvexní, pokud graf funkce na intervalu $(a,b)$ leží pod úsečkou spojující body $(a,f(a))$ a $(b,f(b))$
			- respektive pokud leží pod nebo na úsečce, tak je konvexní, pokud leží ostře pod úsečkou, tak je ryze konvexní
			- podobně konkávnost
		- pokud je druhá derivace funkce kladná, je ryze konvexní (pokud je nezáporná, je konvexní)
		- pokud je druhá derivace funkce záporná, je ryze konkávní (pokud je nekladná, je konkávní)
- Taylorův polynom (limitní forma)
	- Taylorův polynom řádu $n$ funkce $f$ v bodě $a$: $$T_n^{f,a}(x)=\sum_{i=0}^n\frac{f^{(i)}(a)}{i!}(x-a)^i$$
		- poznámka: nultý člen součtu bude vždy $f(a)$
	- má-li funkce $f$ v bodě $a\in\mathbb R$ derivace všech řádů, rozumíme pro $x\in\mathbb R$ její taylorovou řadou se středem v $a$ řadu $$T^{f,a}(x)=\sum_{n=0}^\infty \frac{f^{(n)}(a)}{n!}(x-a)^n$$
		- součet Taylorovy řady je $f(x)$
- Primitivní funkce: definice a metody výpočtu (substituce, per-partes)
	- nechť $-\infty\leq a\lt b\leq +\infty$ a $f:(a,b)\to\mathbb R$ je daná funkce
	- pokud má funkce $F:(a,b)\to\mathbb R$ na $(a,b)$ derivaci a ta se rovná $f(x)$, řekneme, že $F$ je na intervalu $(a,b)$ primitivní funkcí k funkci $f$
	- primitivní funkce je jednoznačná až na konstantu
	- Newtonův integrál funkce $f$ na intervalu $(a,b)$ definujeme jako $$(N)\int_a^bf(x)\,dx:=[F]_a^b=F(b^-)-F(a^+)=\lim_{x\to b^-}F(x)-\lim_{x\to a^+}F(x)$$
		- poznámka: konstanta $c$ se odečte
	- substituci a per-partes je nutné nastudovat (i pro určitý integrál)
	- vzorec pro per-partes: $\int u'v=uv-\int uv'$
- Riemannův integrál: definice, souvislost s primitivní funkcí (Newtonovým integrálem)
	- uvažujeme dělení $D=(a_0,a_1,\dots,a_k)$ intervalu $[a,b]$
		- tzn. $a=a_0\lt a_1\lt a_2\lt \dots\lt a_k=b$
	- definujeme dolní Riemannovu sumu $s(f,D)=\sum_{i=0}^{k-1} |I_i|m_i$
		- $I_i=[a_i,a_{i+1}]$
		- $m_i$ je supremum funkce $f$ v intervalu $I_i$
	- také definujeme horní Riemannovu sumu $S(f,D)=\sum_{i=0}^{k-1}|I_i|M_i$
		- $M_i$ … infimum
	- dolní Riemannův integrál na intervalu $[a,b]$ definujeme jako supremum z $s(f,D)$ pro všechna dělení $D$ intervalu $[a,b]$
		- značí se $\underline{\int_a^b f}$
	- horní Riemannův integrál je infimum z $S(f,D)$
		- $\overline{\int_a^bf}$
	- funkce má Riemannův integrál, pokud se horní a dolní R. integrály rovnají (pak tuhle společnou hodnotu nazveme Riemannovým integrálem)
		- $\int_a^b f$
	- 2. základní věta analýzy: pokud Riemannův a Newtonův integrál existují, pak jsou si rovny
- Aplikace integrálů: odhady součtu řad (konečných i nekonečných)
	- pro přirozené $n$ a neklesající funkci $f$ na intervalu $[1,n]$ platí $$\sum_{k=1}^{n-1}f(k)\leq\int_1^n f\leq\sum_{k=2}^n f(k)$$
	- integrální kritérium konvergence
		- uvažujme nerostoucí nezápornou funkci $f$
		- řada $\sum_{k=1}^\infty f(k)$ konverguje $\iff\lim_{b\to+\infty}\int_1^b f\lt +\infty$
	- přesný postup pro odhad součtu řady je potřeba nacvičit
- Aplikace integrálů: obsahy rovinných útvarů
	- plocha rovinného útvaru $U(a,b,f)$ pod grafem funkce $f$ … $\int_a^b f$
- Aplikace integrálů: objemy a povrchy rotačních útvarů v prostoru
	- $V$ … rotační těleso vzniklé rotací rovinného útvaru $U(a,b,f)$ pod grafem funkce $f$ kolem osy $x$
	- $\mathrm{objem}(V)=\pi\int_a^b f(t)^2\,dt$
	- $\mathrm{povrch}(V)=2\pi\int_a^b f(t)\sqrt{1+(f'(t))^2}\,dt$
- Aplikace integrálů: délka křivky
	- uvažujeme křivku z bodu $a$ do bodu $b$ popsanou funkcí $f$
	- $\int_a^b\sqrt{1+(f'(t))^2}\,dt$

## 2. Algebra a lineární algebra

- Grupy a podgrupy, permutace
	- binární operace na množině $X$ je zobrazení $X \times X \to X$
	- neutrální prvek: $(\exists e \in G)(\forall a \in G): a\circ e = e\circ a = a$
	- inverzní prvek: $(\forall a \in G)(\exists b \in G): a\circ b = b\circ a = e$
	- grupa $(G,\circ)$ je množina $G$ spolu s binární operací $\circ$ na $G$ splňující asociativitu operace $\circ$, existenci neutrálního prvku a existenci inverzních prvků
	- pokud je navíc operace $\circ$ komutativní, pak se jedná o abelovskou grupu
	- grupa $(H,\bullet)$ je podgrupou grupy $(G,\circ)$, pokud $H\subseteq G$ a $\forall a,b\in H:a\bullet b=a\circ b$
		- píšeme $(H,\bullet)\leq (G,\circ)$
	- permutace na množině $\lbrace1,2,\dots,n\rbrace$ je bijektivní zobrazení $p:\lbrace1,2,\dots,n\rbrace\rightarrow \lbrace1,2,\dots,n\rbrace$
		- skládání permutací … $(q\circ p)(i)=q(p(i))$
		- permutační matice
			- $(P)_{i,j} = \begin{cases} 1 &\text{pokud } p(i)=j \\ 0 &\text{jinak}\end{cases}$
		- cyklus … např. $(1,2,3,4)$
			- odpovídá zobrazení, které mapuje 1→2, 2→3, 3→4, 4→1
		- transpozice … permutace, která má pouze jeden netriviální cyklus o délce 2, tedy např. $(1,3)$
		- jakoukoliv permutaci lze rozložit na transpozice
			- cyklus $(1,2,3,4)$ lze rozložit na $(1,4)\circ(1,3)\circ(1,2)$ nebo na $(1,2)\circ(2,3)\circ(3,4)$
		- znaménko permutace $p$ je $\text{sgn}(p)=(-1)^{\text{počet inverzí v}\ p}$
			- inverze v $p$ je dvojice prvků $(i,j):i \lt j \land p(i) \gt p(j)$
			- nebo také $\text{sgn}(p)=(-1)^{\text{počet transpozic v}\ p}$
- Tělesa a speciálně konečná tělesa
	- těleso je množina $\mathbb K$ spolu se dvěma komutativními binárními operacemi $+$ a $\cdot$, kde $(\mathbb K, +)$ a $(\mathbb K \setminus \lbrace0\rbrace, \cdot)$ jsou abelovské grupy a navíc platí distributivita $\forall a,b,c \in \mathbb K : a\cdot (b+c)=(a\cdot b)+(a\cdot c)$
	- charakteristika tělesa
		- v tělese $\mathbb K$, pokud $\exists n \in \mathbb N: \underbrace{1+1+\dots+1}_{n}=0$, pak nejmenší takové $n$ je charakteristika tělesa $\mathbb K$
		- jinak má těleso $\mathbb K$ charakteristiku 0
		- značí se $\text{char}(\mathbb K)$
		- lze dokázat, že u konečných těles musí být prvočíselná
	- $\mathbb Z_p$ je těleso, právě když je $p$ prvočíslo
	- ale existují i konečná tělesa s neprvočíselným řádem (počtem prvků) – např. Galois field $GF(4)$
		- řád musí být kladná celá mocnina prvočísla
- Soustavy lineárních rovnic – maticový zápis, elementární řádkové úpravy, odstupňovaný tvar matice
	- maticový zápis soustavy rovnic
		- soustava $m$ lineárních rovnic o $n$ neznámých … $Ax = b$
		- rozšířená matice soustavy … $(A|b) \in \mathbb{R}^{m×(n+1)}$
		- matice soustavy … $A \in \mathbb{R}^{m×n}$
		- vektor pravých stran … $b \in \mathbb{R}^m$
		- vektor neznámých … $x = (x_1,\dots,x_n)^T$
		- vektor $x \in \mathbb{R}^n$ je řešení soustavy $Ax = b$, pokud splňuje všechny její rovnice
		- soustavy $Ax = 0$ se nazývají homogenní a vždy umožňují $x = 0$
	- elementární řádkové operace
		- definujeme základní dvě elementární řádkové úpravy
			- vynásobení $i$-tého řádku nenulovým $t \in \mathbb R \setminus \lbrace0\rbrace$
			- přičtení $j$-tého řádku k $i$-tému řádku
		- z těch lze odvodit další dvě úpravy
			- přičtení $t$-násobku $j$-tého řádku k $i$-tému řádku ($t$ může být i nulové)
			- záměna dvou řádků
		- provedení jedné elementární úpravy značíme $A\sim A'$
		- provedení posloupnosti úprav značíme $A\sim\sim A'$
		- elementárními úpravami soustavy $(A|b)$ se nemění množina řešení
	- odstupňovaný tvar matice
		- matice je v řádkově odstupňovaném tvaru (REF = row echelon form), pokud jsou nenulové řádky (ostře) seřazeny podle počtu počátečních nul a nulové řádky jsou pod nenulovými
			- k formální definici bychom zavedli notaci $j(i)$ pro pozici prvního nenulového prvku v $i$-tém řádku
		- první nenulový prvek nenulového řádku se nazývá pivot, pod pivotem jsou v REF všechny prvky nulové
		- pro soustavu $A'x = b'$ s $A'$ v REF jsou proměnné odpovídající sloupcům s pivoty bázické, ostatní jsou volné
	- redukovaný odstupňovaný tvar (RREF)
		- pivoty jsou jednotkové
		- nad i pod pivoty jsou nuly
- Gaussova a Gaussova-Jordanova eliminace, popis množiny řešení
	- Gaussova eliminace = převod do odstupňovaného tvaru pomocí elementárních úprav, to se dá popsat algoritmicky:
		- seřadíme řádky podle počtu počátečních nul
		- najdeme první dva řádky, co mají stejně počátečních nul
		- od toho druhého (a všech dalších, co mají stejně nul) odečteme vhodný násobek toho prvního, abychom mu první nenulu vynulovali
		- tohle opakujeme, dokud se nedostaneme do REF
	- Gaussova-Jordanova eliminace = převod do RREF
		- z pivotů se jedničky dělají snadno – stačí řádek vydělit pivotem
		- nad pivoty se jedničky také dostávají snadno – stačí od řádku odečíst vhodný násobek řádku s pivotem v daném sloupci (dává smysl postupovat odspodu)
	- množina řešení
		- pokud je pivot v posledním sloupci rozšířené matice soustavy, soustava rovnic nemá řešení
		- existuje bijekce $\bar x \mapsto \bar x + x^0$ mezi množinami $\lbrace \bar x: A\bar x=0\rbrace$ a $\lbrace x: Ax=b\rbrace$
			- pokud $x^0$ splňuje $Ax^0=b$
		- množinu řešení soustavy $Ax=b$ popíšeme jako $x=y+p_1\overline x_1+p_2\overline x_2+\dots+p_{n-r}\overline x_{n-r}$
		- $y$ … libovolné řešení soustavy $Ax=b$
			- u homogenní soustavy to typicky bude nulový vektor
			- je to člen, který odpovídá tomu $x^0$ výše
		- $p_i\overline x_i$
			- takový člen tam bude za každou volnou proměnnou (bude jich $n-r$, tedy počet řádků – hodnost matice)
			- $p_i$ je libovolný reálný parametr
			- tyhle členy můžeme získat tak, že řešíme soustavu $A\overline x=0$ a řešení vyjádříme pomocí parametrů (a pak je vytkneme)
			- nebo je lze vyčíst z RREF matice
			- ve vektoru $\overline x_i$ bude typicky jednička na místě odpovídající volné proměnné a nuly u všech ostatních volných proměnných (protože je to vlastně složka, která se stará o konkrétní volnou proměnnou)
- Operace s maticemi a základní typy matic, hodnost matice
	- hodnost matice
		- hodnost matice A, značená jako rank(A), je počet pivotů v libovolné A' v REF takové, že $A\sim\sim A'$
	- jednotková matice
		- pro $n \in \mathbb{N}$ je jednotková matice $I_n \in \mathbb{R}^{n×n}$ definovaná tak, že $(I_n)_{i,j} = 1 \iff i=j$, ostatní prvky jsou nulové 
	- transponovaná matice
		- transponovaná matice k matici $A \in \mathbb{R}^{m×n}$ je matice $A^T \in \mathbb R^{n×m}$ splňující $(A^T)_{i,j}=a_{j,i}$
	- symetrická matice
		- čtvercová matice A je symetrická, pokud $A^T =A$, tedy $a_{i,j}=a_{j,i}$
	- maticový součin
		- pro $A \in \mathbb R^{m\times n},B\in \mathbb R^{n\times p}$ je součin $(AB) \in \mathbb R^{m×p}$ definován $(AB)_{i,j}=\sum^{n}_{k=1}a_{i,k}b_{k,j}$
- Regulární a inverzní matice
	- inverzní matice
		- pokud pro čtvercovou matici $A \in \mathbb R^{n\times n}$ existuje $B \in \mathbb R^{n\times n}$ taková, že $AB=I_n$, pak se $B$ nazývá inverzní matice a značí se $A^{-1}$
		- výpočet: $(A|I_n)\sim\sim (I_n|A^{-1})$
	- regulární/singulární matice
		- pokud má matice $A$ inverzi, pak se nazývá regulární, jinak je singulární
	- věta: pro čtvercovou matici $A \in \mathbb R^{n\times n}$ jsou následující podmínky ekvivalentní
		1. matice A je regulární, tedy k ní existuje inverzní matice … $\exists B: AB=I_n$
		2. $\text{rank}(A) = n$
		3. $A\sim\sim I_n$
		4. systém $Ax = 0$ má pouze triviální řešení $x = 0$
	- inverzní matici k matici $A$ lze najít pomocí Gaussovy-Jordanovy eliminace $(A|I_n)\sim\sim(I_n|A^{-1})$
		- pokud tento proces selže, tak je $A$ singulární
- Vektorový prostor, lineární kombinace, lineární závislost a nezávislost, lineární obal, systém generátorů
	- vektorový prostor
		- vektorový prostor $(V,+,\cdot)$ nad tělesem $(\mathbb K, +,\cdot)$ je množina spolu s binární operací $+$ na $V$ a binární operací skalárního násobku $\cdot: \mathbb K \times V \rightarrow V$
		- $(V,+)$ je abelovská grupa
		- $\forall \alpha,\beta \in \mathbb K, \forall u,v \in V$
			- asociativita … $(\alpha \cdot \beta) \cdot u = \alpha \cdot (\beta \cdot u)$
			- neutrální prvek (skalár) vůči násobení skalárem … $1 \cdot u = u$
			- distributivita … $(\alpha + \beta) \cdot u = (\alpha \cdot u) + (\beta \cdot u)$
			- distributivita … $\alpha \cdot (u+v)=(\alpha \cdot u)+(\alpha \cdot v)$
		- prvky $\mathbb K$ se nazývají skaláry, prvky $V$ vektory
		- rozlišujeme nulový skalár $0$ a nulový vektor $o$
	- podprostor vektorového prostoru
		- nechť $V$ je vektorový prostor na $\mathbb K$, potom podprostor $U$ je neprázdná podmnožina $V$ splňující uzavřenost na součet vektorů a uzavřenost na násobení skalárem (z $\mathbb K$) – z toho nutně vyplývá $o \in U$
	- lineární kombinace
		- lineární kombinace vektorů $v_1,\dots,v_k \in V$ nad $\mathbb K$ je libovolný vektor $u = \alpha_1v_1+\dots+\alpha_kv_k$, kde $\alpha_1,\dots,\alpha_k \in \mathbb K$
	- lineárně nezávislé vektory
		- množina vektorů $X$ je lineárně nezávislá, pokud nulový vektor nelze získat netriviální lineární kombinací vektorů z $X$; v ostatních případech je množina $X$ lineárně závislá
		- vektory $v_1,\dots,v_n$ jsou lineárně nezávislé $\equiv$ $\sum_{i=1}^n \alpha_iv_i=o \iff \alpha_1=\dots=\alpha_n=0$
	- lineární obal (podprostor generovaný množinou)
		- lineární obal $\mathcal L(X)$ podmnožiny $X$ vektorového prostoru $V$ je průnik všech podprostorů $U$ z $V$, které obsahují $X$
		- alternativní značení: $\mathrm{span}(X)$
		- pro $X \subseteq V$ platí $\text{span}(X)=\bigcap U:U\Subset V, X\subseteq U$
		- jde o podprostor generovaný $X$, vektory v množině $X$ se označují jako generátory podprostoru
	- věta: průnik podprostorů je taky podprostor
	- věta: $\mathcal L(X)$ je množina všech lineárních kombinací vektorů z $X$
- Steinitzova věta o výměně, báze, dimenze, souřadnice
	- lemma o výměně
		- buď $y_1,\dots,y_n$ systém generátorů vektorového prostoru $V$
		- nechť vektor $x \in V$ má vyjádření $x = \sum_{i=1}^n\alpha_iy_i$
		- pak pro libovolné $k$ takové, že $\alpha_k \neq 0$, je $y_1,\dots,y_{k-1},x,y_{k+1},\dots,y_n$ systém generátorů prostoru $V$
	- Steinitzova věta o výměně
		- buď $V$ vektorový prostor
		- buď $x_1,\dots,x_m$ lineárně nezávislý systém ve $V$
		- nechť $y_1,\dots,y_n$ je systém generátorů $V$
		- pak platí $m\leq n$ a existují navzájem různé indexy $k_1,\dots,k_{n-m}$ takové, že $x_1,\dots,x_m,y_{k_1},\dots,y_{k_{n-m}}$ tvoří systém generátorů $V$
	- báze vektorového prostoru
		- báze vektorového prostoru $V$ je lineárně nezávislá množina $X$, která generuje $V$ (tedy $\text{span}(X)=V$)
	- dimenze vektorového prostoru
		- dimenze konečně generovaného vektorového prostoru $V$ je mohutnost (kardinalita / počet prvků) kterékoli z jeho bází; značí se $\mathrm{dim}(V)$
	- vektor souřadnic
		- nechť $X=(v_1,\dots,v_n)$ je uspořádaná báze vektorového prostoru $V$ nad $\mathbb K$, potom vektor souřadnic $u \in V$ vzhledem k bázi $X$ je $[u]_x=(\alpha_1,\dots,\alpha_n)^T \in \mathbb K^n$, kde $u=\sum_{i=1}^n\alpha_iv_i$
- Vektorové podprostory, zejména maticové (řádkový, sloupcový, jádro) a jejich dimenze
	- řádkový a sloupcový prostor matice $A \in \mathbb K^{m\times n}$
		- sloupcový prostor $\mathcal S(A) \subseteq \mathbb K^m$ je lineární obal sloupců $A$
		- řádkový prostor $\mathcal R(A) \subseteq \mathbb K^n$ je lineární obal řádků $A$
		- $\mathcal S(A)=\lbrace u \in \mathbb K^m:u=Ax,\,x\in \mathbb K^n \rbrace$
		- $\mathcal R(A)=\lbrace v \in \mathbb K^n:v=A^Ty,\,y\in \mathbb K^m \rbrace$
	- jádro matice $A \in \mathbb K^{m\times n}$
		- $\text{ker}(A) = \lbrace x \in \mathbb K^n: Ax=0\rbrace$
	- věta: $\forall A \in \mathbb K^{m\times n}:\text{dim}(\text{ker}(A))+\text{rank}(A)=n$
	- pozorování: dimenze řádkového a sloupcového prostoru se shodují (a rovnají se hodnosti)
- Lineární zobrazení – definice, maticová reprezentace lineárního zobrazení, matice složeného zobrazení
	- lineární zobrazení
		- nechť $U$ a $V$ jsou vektorové prostory nad stejným tělesem $\mathbb K$
		- zobrazení $f:U\rightarrow V$ nazveme lineární, pokud splňuje $\forall u,v \in U, \forall \alpha \in \mathbb K:$
			- $f(u+v)=f(u)+f(v)$
			- $f(\alpha\cdot u)=\alpha \cdot f(u)$
				- z toho vyplývá, že pro lineární zobrazení obecně platí $f(o) = o$
		- věta: lineární zobrazení je jednoznačně definováno tím, kam zobrazí vektory báze (proto můžeme definovat matici lineárního zobrazení)
	- matice lineárního zobrazení
		- nechť $U$ a $V$ jsou vektorové prostory nad stejným tělesem $\mathbb K$ s bázemi $X=(u_1,\dots,u_n)$ a $Y=(v_1,\dots,v_m)$
		- matice lineárního zobrazení $f:U\rightarrow V$ vzhledem k bázím $X$ a $Y$ je $[f]_{X,Y} \in \mathbb K^{m\times n}$, jejíž sloupce jsou vektory souřadnic obrazů vektorů báze $X$ vzhledem k bázi $Y$, tedy $[f(u_1)]_Y,\dots,[f(u_n)]_Y$
		- pro $w \in U$ tedy platí, že $[f(w)]_Y=[f]_{X,Y}[w]_X$
	- matice složeného zobrazení
		- mějme vektorové prostory $U,V,W$ s konečnými uspořádanými bázemi $B,C,D$
		- pro matice lineárních zobrazení $f:U\to V$ a $g:V\to W$ platí vztah $[g\circ f]_{B,D}=[g]_{C,D}[f]_{B,C}$
		- je to hezčí, když použijeme Hladíkovo značení: ${}_D[g\circ f]_B={}_D[g]_C\cdot{}_C[f]_B$
	- matice přechodu
		- nechť $X$ a $Y$ jsou dvě konečné báze vektorového prostoru $U$
		- matice přechodu od $X$ k $Y$ je $[id]_{X,Y}$
		- pro $u \in U$ tedy platí, že $[u]_Y=[id(u)]_Y=[id]_{X,Y}[u]_X$
		- matice přechodu je regulární, platí $[id]_{Y,X}=([id]_{X,Y})^{-1}$
		- výpočet: $[id]_{X,Y}=Y^{-1}X$ nebo také $(Y|X)\sim\sim(I_n|[id]_{X,Y})$
- Obraz a jádro lineárních zobrazení
	- nechť $U$ a $V$ jsou vektorové prostory nad stejným tělesem $\mathbb K$
	- jádro lineárního zobrazení
		- $\text{ker}(f)=\lbrace w \in U:f(w)=o\rbrace$
		- vektory v prostoru $U$, které se zobrazí na nulový vektor v prostoru $V$
	- obraz $f(U)$ podprostoru $U$ je podprostorem $V$
- Isomorfismus prostorů
	- vektorové prostory jsou isomorfní, pokud mezi nimi existuje isomorfismus, tedy bijektivní (vzájemně jednoznačné) lineární zobrazení
	- pro isomorfismus $f$ platí, že existuje $f^{-1}$ a je také isomorfismem
	- isomorfní prostory mají shodné dimenze
	- věta: $f$ je isomorfismus, právě když $[f]_{X,Y}$ je regulární
- Skalární součin, norma indukovaná skalárním součinem
	- skalární součin pro vektorové prostory nad komplexními čísly
		- skalární součin na vektorovém prostoru $V$ nad $\mathbb C$ je zobrazení, které přiřadí každé dvojici vektorů $u,v\in V$ skalár $\langle u|v\rangle\in\mathbb C$ tak, že jsou splněny následující axiomy:
			- $\forall u\in V:\langle u|u\rangle\in\mathbb R^+_0$ (reálné číslo $\geq 0$)
			- $\forall u\in V:\langle u|u\rangle=0\iff u=0$
			- $\forall u,v\in V: \langle v|u\rangle=\overline{\langle u|v\rangle}$ (komplexně sdružené)
			- $\forall u,v,w \in V: \langle u+v|w\rangle=\langle u|w\rangle+\langle v|w\rangle$
			- $\forall u,v\in V,\,\forall \alpha\in\mathbb C: \langle \alpha u|v\rangle=\alpha\langle u|v\rangle$
		- formálně je každý skalární součin zobrazení $V\times V\to\mathbb C$
		- skalární součin na $V$ nad $\mathbb R$ je zobrazení $V\times V\to\mathbb R$, přičemž $\langle v|u\rangle = \langle u|v\rangle$ (ve třetím axiomu), $\alpha\in\mathbb R$ (v posledním axiomu)
		- standardní skalární součin na $\mathbb R^n$: $\langle u|v\rangle=v^Tu$
		- standardní skalární součin na $\mathbb C^n$: $\langle u|v\rangle=v^Hu$
	- norma spojená se skalárním součinem
		- je-li $V$ prostor se skalárním součinem, pak norma odvozená ze skalárního součinu je zobrazení $V\to R^+_0$ přiřazující vektoru $u$ jeho normu $\|u\|=\sqrt{\langle u|u\rangle}$
		- geometrická interpretace v euklidovském prostoru $\mathbb R^n$
			- $\|u\|$ … délka (velikost) $u$
			- $\|u-v\|$ … vzdálenost bodů $u,v$
			- $\langle u|v\rangle$ souvisí s „úhlem“ $\varphi$ mezi $u,v$ a délkami $u,v$
				- $\langle u|v\rangle=\|u\|\cdot\|v\|\cos\varphi$
				- to vyplývá z kosinové věty, kde $a=\|u\|,\,b=\|v\|,\,c=\|u-v\|$
	- kolmé vektory
		- vektory $u,v$ z prostoru se skalárním součinem jsou kolmé (ortogonální), pokud $\langle u|v\rangle=0$
		- kolmé vektory značíme $u\perp v$
- Pythagorova věta, Cauchyho-Schwarzova nerovnost, trojúhelníková nerovnost
	- Pythagoras: $\|a\|^2+\|b\|^2=\|c\|^2$
		- pokud $a,b$ jsou na sebe kolmé a $c=b-a$
		- ovšem taky platí $\|a+b\|^2=\|a\|^2+\|b\|^2$, rovněž pro kolmé $a,b$
	- Cauchy-Schwarz: $|\langle u|v\rangle|\leq\sqrt{\langle u|u\rangle\langle v|v\rangle}$
	- trojúhelníková nerovnost: $\|u+v\|\leq\|u\|+\|v\|$
- Ortonormální systémy vektorů, Fourierovy koeficienty, Gramova-Schmidtova ortogonalizace
	- ortonormální báze
		- bázi $Z=\lbrace v_1,\dots,v_n \rbrace$ prostoru $V$ se skalárním součinem nazveme ortonormální, pokud platí $v_i\perp v_j$ pro každé $i\neq j$ a také $||v_i||=1$ pro každé $v_i\in Z$
		- pozorování: matice, jejichž sloupce tvoří vektory ortonormální báze $\mathbb C^n$ vzhledem ke std. skal. součinu, splňují $A^HA=I_n\implies$ jsou unitární
	- Fourierovy koeficienty
		- nechť $Z=\lbrace v_1,\dots,v_n\rbrace$ je ortonormální báze prostoru $V$
		- tvrzení: pro každé $u\in V$ platí $u=\langle u|v_1\rangle v_1+\dots+\langle u|v_n\rangle v_n$
		- $\langle u|v_i\rangle$ … Fourierovy koeficienty
	- algoritmus GS ortogonalizace
		- převede libovolnou bázi $(u_1,\dots,u_n)$ prostoru $V$ se skalárním součinem na ortonormální bázi $(v_1,\dots,v_n)$
		- for $i=1,\dots,n$ do
			- $w_i\leftarrow u_i-\sum^{i-1}_{j=1}\langle u_i|v_j\rangle v_j$
			- $v_i\leftarrow \frac1{||w_i||}w_i$
		- end
- Ortogonální doplněk, ortogonální projekce, projekce jako lineární zobrazení
	- ortogonální doplněk
		- ortogonální doplněk podmnožiny $V$ prostoru se skalárním součinem $W$ je $V^\perp=\lbrace u\in W\mid\forall v\in V: u\perp v\rbrace$
	- ortogonální projekce
		- nechť $W$ je prostor se skalárním součinem a $V$ je jeho podprostor s ortonormální bází $Z=(v_1,\dots,v_n)$
		- zobrazení $p_Z:W\to V$ definované $p_Z(u)=\sum^n_{i=1}\langle u|v_i \rangle v_i$ je ortogonální (kolmá) projekce $W$ na $V$
	- pozorování: ortogonální projekce je lineární zobrazení
- Ortogonální matice a jejich vlastnosti
	- matice $Q\in\mathbb R^{n\times n}$ je ortogonální, pokud $Q^TQ=I_n$
	- věta: $Q$ je ortogonální, právě když sloupce tvoří ortogonální bázi $\mathbb R^n$
	- tvrzení: je-li $Q$ ortogonální, pak…
		- $Q^T$ je rovněž ortogonální
		- $Q^{-1}$ existuje a je ortogonální
	- součin ortogonálních matic je ortogonální matice
	- další vlastnosti
		- $\braket{Qx|Qy}=\braket{x|y}$
		- $\|Qx\|=\|x\|$
		- zobrazení $x\mapsto Qx$ zachovává úhly a délky
		- platí to i naopak – matice zobrazení zachovávajícího skalární součin je ortogonální
		- $\forall i,j:|Q_{ij}|\leq 1$
		- $\begin{pmatrix}1 & o^T \\ o & Q\end{pmatrix}$ je ortogonální matice
- Definice a základní vlastnosti determinantu (multiplikativnost, determinant transponované matice, vztah s regularitou a vlastními čísly)
	- determinant matice $A\in\mathbb K^{n\times n}$ je dán výrazem $$\text{det }A=\sum_{p\in S_n}\text{sgn}(p)\prod_{i=1}^na_{i,p(i)}$$
	- věta: $\forall A,B\in\mathbb K^{n\times n}:\text{det}(AB)=\text{det }A\cdot\text{det }B$
	- transpozice nemění determinant, $\mathrm{det}\,A=\mathrm{det}\,A^T$
	- matice je regulární, právě když má nenulový determinant
	- pro regulární matici $A$ platí $\mathrm{det}(A^{-1})=\mathrm{det}(A)^{-1}$
	- výpočet determinantu je nutné nastudovat
	- $\mathrm{det}(A)=\lambda_1\cdot\lambda_2\cdot\ldots\cdot\lambda_n$
	- $\lambda$ je vlastním číslem $A$, právě když $\mathrm{det}(A-\lambda I_n)=0$
		- tedy právě když je kořenem charakteristického polynomu $p_A(t)=\mathrm{det}(A-tI_n)$
- Laplaceův rozvoj determinantu
	- notace: $A^{ij}$ je podmatice získaná z $A$ odstraněním $i$-tého řádku a $j$-tého sloupce
	- věta: pro libovolné $A\in\mathbb K^{n\times n}$ a jakékoli $i\in \lbrace 1,\dots,n\rbrace$ platí $$\text{det }A=\sum^n_{j=1}a_{ij}(-1)^{i+j}\text{ det }A^{ij}$$
- Geometrická interpretace determinantu
	- objem rovnoběžnostěnu určeného $k$ vektory je roven absolutní hodnotě determinantu matice, jejíž sloupce tyto vektory tvoří
	- po provedení lineárního zobrazení se objemy těles změní úměrně absolutní hodnotě determinantu matice zobrazení
- Definice, geometrický význam a základní vlastnosti vlastních čísel, charakteristický polynom, násobnost vlastních čísel
	- definice
		- mějme matici $A\in\mathbb C^{n\times n}$
		- vlastní číslo matice $A$ je jakékoliv $\lambda\in\mathbb C$, pro které existuje vektor $x\in\mathbb C^n\setminus \lbrace o\rbrace$ takový, že $Ax=\lambda x$
		- $x$ je pak vlastní vektor příslušný vlastnímu číslu $\lambda$
	- geometrie
		- vlastní vektor reprezentuje invariantní směr při zobrazení $x\mapsto Ax$, tedy směr, který se zobrazí opět na ten samý směr
		- vlastní číslo odpovídá škálování v tomto invariantním směru
	- základní vlastnosti
		- determinant matice je roven součinu vlastních čísel
		- stopa matice (součet diagonály) je roven součtu vlastních čísel
		- matice je regulární, právě když nula není její vlastní číslo
		- $A^T$ má stejná vlastní čísla jako $A$, ale vlastní vektory obecně jiné
		- uvažujeme matici $A\in\mathbb C^{n\times n}$ s vlastními čísly $\lambda_1,\dots,\lambda_n$ a jim odpovídajícími vlastními vektory $x_1,\dots,x_n$
			- je-li $A$ regulární, pak $A^{-1}$ má vlastní čísla $\lambda_1^{-1},\dots,\lambda_n^{-1}$ a vlastní vektory $x_1,\dots,x_n$
			- $A^2$ má vlastní čísla $\lambda_1^{2},\dots,\lambda_n^{2}$ a vlastní vektory $x_1,\dots,x_n$
			- podobně pro $\alpha A$ a taky pro $A+\alpha I_n$
	- charakteristický polynom … $p_A(t)=\mathrm{det}(A-tI_n)$
		- vlastní čísla matice $A$ jsou právě kořeny jejího charakteristického polynomu a je jich $n$ včetně násobností
	- algebraická násobnost $\lambda$ je rovna násobnosti $\lambda$ jakožto kořene $p_A$
	- geometrická násobnost $\lambda$ je rovna $n-\mathrm{rank}(A-\lambda I_n)$, tj. počtu lineárně nezávislých vlastních vektorů, které odpovídají $\lambda$
	- algebraická násobnost $\geq$ geometrická násobnost
		- obvykle se násobností myslí ta algebraická
- Podobnost a diagonalizovatelnost matic, spektrální rozklad
	- matice $A,B\in\mathbb C^{n\times n}$ jsou podobné, pokud existuje regulární $S\in\mathbb C^{n\times n}$ tak, že $A=SBS^{-1}$
	- věta: podobné matice mají stejná vlastní čísla
		- počet vlastních vektorů pro konkrétní vlastní číslo je stejný u obou matic
	- matice $A\in\mathbb C^{n\times n}$ je diagonalizovatelná, je-li podobná nějaké diagonální matici
	- diagonalizovatelná matice $A$ jde tedy vyjádřit ve tvaru $A=S\Lambda S^{-1}$, kde $S$ je regulární a $\Lambda$ diagonální
		- tomuto se říká spektrální rozklad
		- sloupce matice $S$ odpovídají vlastním vektorům (v pořadí, v němž jsou vlastní čísla na diagonále $\Lambda$)
	- věta: matice $A\in\mathbb C^{n\times n}$ je diagonalizovatelná, právě když má $n$ lineárně nezávislých vlastních vektorů
	- věta: pokud má matice $n$ navzájem různých vlastních čísel, pak je diagonalizovatelná
	- $A^2=S\Lambda^2 S^{-1}$
- Symetrické matice, jejich vlastní čísla a spektrální rozklad
	- matice je symetrická, pokud $A=A^T$
	- vlastní čísla reálných symetrických matic jsou reálná
	- věta: pro každou symetrickou matici $A\in\mathbb R^{n\times n}$ existuje ortogonální $Q\in\mathbb R^{n\times n}$ a diagonální $\Lambda\in\mathbb R^{n\times n}$ takové, že $A=Q\Lambda Q^T$
- Positivně semidefinitní a positivně definitní matice – charakterizace a vlastnosti, vztah se skalárním součinem, vlastními čísly
	- definice
		- buď $A\in\mathbb R^{n\times n}$ symetrická
		- pak $A$ je positivně semidefinitní, pokud $x^TAx\geq 0$ pro všechna $x\in\mathbb R^n$
		- $A$ je positivně definitní, pokud $x^TAx\gt 0$ pro všechna $x\neq o$
	- poznámka: nesymetrické matice můžeme symetrizovat úpravou $\frac12(A+A^T)$
	- následující tří vlastnosti jsou ekvivalentní
		- $A$ je positivně semidefinitní (nebo definitní)
		- vlastní čísla $A$ jsou nezáporná
			- pro definitní musí být kladná
		- existuje matice $U\in\mathbb R^{m\times n}$ taková, že $A=U^TU$
			- pro definitní musí mít matice $U$ hodnost $n$
	- vlastnosti
		- jsou-li $A,B$ positivně definitní, pak i $A+B$ je p. d.
		- je-li $A$ positivně definitní a $\alpha\gt 0$, pak i $\alpha A$ je p. d.
		- je-li $A$ positivně definitní, pak je regulární a $A^{-1}$ je p. d.
	- operace $\braket{x|y}$ je skalárním součinem v $\mathbb R^n$, právě když má tvar $\braket{x|y}=x^TAy$ pro nějakou positivně definitní matici $A\in\mathbb R^{n\times n}$
	- testování p. d. pomocí Gaussovy eliminace
		- používáme pouze úpravu přičtení násobku řádku s pivotem k jinému řádku pod ním
		- pokud nám vyjde odstupňovaný tvar s kladnou diagonálou, byla původní matice positivně definitní
- Choleského rozklad (znění věty a praktické použití)
	- pro každou positivně definitní matici $A\in\mathbb R^{n\times n}$ existuje jediná dolní trojúhelníková matice $L\in\mathbb R^{n\times n}$ s kladnou diagonálou taková, že $A=LL^T$
	- algoritmus vypadá složitě, ale dá se to vymyslet intuitivně (je vhodné začít tím, že první prvek matice $A$ je druhou mocninou čísla, které je v obou trojúhelníkových maticích vlevo nahoře)
	- praktické použití
		- řešíme soustavu $Ax=b$
		- máme Choleského rozklad $A=LL^T$
		- snadno najdeme řešení soustavy $Ly=b$ (díky nulám v trojúhelníkové matici stačí substituovat)
		- pak najdeme řešení soustavy $L^Tx=y$
		- proč to funguje?
			- $L(\underbrace{L^Tx}_{=y})=b$

## 3. Diskrétní matematika

- Relace, vlastnosti binárních relací (reflexivita, symetrie, antisymetrie, tranzitivita)
	- (binární) relace mezi množinami $X,Y$ je podmnožina $X\times Y$
	- relace na množině $X$ je podmnožina $X^2$
	- značení – pro relaci $R$ mezi $X,Y:xRy \equiv (x,y)\in R$
	- příklady relací
		- prázdná $\emptyset$
		- univerzální $X\times Y$
		- diagonální $\Delta_X := \lbrace (x,x)\mid x\in X\rbrace$, např. rovnost $x=y$
	- operace s relacemi
		- inverze
			- k relaci $R$ mezi $X,Y$ lze definovat inverzní relaci $R^{-1}$ mezi $Y,X$, přičemž $R^{-1} := \lbrace(y,x)\mid (x,y)\in R\rbrace$
		- skládání
			- pro relaci $R$ mezi $X,Y$ a relaci $S$ mezi $Y,Z$ lze definovat složenou relaci $T=R\circ S$ mezi $X,Z$
			- $xTz \equiv \exists y \in Y: xRy \land ySz$
			- $R\circ \Delta_Y =R,\quad \Delta_X\circ R = R$
			- značení skládání funkcí: $(f\circ g)(x)=g(f(x))$
	- relace $R$ na $X$ je…
		- reflexivní $\equiv \forall x \in X: xRx$
			- $\Delta_X \subseteq R$
		- symetrická $\equiv \forall x,y \in X: xRy \implies yRx$
			- $R=R^{-1}$
		- antisymetrická $\equiv \forall x,y \in X: xRy \land yRx \implies x=y$
			- $R\cap R^{-1}\subseteq \Delta_X$
		- tranzitivní $\equiv \forall x,y,z \in X: xRy \land yRz \implies xRz$
			- $R\circ R \subseteq R$
- Ekvivalence a rozkladové třídy
	- relace $R$ na $X$ je ekvivalence $\equiv R$ je reflexivní & symetrická & tranzitivní
		- např. rovnost čísel, rovnost mod $K$, geometrická podobnost
	- ekvivalenční třída prvku $x \in X:R[x]=\lbrace y \in X \mid xRy\rbrace$
	- množinový systém $\mathcal S\subseteq 2^X$ je rozklad množiny $X \equiv$
		- $\forall A \in \mathcal S: A \neq \emptyset$
		- $\forall A,B\in \mathcal S: A\neq B \implies A \cap B = \emptyset$
		- $\bigcup_{A\in \mathcal S}A=X$
	- věta (vztah mezi ekvivalencemi a rozklady)
		1. $\forall x \in X: R[x]\neq \emptyset$
		2. $\forall x,y \in X:$ buď $R[x]=R[y]$, nebo $R[x] \cap R[y]=\emptyset$
		3. $\lbrace R[x] \mid x \in X\rbrace$ (množina všech ekvivalenčních tříd) určuje ekvivalenci R jednoznačně
- Částečná uspořádání – základní pojmy (minimální a maximální prvky, nejmenší a největší prvky, řetězec, antiřetězec)
	- relace $R$ na množině $X$ je (částečné) uspořádání $\equiv R$ je reflexivní & antisymetrická & tranzitivní
	- (částečně) uspořádaná množina $(X,R)$
		- zkráceně ČUM
		- $R$ je (částečné) uspořádání na $X$
	- prvky $x,y \in X$ jsou porovnatelné $\equiv xRy \lor yRx$
	- uspořádání je lineární $\equiv \forall x,y\in X$ porovnatelné
		- (všechny prvky množiny jsou navzájem porovnatelné)
	- částečné uspořádání (nebo pouze uspořádání) je obecný pojem, některá taková uspořádání jsou navíc lineární
	- ostré uspořádání – každému uspořádání $\leq$ na X přiřadíme relaci $<$ na X: $a < b \equiv a \leq b \land a \neq b$ 
		- pozor – ostré uspořádání není speciálním případem uspořádání (protože není reflexivní)
		- vlastnosti ostrého uspořádání – ireflexivní, antisymetrické, tranzitivní
	- Hasseův diagram graficky zachycuje vztahy mezi prvky ČUM (porovnatelné prvky jsou spojeny, větší prvky jsou výše)
	- prvek $x\in X$ je nejmenší $\equiv \forall y \in X: x\leq y$
	- prvek $x\in X$ je minimální $\equiv \nexists y \in X: y\lt x$
	- $x$ je nejmenší $\implies$ $x$ je minimální
	- v Hassově diagramu
		- z minimálního prvku dolů nevede žádná spojnice
		- nejmenší prvek je nejníž v diagramu, existuje do něj cesta z libovolného jiného prvku
	- věta: konečná neprázdná uspořádaná množina má minimální a maximální prvek
	- pro $(X,\leq)$ ČUM:
		- $A\subseteq X$ je řetězec $\equiv \forall a,b \in A: a,b$ jsou porovnatelné
		- $A \subseteq X$ je antiřetězec (nezávislá množina) $\equiv \nexists a,b$ různé & porovnatelné
- Výška a šířka částečně uspořádané množiny a věta o jejich vztahu (o dlouhém a širokém)
	- $\omega(X,\leq)$ je délka nejdelšího řetězce = maximum z délek řetězců (výška uspořádání)
	- $\alpha(X,\leq)$ je délka nejdelšího antiřetězce (šířka uspořádání)
	- věta: pro každou konečnou ČUM $(X,\leq)$ platí $\alpha(X,\leq)\cdot \omega(X,\leq)\geq |X|$
	- důsledek: $\text{max}(\alpha,\omega)\geq\sqrt{|X|}$
- Funkce, typy funkcí (prostá, na, bijekce)
	- funkce z množiny $X$ do množiny $Y$ je relace $A$ mezi $X$ a $Y$ t. ž. $(\forall x\in X)(\exists! y\in Y):xAy$
	- funkce $f:X\to Y$ je…
		- prostá (injektivní) $\equiv \nexists x,x' \in X: x \neq x' \land f(x)=f(x')$
		- na $Y$ (surjektivní) $\equiv (\forall y \in Y)(\exists x \in X): f(x)=y$
		- vzájemně jednoznačná (bijektivní) $\equiv (\forall y \in Y)(\exists! x \in X):f(x)=y$
			- taková funkce je tedy prostá i „na“
			- k takové funkci existuje inverzní funkce $f^{-1}$ z $Y$ do $X$
- Počty různých typů funkcí mezi dvěma konečnými množinami
	- věta: počet $f:N\to M=m^n$
		- pro $|N|=n, |M|=m;\quad m,n\gt 0$
	- definice: klesající mocnina
		- $m^{\underline n}=\underbrace{m\cdot (m-1)\cdot (m-2)\cdot\ldots\cdot(m-n+1)}_n$
		- tedy $m^{\underline n}=\frac{m!}{(m-n)!}$
	- věta: počet prostých $f:N\to M=m^{\underline{n}}$
	- počet surjektivních zobrazení lze určit pomocí principu inkluze a exkluze
	- bijekcí je $n!$
	- počet uspořádaných $k$-tic $|X^k|=|X|^k$, lze jej totiž vyjádřit jako počet funkcí $f:[k]\to X$
- Permutace a jejich základní vlastnosti (počet a pevný bod)
	- definice: $[n]=\lbrace1,2,\dots,n\rbrace$
	- věta: na množině $[n]$ existuje $n!$ permutací (podobně na každé n-prvkové množině)
	- pevný bod permutace je prvek, který se zobrazí sám na sebe
- Kombinační čísla a vztahy mezi nimi, binomická věta a její aplikace
	- kombinační číslo (binomický koeficient) ${n\choose k}:={n^{\underline k} \over k!}={n!\over k!(n-k)!}$
	- Pascalův trojúhelník – n roste shora dolů, k zleva doprava
	- $X\choose k$ … množina všech k-prvkových podmnožin množiny $X$
	- ${n\choose k} = {n\choose n-k}$ … každé k-prvkové podmnožině přiřadíme její doplněk
		- Pascalův trojúhelník je symetrický
	- ${n-1\choose k-1}+{n-1\choose k}={n\choose k}$
		- zvolíme jeden prvek $a$ a rozdělíme všechny k-prvkové podmnožiny podle toho, zda obsahují $a$, nebo ne
		- buňka v Pascalově trojúhelníku je součtem dvou buněk nad ní (pokud není na kraji)
	- Binomická věta: $(x+y)^n=\sum_{i=0}^n{n\choose i}x^{n-i}y^i$
	- aplikace
		- řádek Pascalova trojúhelníku se sečte na $2^n=(1+1)^n=\sum_{k=0}^n\binom{n}{k}$
		- důkaz $(x^n)'=nx^{n-1}$
			- použijeme $f(x+h)=(x+h)^n=x^n+nx^{n-1}h+\binom n2 x^{n-2}h^2+\dots+h^n$
			- dosadíme do $\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}$
		- $e=\lim\,(1+\frac1n)^n$
- Princip inkluze a exkluze: obecná formulace (a důkaz)
	- konkrétní ukázky principu inkluze a exkluze (PIE)
		- $|A\cup B|=|A|+|B|-|A\cap B|$
		- $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$
	- věta: pro konečné množiny $A_1,\dots,A_n$ platí $$|\bigcup_{i=1}^nA_i|=\sum_{k=1}^n(-1)^{k+1}\sum_{I\in{[n]\choose k}}|\bigcap_{i\in I}A_i|$$
	- důkaz
		- pro prvek $x$ ve sjednocení spočítáme příspěvky k levé (vždy 1) a pravé straně
		- nechť $x$ patří do právě $t$ množin
		- průniky $k$-tic
			- $k \gt t$ … přispěje $0$
			- $k\leq t$ … přispěje $(-1)^{k+1}{t\choose k}$
				- vybíráme $k$-tice množin z $t$-množin, do kterých prvek patří
				- minus jednička vychází ze vzorce
			- chceme $\sum_{k=1}^t(-1)^{k+1}{t\choose k}=1$
			- lze upravit na $\sum_{k=1}^t(-1)^{k}{t\choose k}=-1$
			- z binomické věty $0=(1-1)^t=\sum_{k=0}^t{t\choose k}(-1)^{k}$
			- tedy bez prvního členu se součet rovná $-1\quad \square$
- Princip inkluze a exkluze: použití (problém šatnářky, Eulerova funkce pro počet dělitelů, počet surjekcí)
	- problém šatnářky
		- Šatnářka $n$ pánům vydá náhodně $n$ klobouků (které si předtím odložili v šatně). Jaká je pravděpodobnost, že žádný pán nedostane od šatnářky zpět svůj klobouk?
		- jaká je pravděpodobnost, že náhodně zvolená permutace nebude mít žádný pevný bod
			- každá z $n!$ permutací je stejně pravděpodobná
			- $š(n)$ … počet permutací bez pevného bodu
			- pravděpodobnost je rovna $š(n)/n!$
		- $S_n$ … množina všech permutací
		- $A_i=\lbrace \pi \in S_n \mid \pi(i)=i\rbrace$
			- množina permutací s pevným bodem v $i$-tém prvku (jedna permutace může patřit do více takových množin)
		- $A=\bigcup_{i=1}^n A_i$ … (množina všech „špatných“ permutací)
		- musíme vyjádřit velikosti průniků
			- permutací s (konkrétními) $k$ pevnými body je $(n-k)!$, protože permutuji všechny prvky kromě těch pevných
		- dosazením do principu inkluze a exkluze vyjde $|A|=\sum_{k=1}^n(-1)^{k+1}{n\choose k}(n-k)!$
			- $n\choose k$ vyplývá z počtu prvků druhé sumy
			- ${n\choose k}(n-k)!={n!\over k!}$
		- $|A|=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}=n!\cdot\sum_{k=1}^n{(-1)^{k+1}\over k!}$
		- $|A|=n!({1\over 1!}-{1\over 2!}+{1\over 3!}-\dots+{(-1)^{n+1}\over n!})$
		- $š(n)=n!-|A|=n!\cdot(1-{1\over 1!}+{1\over 2!}-{1\over 3!}+\dots+{(-1)^n\over n!})$
			- závorka konverguje k $e^{-1}$
			- závorka odpovídá pravděpodobnosti v problému šatnářky
		- $š(n)=n!\cdot\sum_{k=0}^n\frac{(-1)^k}{k!}$
		- pravděpodobnost … $\sum_{k=0}^n\frac{(-1)^k}{k!}\approx e^{-1}$
	- Eulerova funkce $\varphi(n)$
		- je to počet čísel z $[n]$ nesoudělných s $n$
			- pro prvočíslo $p$ platí $\varphi(n)=p-1$, protože je soudělné samo se sebou a protože podle definice nesoudělnosti (NSD = 1) není soudělné s jedničkou
		- tvrzení: nechť $n=p_1^{e_1}\cdot p_2^{e_2}\cdot\ldots\cdot p_k^{e_k}$ je prvočíselný rozklad, pak $\varphi(n)=n(1-\frac{1}{p_1})(1-\frac1{p_2})\dots(1-\frac1{p_k})$
		- důkaz
			- jako $A_i$ označím množinu čísel z $[n]$ soudělných $i$-tým prvočíslem $p_i$
			- zjevně $\varphi(n)=n-|\bigcup_{i=1}^k A_i|$
			- $|A_i|=\frac n{p_i}$
			- pro různé $i,j\in[k]$ platí $|A_i\cap A_j|=\frac n{p_ip_j}$
			- to se dá zobecnit na průnik více množin
			- dle PIE $|\bigcup_{i=1}^kA_i|=\sum_{I\in 2^{[n]}\setminus\set\emptyset}(-1)^{|I|+1}\frac{n}{\prod_{i\in I} p_i}$
			- $=n(\frac1{p_1}+\dots+\frac1{p_k}-\frac1{p_1p_2}-\dots+\frac1{p_1p_2p_3}+\dots+(-1)^{k+1}\frac1{p_1\dots p_k})$
			- proto $\varphi(n)=n(1-\frac1{p_1}-\dots-\frac1{p_k}+\frac{1}{p_1p_2}+\dots+(-1)^k\frac1{p_1\dots p_k})$
			- tedy $\varphi(n)=n(1-\frac{1}{p_1})(1-\frac1{p_2})\dots(1-\frac1{p_k})\quad\square$
				- z každé závorky vždy vybíráme levý nebo pravý člen
	- počet surjekcí
		- věta
			- nechť $X,Y$ jsou konečné množiny, $|X|=n$, $|Y|=m$, $n\geq m\gt 0$
			- potom počet zobrazení $f$ množiny $X$ na množinu $Y$ je $\sum_{k=0}^m(-1)^k\binom mk(m-k)^n$
		- důkaz
			- počet všech funkcí z $X$ do $Y$ je $m^n$
			- definujeme $F_i$ jako množinu zobrazení, že $i$-tý prvek z množiny $Y$ není pokrytý (neexistuje $x\in X$, aby $f(x)=y_i$, kde $y_i$ je $i$-tý prvek z $Y$)
			- takže počet surjekcí bude $m^n-|\bigcup_{i=1}^m F_i|$
			- použijeme PIE: $|\bigcup_{i=1}^mF_i|=\sum_{k=1}^m(-1)^{k+1}\sum_{I\in{[m]\choose k}}|\bigcap_{i\in I}F_i|$
			- $=\sum_{k=1}^m(-1)^{k+1}\binom mk(m-k)^n$
				- $(m-k)^n$ dostaneme tak, že uvažujeme funkce z $n$-prvkové množiny do množiny s $m-k$ prvky (na vybraných $k$ bodů naše funkce nesmí směřovat)
			- počet surjekcí $m^n-|\bigcup_{i=1}^m F_i|=m^n-\sum_{k=1}^m(-1)^{k+1}\binom mk(m-k)^n$ pak ještě upravíme do finálního tvaru $\quad\square$
- Hallova věta o systému různých reprezentantů a její vztah k párování v bipartitním grafu, princip důkazu a algoritmické aspekty (polynomiální algoritmus pro nalezení SRR)
	- párování je taková množina hran, kde žádné dvě hrany nemají společný vrchol
		- maximální párování je takové párování, které má nejvíce hran
		- perfektní párování je takové párování, které pokrývá všechny vrcholy grafu
	- systém různých reprezentantů v hypergrafu
		- systém různých reprezentantů (SRR) v hypergrafu $H=(V,E)$ je funkce $r:E\to V$ taková, že
			- $\forall e\in E: r(e)\in e$
			- $\forall e,f\in E:e\neq f\implies r(e)\neq r(f)$ … tj. $r$ je prostá
		- $r(e)$ … „reprezentant hyperhrany $e$“
		- analogie s předsedy spolků
	- pozorování: v bipartitním grafu s partitami $A,B$ má každé párování velikost nejvýše $|A|$ (i nejvýše $|B|$)
	- definice: pro graf $G=(V,E)$ a množinu $X\subseteq V$ označím $N(X):=\set{y\in V\setminus X: (\exists x\in X)\set{x,y}\in E}$
	- Hallova věta, bipartitní grafová verze
		- nechť $G$ je bipartitní graf s partitami $A,B$, potom $G$ má párování velikosti $|A|$ $\iff\underbrace{\forall X\subseteq A:|N(X)|\geq |X|}_{\text{„Hallova podmínka“}}$
	- důkaz
		- $\implies$
			- pokud existuje párování velikosti $|A|$, tak pro každou $X\subseteq A$ existuje $|X|$ vrcholů spárovaných s $X$, ty patří do $N(X)$, tedy $|N(X)|\geq |X|$
		- $\impliedby$
			- nechť $M$ je největší párování v $G$
			- pro spor nechť $|M|\lt|A|$
			- dle Kőnigovy–Egerváryho věty existuje pokrytí $C$, kde $|C|=|M|\lt |A|$
			- $C_A:= C\cap A$
			- $C_B:=C\cap B$
			- $X:=A\setminus C_A$
			- zjistím, že $N(X)\subseteq C_B$
				- protože nepokryté hrany musí pokrývat vrcholy v $N(X)$
			- navíc $|X|=|A|-|C_A|\gt |C_B|\geq |N(X)|$
				- jelikož $|C|\lt|A|\implies |A|\gt|C_A|+|C_B|$
			- to je spor s Hallovou podmínkou
		- idea $\impliedby$
			- uvažujeme ostře menší párování, tedy podle Kőnigovy–Egerváryho věty musí existovat i menší pokrytí
				- věta říká, že velikost maximální párování se rovná velikosti minimálního pokrytí (jako u toku a řezu)
			- prohlásíme, že vrcholy v $X$ nejsou v pokrytí, tak ty hrany mezi nimi a $N(X)$ musí pokrývat vrcholy v $N(X)$, ale těch by pak bylo málo (méně než požaduje Hallova podmínka)
			- takže jsme dokázali obměnu implikace
	- pozorování: jakmile uvnitř hypergrafu je množina čtyř hyperhran, které ve svém sjednocení mají tři vrcholy, tak nemůžu najít systém různých reprezentantů
		- platí to obecně pro množinu $k$ hyperhran – když budou mít ve sjednocení méně než $k$ vrcholů, tak nenajdu SRR
		- implikace platí i obráceně, lze vyslovit jako větu
	- Hallova věta, hypergrafová verze
		- hypergraf $H=(V,E)$ má SRR, právě když $\forall F\subseteq E:\left|\bigcup_{e\in F} e\right|\geq |F|$
	- důkaz
		- nechť $H=(V,E)$ je hypergraf, nechť $I_H$ je jeho graf incidence
		- $H$ má SRR $\iff$ $I_H$ má párování velikosti $|E|$
		- Hallova podmínka pro $H$: $\forall F\subseteq E: \left|\bigcup_{e\in F}e\right|\geq |F|\iff$ bipartitní Hallova podmínka pro $I_H$ a partitu $E$
	- algoritmické aspekty
		- maximální párování lze najít v polynomiálním čase
		- proto i SRR lze najít v polynomiálním čase

## 4. Teorie grafů

- Základní pojmy teorie grafů – graf, vrcholy a hrany, izomorfismus grafů, podgraf, okolí vrcholu a stupeň vrcholu, doplněk grafu, bipartitní graf
	- graf je $(V, E)$, kde $V$ je konečná neprázdná množina vrcholů a $E \subseteq {V \choose 2}$ je množina hran
		- lze značit jako $G=(V,E)$, potom $V(G)$ je množina vrcholů a $E(G)$ je množina hran
	- izomorfismus
		- grafy jsou izomorfní $\equiv$ existuje bijekce, která zachovává vlastnost být spojen hranou
		- v podstatě stačí přejmenovat vrcholy a dostaneme dva stejné grafy
		- značení $\cong$
		- $\cong$ je ekvivalence na libovolné množině grafů
			- neexistuje množina všech grafů (protože neexistuje množina všech množin)
	- podgraf
		- graf $G'=(V',E')$ je podgrafem grafu $G=(V,E)$ (značíme $G'\subseteq G$), když $V'\subseteq V \land E'\subseteq E$
		- graf $G'=(V',E')$ je indukovaným podgrafem grafu $G=(V,E)$, když $V'\subseteq V \land E'= E\cap {V'\choose 2}$
			- „podgraf indukovaný množinou vrcholů“
			- $G[A] := (A, E(G) \cap {A \choose 2})$, kde $A\subseteq V(G)$
	- okolí vrcholu
		- okolí vrcholu $v$ jsou ty vrcholy, které s vrcholem $v$ sousedí (sdílejí hranu)
		- $N_G(v)=\set{u\in V(G):\exists uv\in E(G)}$
	- stupeň vrcholu
		- stupeň vrcholu – počet hran, kterých se účastní daný vrchol
		- graf je k-regulární, pokud je stupeň všech vrcholů grafu roven k
		- skóre grafu = posloupnost stupňů vrcholů (až na pořadí) → jakmile dvěma grafům vyjde jiné skóre, nemohou být izomorfní
	- doplněk grafu
		- doplněk/komplement grafu $G$ je graf $G_0$, který má stejné vrcholy jako $G$, ale má právě ty hrany, které v grafu $G$ chybí
	- bipartitní graf
		- graf (V, E) je bipartitní $\equiv \exists L,P\subseteq V$ t. ž.:
			- $L \cup P = V$
			- $L \cap P = \emptyset$
			- $\forall e \in E: |e \cap L| = 1\quad (\land\ |e \cap P| = 1)$
				- nebo $E(G)\subseteq\lbrace\lbrace x,y\rbrace\mid x\in L,y\in P\rbrace$
		- partity grafu – jednotlivé „strany“
- Základní příklady grafů – úplný graf a úplný bipartitní graf, cesty a kružnice
	- úplný graf $K_n$
		- $V(K_n):=[n]$
		- $E(K_n):={V(K_n)\choose 2}$
	- úplný bipartitní $K_{m,n}$
		- každý prvek nalevo je spojený s každým napravo
		- prvky na jedné straně mezi sebou nejsou spojeny
	- prázdný graf $E_n$
		- $V(E_n):=[n]$
		- $E(E_n) =\emptyset$
	- cesta $P_n$
		- $V(P_n):=\{0,\dots, n\}$
		- $E(P_n):=\{\{i,i+1\}\mid 0\leq i \lt n\}$
		- délka cesty se měří v počtu hran
	- kružnice/cyklus $C_n$
		- $n\geq 3$
		- $V(C_n):=\{0,\dots, n–1\}$
		- $E(C_n):=\{\{i,(i+1)\bmod n\}\mid 0\leq i \lt n\}$
- Souvislost grafů, komponenty souvislosti, vzdálenost v grafu
	- graf $G$ je souvislý $\equiv\forall u,v\in V(G):$ existuje cesta v $G$ s krajními vrcholy $u,v$
	- dosažitelnost v $G$ je relace $\sim$ na $V(G)$ t. ž. $u\sim v\equiv$ existuje cesta v $G$ s krajními vrcholy $u,v$
		- relace $\sim$ je ekvivalence
		- tranzitivita se dokazuje pomocí dvou posloupností vrcholů $x \sim y$ a $y\sim z$ a následně zvolení nejzazšího vrcholu z posloupnosti $y\sim z$, který je obsažen v posloupnosti $x\sim y$ a v tomto vrcholu se posloupnosti slepí (přičemž části za ním v první posloupnosti a před ním v druhé posloupnosti se ustřihnou)
	- komponenty souvislosti jsou podgrafy indukované třídami ekvivalence $\sim$
		- komponenty jsou souvislé
		- graf je souvislý $\iff$ má 1 komponentu
	- vzdálenost (grafová metrika) v souvislém grafu $G$
		- $d_G:V^2\to\mathbb R$
		- $d_G(u,v):=$ min. z délek (počtu hran) všech cest mezi $u,v$
	- vlastnosti metriky (funkce je metrika = chová se jako vzdálenost)
		- $d_G(u,v)\geq 0$
		- $d_G(u,v) = 0 \iff u=v$
		- platí trojúhelníková nerovnost $d_G(u,w) \leq d_G(u,w) + d_G(w,v)$
		- $d_G(v,u)=d_G(u,v)$
	- grafové operace: přidání/odebrání vrcholu/hrany, dělení hrany, kontrakce hrany
	- sled v grafu (walk) – můžou se opakovat vrcholy i hrany
		- $(v_0,e_1,v_1,e_2,\dots,e_n,v_n)$
		- $\forall i: e_i=\lbrace v_{i-1},v_i\rbrace$
	- tah v grafu – můžou se opakovat vrcholy, hrany ne
		- tah může být uzavřený (končí, kde začal), nebo otevřený
	- eulerovský tah
		- eulerovský tah obsahuje všechny hrany a vrcholy grafu
			- někdy se eulerovský tah definuje bez nutnosti obsahovat všechny vrcholy
		- graf je eulerovský $\equiv$ existuje v něm uzavřený eulerovský tah
	- věta: graf $G$ je eulerovský $\iff G$ je souvislý a každý jeho vrchol má sudý stupeň
- Stromy – definice a základní vlastnosti (existence listů, počet hran stromu)
	- strom je souvislý graf bez kružnic (= acyklický)
	- les je acyklický graf
	- list je vrchol stupně 1
		- strom o jednom vrcholu („pařez“) nemá žádný list
	- lemma: každý strom s aspoň 2 vrcholy má aspoň 1 list (respektive aspoň dva listy)
	- lemma: je-li $v$ list grafu $G$, pak $G$ je strom, právě když $G-v$ je strom
	- strom $G$ má $|V(G)|-1$ hran (Eulerova formule)
- Ekvivalentní charakteristiky stromů
	1. G je souvislý a acyklický (strom)
	2. mezi vrcholy $u, v$ existuje právě jedna cesta (jednoznačně souvislý)
	3. G je souvislý a po smazání libovolné jedné hrany už nebude souvislý (minimální souvislý)
	4. G je acyklický a po přidání libovolné jedné hrany vznikne cyklus (maximální acyklický)
	5. G je souvislý a platí pro něj Eulerova formule $|E(G)|=|V(G)|-1$
- Rovinné grafy – definice a základní pojmy (rovinný graf a rovinné nakreslení grafu, stěny)
	- rovinné nakreslení grafu = nakreslení grafu, aby se hrany nekřížily
		- vrcholy = body v rovině (navzájem různé)
		- hrany = křivky, které se neprotínají a jejich společnými body jsou jejich společné vrcholy
	- stěny nakreslení
		- části, na které nakreslení grafu rozděluje rovinu
		- stěnou je i vnější stěna (zbytek roviny)
		- hranice stěny – skládá se z hran
		- hranice stěny je nakreslení uzavřeného sledu
	- graf je rovinný, pokud má alespoň jedno rovinné nakreslení
	- topologický graf je uspořádaná dvojice (graf, nakreslení)
	- $K_5$ a $K_{3,3}$ nejsou rovinné
		- graf je rovinný, právě když žádný jeho podgraf není izomorfní s nějakým dělením grafu $K_5$ nebo $K_{3,3}$ (tzn. podgraf může mít podrozdělené hrany – „$K_5$“ s libovolně podrozdělenými hranami pořád nebude rovinná)
- Eulerova formule a maximální počet hran rovinného grafu (důkaz a použití)
	- věta
		- nechť $G$ je souvislý graf nakreslený do roviny, $v:=|V(G)|, e:=|E(G)|, f:=$ počet stěn nakreslení
		- potom $v+f=e+2$ (Eulerova formule)
	- důkaz: indukcí podle $e$
		- $e=v-1$ (G je strom)
			- $f=1$
			- $v+1=v-1+2\quad\checkmark$
		- $e-1\to e$
			- mějme graf $G$ s $e$ hranami
			- zvolím si libovolnou hranu $x$ na kružnici
			- $G':=G-x$
			- $v'=v,\quad e'=e-1,\quad f'=f-1$
			- z IP: $v'+f'=e'+2$
			- po dosazení: $v+f-1=e-1+2$
			- k oběma stranám přičteme jedničku
			- $v+f=e+2\quad\square$
	- věta: maximální rovinný graf je triangulace
		- dokud hranice stěny není trojúhelník, je tam nějaká dvojice nespojených vrcholů
	- počet hran maximálního rovinného grafu
		- každá stěna přispěje třemi hranami
		- každá hrana patří ke dvěma stěnám
		- počítáme „strany hran“: $3f=2e$
		- $f={2\over 3}e$
		- $v+{2\over 3}e=e+2$
		- $e=3v-6$
	- věta: v každém rovinném grafu s aspoň 3 vrcholy je $|E|\leq 3|V|-6$
	- důkaz
		- doplníme do $G$ hrany, až získáme maximální rovinný $G'$
		- $e'=3v-6$ (vrcholy nepřidáváme)
		- $e\leq e'=3v-6$
	- důsledek
		- průměrný stupeň vrcholu v rovinném grafu je menší než 6
			- $\sum \text{deg}(\xi)=2e\leq 6v-12$
			- průměrný stupeň $\leq {6v-12\over v}\lt 6$
	- počet hran a vrchol nízkého stupně v rovinných grafech bez trojúhelníků
		- maximální rovinné grafy bez trojúhelníků mají stěny čtvercové, pětiúhelníkové, nebo to může být strom ve tvaru hvězdy
		- pro čtvercově stěny platí $4f=2e$, pro pětiúhelníkové $5f=2e$
		- obecně $4f\leq 2e\to f\leq \frac 12 e$
		- $v+\frac 12e\geq e+2$
		- $e\leq 2v-4$
		- průměrný stupeň $\leq {4v-8\over v} \lt$ 4
		- existuje vrchol stupně max. 3
- Barevnost grafů – definice dobrého obarvení, vztah barevnosti a klikovosti grafu
	- obarvení grafu $G$ $k$ barvami ($k$-obarvení) je $c:V(G)\to[k]$ t. ž. kdykoli $\lbrace x,y\rbrace\in E(G)$, pak $c(x)\neq c(y)$
	- barevnost $\chi(G)$ grafu $G:=\text{min }k:\exists$ k-obarvení grafu $G$
	- pozorování: kdykoli $H\subseteq G$, pak $\chi(H)\leq \chi(G)$
	- barevnost některých grafů
		- úplné grafy … $\chi(K_n)=n$
		- cesty … $\chi(P_n)=2$ pro $n\geq 1$
		- sudé kružnice … $\chi(C_{2k})=2$
		- liché kružnice … $\chi(C_{2k+1})=3$
		- stromy jsou 2-obarvitelné
		- pro rovinné grafy existuje věta o čtyřech barvách (je to těsný horní odhad – existují rovinné grafy, které nelze obarvit třemi barvami, např. $K_4$)
	- věta: $\chi(G)\leq 2\iff G$ je bipartitní $\iff G$ neobsahuje lichou kružnici
	- definice: klikovost grafu $\kappa(G)$ je maximální $k$ takové, že v grafu jako podgraf existuje úplný graf $K_k$
		- $\chi(G)\geq\kappa(G)$
	- klika v grafu je množina vrcholů taková, že každé dva jsou spojené hranou
	- nezávislá množina v grafu je množina vrcholů taková, že žádné dva vrcholy nejsou spojené hranou
- Hranová a vrcholová souvislost grafů
	- $F\subseteq E$ je hranový řez v $G$, pokud $G-F$ je nesouvislý
		- kde $G-F\coloneqq(V,E\setminus F)$
	- graf je hranově $k$-souvislý, pokud neobsahuje žádný hranový řez velikosti menší než $k$
	- stupeň hranové souvislosti (nebo jen hranová souvislost) grafu $G$, značený $k_e(G)$, je největší $k$ takové, že $G$ je hranově $k$-souvislý
		- pozorování: $k_e(G)=$ velikost nejmenšího hranového řezu v $G$
	- $A\subseteq V$ je vrcholový řez, pokud $G-A$ je nesouvislý
		- kde $G-A=(V\setminus A,E\cap {V\setminus A\choose 2})$
	- graf je vrcholově $k$-souvislý, pokud má aspoň $k+1$ vrcholů a neobsahuje žádný vrcholový řez velikosti menší než $k$
	- vrcholová souvislost grafu $G$, značená $k_v(G)$, je největší $k$ takové, že $G$ je vrcholově $k$-souvislý
		- pozorování: $k_v(K_n)=n-1$
		- pozorování: $G$ není úplný … $k_v(G)=$ velikost nejmenšího vrcholového řezu
- Hranová a vrcholová verze Mengerovy věty
	- Mengerova věta, hranová $xy$-verze
		- pro dva různé vrcholy $x,y$ grafu $G$ platí, že $G$ obsahuje $k$ hranově disjunktních cest z $x$ do $y$ $\iff G$ neobsahuje hranový $xy$-řez velikosti menší než $k$ 
	- Mengerova věta, globální hranová verze
		- graf $G$ je hranově $k$-souvislý $\iff$ mezi každými dvěma různými vrcholy existuje $k$ hranově disjunktních cest
	- definice: dvě cesty v $G$ z $x$ do $y$ jsou navzájem vnitřně vrcholově disjunktní (VVD), pokud nemají žádný společný vrchol kromě $x,y$
	- Mengerova věta, vrcholová $xy$-verze
		- nechť $G=(V,E)$ je graf
		- nechť $x,y$ jsou různé **nesousední** vrcholy
		- nechť $k\in\mathbb N$
		- potom $G$ obsahuje $k$ navzájem VVD cest z $x$ do $y\iff G$ neobsahuje vrcholový $xy$-řez velikosti $\lt k$
	- Mengerova věta, globální vrcholová verze
		- $G$ je vrcholově $k$-souvislý $\iff$ mezi každými dvěma různými vrcholy $x,y$ existuje $k$ navzájem VVD cest
- Orientované grafy, silná a slabá souvislost
	- orientovaný graf … $(V,E): E \subseteq V^2 \setminus \{(x,x)\mid x\in V\}$
		- nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)
	- podkladový graf je neorientovaný graf založený na tom původním orientovaném
		- pro orientovaný $G=(V,E)$ existuje podkladový $G^0=(V,E^0)$, kde $\lbrace u,v\rbrace \in E^0\equiv (u,v)\in E\lor (v,u)\in E$
	- vstupní a výstupní stupeň $\text{deg}^\text{in},\text{deg}^\text{out}$ (hrany vedoucí do vrcholu / z vrcholu)
	- vrchol je vyvážený $\equiv \text{deg}^\text{in}(v)=\text{deg}^\text{out}(v)$
	- graf je vyvážený $\equiv$ všechny vrcholy jsou vyvážené
	- součet vstupních stupňů = součet výstupních stupňů = počet hran
	- orientovaný graf je slabě souvislý $\equiv$ jeho podkladový graf je souvislý
	- o. graf je silně souvislý $\equiv$ existuje orientovaná cesta mezi každými dvěma vrcholy
	- silná souvislost $\implies$ slabá souvislost
	- věta: pro orientovaný graf $G$ platí: $G$ je vyvážený a slabě souvislý $\iff$ $G$ je eulerovský $\iff$ $G$ je vyvážený a silně souvislý
- Toky v sítích: definice sítě a toku v ní
	- tokovou síť tvoří
		- $V$ … množina vrcholů
		- $E$ … množina orientovaných hran, $E\subseteq V\times V$
		- $z\in V$ … zdroj
		- $s\in V\setminus\set{z}$ … spotřebič / stok
		- $c:E\to [0,+\infty)$ … $c(e)$ je kapacita hrany $e$
	- definice umožňuje mít hrany oběma směry, připouští také smyčky, ty však z hlediska toků v sítích nejsou nijak užitečné
	- poznámka: ze stoku může vycházet orientovaná hrana, podobně do zdroje může vést hrana
	- tok v síti $(V,E,z,s,c)$ je funkce $f:E\to[0,+\infty)$ splňující
		- $\forall e\in E:0\leq f(e)\leq c(e)$
		- $\forall x\in V\setminus \set{z,s}:$ součet toků do vrcholu $x$ se rovná součtu toků z vrcholu (formálně pomocí sum) … Kirchhoffův zákon
- Existence maximálního toku (bez důkazu)
	- velikost toku $f$ v síti $(V,E,z,s,c)$ je $w(f)\coloneqq f[\text{Out}(z)]-f[\text{In}(z)]$
	- kde $\mathrm{Out}(z)$ a $\mathrm{In}(z)$ jsou množiny hran do, respektive ze zdroje a $f[A]\coloneqq\sum_{e\in A}f(e)$ pro $A\subseteq E$
	- maximální tok je tok, který má největší velikost
	- fakt: v každé tokové síti existuje maximální tok
	- poznámka: obecně na přednášce uvažujeme konečné tokové sítě, grafy apod.
	- idea důkazu
		- mějme síť, očíslujme hrany (od $1$ do $m$)
		- tok $f$ reprezentujme jako uspořádanou $m$-tici hodnot
		- množina všech toků je uzavřená a omezená podmnožina $\mathbb R^m$, je tedy kompaktní
		- funkce, která toku $f$ přiřadí $w(f)$, je spojitá
		- víme z analýzy, že spojitá funkce na kompaktní množině nabývá maxima
	- řez v síti $(V,E,z,s,c)$ je množina hran $R\subseteq E$ taková, že každá orientovaná cesta ze $z$ do $s$ obsahuje aspoň jednu hranu $R$
	- Minimaxová věta o toku a řezu: nechť $f_\text{max}$ je maximální tok a $R_\text{min}$ je minimální řez v $(V,E,z,s,c)$, potom $w(f_\text{max})=c(R_\text{min})$
- Princip hledání maximálního toku v síti s celočíselnými kapacitami (například pomocí Ford-Fulkersonova algoritmu)
	- rezerva hrany $uv$
		- $r(uv)\coloneqq c(uv)-f(uv)+f(vu)$
	- hrana je nasycená $\equiv$ má nulovou rezervu
	- hrana je nenasycená $\equiv$ má kladnou rezervu
	- 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

## 5. Pravděpodobnost a statistika

- Pravděpodobnostní prostor, náhodné jevy, pravděpodobnost (definice, příklady)
	- $\Omega$ … množina elementárních jevů
	- $\mathcal F\subseteq\mathcal P(\Omega)$ je prostor jevů, pokud…
		- $\emptyset,\Omega\in\mathcal F$
		- $A\in\mathcal F\implies A^c=\Omega\setminus A\in\mathcal F$
		- $A_1,A_2,\ldots\in\mathcal F\implies\bigcup A_i\in \mathcal F$
	- $P:\mathcal F\to[0,1]$ je pravděpodobnost, pokud…
		- $P(\Omega)=1$
		- $P(\bigcup A_i)=\sum P(A_i)$ pro $A_1,A_2,\ldots\in \mathcal F$ po dvou disjunktní
	- příklady pravděpodobnostních prostorů
		- klasický – tedy konečný s uniformní pravděpodobností, např. $\Omega=[6]$ (hod kostkou)
			- příklad elementárního jevu … padla šestka
			- příklad jevu … padlo sudé číslo
		- diskrétní – dovolíme cinknutou kostku (nevyžadujeme uniformní pravděpodobnost)
		- geometrický – např. „náhodně“ střílíme na terč, takže šance, že zasáhneme konkrétní oblast, je úměrná obsahu oblasti (ale může být i ve více než dvou dimenzích)
		- spojitý – schopný střelec se trefuje spíše do středu terče (opět dovolíme i jiné než uniformní rozdělení)
- Základní pravidla pro počítání s pravděpodobností
	- $P(A)+P(A^c)=1$
	- $A\subseteq B\implies P(B\setminus A)=P(B)-P(A)\implies P(A)\leq P(B)$
	- $P(A\cup B)=P(A)+P(B)-P(A\cap B)$
	- $P(A_1\cup A_2\cup\dots)\leq\sum_i P(A_i)$ … subaditivita, Booleova nerovnost
- Nezávislost náhodných jevů, podmíněná pravděpodobnost
	- jevy $A,B\in\mathcal F$ jsou nezávislé, pokud $P(A\cap B)=P(A)\cdot P(B)$
	- můžeme uvažovat i větší množiny jevů
		- jevy v množině jsou (vzájemně) nezávislé, pokud pro každou konečnou podmnožinu platí, že $P(\bigcap)=\prod P$
		- pokud podmínka platí jen pro dvouprvkové podmnožiny, jsou jevy *po dvou nezávislé*
	- pokud $A,B\in\mathcal F$ a $P(B)\gt 0$, definujeme podmíněnou pravděpodobnost $A$ při $B$ jako $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$
	- zjevně $P(A\cap B)=P(A)\cdot P(B\mid A)$
	- $P(A_1\cap A_2\cap \dots\cap A_n)=P(A_1)P(A_2\mid A_1)P(A_3\mid A_1\cap A_2)\dots P(A_n\mid A_1\cap\dots\cap A_{n-1})$
		- lze ukázat indukcí (nebo neformálně rozepsáním členů vpravo a vykrácením)
	- věta o úplné pravděpodobnosti
		- mějme $B_1,B_2,\dots$ rozklad $\Omega$
		- $P(A)=\sum_iP(B_i)\cdot P(A\mid B_i)$
			- sčítance s $P(B_i)=0$ považujeme za nulové
- Bayesův vzorec
	- mějme $B_1,B_2,\dots$ rozklad $\Omega$
	- $P(B_j\mid A)=\frac{P(B_j)\cdot P(A\mid B_j)}{\sum_i P(B_i)\cdot P(A\mid B_i)}$
- Náhodné veličiny a jejich rozdělení
	- náhodná veličina je funkce, která přiřazuje každému elementárnímu náhodnému jevu nějakou (obvykle číselnou) hodnotu
	- pro diskrétní náhodnou veličinu $X$ definujeme pravděpodobnostní funkci $p_X(x)=P(\set{X=x})$
	- spojité náhodné veličiny obvykle popisujeme pomocí distribuční funkce a hustoty
		- distribuční funkce náhodné veličiny $X$ je funkce $F_X:\mathbb R\to [0,1]$ definovaná předpisem $F_X(x):=P(X\leq x)$
		- zjevně $P(a\lt X\leq b)=F_X(b)-F_X(a)$
		- vlastnosti
			- $F_X$ je neklesající
			- $\lim_{x\to+\infty} F_X(x)=1$
			- $\lim_{x\to-\infty} F_X(x)=0$
			- $F_X$ je zprava spojitá
		- náhodná veličina $X$ se nazývá spojitá, pokud existuje nezáporná reálná funkce $f_X$ tak, že $F_X(x)=P(X\leq x)=\int_{-\infty}^x f_X(t)\text dt$
		- hustota $f_X$ … „limita histogramů“
		- zjevně $\int_{-\infty}^\infty f=1$
- Střední hodnota – linearita střední hodnoty, střední hodnota součinu nezávislých veličin, Markovova nerovnost
	- $\mathbb E(X)=\sum_{x\in\text{Im}(X)}x\cdot P(X=x)$
		- nebo $\mathbb E(X)=\int_{-\infty}^{\infty} x f_X(x)\text dx$
	- pozorování: $\mathbb E(X)=\sum_{\omega\in\Omega}X(\omega)\cdot P(\set{\omega})$
	- pravidlo naivního statistika
		- $\mathbb E(g(X))=\sum_{x\in\text{Im}(X)}g(x)P(X=x)$
		- nebo $\mathbb E(g(X))=\int_{-\infty}^\infty g(x)f_X(x)\text dx$
	- linearita $\mathbb E(aX+b)=a\mathbb E(X)+b$ plyne z PNS pro funkci $ax+b$
	- podmíněná střední hodnota $\mathbb E(X\mid B)=\sum_{x\in\text{Im}(X)}x\cdot P(X=x\mid B)$
	- věta o celkové střední hodnotě: $\mathbb E(X)=\sum_i P(B_i)\cdot \mathbb E(X\mid B_i)$
	- $\mathbb E(g(X,Y))=\sum_x\sum_y g(x,y) P(X=x\land Y=y)$
	- $\mathbb E(aX+bY)=a\mathbb E(X)+b\mathbb E(Y)$
	- pro nezávislé $X,Y$ platí $\mathbb E(XY)=\mathbb E(X)\mathbb E(Y)$
	- Markovova nerovnost
		- pro $X\geq 0$ a $a\gt0$ platí $P(X\geq a)\leq\frac{\mathbb E(X)}a$
- Rozptyl – definice, vzorec pro rozptyl součtu (závislých či nezávislých veličin)
	- rozptyl … $\text{var}(X)=\mathbb E((X-\mathbb EX)^2)$
	- směrodatná odchylka … $\sigma_X=\sqrt{\text{var}(X)}$
	- věta: $\text{var}(X)=\mathbb E(X^2)-\mathbb E(X)^2$
	- počítání s rozptylem
		- $\mathrm{var}(aX+b)=a^2\mathrm{var}(X)$
	- rozptyl součtu nezávislých veličin je součet rozptylů
		- $\mathrm{var}(X+Y)=\mathrm{var}(X)+\mathrm{var}(Y)$
	- kovariance a její vlastnosti
		- definice: $\text{cov}(X,Y)=\mathbb E((X-\mathbb EX)(Y-\mathbb EY))$
		- věta: $\text{cov}(X,Y)=\mathbb E(XY)-\mathbb E(X)\mathbb E(Y)$
		- pro nezávislé $X,Y$ platí $\text{cov}(X,Y)=0$
		- zjevně $\text{cov}(X,X)=\text{var}(X)$
		- $\text{cov}(aX+bY,Z)=a\text{cov}(X,Z)+b\text{cov}(Y,Z)$
		- korelace
			- $\rho(X,Y)=\frac{\text{cov}(X,Y)}{\sigma_X\cdot\sigma_Y}$
	- rozptyl součtu náhodných veličin (závislých i nezávislých)
		- nechť $X=\sum_{i=1}^n X_i$
		- pak $\text{var}(X)=\sum_{i=1}^n\sum_{j=1}^n\text{cov}(X_i,X_j)$
- Práce s konkrétními rozděleními: geometrické, binomické, Poissonovo, normální, exponenciální
	- Bernoulliho/alternativní rozdělení $\text{Ber}(p)$
		- počet úspěchů při jednom pokusu (kde $p$ je pravděpodobnost úspěchu)
		- $p_X(1)=p$
		- $p_X(0)=1-p$
		- jinak $p_X(x)=0$
		- $\mathbb E(X)=p$
		- $\text{var}(X)=p(1-p)$
	- geometrické rozdělení $\text{Geom}(p)$
		- při kolikátém pokusu poprvé uspějeme
		- $p_X(k)=(1-p)^{k-1}\cdot p$
		- $\mathbb E(X)=1/p$
		- $\text{var}(X)=\frac{1-p}{p^2}$
	- binomické rozdělení $\text{Bin}(n,p)$
		- počet úspěchů při $n$ nezávislých pokusech
		- $p_X(k)={n\choose k}p^k(1-p)^{n-k}$
		- $\mathbb E(X)=np$
		- $\text{var}(X)=np(1-p)$
	- Poissonovo rozdělení $\text{Pois}(\lambda)$
		- počet doručených zpráv za časový úsek, $\lambda$ je průměrná hodnota
		- $p_X(k)=\frac{\lambda^k}{k!}e^{-\lambda}$
		- $\text{Pois}(\lambda)$ je limitou $\text{Bin}(n,\lambda/n)$ pro $n\to\infty$
		- $\mathbb E(X)=\lambda$
		- $\text{var}(X)=\lambda$
	- uniformní $U(a,b)$
		- $f_X(x)=\frac 1{b-a}$
		- $F_X(x)=\frac{x-a}{b-a}$
		- $\mathbb E(X)=\frac{a+b}2$
		- $\text{var}(X)=\frac{(b-a)^2}{12}$
	- exponenciální $\text{Exp}(\lambda)$
		- $f_X(x)=\lambda e^{-\lambda x}$ pro $x\geq 0$
		- $F_X(x)=1-e^{-\lambda x}$ pro $x\geq 0$
		- $\mathbb E(X)=1/\lambda$
		- $\text{var}(X)=1/\lambda^2$
	- standardní normální rozdělení
		- $N(0,1)$
		- $f_X(x)=\varphi(x)=\frac1{\sqrt{2\pi}} e^{-x^2/2}$
	- obecné normální rozdělení
		- $N(\mu,\sigma^2)$
		- $f_X(x)=\frac 1{\sigma\sqrt{2\pi}}e^{-\frac12(\frac{x-\mu}{\sigma})^2}$
		- máme-li $X\sim N(\mu,\sigma^2)$, pak pro $Z=\frac{X-\mu}\sigma$ platí $Z\sim N(0,1)$
		- pro normální nezávislé náhodné veličiny $X_i\sim N(\mu_i,\sigma_i^2)$ (nechť je jich konečně) je i součet normální náhodná veličina $\sum X_i\sim N(\sum\mu_i,\sum\sigma_i^2)$
		- pravidlo $3\sigma$
			- $P(\mu-\sigma\lt X\lt\mu+\sigma)\doteq 0.68$
			- $P(\mu-2\sigma\lt X\lt\mu+2\sigma)\doteq 0.95$
			- $P(\mu-3\sigma\lt X\lt\mu+3\sigma)\doteq 0.997$
- Limitní věty: zákon velkých čísel
	- mějme $X_1,X_2,\dots$ stejně rozdělené nezávislé náhodné veličiny
	- $\bar X_n=(X_1+\dots+X_n)/n$ … výběrový průměr
	- silný zákon velkých čísel
		- $\lim_{n\to\infty}\bar X_n=\mu$ skoro jistě (s pravděpodobností 1)
		- použití: Monte Carlo integrování kruhu
	- slabý zákon velkých čísel (zlepšení přesnosti opakovaným měřením)
		- $\forall\varepsilon\gt 0:\lim_{n\to\infty} P(|\bar X_n-\mu|\gt\varepsilon)=0$
		- říkáme, že $\bar X_n$ konverguje k $\mu$ v pravděpodobnosti, píšeme $\bar X_n\xrightarrow P\mu$
- Limitní věty: centrální limitní věta
	- nechť $X_1,X_2,\dots$ jsou stejně rozdělené se střední hodnotou $\mu$ a rozptylem $\sigma^2$
	- označme $Y_n=\frac{(X_1+\dots+X_n)-n\mu}{\sigma\sqrt{n}}$
	- pak $Y_n\xrightarrow d N(0,1)$
		- $Y_n$ konverguje v distribuci k $N(0,1)$
		- tzn. $\lim_{n\to\infty} F_{Y_n}(x)=\Phi(x)$
	- CLV se hodí k aproximaci distribuce součtu nebo průměru velkého počtu náhodných veličin normálním rozdělením
		- takže můžeme provádět bodové a intervalové odhady i tam, kde data nejsou normálně rozdělená, ale známe rozptyl
- Bodové odhady – alespoň jedna metoda pro jejich tvorbu, vlastnosti
	- pro náhodný výběr $X_1,\dots,X_n\sim F_\theta$ a libovolnou funkci $g$ nazveme bodový odhad $\hat\theta_n$…
		- nevychýlený/nestranný, pokud $\mathbb E(\hat\theta_n)=g(\theta)$
		- asymptoticky nevychýlený, pokud $\lim_{n\to\infty}\mathbb E(\hat\theta_n)=g(\theta)$
		- konzistentní, pokud $\hat\theta_n\xrightarrow P g(\theta)$
	- dále definujeme
		- vychýlení … $\text{bias}(\hat\theta_n)=\mathbb E(\hat\theta_n)-\theta$
		- střední kvadratickou chybu … $\text{MSE}(\hat\theta_n)=\mathbb E((\hat\theta_n-\theta)^2)$
	- věta: $\text{MSE}(\hat\theta_n)=\text{bias}(\hat\theta_n)^2+\text{var}(\hat\theta_n)$
	- metoda momentů
		- $r$-tý moment $X$ … $\mathbb EX^r=m_r(\theta)$
		- $r$-tý výběrový moment … $\frac1n\sum_{i=1}^n X_i^r=\widehat{m_r}$
			- konzistentní nevychýlený odhad pro $r$-tý moment
		- nalezneme $\theta$ takové, že $m_r(\theta)=\widehat{m_r}$
		- typicky stačí použít první moment, dostaneme nějakou rovnici
		- $m_1=\mu$
		- $m_2=\mathbb E(X^2)=\text{var}(X)+(\mathbb EX)^2=\sigma^2+\mu^2$
	- metoda maximální věrohodnosti
		- $\hat\theta_{ML}=\text{argmax}_\theta\;p(x;\theta)$
			- $\text{argmax}_\theta\;f(x;\theta)$
			- abych se nemusel rozhodovat mezi $p$ a $f$, budu používat $L$
		- výpočetně jednodušší bude používat logaritmus $L$, který označíme $\ell$
		- příklad
			- ve vzorku $k$ leváků z $n$ lidí, hledáme pravděpodobnost $\theta$, že je někdo levák
			- $L(x;\theta)=\theta^k(1-\theta)^{n-k}$
			- $\ell(x;\theta)=k\log\theta+(n-k)\log(1-\theta)$
			- $\ell'(x;\theta)=\frac k\theta-\frac{n-k}{1-\theta}$
				- hledáme maximum, položíme derivaci rovnou nule (a zkontrolujeme krajní hodnoty)
		- podobně pro spojitý případ – „maximalizujeme“ rovnici pro pravděpodobnost konkrétního výběru
- Intervalové odhady: metoda založená na aproximaci normálním rozdělením
	- statistiky $D\leq H$ určují konfidenční interval o spolehlivosti $1-\alpha$, pokud $P(D\leq\theta\leq H)=1-\alpha$
		- zkráceně $(1-\alpha)$-CI
	- interval budeme uvažovat ve tvaru $[x-\delta,x+\delta]$
	- postup
		- máme nestranný bodový odhad $\hat\theta$ pro parametr $\theta$
		- $\hat\theta$ má normální rozdělení
		- $\hat\theta\pm z_{\alpha/2}\cdot\text{se}$ je $(1-\alpha)$-CI
			- $z_{\alpha/2}:=\Phi^{-1}(1-\alpha/2)$
			- $\text{se}:=\sigma(\hat\theta)$
- Testování hypotéz – základní přístup, chyby 1. a 2. druhu, hladina významnosti
	- nulová hypotéza … defaultní, konzervativní model
	- alternativní hypotéza … alternativní model, „zajímavost“
	- nulovou hypotézu buď zamítneme, nebo nezamítneme
	- chyba 1. druhu – chybné zamítnutí, „trapas“
	- chyba 2. druhu – chybné přijetí, „promarněná příležitost“
	- hladina významnosti $\alpha$ … pravděpodobnost chyby 1. druhu
		- typicky se volí $\alpha=0.05$
	- $\beta$ … pravděpodobnost chyby 2. druhu
	- kritický obor … je to množina, kterou určíme před provedením testu; pokud se výsledek našeho testu bude nacházet v kritickém oboru, zamítneme nulovou hypotézu
		- tedy $\alpha=P(h(X)\in W; H_0)$
	- síla testu … $1-\beta$
		- chceme co největší
	- $p$-hodnota … nejmenší $\alpha$ taková, že na hladině $\alpha$ zamítáme $H_0$

## 6. Logika

- 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.)
	- výroková logika
		- jazyk je určený neprázdnou množinou výrokových proměnných $\mathbb P$ (také jim říkáme prvovýroky nebo atomické výroky)
		- množina $\mathbb P$ může být konečná nebo i nekonečná (ale obvykle bude spočetná) a bude mít dané uspořádání
	- predikátová logika
		- signatura je dvojice $\braket{\mathcal {R,F}}$, kde $\mathcal{R,F}$ jsou disjunktní množiny symbolů (relační a funkční, ty zahrnují konstantní) spolu s danými aritami a neobsahují symbol $=$
		- do jazyka patří…
			- spočetně mnoho proměnných
			- relační, funkční a konstantní symboly ze signatury a symbol $=$, jde-li o jazyk s rovností
			- univerzální a existenční kvantifikátory pro každou proměnnou
			- symboly pro logické spojky a závorky
		- struktura v signatuře $\braket{\mathcal{R,F}}$ je trojice $\mathcal A=\braket{A,\mathcal{R^A,F^A}}$, kde…
			- $A$ je neprázdná množina, říkáme jí doména (také universum)
			- $\mathcal {R^A}$ je množina interpretací jednotlivých relačních symbolů (kde interpretace $n$-árního relačního symbolu je množina uspořádaných $n$-tic prvků z $A$)
			- $\mathcal {F^A}$ je množina interpretací jednotlivých funkčních symbolů (kde intepretace $n$-árního funkčního symbolu odpovídá funkci přiřazující $n$-tici prvků z $A$ jeden prvek z $A$)
				- speciálně pro konstantní symbol $c\in\mathcal F$ je $c^\mathcal A\in A$
		- termy jazyka $L$ jsou konečné nápisy definované induktivně
			- proměnná je term
			- konstantní symbol je term
			- pro $n$-ární funkční symbol $f$ a termy $t_1,\dots,t_n$ je nápis $f(t_1,\dots,t_n)$ také term
		- atomická formule jazyka $L$ je nápis $R(t_1,\dots,t_n)$, kde $R$ je $n$-ární relační symbol z $L$ (v jazyce s rovností to může být i rovnost) a $t_i$ je $L$-term
		- formule jazyka $L$ jsou konečné nápisy definované induktivně
			- atomická formule je formule
			- negace formule je formule
			- spojením dvou formulí binární logickou spojkou dostaneme formuli
			- přidáním kvantifikátoru před formuli dostaneme formuli
		- výskyt proměnné je vázaný, pokud jí odpovídá nějaký kvantifikátor, jinak je výskyt volný
		- proměnná je volná, pokud má volný výskyt, je vázaná, pokud má vázaný výskyt
		- formule je otevřená, neobsahuje-li žádný kvantifikátor
		- formule je uzavřená (= sentence), pokud nemá žádnou volnou proměnnou
		- term $t$ je substituovatelný za proměnnou $x$ ve formuli $\varphi$, pokud po simultánním nahrazení všech volných výskytů $x$ ve $\varphi$ za $t$ nevznikne ve $\varphi$ žádný vázaný výskyt proměnné z $t$
			- v tom případě říkáme vzniklé formuli instance $\varphi$ vzniklá substitucí $t$ za $x$ a označujeme ji $\varphi(x/t)$
- Prenexní tvary formulí predikátové logiky
	- PNF = kvantifikátory jsou před formulí, formule se dělí na kvantifikátorový prefix a otevřené jádro
	- převod na PNF – postupně kvantifikátory vytahuju (podle pravidel), v případě potřeby přejmenuju proměnnou, tím vznikne varianta (pokud je v druhé části formule volná proměnná se stejným názvem)
	- pravidlo převodu: pokud vytahujeme kvantifikátor z negace, musíme ho „přepnout“ (pozor: u implikace je levá strana jakoby negovaná)
- Znalost základních normálních tvarů (CNF, DNF, PNF)
	- PNF = kvantifikátory jsou před formulí, formule se dělí na kvantifikátorový prefix a otevřené jádro
	- tvary výroků
		- literál je prvovýrok nebo negace prvovýroku
			- pro literál $\ell$ označuje $\overline\ell$ literál k němu opačný (tedy jeho negaci)
		- klauzule je disjunkce literálů
			- jednotková klauzule je samotný literál
			- prázdná klauzule je $\bot$
		- výrok je v konjunktivní normální formě (CNF), pokud je konjunkcí klauzulí
			- prázdný výrok v CNF je $\top$
		- elementární konjunkce je konjunkce literálů
			- jednotková elementární konjunkce je samotný literál
			- prázdná elementární konjunkce je $\top$
		- výrok je v disjunktivní normální formě (DNF), pokud je disjunkcí elementárních konjunkcí
			- prázdný výrok v DNF je $\bot$
		- výrok je hornovský (v Hornově tvaru), pokud je konjunkcí hornovských klauzulí, tj. klauzulí obsahujících nejvýše jeden pozitivní literál
	- množinová reprezentace
		- klauzule je konečná množina literálů
			- prázdnou klauzuli označíme $\square$, není nikdy splněna
		- CNF formule je (konečná nebo nekonečná) množina klauzulí
			- prázdná formule $\emptyset$ je vždy splněna
- Převody na normální tvary
	- sémantický převod
		- najdeme modely výroku
		- pro DNF budeme uvažovat disjunkci elementárních konjunkcí, přičemž každá elementární konjunkce popíše jeden model
		- pro CNF musíme najít nemodely formule, každá klauzule zakáže jeden nemodel
			- pokud je první nemodel $(0,0,0)$, pak první klauzule bude $(p\lor q\lor r)$
	- syntaktický převod
		- přepíšeme implikaci a ekvivalenci pomocí konjunkce, disjunkce a negace
		- přesuneme negace dovnitř (k literálům)
		- použijeme distributivitu konjunkce a disjunkce, abychom jednu přesunuli dovnitř (podle toho, jestli chceme CNF nebo DNF)
- Použití normálních tvarů pro algoritmy (SAT, rezoluce)
	- problém Horn-SAT
		- výrok je hornovský, pokud je konjunkcí hornovských klauzulí, tj. klauzulí obsahujících nejvýše jeden pozitivní literál
		- algoritmus
			- pokud $\varphi$ obsahuje dvojici opačných jednotkových klauzulí, není splnitelný
			- pokud $\varphi$ neobsahuje žádnou jednotkovou klauzuli, je splnitelný, ohodnotíme všechny zbývající proměnné nulou
			- pokud $\varphi$ obsahuje jednotkovou klauzuli $\ell$, ohodnotíme literál $\ell$ hodnotou 1, provedeme jednotkovou propagaci a postup opakujeme
		- jednotková propagace pro $\ell=1$
			- každou klauzuli obsahující $\ell$ odstraníme (protože je takto splněna)
			- $\overline\ell$ odstraníme ze všech klauzulí, které ho obsahují (protože $\overline\ell$ nemůže zajistit splnění dané klauzule)
		- Horn-SAT lze řešit v lineárním čase
	- algoritmus DPLL pro řešení SAT
		- literál $\ell$ má čistý výskyt ve $\varphi$, pokud se $\ell$ vyskytuje ve $\varphi$ a opačný literál $\overline\ell$ se ve $\varphi$ nevyskytuje
			- takový literál můžu nastavit na 1
			- to neovlivní splnitelnost výroku, ale zmenší to množinu modelů, které jsem schopen nalézt
		- algoritmus
			- dokud $\varphi$ obsahuje jednotkovou klauzuli $\ell$, ohodnoť $\ell=1$ a proveď jednotkovou propagaci
			- dokud existuje literál $\ell$, který má ve $\varphi$ čistý výskyt, ohodnoť $\ell=1$ a odstraň klauzule obsahující $\ell$
			- pokud $\varphi$ neobsahuje žádnou klauzuli, je splnitelný
			- pokud $\varphi$ obsahuje prázdnou klauzuli, není splnitelný
			- jinak zvol dosud neohodnocenou výrokovou proměnnou $p$ a zavolej algoritmus rekurzivně na $\varphi\land p$ a na $\varphi\land\neg p$
		- algoritmus běží v exponenciálním čase
	- rezoluce
		- použitím rezolučního pravidla z klauzulí $\varphi\lor p$ a $\psi\lor\neg p$ dostaneme $\varphi\lor\psi$
		- takhle spolu můžeme postupně rezolvovat různé klauzule z teorie
		- pokud nám vyjde prázdná klauzule, je teorie sporná
		- k dokázání výroku $\varphi$ v teorii $T$ hledáme rezoluční zamítnutí $T\cup\neg\varphi$
			- nebo přímo rezoluční důkaz výroku $\varphi$ (tzn. na konci rezoluce nám vyjde $\varphi$)
- Pojem modelu teorie
	- model (jazyka) ve výrokové logice je pravdivostní ohodnocení proměnných
		- model $v$ je modelem teorie $T$, pokud každý axiom z $T$ v modelu $v$ platí, píšeme $v\models T$
	- v predikátové logice: model jazyka $L$ nebo také $L$-struktura je libovolná struktura v signatuře jazyka $L$
		- model teorie $T$ je $L$-struktura, ve které platí všechny axiomy teorie $T$
- Pravdivost, lživost, nezávislost formule vzhledem k teorii, splnitelnost, tautologie, důsledek
	- pravdivý výrok platí v každém modelu (jazyka/teorie)
		- je pravdivý v logice = platí v logice = je tautologie
		- je pravdivý v $T$ = platí v $T$ = je důsledek $T$
	- lživý (sporný) výrok neplatí v žádném modelu
	- nezávislý výrok platí v nějakém modelu a neplatí v jiném modelu
	- splnitelný výrok platí v nějakém modelu (tedy není lživý, je pravdivý nebo nezávislý)
- Analýza výrokových teorií nad konečně mnoha prvovýroky
	- nechť $T$ je bezesporná teorie nad $\mathbb P$
		- $|\mathbb P|=n\in\mathbb N^+$ … počet proměnných v jazyce
		- $m=|M_{\mathbb P}(T)|$ … velikost množiny modelů teorie $T$
	- neekvivalentních výroků nad $\mathbb P$ je $2^{2^n}$
		- každý výrok odpovídá jedné podmnožině množiny modelů (všech modelů je $2^n$)
	- neekvivalentních výroků nad $\mathbb P$ pravdivých/lživých v $T$ je $2^{2^n-m}$
	- neekv. výroků nad $\mathbb P$ nezávislých v $T$ je $2^{2^n}-2\cdot 2^{2^n-m}$
		- vezmeme všechny a odečteme pravdivé a lživé
	- neekv. jednoduchých extenzí teorie $T$ je $2^m$, z toho sporná je jedna
		- podle toho, které modely ubereme
	- neekv. kompletních jednoduchých extenzí teorie $T$ je $m$
		- každá odpovídá jednomu modelu
	- $T$-neekvivalentních výroků nad $\mathbb P$ je $2^m$
	- $T$-neekv. výroků nad $\mathbb P$ pravdivých/lživých (v $T$) je $1$
	- $T$-neekv. výroků nad $\mathbb P$ nezávislých (v $T$) je $2^m-2$
- Extenze teorií – schopnost porovnat sílu teorií, konzervativnost, skolemizace
	- extenze teorie $T$ je libovolná teorie $T'$ v jazyce $\mathbb P'\supseteq\mathbb P$ splňující $\text{Csq}_{\mathbb P}(T)\subseteq\text{Csq}_{\mathbb P'}(T')$
		- kde $\text{Csq}_\mathbb P(T)$ je množina všech důsledků teorie (výroků/sentencí pravdivých v teorii $T$ v jazyce $\mathbb P$)
	- extenze je jednoduchá, pokud $\mathbb P'=\mathbb P$
	- extenze je konzervativní, pokud $\text{Csq}_{\mathbb P}(T)=\text{Csq}_{\mathbb P}(T')=\text{Csq}_{\mathbb P'}(T')\cap\text{VF}_\mathbb P$
	- sémantický význam (v řeči modelů)
		- mějme teorii $T$ v jazyce $\mathbb P$ a teorii $T'$ v jazyce $\mathbb P'$, kde $\mathbb P\subseteq\mathbb P'$
		- $T'$ je jednoduchou extenzí $T$, právě když $\mathbb P'=\mathbb P$ a $M_\mathbb P(T')\subseteq M_\mathbb P(T)$
		- $T'$ je extenzí $T$, právě když $M_{\mathbb P'}(T')\subseteq M_{\mathbb P'}(T)$
		- $T'$ je konzervativní extenzí $T$, pokud je extenzí a navíc platí, že každý model $T$ lze nějak expandovat na model $T'$
		- $T'$ je extenzí $T$ a zároveň $T$ je extenzí $T'$, právě když $T'\sim T$ (jazyky a množiny modelů se rovnají)
		- kompletní jednoduché extenze $T$ jednoznačně až na ekvivalenci odpovídají modelům $T$
	- $T'$ je extenzí $T$ o definice, pokud vznikla z $T$ postupnou extenzí o definice relačních a funkčních (případně konstantních) symbolů
	- je-li $T'$ extenze teorie $T$ o definice, potom platí:
		- každý model teorie $T$ lze jednoznačně expandovat na model $T'$
		- $T'$ je konzervativní extenze $T$
		- pro každou $L'$-formuli $\varphi'$ existuje $L$-formule $\varphi$ taková, že $T'\models\varphi'\leftrightarrow\varphi$
	- Skolemova varianta sentence vzniká z původní PNF sentence skolemizací
		- skolemizace spočívá v tom, že tyto kroky iterujeme přes všechny existenční kvantifikátory $(\exists y_i)$
			- odstraníme z prefixu existenční kvantifikátor $(\exists y_i$)
			- za proměnnou $y_i$ substituujeme term $f_i(x_1,\dots,x_{n_i})$, kde $x_1,\dots,x_{n_i}$ jsou proměnné, jejichž univerzální kvantifikátory předcházejí $(\exists y_i)$
		- začínáme s $L$-sentencí v PNF, jejíž všechny vázané proměnné jsou různé
		- dostaneme $L'$-sentenci v PNF, kde $L'$ je rozšíření $L$ o nové $n_i$-ární funkční symboly
- Dokazatelnost – pojem formálního důkazu, zamítnutí; schopnost práce v některém z formálních dokazovacích systémů (např. tablo)
	- důkaz, zamítnutí
		- důkaz faktu, že v teorii $T$ platí výrok $\varphi$ je konečný syntaktický objekt vycházející z axiomů $T$ a výroku $\varphi$
		- důkaz konstruujeme syntakticky, aniž bychom se museli zabývat modely
		- po dokazovacím systému požadujeme dvě vlastnosti: korektnost (je-li výrok dokazatelný z $T$, je pravdivý v $T$) a úplnost (je-li výrok pravdivý v $T$, je dokazatelný z $T$)
		- důkaz říká, že $\varphi$ platí, zamítnutí říká, že $\varphi$ neplatí
			- rezoluční důkaz $\varphi$ v teorii $S$ má v kořeni $\varphi$, rezoluční zamítnutí teorie $S$ má v kořeni $\square$
	- tablo důkaz
		- konečné tablo z teorie $T$ je uspořádaný, položkami označkovaný strom zkonstruovaný aplikací konečně mnoha následujících pravidel:
			- jednoprvkový strom označkovaný libovolnou položkou je tablo z teorie $T$
			- pro libovolnou položku $P$ na libovolné větvi $V$ můžeme na konec větve $V$ připojit atomické tablo pro položku $P$
			- na konec libovolné větve můžeme připojit položku $\text T\alpha$ pro libovolný axiom teorie $\alpha\in T$
		- tablo je konečné nebo nekonečné, každopádně vzniklo ve spočetně mnoha krocích
		- tablo pro položku $P$ je tablo s položkou $P$ v kořeni
		- tablo důkaz výroku $\varphi$ z teorie $T$ je sporné tablo z teorie $T$ s  položkou $\text F\varphi$ v kořeni
			- pokud existuje, je $\varphi$ tablo dokazatelný z $T$, píšeme $T\vdash\varphi$
			- podobně definujeme tablo zamítnutí s $\text T\varphi$ v kořeni, tablo zamítnutelnost se značí $T\vdash \neg\varphi$
		- tablo je sporné, pokud je každá jeho větev sporná
		- větev je sporná, pokud obsahuje položky $\text T\psi$ a $\text F\psi$ pro nějaký výrok $\psi$, jinak je bezesporná
		- tablo je dokončené, pokud je každá jeho větev dokončená
		- větev je dokončená…
			- pokud je sporná
			- nebo pokud je každá její položka na této větvi redukovaná a pokud větev zároveň obsahuje položku s T pro každý axiom teorie
		- položka je redukovaná na dané větvi, pokud obsahuje pouze výrokovou proměnnou nebo se na dané větvi vyskytuje jako kořen atomického tabla (tedy došlo k jejímu rozvoji na dané větvi)
		- v predikátové logice navíc řešíme kvantifikátory – položky typu *svědek* a *všichni*
- 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, právě když každá její konečná část má model
	- aplikace
		- popíšeme požadovanou vlastnost nekonečného objektu pomocí (nekonečné) výrokové teorie
		- z konečné části teorie sestrojíme konečný podobjekt mající danou vlastnost
	- příklady
		- spočetně nekonečný graf je bipartitní $\iff$ každý jeho konečný podgraf je bipartitní
			- $T=\set{p_u\to\neg p_v\mid\set{u,v}\in E(G)}$
		- nestandardní model přirozených čísel
			- vezmeme standardní model přirozených čísel (jeho teorii)
			- přidáme nový konstantní symbol
			- přidáme k teorii výrok, že je ta konstanta ostře větší než každý $n$-tý numerál
			- každá konečná část této nové teorie má model, takže i celá ta nová teorie má 
	- První věta o neúplnosti: Pro každou bezespornou rekurzivně axiomatizovanou extenzi $T$ Robinsonovy aritmetiky existuje sentence, která je pravdivá v $\underline{\mathbb N}$, ale není dokazatelná v $T$.
		- Robinsonova aritmetika je teorie jazyka aritmetiky $L=\braket{S,+,\cdot,0,\leq}$ s rovností
			- má osm (tradičně spíše sedm) axiomů, některé z nich:
				- $S(x)\neq 0$
				- $S(x)=S(y)\to x=y$
				- $x+0=x$
				- $x+S(y)=S(x+y)$
		- $\underline{\mathbb N}=\braket{\mathbb N,S,+,\cdot,0,\leq}$ … standardní model přirozených čísel
	- důsledek 1.1: je-li $T$ rekurzivně axiomatizovaná extenze Robinsonovy aritmetiky a je-li navíc $\underline{\mathbb N}$ modelem teorie $T$, potom $T$ není kompletní
		- pro sentenci, která není dokazatelná v $T$, nemůže být dokazatelná ani její negace (byl by to spor s její pravdivostí v $\underline{\mathbb N}$)
	- důsledek 1.2: teorie $\text{Th}(\underline{\mathbb N})$ není rekurzivně axiomatizovatelná
		- kdyby byla, nemohla by být kompletní – ale ona kompletní je
		- značení: $\text{Th}(\underline{\mathbb N})$ … množina všech sentencí pravdivých v $\underline{\mathbb N}$ (tzv. teorie struktury $\underline{\mathbb N}$)
	- věta (Rosserův trik): v každé bezesporné rekurzivně axiomatizované extenzi Robinsonovy aritmetiky existuje nezávislá sentence – tedy taková není kompletní
		- v podstatě plyne z důsledku 1.1, jen se zbavuje $\underline{\mathbb N}$ 
	- Druhá věta o neúplnosti: Pro každou bezespornou rekurzivně axiomatizovanou extenzi $T$ Peanovy aritmetiky platí, že $\mathit{Con_T}$ není dokazatelná v $T$.
	- $\mathit{Con_T}$ … sentence vyjadřující bezespornost (konzistence) teorie $T$
		- $\mathit{Con_T}=\neg(\exists y)\mathit{Prf_{T}}(\underline{0=S(0)},y)$
		- $\mathit{Prf_{T}}(x,y)$ … $y$ je důkaz $x$ v $T$
	- důsledek 2.1: existuje model Peanovy aritmetiky (PA), ve kterém platí sentence $(\exists y)\mathit{Prf_{PA}}(\underline{0=S(0)},y)$
	- důsledek 2.2: existuje bezesporná rekurzivně axiomatizovaná extenze $T$ Peanovy aritmetiky, která dokazuje svou spornost, tj. taková, že $T\vdash\neg \mathit{Con_T}$
	- důsledek 2.3: je-li teorie množin ZFC bezesporná, nemůže být sentence $\mathit{Con_{ZFC}}$ v teorii ZFC dokazatelná
- Rozhodnutelnost – pojem kompletnosti a její kritéria, význam pro rozhodnutelnost; příklady rozhodnutelných a nerozhodnutelných teorií
	- teorie je sporná, jestliže… (ekvivalentně)
		- v ní platí spor
		- nemá žádný model
		- v ní platí všechny výroky
	- teorie je bezesporná (splnitelná), pokud není sporná, tj. má nějaký model
	- teorie je kompletní jestliže není sporná a každý výrok (respektive sentence) je v ní pravdivý nebo lživý (tj. nemá žádné nezávislé výroky), ekvivalentně, pokud má právě jeden model (až na elementární ekvivalenci v predikátové logice)
		- struktury $\mathcal{A,B}$ (v témž jazyce) jsou elementárně ekvivalentní, pokud v nich platí tytéž sentence (značíme $\mathcal A\equiv \mathcal B$)
		- zjevně $\mathcal A\equiv \mathcal B\iff\text{Th}(\mathcal A)=\text{Th}(\mathcal B)$
	- o teorii $T$ říkáme, že je…
		- rozhodnutelná, pokud existuje algoritmus, který pro každou vstupní formuli $\varphi$ doběhne a odpoví, zda $T\models\varphi$
		- částečně rozhodnutelná, pokud existuje algoritmus, který pro každou vstupní formuli $\varphi$…
			- pokud $T\vDash\varphi$, doběhne a odpoví „ano“
			- pokud $T\nvDash\varphi$, buď nedoběhne, nebo doběhne a odpoví „ne“
	- „rekurzivní“ pojmy
		- teorie $T$ je rekurzivně axiomatizovaná, pokud existuje algoritmus, který pro každou vstupní formuli $\varphi$ doběhne a odpoví, zda $\varphi\in T$
		- třída $L$-struktur $K\subseteq M_L$ je rekurzivně axiomatizovatelná, pokud existuje rekurzivně axiomatizovaná $L$-teorie $T$ taková, že $K=M_L(T)$
		- teorie $T'$ je rekurzivně axiomatizovatelná, pokud je rekurzivně axiomatizovatelná třída jejích modelů, neboli pokud je $T'$ ekvivalentní nějaké rekurzivně axiomatizované teorii
		- řekneme, že teorie $T$ má rekurzivně spočetnou kompletaci, pokud (nějaká) množina (až na ekvivalenci) všech jednoduchých kompletních extenzí teorie $T$ je rekurzivně spočetná, tj. existuje algoritmus, který pro danou vstupní dvojici přirozených čísel $(i,j)$ vypíše na výstup $i$-tý axiom $j$-té extenze (v nějakém pevně daném uspořádání), nebo odpoví, že takový axiom už neexistuje
	- tvrzení: je-li $T$ rekurzivně axiomatizovaná, potom je částečně rozhodnutelná, je-li navíc kompletní, je rozhodnutelná
	- tvrzení: je-li $\mathcal A$ konečná struktura v konečném jazyce s rovností, potom je teorie $\text{Th}(\mathcal A)$ rekurzivně axiomatizovatelná
	- tvrzení: pokud je teorie $T$ rekurzivně axiomatizovaná a má rekurzivně spočetnou kompletaci, potom je $T$ rozhodnutelná
	- nerozhodnutelnost
		- mějme formuli $\varphi$ ve tvaru $(\exists x_1)\dots(\exists x_n) \;p(x_1,\dots,x_n)=q(x_1,\dots,x_n)$
			- kde $p$ a $q$ jsou polynomy s přirozenými koeficienty
			- věta: neexistuje algoritmus, který by pro danou dvojici polynomů s přirozenými koeficienty rozhodl, zda mají přirozené řešení, tj. zda platí $\underline{\mathbb N}\vDash\varphi$
		- věta: neexistuje algoritmus, který by pro danou vstupní formuli $\varphi$ rozhodl, zda je logicky platná (tedy zda je tautologie)
	- příklady rozhodnutelných teorií
		- teorie čisté rovnosti (bez axiomů, v jazyce $L=\braket{}$ s rovností)
		- teorie unárního predikátu (bez axiomů, v jazyce $L=\braket{U}$ s rovností, kde $U$ je unární relační symbol)
		- teorie hustých lineárních uspořádání DeLO\*
		- teorie komutativních grup
		- teorie Booleových algeber
		- teorie následníka s nulou
		- Presburgerova aritmetika
	- příklady nerozhodnutelných teorií
		- Robinsonova aritmetika (a také Peanova aritmetika a ZFC, což jsou její extenze)
		- teorie (obecných) grup