The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b4b01dma [2025/05/28 11:24] – mistrjirka
+++ statnice:bakalar:b4b01dma [2025/05/31 10:26] (current) – [Příklad 2 – násobný kořen] mistrjirka
@@ Line 1: / Line 1: @@
-==== Způsoby popisu rozdělení náhodných veličin a vektorů. Odhady parametrů rozdělení. Základní statistické testy. Markovské řetězce a jejich asymptotické vlastnosti. ====
+====== Vlastnosti celých čísel, Euklidův algoritmus. Binární relace. Matematická indukce, rekurzivní vztahy. ======
-[[https://fel.cvut.cz/cz/education/bk/predmety/46/81/p4681506.html|B0B01PST]] [[https://cmp.felk.cvut.cz/~navara/stat/index.htm|Webové stránky předmětu]] [[https://math.fel.cvut.cz/en/people/heliskat/01pst2.html|Helisova stránky předmětu]]
+[[https://fel.cvut.cz/cz/education/bk/predmety/46/80/p4680906.html|B4B01DMA]] [[https://math.fel.cvut.cz/cz/lide/habala/teaching/dma/dmasch.htm|Webové stránky předmětu]]
-  * **Definice pravděpodobnosti (Kolmogorovova)** – nezávislost náhodných jevů, podmíněná pravděpodobnost, Bayesova věta. Pojem náhodné veličiny, popis jejího rozdělení pomocí distribuční funkce, hustoty, pravděpodobnostní funkce. Střední hodnota, rozptyl, směrodatná odchylka, momenty náhodných veličin. Základní typy spojitých a diskrétních rozdělení.
+  * **Dělitelnost** – definice, základní vlastnosti (například tranzitivita), výpočet gcd(a, b).
-  * **Náhodné vektory a jejich popis** – nezávislost náhodných veličin, kovariance a korelace.
+  * **Celá čísla modulo n** – definice kongruence, pravidla počítání, inverzní číslo a podmínky jeho existence.
-  * **Čebyševova nerovnost** – centrální limitní věta.
+  * **Bezoutova identita** – vyjádření gcd jako lineární kombinace čísel a, b. Využití pro řešení diofantických rovnic a hledání inverzního čísla modulo n.
-  * **Základní pojmy statistiky** – náhodný výběr, empirické rozdělení.
+  * **Euklidův algoritmus** – teorie a praxe výpočtu gcd postupným dělením se zbytkem. Rozšířená verze umožňující získat Bezoutovu identitu.
-  * **Obecné vlastnosti odhadů parametrů** – odhady střední hodnoty, rozptylu, směrodatné odchylky, momentů. Odhady parametrů metodou momentů a metodou maximální věrohodnosti. Intervalové odhady.
+  * **Binární relace** – definice a příklady. Čtyři základní vlastnosti: reflexivita, symetrie, antisymetrie, tranzitivita. Ilustrace grafem relace nebo příklady ze života.
-  * **Princip statistického testování hypotéz** – testy střední hodnoty a rozptylu, porovnání dvou rozdělení, $\chi^2$-test dobré shody, test nezávislosti v kontingenční tabulce.
+  * **Indukce** – princip matematické indukce, slabá a silná verze, ilustrace na jednoduchých důkazech.
-  * **Markovovy řetězce** – základní pojmy a vlastnosti, popis přechodovým diagramem a maticí přechodu. Klasifikace stavů, periodicita, rozložitelnost. Asymptotické chování Markovových řetězců.
+  * **Rekurentní rovnice** – vlastnosti homogenních lineárních rekurentních rovnic. Řešení jako vektorový prostor s bází určenou kořeny charakteristického polynomu.
+===== 1. Dělitelnost =====
-===== Definice pravděpodobnosti (Kolmogorovova) =====
+==== Definice, základní vlastnosti (tranzitivita a podobně), gcd(a,b). ====
-**Definice pravděpodobnosti (Kolmogorovova)** – nezávislost náhodných jevů, podmíněná pravděpodobnost, Bayesova věta. Pojem náhodné veličiny, popis jejího rozdělení pomocí distribuční funkce, hustoty, pravděpodobnostní funkce. Střední hodnota, rozptyl, směrodatná odchylka, momenty náhodných veličin. Základní typy spojitých a diskrétních rozdělení.
-<markdown>
+Nechť $a,b\in \mathbb{Z}$. Řekneme, že $a$ dělí $b$, značeno $a \mid b$, jestliže existuje $k \in \mathbb{Z}$ takové, že $b = k \cdot a$. V takovém případě říkáme, že **$a$ je dělitel (faktor) čísla $b$** a že **$b$ je násobek čísla $a$**. Pokud toto není pravda, značíme $a \nmid b$.
-Kolmogorovova definice pravděpodobnosti je založená na axiomech, které stanovují základní vlastnosti pravděpodobnostních jevů. Tyto axiomy jsou:
-</markdown>
-  * **Axiom nezápornosti**: Pravděpodobnost každého jevu je nezáporná, tj. $P(A) \geq 0$ pro každý jev A.
-  * **Axiom normovanosti**: Pravděpodobnost jistého jevu (celého prostoru) je rovna 1, tj. $P(\omega) = 1$.
-  * **Axiom aditivity**: Pro dva neslučitelné jevy A a B platí, že pravděpodobnost jejich sjednocení je rovna součtu jejich pravděpodobností, tj. $P(A \cup B) = P(A) + P(B)$.
-==== Podmíněná pravděpodobnost ====
-**Podmíněná pravděpodobnost** je pravděpodobnost jevu A za předpokladu, že nastal jev B. Definuje se jako:
-$$P(A|B) = \frac{P(A \cap B)}{P(B)}, \quad P(B) > 0$$
-Tato rovnice říká, že podmíněná pravděpodobnost A vzhledem k B je rovna poměru pravděpodobnosti průniku A a B k pravděpodobnosti B.
-Z toho vyplývá tato identita:
+Tato relace je:
-$$P(A) = P(A|B)P(B) + P(A|B^c)P(B^c)$$
+  * **reflexivní** – každé číslo dělí samo sebe, $a \mid a$.
+  * **tranzitivní** – pokud $a \mid b$ a $b \mid c$, pak $a \mid c$.
+  * **antisymetrická** – pokud $a \mid b$ a $b \mid a$, pak $|a| = |b|$.
+  * **nesymetrická** – obecně neplatí, že $a \mid b \Rightarrow b \mid a$.
-==== Bayesova věta ====
+Množina $\mathbb{Z}$ je uzavřená na operace sčítání, odčítání i násobení.
-**Bayesova věta** je důležitý nástroj pro výpočet podmíněných pravděpodobností. Umožňuje přepočítat pravděpodobnost jevu A za předpokladu, že nastal jev B, a to pomocí následujícího vzorce:
-$$
-P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$
-Tento vzorec ukazuje, jak lze využít pravděpodobnost B vzhledem k A a apriorní pravděpodobnost A k výpočtu podmíněné pravděpodobnosti A vzhledem k B.
-==== Náhodná veličina ====
+==== Společný dělitel a GCD ====
-Měřitelná funkce, která přiřazuje každému elementárnímu jevu reálné číslo. Jeji chování popisuje neklesající distribuční funkce $F(t) = P(X \leq t)$, kde $X$ je náhodná veličina a $t$ je reálné číslo. Distribuční funkce přiděluje každému reálnému číslu pravděpodobnost (hodnoty od 0 do 1), že náhodná veličina nabude hodnoty menší nebo rovné tomuto číslu.
-Hustota pravděpodobnosti je derivací distribuční funkce, pokud existuje:
+Číslo $d \in \mathbb{N}$ je **společný dělitel** (common divisor) čísel $a$, $b$, pokud $d \mid a$ a $d \mid b$.
-$$
-f(t) = \frac{dF(t)}{dt}$$
+Největší společný dělitel (greatest common divisor) čísel $a$ a $b$ označujeme $\text{gcd}(a,b)$ a definujeme jako největší číslo, které dělí obě čísla:
-$$ f(t) \geq 0$$
-Pravděpodobnostní funkce je funkce $p_x(t) = P(X = t)$, která udává pravděpodobnost, že náhodná veličina $X$ nabude konkrétní hodnoty $t$.
-=== Diskrétní náhodná veličina ===
-Nabývá konečný počet hodnot, distrbuční funkce je schodová funkce, pravděpodobnostní funkce je dána jako:
 $$
-p(t) = P(X = t) = \sum_{i} p_i \delta(t - t_i)
+n = \text{gcd}(a,b) \iff n \mid a \land n \mid b \land \forall d \in \mathbb{Z}: (d \mid a \land d \mid b \Rightarrow d \leq n)
 $$
+Platí:
+  * $\text{gcd}(0, 0) = 0$
+  * $\text{gcd}(a, 0) = |a|$
+  * $\text{gcd}(a, b) = \text{gcd}(|a|, |b|)$ – používáme nezáporné hodnoty
-{{:statnice:bakalar:pasted:20250526-103518.png}}
+==== Poznámky ====
+  * Dvě čísla $a$, $b$ jsou **nesoudělná**, pokud $\text{gcd}(a,b) = 1$.
+  * Existuje také pojem **společný násobek**: $m$ je společný násobek čísel $a$, $b$, pokud $a \mid m$ a $b \mid m$.
+  * Nejmenší takové $m$ je **nejmenší společný násobek** (lcm), značíme $\text{lcm}(a,b)$.
+  * Platí:
+    $$
+    \text{lcm}(a, b) \cdot \text{gcd}(a, b) = |a| \cdot |b|
+    $$
+  * pokud $a, b \neq 0$.
+  * Pro libovolné $a$: $\text{lcm}(a, 0) = 0$
+  * Lze se k tomu dostat přes prvočíslený rozklad  nebo Euklidův algoritmus.
-=== Spojitá náhodná veličina ===
+===== 2. Celá čísla modulo n =====
-Nabývá nekonečný počet hodnot, distribuční funkce je spojitá a pravděpodobnostní funkce je dána jako hustota pravděpodobnosti. Ale pravděpodobnost, že náhodná veličina nabude konkrétní hodnoty, je vždy 0. Hustota pravděpodobnosti je definována jako:
-$$
-f(t) = \frac{dF(t)}{dt}
-$$
-{{:statnice:bakalar:pasted:20250526-103420.png}}
-=== Smíšená náhodná veličina ===
-Nabývá jak diskrétních, tak spojitých hodnot. Distribuční funkce je kombinací schodové a spojité části. Hustota pravděpodobnosti je definována jako:
-$$
-f(t) = \sum_{i} p_i \delta(t - t_i) + f_c(t),$$
-kde $p_i$ jsou pravděpodobnosti diskrétních hodnot $t_i$ a $f_c(t)$ je hustota spojité části.
-==== Střední hodnota, rozptyl a směrodatná odchylka ====
+– co je kongruence, jak se tam počítá, co je inverzní číslo a kdy existuje.
-**Střední hodnota** (očekávaná hodnota) náhodné veličiny $X$ je definována jako:
-$$
-E(X) = \int_{-\infty}^{\infty} t f(t) dt,$$
-kde $f(t)$ je hustota pravděpodobnosti pro spojitou náhodnou veličinu, nebo pro diskrétní náhodnou veličinu:
-$$
-E(X) = \sum_{i} t_i p_i,$$
-kde $t_i$ jsou hodnoty, které náhodná veličina $X$ může nabývat, a $p_i$ jsou jejich pravděpodobnosti.
-**Rozptyl** náhodné veličiny $X$ je definován jako:
-$$
-Var(X) = E((X - E(X))^2) = E(X^2) - (E(X))^2,$$
-kde $E(X^2)$ je očekávaná hodnota druhé mocniny náhodné veličiny.
-**Směrodatná odchylka** je druhá odmocnina rozptylu:
-$$
-\sigma(X) = \sqrt{Var(X)}$$
-**Moment** náhodné veličiny $X$ je definován jako:
-$$
-M_k(X) = E(X^k) = \int_{-\infty}^{\infty} t^k f(t) dt,$$
-pro $k = 1, 2, \ldots$
-Pro diskrétní náhodnou veličinu je moment definován jako:
-$$
-M_k(X) = \sum_{i} t_i^k p_i,$$
-kde $t_i$ jsou hodnoty, které náhodná veličina $X$ může nabývat, a $p_i$ jsou jejich pravděpodobnosti.
-==== Základní typy rozdělení ====
-=== Diskrétní rozdělení ===
-**Binomické rozdělení** – popisuje počet úspěchů v $n$ nezávislých Bernoulliho pokusech, kde každý pokus má pravděpodobnost úspěchu $p$. Distribuční funkce je dána jako:
-$$
-P(X = k) = \binom{n}{k} p^k (1 - p)^{n - k}, \quad k = 0, 1, \ldots, n$$
-**Poissonovo rozdělení** – popisuje počet událostí, které nastanou v pevném časovém intervalu, pokud jsou tyto události nezávislé a nastávají s konstantní průměrnou rychlostí $\lambda$. Distribuční funkce je dána jako:
-$$
-P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}, \quad k = 0, 1, 2, \ldots$$
-**Geometrické rozdělení** – popisuje počet pokusů potřebných k dosažení prvního úspěchu v sérii nezávislých Bernoulliho pokusů. Distribuční funkce je dána jako:
-$$
-P(X = k) = (1 - p)^{k - 1} p, \quad k = 1, 2, \ldots$$
-**Alternativní rozdělení** – popisuje počet pokusů potřebných k dosažení prvního úspěchu v sérii nezávislých Bernoulliho pokusů, ale s různými pravděpodobnostmi úspěchu v jednotlivých pokusech. Distribuční funkce je dána jako:
-$$
-P(X = k) = \prod_{i=1}^{k-1} (1 - p_i) p_k, \quad k = 1, 2, \ldots$$
-**Rovnoměrné rozdělení** – popisuje náhodnou veličinu, která může nabývat hodnot v intervalu $[a, b]$ s rovnoměrnou pravděpodobností. Distribuční funkce je dána jako:
-$$
-P(X = k) = \frac{1}{b - a + 1}, \quad k = a, a + 1, \ldots, b$$
-**Hypergeometrické rozdělení** – popisuje počet úspěchů v náhodném výběru $n$ položek z populace o velikosti $N$, která obsahuje $K$ úspěšných položek. Distribuční funkce je dána jako:
-$$
-P(X = k) = \frac{\binom{K}{k} \binom{N - K}{n - k}}{\binom{N}{n}}, \quad k = 0, 1, \ldots, \min(K, n)$$
-Napřiklad "M" losů z nichž "J" vyhrává, tak udává počet výherních losů, z výtažených "S" losů.
-$$
-E(x) = \frac{(J \cdot S)}{M}
-$$
-=== Spojitá rozdělení ===
+==== Modulo ====
-**Rovnoměrné rozdělení** – popisuje náhodnou veličinu, která může nabývat hodnot v intervalu $[a, b]$ s rovnoměrnou pravděpodobností. Distribuční funkce je dána jako:
-$$
-F(x) = \begin{cases}
-, & x < a \\
-\frac{x - a}{b - a}, & a \leq x < b \\
-, & x \geq b
-\end{cases}
-$$
-Hustota je tvaru
-$$
-f(x) = \begin{cases}
-\frac{1}{b - a}, & a < x < b \\
-, & \text{jinak}
-\end{cases}
-$$
-**Normální rozdělení** – popisuje náhodnou veličinu, která má symetrické rozdělení kolem střední hodnoty $\mu$ a standardní odchylky $\sigma$. Distribuční funkce je dána jako:
+**Modulo** znamená „zbytek po dělení“. Zapisujeme jako $a \bmod n$ a označuje zbytek po celočíselném dělení $a$ číslem $n$.
-$$
-\Phi(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{x} e^{-\frac{t^2}{2}}\,dt.
-$$
-Hustota je tvaru
+Příklad: $17 \bmod 5 = 2$, protože $17 = 3 \cdot 5 + 2$.
-$$
-f(x) = \frac{1}{\sqrt{2 \pi}} e^{-\frac{x^2}{2}}
-$$
-**Exponenciální rozdělení** – popisuje čas mezi událostmi v Poissonově procesu. Distribuční funkce je dána jako:
-$$
-F(x) = 1 - e^{-\lambda x}, \quad x \geq 0$$
-Hustota pravděpodobnosti je dána jako:
-$$
-f(x) = \lambda e^{-\lambda x}, \quad x \geq 0$$
-===== Náhodné vektory a jejich popis =====
-**Náhodné vektory a jejich popis** – nezávislost náhodných veličin, kovariance a korelace.
-**Náhodný vektor** je n-rozměrný vektor $(X_1, X_2, \ldots, X_n)$, kde každá složka $X_i$ je náhodná veličina (Měřitelná funkce, která přiřazuje každému elementárnímu jevu reálné číslo) definovaná na stejném pravděpodobnostním prostoru.
+==== Kongruence ====
-Společná distribuční funkce náhodného vektoru je definována jako:
+Čísla $a,b\in \mathbb{Z}$ jsou **kongruentní modulo** $n$, pokud mají stejný zbytek po dělení $n$.
+Formálně:
 $$
-F(x_1, x_2, \ldots, x_n) = P(X_1 \leq x_1, X_2 \leq x_2, \ldots, X_n \leq x_n)
+a \equiv b \pmod{n} \iff n \mid (a - b)
 $$
+což znamená, že existuje $k \in \mathbb{Z}$ takové, že $a = b + kn$.
-Pro spojitý náhodný vektor existuje společná hustota pravděpodobnosti $f(x_1, x_2, \ldots, x_n)$ taková, že:
+Ekvivalentně také platí:
 $$
-F(x_1, x_2, \ldots, x_n) = \int_{-\infty}^{x_1} \int_{-\infty}^{x_2} \cdots \int_{-\infty}^{x_n} f(t_1, t_2, \ldots, t_n) dt_1 dt_2 \cdots dt_n
+a \bmod n = b \bmod n
 $$
-==== Nezávislost náhodných veličin ====
+Kongruence vytváří **ekvivalenční relaci** na množině $\mathbb{Z}$ a rozděluje ji do tříd zbytků.
-Náhodné veličiny $X_1, X_2, \ldots, X_n$ jsou **nezávislé**, pokud pro libovolné hodnoty $x_1, x_2, \ldots, x_n$ platí:
+Každé číslo $a$ patří do třídy zbytků $[a]_n$, která obsahuje všechna čísla kongruentní s $a$ modulo $n$.
+==== Počítání v $\mathbb{Z}_n$ ====
+Nechť $n \in \mathbb{N}$, a platí $a \equiv u \pmod{n}$ a $b \equiv v \pmod{n}$, pak:
+  * $a + b \equiv u + v \pmod{n}$
+  * $a - b \equiv u - v \pmod{n}$
+  * $ab \equiv uv \pmod{n}$
+Tyto operace v modulo aritmetice definují strukturu **komutativního okruhu** $\mathbb{Z}_n$ (množina všech zbytkových tříd modulo $n$).
+Alternativní zápis (například v kryptografii nebo při implementaci):
+  * $a \oplus b = (a + b) \bmod n$
+  * $a \odot b = (a \cdot b) \bmod n$
+==== Inverzní číslo ====
+Nechť $a \in \mathbb{Z}$ a $n \in \mathbb{N}$. Číslo $x \in \mathbb{Z}$ je **inverzní k $a$ modulo $n$**, pokud:
 $$
-F(x_1, x_2, \ldots, x_n) = F_1(x_1) \cdot F_2(x_2) \cdots F_n(x_n)
+a \cdot x \equiv 1 \pmod{n}
 $$
-kde $F_i(x_i)$ je marginální distribuční funkce náhodné veličiny $X_i$.
-Pro spojité náhodné veličiny je podmínka nezávislosti ekvivalentní s:
+Takové $x$ převádí $a$ na jedničku v $\mathbb{Z}_n$, čímž umožňuje dělení (násobení inverzní hodnotou).
+**Podmínka existence**: Inverzní číslo existuje právě tehdy, když $\text{gcd}(a,n) = 1$, tj. $a$ a $n$ jsou nesoudělná čísla. Pokud existuje, je v $\mathbb{Z}_n$ jednoznačné.
+**Výpočet**:
+  * Pomocí **rozšířeného Eukleidova algoritmu** – najdeme $x, y \in \mathbb{Z}$ tak, že $a \cdot x + n \cdot y = 1$, potom $x \bmod n$ je hledané inverzní číslo.
+  * Inverzi nelze spočítat, pokud $a$ a $n$ mají společného dělitele většího než 1 (například $2^{-1} \bmod 4$ neexistuje).
+==== Prvočísla ====
+Prvočísla hrají v počítání modulo důležitou roli.
+**Definice**: Přirozené číslo $p > 1$ je **prvočíslo**, pokud jeho jedinými děliteli jsou $1$ a $p$.
+V $\mathbb{Z}_p$ pro prvočíslo $p$ má **každý nenulový prvek inverzi** – $\mathbb{Z}_p$ je tedy pole.
+Čísla, která nejsou prvočísla a mají více než dva různé dělitele, nazýváme **složená čísla**.
+===== 3. Bezoutova identita =====
+– Která gcd poskytne jako lineární kombinaci čísel $a,b$. K čemu se dá použít: hledání inverzního čísla ve světě modulo, řešení diofantických rovnic.
+Bezoutova identita říká, že největší společný dělitel dvou čísel $a, b \in \mathbb{Z}$ lze zapsat jako jejich lineární kombinaci s celočíselnými koeficienty:
 $$
-f(x_1, x_2, \ldots, x_n) = f_1(x_1) \cdot f_2(x_2) \cdots f_n(x_n)
+\gcd(a,b) = \alpha a + \beta b \quad \text{pro nějaká } \alpha, \beta \in \mathbb{Z}
 $$
-==== Kovariance a korelace ====
+Tato identita je základem pro řadu dalších výsledků v teorii čísel, zejména při řešení diofantických rovnic a při hledání inverzního čísla modulo $n$.
-**Kovariance** dvou náhodných veličin $X$ a $Y$ je definována jako:
+Příklad:
 $$
-\text{Cov}(X, Y) = E[(X - E(X))(Y - E(Y))] = E(XY) - E(X)E(Y)
+\gcd(12, 42) = 6 = (-3) \cdot 12 + 1 \cdot 42
 $$
-<markdown>
+Jedno z možných řešení pro $(\alpha,\beta)=(-3,1)$.
-**Vlastnosti kovariance:**
-</markdown>
-  * $\text{Cov}(X, X) = Var(X)$
-  * $\text{Cov}(X, Y) = \text{Cov}(Y, X)$
-  * $\text{Cov}(aX + b, cY + d) = ac \cdot \text{Cov}(X, Y)$
-  * $Var(X + Y) = Var(X) + Var(Y) + 2\text{Cov}(X, Y)$
-<markdown>
-**Korelace** je to kovariance pro normované náhodné veličiny, definovaná jako:
+==== Hledání inverzního čísla ====
-</markdown>
+Chceme nalézt inverzní prvek $a^{-1} \in \mathbb{Z}_n$, tedy takové $x$, že $a \cdot x \equiv 1 \pmod{n}$.
+Postup:
+  * Použijeme rozšířený Eukleidův algoritmus na $a$ a $n$.
+  * Výsledkem bude rovnost $1 = A \cdot a + B \cdot n$.
+  * Z toho plyne $a \cdot A \equiv 1 \pmod{n}$, tedy $A$ je inverzní prvek k $a$ modulo $n$.
+  * Inverzní číslo existuje právě tehdy, když $\gcd(a,n) = 1$.
+Neboli:
+  * Najdeme $\gcd(a, n)$ ve tvaru $1 = A \cdot a + B \cdot n$ (rozšířený Eukleidův algoritmus).
+  * Pokud $\gcd(a,n) > 1$, inverzní prvek **neexistuje**.
+  * Pokud $\gcd(a,n) = 1$, pak $A$ je právě inverzní prvek $a^{-1} \mod n$, protože:
+==== Diofantické rovnice ====
+Pojem **lineární diofantická rovnice** označujme libovolnou rovnici typu $ax + by = c$ s neznámými $x,y\in \mathbb{Z}$, kde $a,b,c \in \mathbb{Z}$ jsou konstanty.
+**Definice**: Diofantická rovnice je rovnice, jejímž cílem je najít **celočíselná** řešení. Např.:
 $$
-\rho(X, Y) = \frac{\text{Cov}(X, Y)}{\sigma_X \sigma_Y}$$
+ax + by = c
-Korelace nabývá hodnot v intervalu $[-1, 1]$ a měří sílu lineární závislosti mezi náhodnými veličinami. Pokud $\rho(X, Y) = 0$, pak jsou $X$ a $Y$ nezávislé.
 $$
-Var(X + Y) = Var(X) + Var(Y) + 2 \cdot \text{Cov}(X, Y)
-$$
-===== Čebyševova nerovnost =====
-<markdown>
-**Čebyševova nerovnost** – centrální limitní věta.
-Čebyševova nerovnost je fundamentální výsledek v teorii pravděpodobnosti, který poskytuje horní odhad pravděpodobnosti odchylky náhodné veličiny od její střední hodnoty.
+Řešení existuje tehdy a jen tehdy, když $c$ je dělitelná $\gcd(a,b)$. Bezoutova identita pak dává způsob, jak jedno řešení najít.
-</markdown>
+**Řešení diofantických rovnic:**
-**Formulace:** Nechť $X$ je náhodná veličina s konečnou střední hodnotou $E(X) = \mu$ a konečným rozptylem $Var(X) = \sigma^2$. Pak pro libovolné $\epsilon > 0$ platí:
-$$
-P(|X - \mu| \geq \epsilon) \leq \frac{\sigma^2}{\epsilon^2}$$
-<markdown>
-**Ekvivalentní formulace:**
+Nechť $a,b,c\in \mathbb{Z}$. Lineární diofantická rovnice $ax + by = c$ má alespoň jedno řešení právě tehdy, když c je násobkem $gcd(a,b)$ (téměř přímo vychází z Bezoutovy identity).
-</markdown>
-$$
-P(|X - \mu| < \epsilon) \geq 1 - \frac{\sigma^2}{\epsilon^2}$$
-<markdown>
-**Interpretace:**
+Jeli daná diofantická rovnice $ax +by = c$, pak definujeme její **přidruženou homogenní rovnici** jako $ax + by = 0$.
-- Nerovnost říká, že pravděpodobnost velkých odchylek od střední hodnoty je malá
-</markdown>
-  * Čím menší je rozptyl $\sigma^2$, tím více se hodnoty náhodné veličiny koncentrují kolem střední hodnoty
-  * Čím větší je tolerance $\epsilon$, tím větší je pravděpodobnost, že se hodnota vejde do intervalu $(\mu - \epsilon, \mu + \epsilon)$
-<markdown>
-**Praktický význam:**
+**Věta o řešení homogeních rovnic**:
-- Poskytuje univerzální odhad platný pro všechna rozdělení s konečným rozptylem
-- Je základem pro odvození zákona velkých čísel
-- Používá se jako teoretické zdůvodnění pro centrální limitní větu
-**Kontext k CLV:** Čebyševova nerovnost umožňuje dokázat slabý zákon velkých čísel, který je klíčovým krokem k pochopení centrální limitní věty. CLV pak zpřesňuje asymptotické chování průměrů nezávislých náhodných veličin.
+Uvažujme rovnici $ax+by=0$ pro $a,b \in \mathbb{Z}$. Množina všech jejích celočíslených řešení je $$\left\{ \left(k \frac{b}{\gcd(a, b)}, - k \frac{a}{\gcd(a, b)}\right) : k \in \mathbb{Z} \right\} $$
-</markdown>
-==== Centrální limitní věta ====
-<markdown>
-**Centrální limitní věta (CLV)** je jedním z nejdůležitějších výsledků v teorii pravděpodobnosti. Říká, že pokud máme dostatečně velký počet nezávislých a identicky rozdělených náhodných veličin, jejich průměr se bude blížit normálnímu rozdělení bez ohledu na původní rozdělení těchto veličin.
-</markdown>
-**Formulace:** Nechť $X_1, X_2, \ldots, X_n$ jsou nezávislé a identicky rozdělené náhodné veličiny s konečnou střední hodnotou $\mu$ a konečným nenulovým rozptylem $\sigma^2$. Pak pro průměr těchto veličin platí:
-$$
-\frac{\sqrt{n}(\bar{X}_n - \mu)}{\sigma} \xrightarrow{d} N(0, 1)$$
-kde $\bar{X}_n = \frac{1}{n} \sum_{i=1}^{n} X_i$ je průměrná hodnota těchto veličin a $N(0, 1)$ je standardní normální rozdělení.
-<markdown>
-Praktický vzorec pro CLV:
-</markdown>
-$$
-P(X \leq x) \approx P(\text{norm}(X) \leq \frac{x - \mu}{\sigma / \sqrt{n}}) = \Phi\left(\frac{x - \mu}{\sigma / \sqrt{n}}\right),
-$$
-kde $\mu$ je střední hodnota, $\sigma$ je směrodatná odchylka a $\Phi$ je distribuční funkce standardního normálního rozdělení.
-===== Základní pojmy statistiky =====
-**Základní pojmy statistiky** – náhodný výběr, empirické rozdělení.
-==== Náhodný výběr ====
+==== Algoritmus řešení diofantických rovnic ====
-Náhodnému vektoru $\mathbb{X} = (X_1, X_2, \ldots, X_n)$ nezávisle rozdělených náhodných veličin s distribuční funkcí $F_{\theta}$, která závisí na parametru $\theta$, říkáme **náhodný výběr**.
-Funkce
-$$
- \bar{X} = \frac{1}{n} \sum_{i=1}^{n} X_i
-$$
-náhodného výběru $\mathbb{X} = (X_1, X_2, \ldots, X_n)$ se nazývá **výběrový průměr** a je to odhad střední hodnoty náhodného vektoru.
-$S_{n}^{2} = \frac{1}{n - 1} \sum_{i=1}^{n} (X_i - \bar{X}_n)^2$ se nazývá **výběrový rozptyl** a je to odhad rozptylu náhodného vektoru. $S_n = \sqrt{S^2_n}$ je **výběrová směrodatná odchylka**.
+**Algoritmus** pro nalezení všech celočíselných řešení rovnice $ax+by=c$.
-  * Výběrový průměr $\bar{X}_n$ a výběrový rozptyl $S^2_n$ jsou nezávislé náhodné veličiny.
+  - Najdeme $gcd(a,b)=A\cdot a + B\cdot b$ (Podobné jako u inverzního čísla, vychází z Bezoutovy identity)
-  * Výběrový průměr $\bar{X}_n$ má rozdělení $N(\mu, \frac{\sigma^2}{n})$, kde $\mu$ je střední hodnota a $\sigma^2$ je rozptyl původního rozdělení.
+  - Jestliže $c$ není násobkem gcd(a,b), pak neexistuje řešení
+  - Jestliže $gcd(a,b)$ dělí c:
+    - Zadefinujeme $c'=\frac{c}{gcd(a,b)}$ a získáme partikulární řešení $x_p=Ac'$ a $y_p = Bc'$
+    - Pro jednochost zápisu zadefinujeme $a'=\frac{a}{gcd(a,b)}$, $b'=-\frac{b}{gcd(a,b)}$ pro $k\in \mathbb{Z}$(Toto vychází z věty o řešení homogeních rovnic).
+    - Sečtením partikulárního a obecného homogenního řešení získáme množinu všech celočíselných řešení $$x = x_p + kb', y = y_p - ka' \text{ pro } k \in \mathbb{Z}$$ Případně lze prohodit $-$ pro získání $$x = x_p - kb', y = y_p + ka' \text{ pro } k \in \mathbb{Z}$$
+Pro řešení difonatických rovnic musíme najít 2 části řešení, homogenní a partikulární část. Partikulární část řešení najde jedno specifické řešení diofantické rovnice, ale abychom našli všechny řešení tak musíme vyřešit homogenní část ta nám umožní najít všechny řešení.
-==== Empirické rozdělení ====
+==== Bonus: Malá Fermatova věta ====
-Nechť $x_1, x_2, \ldots, x_n$ je realizace náhodného výběru rozsahu $n$ z nějakého rozdělení s neznámou distribuční funkcí $F(x)$.
-**Empirická distribuční funkce** (ECDF) $F_n(x)$ je definována jako:
+Malá Fermatova věta se často používá při hledání inverzních prvků modulo prvočíslo.
+  * Pro každé prvočíslo $p$ a každé celé číslo $a$ platí:
+    $$
+    a^p \equiv a \pmod{p}
+    $$
+  * Pokud $a \not\equiv 0 \pmod{p}$, pak:
+    $$
+    a^{p-1} \equiv 1 \pmod{p}
+    $$
+Z toho plyne, že inverzní prvek lze vypočítat jako:
 $$
-F_n(x) = \frac{1}{n} \sum_{i=1}^{n} I(x_i \leq x)
+a^{-1} \equiv a^{p-2} \pmod{p}
 $$
-kde $I(A)$ je indikátorová funkce události $A$, která je rovna 1, pokud je událost $A$ pravdivá, a 0 jinak. Jinými slovy, $F_n(x)$ udává podíl pozorování v náhodném výběru, která jsou menší nebo rovna $x$.
+===== 4. Euklidův algoritmus =====
-Graf Empirické distribuční funkce je schodovitý a roste v krocích o velikosti $1/n$ v bodech, kde se nacházejí pozorované hodnoty $x_i$. Pro hodnoty mezi těmito body zůstává funkce konstantní.
+– jak funguje, teoreticky (přechod ke zbytku po dělení) i prakticky, jak se pozná kdy končí. Jak funguje jeho rozšířená verze, která umí poskytnout Bezoutovu identitu (prakticky).
-Například byly naměřeny hodnoty $x_1 = 1, x_2 = 2, x_3 = 2, x_4 = 3$. Empirická distribuční funkce by byla:
+Ve své základní verzi slouží k hledání GCD (Největšího společného dělitele).
+Postupně počítáme zbytky po dělení, přičemž v každém kroku dělíme předchozí dvě čísla. Vždy odečteme co největší násobek menšího čísla od většího, čímž získáme nové, menší číslo. Algoritmus končí ve chvíli, kdy je zbytek nulový – tehdy je poslední nenulové číslo právě $\gcd(a,b)$.
+Níže je uveden příklad pro čísla $408$ a $108$:
 <tikzjax>
+\usepackage{tikz}
+\usetikzlibrary{matrix,arrows.meta,positioning}
 \begin{document}
 \begin{tikzpicture}
-\draw[->] (0,0) -- (5,0) node[right] {$x$};
+  \matrix (m) [
-\draw[->] (0,0) -- (0,3.5) node[above] {$F_n(x)$};
+    matrix of nodes,
-\draw[thick] (0,0) -- (1,0) -- (1,0.75) -- (2,0.75) -- (2,2.25) -- (3,2.25) -- (3,3) -- (5,3);
+    nodes in empty cells,
-\foreach \x in {1,2,3} {
+    nodes={font=\ttfamily, minimum width=0.5em, minimum height=1.2em, align=center},
-  \draw[fill] (\x,{0.75*(\x==1) + 2.25*(\x==2) + 3*(\x==3)}) circle (1.5pt);
+    column sep=0.1em,
-  \draw[] (\x,{0.75*(\x>1) + 2.25*(\x>2) + 3*(\x>3)}) circle (1.5pt);
+  ] {
-}
+& \verb!|! &   & \\
-\node[below] at (1,0) {1};
+& \verb!|! & $(-3)\times$ & \\
-\node[below] at (2,0) {2};
+& \verb!|! & $(-1)\times$ &  \\
-\node[below] at (3,0) {3};
+& \verb!|! & $(-3)\times$ &    \\
-\node[left] at (0,0.75) {0.25};
+& \verb!|! & $(-2)\times$ &   \\
-\node[left] at (0,2.25) {0.75};
+& \verb!|! &    &    \\
-\node[left] at (0,3) {1};
+  };
+  \end{tikzpicture}
+\end{document}
+  </tikzjax>
+Díky postupnému zmenšování čísel má algoritmus logaritmickou časovou složitost, což z něj dělá velmi efektivní metodu i pro velká čísla.
+==== Rozšířený Euklidův algoritmus ====
+Rozšířený Euklidův algoritmus najde nejen GCD (největší společný dělitel), ale zároveň i lineární kombinaci počátečních čísel ze kterých se GCD skládá, což je kritické pro použití Bezoutovy identity a řešení diofantických rovnic. Pro shrnutí: Nechť $a,b \in \mathbb{N}$, poté Euklidův algoritmus dokáže najít $A,B \in \mathbb{Z}$, tak že $a\cdot A + b\cdot B = gcd(a,b)$.
+Po jeho použití dostaneme rovnou Bezoutovu identitu, zkonstruujeme ho následující tabulkou, kde vedle původních čísel dosadíme jednotkovou matici (zde hledáme $\text{gcd}(408, 108)$ a Bezoutovu identitu $12 = A\cdot408 + B\cdot108$), princip je stejný jako u Euklidova algoritmu:
+Každý řádek se skládá z $r_i$ | $x_i$ | $y_i$, kde $r_i = x_i\cdot a + y_i\cdot b$. Pro výpočet řádku $i+1$ hledáme $a = \textbf{floor}(r_{i-1} / r_i)$ poté nový řádek je $r_{i+1}$ | $x_i\cdot (-a) + x_{i-1}$ | $y_i\cdot (-a) + y_{i-1}$
+Každý řádek obsahuje tři hodnoty $r_i \;|\; x_i \;|\; y_i$, kde:
+  * $r_i$ je aktuální zbytek,
+  * $x_i$ a $y_i$ jsou koeficienty, které splňují: $r_i = x_i \cdot a + y_i \cdot b$
+<tikzjax>
+\usepackage{tikz}
+\usetikzlibrary{matrix,arrows.meta,positioning}
+\begin{document}
+\begin{tikzpicture}
+  % set up the matrix
+  \matrix (m) [
+    matrix of nodes,
+    nodes in empty cells,
+    nodes={font=\ttfamily, minimum width=1.5em, minimum height=1.2em, align=center},
+    column sep=1em,
+  ] {
+        & \verb!|! & 408 & 108 & \\
+& \verb!|! &  1 &   0 &       \\
+& \verb!|! &  0 &   1 &  \\
+& \verb!|! &  1 &  -3 &  \\
+& \verb!|! & -1 &   4 &  \\
+& \verb!|! &  4 & -15 &  \\
+& \verb!|! &    &     &       \\
+  };
+  \draw[-{Stealth}]
+    (m-3-5.west) to[out=0,in=0]
+      node[midway, anchor=west, xshift=2pt] {$-3\times$}
+    (m-2-5.west);
+  \draw[-{Stealth}]
+    (m-4-5.west) to[out=0,in=0]
+      node[midway, anchor=west, xshift=2pt] {$-1\times$}
+    (m-3-5.west);
+  \draw[-{Stealth}]
+    (m-5-5.west) to[out=0,in=0]
+      node[midway, anchor=west, xshift=2pt] {$-3\times$}
+    (m-4-5.west);
+  \draw[-{Stealth}]
+    (m-6-5.west) to[out=0,in=0]
+      node[midway, anchor=west, xshift=2pt] {$-2\times$}
+    (m-5-5.west);
+  \node(eq)[below=1.5em of m]
+    {$12 \;=\; 4\cdot408 \;+\;(-15)\cdot108$};
+    \draw[-{Stealth}, red, thick]
+    (m-6-1.south) to[out=180,in=180]
+    node[midway, anchor=east, xshift=-2pt] {gcd}
+    (eq.west);
 \end{tikzpicture}
 \end{document}
 </tikzjax>
-<markdown>
-**Vlastnosti empirické distribuční funkce:**
+Rozšířený Euklidův algoritmus vždy vrací koeficienty $\alpha, \beta \in \mathbb{Z}$, které splňují Bezoutovu identitu pro zadaná $a,b$.
-</markdown>
-  * Je to schodovitá funkce, která má skoky velikosti $1/n$ (nebo násobku $1/n$, pokud se některé hodnoty $x_i$ opakují) v bodech pozorovaných hodnot $x_i$.
-  * Pro každé pevné $x$ je $F_n(x)$ náhodná veličina.
-  * $F_n(x)$ je nestranným odhadem teoretické distribuční funkce $F(x)$, tj. $E[F_n(x)] = F(x)$.
-  * Podle Glivenko-Cantelliho věty platí, že $F_n(x)$ konverguje k $F(x)$ stejnoměrně pro $n \to \infty$: $\sup_{x \in \mathbb{R}} |F_n(x) - F(x)| \xrightarrow{a.s.} 0 \quad \text{pro } n \to \infty$
-<markdown>
-To znamená, že s rostoucím počtem pozorování se empirická distribuční funkce stále více přibližuje skutečné distribuční funkci.
-</markdown>
+===== 5. Binární relace =====
+– definice a ilustrace na jednoduchých příkladech. Čtyři základní vlastnosti (reflexivita, symetrie, antisymetrie, tranzitivita): jaký mají význam, umět ilustrovat na grafu relace, popřípadě (alespoň intuitivně) rozpoznat u nějaké relace ze života.
-====== Obecné vlastnosti odhadů parametrů ======
+==== Definice ====
-<markdown>
-Při odhadování neznámých parametrů základního souboru na základě pozorovaných dat z náhodného výběru se snažíme, aby naše odhady měly určité žádoucí vlastnosti. Tyto vlastnosti nám pomáhají posoudit kvalitu odhadu a vybrat ten nejlepší možný.
-</markdown>
-===== Značení =====
+Nechť $A, B$ jsou množiny. **Binární relace** $R$ z $A$ do $B$ je libovolná podmnožina kartézského součinu:
-<markdown>
+$$
-Nejprve si zavedeme značení, které se v teorii odhadu běžně používá:
+R \subseteq A \times B
-</markdown>
+$$
-  * $\vartheta$: Jakákoli hodnota parametru (reálné číslo).
-  * $\vartheta^*$: Skutečná (správná) hodnota parametru (reálné číslo).
-  * $\hat{\Theta}_n$: Odhad parametru založený na náhodném výběru rozsahu $n$ (toto je náhodná veličina).
-  * $\hat{\vartheta}$, $\hat{\vartheta}_n$: Realizace odhadu, tj. konkrétní hodnota odhadu získaná z dat (reálné číslo).
-===== Žádoucí vlastnosti bodových odhadů =====
+Jestliže $(a, b) \in R$, zapisujeme $a \mathcal{R} b$ a říkáme, že **prvek $a$ je v relaci s $b$** vzhledem k relaci $\mathcal{R}$.
-<markdown>
+Pokud $(a, b) \notin R$, pak $a$ **není v relaci** s $b$.
-Bodový odhad je funkce náhodného výběru, jejíž předpis nezávisí na odhadovaném parametru.  Snažíme se, aby bodové odhady měly následující vlastnosti:
-.  **Nestrannost (nevychýlenost)**:
+Pokud je relace na jedné množině ($A = B$), říkáme, že je **na množině $A$**.
-</markdown>
-    * Odhad $\hat{\Theta}_n$ se nazývá nestranný, pokud jeho střední hodnota je rovna skutečné hodnotě parametru $\vartheta^*$, tj. $E[\hat{\Theta}_n] = \vartheta^*$.  To znamená, že $E[\hat{\Theta}_n - \vartheta^*] = 0$.
-<markdown>
-  * Pokud tato podmínka není splněna, odhad je **vychýlený**.
-.  **Asymptotická nestrannost**:
+==== Čtyři základní vlastnosti ====
-</markdown>
-    * Odhad $\hat{\Theta}_n$ je asymptoticky nestranný, pokud se jeho střední hodnota blíží skutečné hodnotě parametru $\vartheta^*$ s rostoucím rozsahem výběru $n$, tj. $\lim_{n\rightarrow\infty} E[\hat{\Theta}_n] = \vartheta^*$.  To také znamená, že $\lim_{n\rightarrow\infty} E[\hat{\Theta}_n - \vartheta^*] = 0$.
-<markdown>
-.  **Konzistence**:
+Relace $\mathcal{R}$ na množině $A$ může mít tyto čtyři základní vlastnosti:
-</markdown>
-    * Odhad $\hat{\Theta}_n$ je konzistentní, pokud s rostoucím rozsahem výběru $n$ konverguje v pravděpodobnosti k odhadovanému parametru $\vartheta^*$. To znamená, že platí dvě podmínky:
-        * Je asymptoticky nestranný: $\lim_{n\rightarrow\infty} E[\hat{\Theta}_n] = \vartheta^*$ (nebo $E[\hat{\Theta}_n - \vartheta^*] = 0$).
-        * Jeho rozptyl se blíží k nule: $\lim_{n\rightarrow\infty} D[\hat{\Theta}_n] = 0$ (nebo $\lim_{n\rightarrow\infty} \sigma_{\hat{\Theta}_n} = 0$).
-<markdown>
-.  **Efektivita (účinnost)**:
+  * $\mathcal{R}$ je reflexivní, když $\forall a \in A$ platí $ a\mathcal{R}a$. Každý prvek je v relaci sám se sebou. Např. relace „má stejnou hodnotu jako“.
-</markdown>
+  * $\mathcal{R}$ je symetrická, když $\forall a, b \in A$ platí $ a\mathcal{R}b \implies b\mathcal{R}a$. Pokud $a$ souvisí s $b$, pak i $b$ souvisí s $a$. Např. „je sourozenec“ nebo „je stejně vysoký jako“.
-    * Efektivní odhad je takový, který má malý rozptyl.  Kvalitu odhadu z hlediska efektivity posuzujeme pomocí střední kvadratické chyby $E[(\hat{\Theta}_n - \vartheta^*)^2]$.
+  * $\mathcal{R}$ je antisymetrická, když $\forall a, b \in A$ platí $ (a\mathcal{R}b \land b\mathcal{R}a) \implies a=b$. Pokud $a$ souvisí s $b$ a zároveň $b$ s $a$, pak musí jít o stejný prvek. Např. relace „je menší nebo rovno“.
-    * Tato chyba se dá rozložit na $D[\hat{\Theta}_n] + (E[\hat{\Theta}_n] - \vartheta^*)^2$.
+  * $\mathcal{R}$ je tranzitivní, když $\forall a, b, c \in A$ platí $ (a\mathcal{R}b \land b\mathcal{R}c) \implies a\mathcal{R}c$. Pokud $a$ souvisí s $b$ a $b$ s $c$, pak $a$ souvisí s $c$. Např. „je předchůdce“ nebo „má stejné příjmení jako“.
-    * Pro **nestranný odhad** se střední kvadratická chyba redukuje pouze na rozptyl $D[\hat{\Theta}_n]$.
-<markdown>
-    * **Nejlepší nestranný odhad** je ten, který má ze všech nestranných odhadů nejmenší rozptyl (je nejvíce eficientní).  Je však možné, že existují vychýlené odhady, které jsou efektivnější než nejlepší nestranný odhad.
-.  **Robustnost**:
+==== Ekvivalence ====
-    * Robustní odhad je odolný vůči šumu nebo odlehlým hodnotám v datech.  To znamená, že i při zašuměných datech dostáváme relativně dobrý výsledek.
-    * Přesné matematické kritérium pro robustnost často chybí, ale jedná se o velmi praktickou vlastnost.
-</markdown>
-===== Odhady konkrétních parametrů =====
+Relace $\mathcal{R}$ na množině $A$ je **ekvivalence**, pokud splňuje: reflexivitu, symetrii, tranzitivitu.
-  * **Odhady střední hodnoty** ($\mu$):
-    * Výběrový průměr $\overline{X}_n = \frac{1}{n} \sum_{i=1}^{n} X_i$ je nestranným a konzistentním odhadem střední hodnoty $E[X]$.
-  * **Odhady rozptylu ($\sigma^2$)**:
-    * Výběrový rozptyl $S^2_n = \frac{1}{n-1} \sum_{i=1}^{n}(X_i - \overline{X}_n)^2$ je nestranným a konzistentním odhadem rozptylu $D[X]$.
-  * **Odhady směrodatné odchylky ($\sigma$)**:
-    * Výběrová směrodatná odchylka $S_n = \sqrt{S^2_n}$ je odhadem směrodatné odchylky $\sigma$.
-<markdown>
-* **Odhady momentů**:
-</markdown>
-    * Pro odhad $k$-tého obecného momentu $E[X^k]$ se používá výběrový $k$-tý obecný moment $m_{X^k} = \frac{1}{n}\sum_{j=1}^{n}x_j^k$.
+Taková relace přirozeně rozdělí množinu $A$ na **třídy ekvivalence** – tedy podmnožiny, kde jsou prvky navzájem v relaci.
-===== Metody odhadování parametrů =====
+**Definice třídy ekvivalence**:
-<markdown>
+Pro $a \in A$ definujeme:
-Existuje několik metod pro konstrukci odhadů. Dvě základní jsou:
+$$
+[a]_{\mathcal{R}} = \{ b \in A \mid a \mathcal{R} b \}
+$$
-.  **Metoda momentů (MM)**:
+Každý prvek $a$ náleží právě jedné třídě, množina všech tříd tvoří rozklad $A$.
-    * Princip: Klademe do rovnosti teoretické momenty (které závisí na neznámých parametrech) a jejich výběrové protějšky spočítané z dat.
-</markdown>
-    * Například pro $k$ neznámých parametrů $\theta_1, \ldots, \theta_k$ řešíme soustavu $k$ rovnic $E[X^i] = m_{X^i}$ pro $i=1, \ldots, k$.  Alternativně, pokud jsou dva parametry, můžeme položit $E[X] = \overline{X}_n$ a $D[X] = S^2_n$.
-<markdown>
-  * Výhody: Často jednoduché získání vzorců.  Zohledňuje všechna data z výběru.
-  * Nevýhody: Řešení nemusí vždy existovat.  Nemusí vždy dávat nejlepší výsledky ve srovnání s jinými metodami.
-  * Volí se často v případech, kdy je soustava věrohodnostních rovnic (viz MLE níže) obtížně řešitelná.
-.  **Metoda maximální věrohodnosti (MLE - Maximum Likelihood Estimation)**:
+==== Částečné uspořádání ====
-    * Princip: Hledáme takové hodnoty parametrů, které maximalizují tzv. věrohodnostní funkci.  Věrohodnostní funkce vyjadřuje, jak "pravděpodobná" jsou pozorovaná data pro různé hodnoty parametrů.
-</markdown>
-    * Pro náhodný výběr $X_1, \ldots, X_n$ z rozdělení s hustotou $f(x; \theta)$ (spojitý případ) nebo pravděpodobnostní funkcí $P(X=x; \theta)$ (diskrétní případ), je věrohodnostní funkce $L(\theta; x)$ definována jako součin těchto funkcí přes všechna pozorování:
-        * Spojitý případ: $L(\theta; x) = \prod_{i=1}^{n} f(x_i; \theta)$.
-        * Diskrétní případ: $L(\theta; x) = \prod_{i=1}^{n} P(X_i=x_i; \theta)$.
-<markdown>
-  * Postup:
-</markdown>
-        * Sestrojíme věrohodnostní funkci $L(\theta)$.
-        * Často je výhodnější pracovat s logaritmem věrohodnostní funkce (log-likelihood) $l(\theta) = \ln L(\theta)$, protože součiny se převedou na součty, což zjednodušuje derivování.
-        * Položíme derivaci $l(\theta)$ podle parametru $\theta$ rovnu nule: $\frac{\partial l(\theta)}{\partial \theta} = 0$.
-        * Řešením této rovnice (nebo soustavy rovnic, pokud je parametrů více) získáme maximálně věrohodný odhad $\hat{\theta}$.
-<markdown>
-  * Myšlenka: Hledáme parametry, které nejlépe "vysvětlují" pozorovaná data, tj. při kterých by pozorované výsledky byly "nejméně nepravděpodobné".
-  * Pro základní rozdělení dávají obě metody (MM a MLE) shodné výsledky.  V složitějších případech se volí metoda i podle citlivosti vzorců na chyby v datech.
-</markdown>
-===== Intervalové odhady (Intervaly spolehlivosti) =====
+Relace $\mathcal{R}$ na množině $A$ je **částečné uspořádání**, pokud splňuje: reflexivitu, antisymetrii, tranzitivitu.
-<markdown>
-Na rozdíl od bodového odhadu, který poskytuje jedinou hodnotu parametru, intervalový odhad udává interval, ve kterém se s určitou pravděpodobností (tzv. koeficientem spolehlivosti) nachází skutečná hodnota parametru.
-</markdown>
+Takovou relaci značíme často symbolem $\preceq$ nebo $\leq$ (např. „dělitelnost“). Dvojice $(A, \mathcal{R})$ se pak nazývá **částečně uspořádaná množina**.
-  * **Definice**: $(1 - \alpha) \times 100\%$ interval spolehlivosti pro parametr $\vartheta$ je interval $(L, U)$ takový, že $P(L < \vartheta^* < U) \geq 1 - \alpha$.
-    * $1 - \alpha$ je **koeficient spolehlivosti** (např. 95%, pokud $\alpha = 0.05$).
-    * $\alpha$ je **hladina významnosti** (pravděpodobnost, že interval nepokryje skutečnou hodnotu parametru).
-  * Intervaly mohou být **oboustranné**, **dolní jednostranné** ($I = (L, \infty)$)  nebo **horní jednostranné** ($I = (-\infty, U)$).
-  * Symetrický oboustranný odhad znamená, že pravděpodobnost překročení horní meze je stejná jako pravděpodobnost podkročení dolní meze (obvykle $\alpha/2$ pro každou stranu).
-Konstrukce intervalových odhadů vyžaduje znalost rozdělení pravděpodobnosti odhadu $\hat{\Theta}_n$ nebo nějaké z něj odvozené statistiky.
-<markdown>
-Toto jsou základní obecné vlastnosti a metody odhadování parametrů. Konkrétní vzorce pro odhady a intervaly spolehlivosti se pak liší v závislosti na konkrétním rozdělení dat a odhadovaném parametru.
+==== Hasseův diagram ====
-</markdown>
-===== Princip statistického testování hypotéz =====
-**Princip statistického testování hypotéz** –  testy střední hodnoty a rozptylu, porovnání dvou rozdělení, $\chi^2$-test dobré shody, test nezávislosti v kontingenční tabulce.
-<markdown>
-**Princip statistického testování hypotéz** je metoda pro ověřování tvrzení (hypotéz) o parametrech nebo rozdělení náhodných veličin na základě dat. Zahrnuje následující kroky:
-. **Formulace hypotéz**:
+**Hasseův diagram** je grafické znázornění částečně uspořádané množiny.
-   - **Nulová hypotéza (H₀)**: Základní tvrzení, které se testuje (např. "střední hodnota je rovna určité hodnotě").
-   - **Alternativní hypotéza (H₁)**: Tvrzení, které se považuje za alternativu k H₀ (např. "střední hodnota se liší od určité hodnoty").
-</markdown>
+  * Vrcholy představují prvky množiny $A$.
-  * **Volba hladiny významnosti ($\alpha$)**:
+  * Hrana mezi $a$ a $b$ značí relaci $a \mathcal{R} b$, kde $a < b$ a neexistuje $c$, pro které by $a < c < b$.
-<markdown>
+  * Prvek $a$ je v diagramu **níž** než $b$, pokud $a \mathcal{R} b$.
-   - Pravděpodobnost, že zamítneme H₀, i když je pravdivá (často 0.05 nebo 0.01).
-. **Výběr testové statistiky**:
+**Další pojmy v uspořádání**:
-</markdown>
-   * Výpočet statistiky, která kvantifikuje rozdíl mezi daty a H₀ (např. t-statistika, $\chi^2$-statistika).
-<markdown>
-. **Výpočet kritické hodnoty nebo p-hodnoty**:
+  * **Největší prvek** – prvek, ke kterému vede cesta z každého jiného prvku (nemusí existovat).
-   - **Kritická hodnota**: Mez, kterou porovnáváme s testovou statistikou.
+  * **Maximum** – prvek, nad kterým už není žádný jiný.
-   - **p-hodnota**: Pravděpodobnost, že bychom získali pozorované nebo extrémnější výsledky, pokud je H₀ pravdivá.
+  * **Nejmenší prvek** – prvek, ze kterého vede cesta ke všem ostatním (nemusí existovat).
+  * **Minimum** – prvek, pod kterým už není žádný jiný.
-. **Rozhodnutí**:
+**Linearizace částečného uspořádání**:
-</markdown>
+Z Hasseova diagramu vytvoříme posloupnost prvků (např. zleva doprava, po úrovních), která zachovává uspořádání.
-   * Pokud p-hodnota < $\alpha$ nebo testová statistika překročí kritickou hodnotu, zamítáme H₀.
-<markdown>
-   - Jinak nezamítáme H₀.
-</markdown>
+===== 6. Indukce =====
+– je třeba rozumět principu, vnímat různé verze (slabá, silná), umět případně ilustrovat na nějakém jednoduchém důkazu.
-====== Testy střední hodnoty a rozptylu ======
+==== Slabý princip matematické indukce ====
-<markdown>
+Nechť $n_0 \in \mathbb{Z}$, ať $V(n)$ je výrok (vlastnost) pro celá čísla $n \geq n_0$.
-**Testy střední hodnoty**:
+Předpokládejme, že platí:
-- **Jednovýběrový t-test**: Ověřuje, zda střední hodnota populace je rovna zadané hodnotě (předpoklad: normalita nebo velký výběr).
+  * $V(n_0)$
-- **Dvouvýběrový t-test**: Porovnává střední hodnoty dvou nezávislých skupin.
+  * $\forall n \geq n_0: \; V(n) \Rightarrow V(n+1)$
-- **Párový t-test**: Porovnává střední hodnoty dvou závislých skupin (např. před a po zásahu).
-**Testy rozptylu**:
+Pak $V(n)$ platí pro všechna $n \geq n_0$.
-- **F-test**: Porovnává rozptyly dvou populací (předpoklad: normalita).
-</markdown>
-  * **$\chi^2$-test rozptylu**: Ověřuje, zda rozptyl populace je roven zadané hodnotě.
-====== Porovnání dvou rozdělení ======
+==== Příklad (slabá indukce) ====
-<markdown>
+Dokážeme, že $2^n \ge n+1$ pro každé $n \in \mathbb{N}_0$.
-**Porovnání dvou rozdělení**:
-- **Kolmogorov-Smirnovův test**: Testuje, zda dvě výběrová rozdělení pocházejí ze stejné populace.
-- **Mann-Whitneyho test**: Neparametrický test pro porovnání dvou nezávislých výběrů (bez předpokladu normality).
-- **Wilcoxonův test**: Neparametrický test pro porovnání dvou závislých výběrů.
-</markdown>
-====== $\chi^2$-test dobré shody ======
+  * **Základ:** $n = 0$: $2^0 = 1 \ge 1$
+  * **Indukční krok:** Předpokládáme $2^n \ge n+1$. Pak:
+    $$
+^{n+1} = 2 \cdot 2^n \ge 2(n+1) \ge (n+1)+1
+    $$
+protože $n+1 \ge 1$
-**$\chi^2$-test dobré shody**:
+==== Silný princip matematické indukce ====
-<markdown>
-- Ověřuje, zda pozorovaná data odpovídají očekávanému rozdělení (např. binomické, normální).
-- **Výpočet**:
-  </markdown>
-$$\chi^2 = \sum \frac{(O_i - E_i)^2}{E_i}$$
-kde $O_i$ jsou pozorované četnosti a $E_i$ očekávané četnosti.
-**Předpoklady**: Větší počet očekávaných hodnot (obvykle $\geq$ 5).
-====== Test nezávislosti v kontingenční tabulce ======
+**Vysvětlení:**
+Na rozdíl od slabé indukce zde při kroku $n+1$ předpokládáme, že tvrzení platí **pro všechna** menší čísla $n_0, n_0\!+\!1,\dots,n$.
+Je to, jako bys stavěl schody a u každého nového stupínku směl využít celou „platformu“ před sebou, nejen poslední schod.
-<markdown>
+Formálně:
-**Test nezávislosti v kontingenční tabulce**:
+Pokud platí
-- Ověřuje, zda dvě kategorické proměnné jsou nezávislé.
+  * $V(n_0)$,
-- **Výpočet**:
+  * $\forall n \geq n_0:\; \bigl(\forall k,\; n_0\le k\le n \Rightarrow V(k)\bigr)\;\Rightarrow\; V(n+1)$,
-  </markdown>
+pak $V(n)$ platí pro všechna $n \geq n_0$.
-$$\chi^2 = \sum \frac{(O_{ij} - E_{ij})^2}{E_{ij}}$$
-  kde $O_{ij}$ jsou pozorované četnosti a $E_{ij}$ očekávané četnosti (vypočtené jako $E_{ij} = \frac{r_i \cdot c_j}{n}$).
-  * **Předpoklady**: Větší očekávané četnosti (obvykle $\geq$ 5).
-===== Markovovy řetězce =====
+==== Příklad (silná indukce) ====
-**Markovovy řetězce** – základní pojmy a vlastnosti, popis přechodovým diagramem a maticí přechodu. Klasifikace stavů, periodicita, rozložitelnost. Asymptotické chování Markovových řetězců.
-==== Základní pojmy a popis ====
+Dokážeme, že každé celé číslo $n \ge 2$ lze zapsat jako součin prvočísel.
-<markdown>
-Markovovy řetězce jsou stochastické procesy s konečným nebo spočetným počtem stavů, kde pravděpodobnost přechodu do dalšího stavu závisí pouze na aktuálním stavu (vlastnost Markova).
-- **Přechodový diagram**: Graf s uzly (stavy) a hranami (pravděpodobnosti přechodu).
-</markdown>
-  * **Matice přechodu** $ P(t) $: Matice velikosti $ n \times n $, kde $ p_{ij}(t) $ je pravděpodobnost přechodu ze stavu $ i $ do stavu $ j $ v čase $ t $.
-=== Klasifikace stavů ===
+  * **Základ:** $n = 2$ je prvočíslo, tedy rozklad existuje.
-<markdown>
+  * **Indukční krok:** Předpokládáme, že tvrzení platí pro všechna $k$ s $2 \le k \le n$.
-| Typ stavu       | Definice                                                                 |
+  * Uvažujme $n+1$:
-|-----------------|--------------------------------------------------------------------------|
+    - Pokud je $n+1$ prvočíslo, rozklad je hotový.
-</markdown>
+    - Pokud je složené, existují $a, b$ taková, že $n+1 = a \cdot b$ a $2 \le a,b \le n$.
-| **Absorbující** | $p_{jj} = 1$ (po vstupu nelze opustit)                                |
+    - Podle indukčního předpokladu lze $a$ i $b$ rozložit na součin prvočísel.
-<markdown>
+    - Součinem těchto rozkladů získáme rozklad i pro $n+1$.
-| **Tranzientní**   | Existuje nenulová pravděpodobnost, že se nikdy nevrátíme do tohoto stavu |
-| **Rekurentní**    | Stav je navštíven nekonečně často s pravděpodobností 1                   |
+**Krátký slovní popis:**
-</markdown>
+V kroku $n+1$ můžeme předpokládat platnost tvrzení pro **každé** $k$ s $2\le k\le n$.
-| **Periodický**   | Návrat do stavu je možný pouze v násobcích čísla $d_j$ (perioda)     |
+Je-li $n+1$ složené, rozdělíme ho na dva menší činitele $a,b$ (to lze díky tomu že víme, že čísla která nejsou prvočíslo jsou dělitelná ne jen sama sebou a 1) a pro oba už známe rozklad (protože čísla jsou menší než $n$ a pro ty už jsme si to dokázali) → jejich součinem dostaneme
-| **Aperiodický**  | Perioda $d_j = 1$                                                     |
+rozklad i pro $n+1$.
+===== 7. Rekurentní rovnice =====
+ – základní vlastnosti homogenních lineárních rekurentních rovnic (jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze), jak najít vhodnou bázi (pomocí kořenů charakteristického polynomu).
+**Definice:**
+Rekurentní (nebo také rekurzivní) vztah pro posloupnost $\{a_k\}$ je libovolná rovnice typu:
+$$
+F(a_n, a_{n-1}, a_{n-2}, \dots, a_0) = 0
+$$
+kde $F$ je nějaká funkce.
+Například problém Hanojských věží lze vyjádřit vztahem:
+$$
+H_n = 2 \cdot H_{n-1} + 1
+\quad\text{tedy}\quad
+H_n - 2H_{n-1} - 1 = 0
+$$
+====Lineární rekurentní rovnice====
+Lineární rekurentní rovnice (nebo také lineární rekurzivní rovnice) **řádu $k$** je rovnice tvaru:
+$$
+a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n
+\quad \text{pro všechna } n \geq n_0
+$$
+  * $k$ je řád rovnice – největší indexový posun v levé straně.
+  * Koeficienty $c_i(n)$ jsou funkce $\mathbb{Z} \to \mathbb{R}$ (mohou být konstantní nebo závislé na $n$).
+  * $b_n$ je tzv. pravá strana rovnice (např. nulová, nebo jiná posloupnost).
+Rovnice se nazývá **homogenní**, pokud platí $b_n = 0$ pro všechna $n \geq n_0$.
+  * Množina všech řešení homogenní rovnice tvoří **vektorový prostor** dimenze $k$.
+  * Řešení lze vyjádřit pomocí **báze** tohoto prostoru, kterou určujeme z kořenů tzv. charakteristického polynomu.
+====Řešení====
+Nechť je dána lineární rekurentní rovnice:
+$$
+a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n
+$$
+**Řešením** rozumíme posloupnost $\{a_n\}_{n=n_0}^\infty$, která po dosazení splňuje rovnici pro všechna $n \geq n_0$.
+====Charakteristická rovnice====
+**Definice:**
+$$
+a_{n+k} + c_{k-1}a_{n+k-1} + \dots + c_0a_n = b_n
+$$
+Pokud je $b_n = 0$ pro všechna $n$, rovnice se nazývá **homogenní** a můžeme k ní přiřadit **charakteristický polynom**:
+$$
+p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0
+$$
+Řešením rovnice $p(\lambda) = 0$ (tzv. **charakteristická rovnice**) jsou tzv. **charakteristická čísla** (nebo také **kořeny** či „vlastní čísla“).
+  * Každé charakteristické číslo $\lambda$ generuje **jednu základní posloupnost** $a_n=\lambda^n$. Mluvíme-li o „vektorovém prostoru“, nemyslíme tím čísla $\lambda$, ale **množinu všech posloupností** vzniklých lineárními kombinacemi těchto základních posloupností.
+  * Pokud má polynom $p$ více různých kořenů $\lambda_1,\dots,\lambda_m$, tvoří **bázi** prostoru řešení posloupnosti $\lambda_1^n,\dots,\lambda_m^n$. Libovolná lineární kombinace
+$$
+a_n = \alpha_1\lambda_1^n+\dots+\alpha_m\lambda_m^n
+$$
+    * je také řešením, takže celý prostor řešení má dimenzi $m$.
+  * Má-li některý kořen násobnost $r>1$, přidávají se do báze i členy $n\lambda^n,\,n^2\lambda^n,\dots,n^{r-1}\lambda^n$, aby dimenze prostoru zůstala rovna řádu $k$.
+Pomocí těchto tvarů sestavíme obecné řešení homogenní rovnice – každý kořen přispívá jedním nebo více lineárně nezávislými členy.
+====Příklad 1 – dva různé kořeny====
+Homogenní rovnice druhého řádu
+$$
+a_{n+2}-3a_{n+1}+2a_n=0
+$$
+má charakteristický polynom $p(\lambda)=\lambda^2-3\lambda+2$
+a kořeny $\lambda_1=1,\;\lambda_2=2$.
+  * Základní řešení: $u_n = 1^n = 1$, $v_n = 2^n$.
+  * Obecné řešení: $$a_n = \alpha\cdot1 + \beta\cdot2^n.$$
+  * Prostor všech řešení je tedy 2-rozměrný a jeho (jednou z možných) bází je $\{\,1,\,2^n\}$.
+====Příklad 2 – násobný kořen====
+Rovnice
+$$
+a_{n+2}-2a_{n+1}+a_n=0
+$$
+má charakteristický polynom $p(\lambda)=(\lambda-1)^2$, kořen $\lambda=1$ s násobností 2.
+  * Základní řešení: $u_n = 1^n = 1$, $v_n = n\cdot1^n = n$.
+  * Obecné řešení: $$a_n = \alpha + \beta n.$$
+  * Znovu dostáváme 2-rozměrný prostor řešení, tentokrát s bází $\{\,1,\,n\}$.
-==== Rozložitelnost a asymptotika ====
-<markdown>
-- **Rozložitelnost (reducibilní řetězec)**: Pokud neexistuje cesta mezi některými stavy.
-- **Irreducibilní řetězec**: Všechny stavy jsou vzájemně dosažitelné.
-</markdown>
-  * **Asymptotické chování**: Pro irreducibilní, aperiodické a pozitivně rekurentní řetězce konverguje distribuce k **stacionárnímu rozdělení** $\pi$, které splňuje $\pi = \pi P$.
-==== Přechodový diagram a matice ====
-Příklad diagramu:
-<tikzjax>
-\usepackage{tikz}
-\usetikzlibrary{matrix,arrows.meta,positioning}
-\begin{document}
-\begin{tikzpicture}
-  \node (A) at (0,0) {A};
-  \node (B) at (2,0) {B};
-  \node (C) at (4,0) {C};
-  \draw[->, >=latex] (A) to[bend left] node[above] {0.5} (B);
-  \draw[->, >=latex] (A) to[bend left] node[below] {0.3} (C);
-  \draw[->, >=latex] (B) to[loop above] node {1.0} (B);
-  \draw[->, >=latex] (C) to[bend left] node[above] {0.1} (A);
-  \draw[->, >=latex] (C) to[bend left] node[below] {0.2} (B);
-  \draw[->, >=latex] (C) to[loop above] node {0.7} (C);
-\end{tikzpicture}
-\end{document}
-</tikzjax>
-==== Matice přechodu ====
-|       | A     | B     | C     |
-| **A** | 0.0   | 0.5   | 0.3   |
-| **B** | 0.0   | 1.0   | 0.0   |
-| **C** | 0.1   | 0.2   | 0.7   |

Trace:

Differences

Search

Navigation

Print/export

Tools

QR Code