---
# System prepended metadata

title: Zjednodušené zápisky na intuitivní úroveň
tags: [opakování]

---

# Zjednodušené zápisky na intuitivní úroveň

:::danger
Pište to tak jako kdyby jste to říkali před komisí.
Vyhněte se definicím není-li to nutné.
Snažte se nezatěžovat věcmi navíc, ale jen zachytit esenci.
:::

## SZ1: Metody umělé inteligence
### Prohledávání stavového prostoru, lokální prohledávání a metaheuristiky s jedním řešením
Okolí definujeme jako $O: S\rightarrow2^S$, kde S je množina možných řešení.

#### Prohledávání stavového prostoru
Je způsob jak řešit problémy jejichž prostředí je pozorovatelné, statické a deterministické. Prostředí je reprezentováno stavovým prostorem a cílem je najít minimální sekvenci přechodů pomocí kterých se dostaneme z počátečního stavu do cílového stavu.

Typickými problémy je problém obchodního cestujícího (TSP), navigace z A do B, atp.
Algoritmy prohledávání se dělí na neinformované (BFS,DFS,...) a informované (Greedy best-first search, A*).


#### Metaheuristiky s jedním řešením
Metaheuristika je obecná heuristika aplikovatelná na vícero problémů. Například simulované žíhání, evoluční algoritmy, ...

Při volbě metaheuristik je důležité balancovat dva základní protichůdné principy a ty jsou exploitation vs exploration. Nebo-li jak moc bude algoritmus využívat toho co ví oproti prozkoumávání nových možností.

Metaheuristiky s jedním řešením jsou přístupy které se snaží vylepšovat jedno řešení. Tedy simulované žíhání, iterovaný prohledávání, atp. Oproti tomu jsou metaheuristiky založené na populaci tj.: evoluční algoritmy, genetické algoritmy. A metaheuristiky založené na swarm inteligence: ant colony optimalization. (obojí učí pelánek v Modelování a simulace)

Základní metaheuristiky s jedním řešením pro lokální okolí jsou:
1. permutační problémy
* k-distance -- vyměnění k uzlů mezi sebou
* k-opt -- vymaže k hran a přidá nových k hran
2. rozvrhovací problémy
* operátor vložení -- vyjme a vloží k prvků jinam
* operátor výměny -- vymění k prvků
* operátor inverze -- otočí pořadí u k prvků

Základní metaheuristiky s jedním řešením pro rozsáhlá okolí jsou:
* k-level ejection chain 
* cyclic exchange



#### Lokální prohledávání
Lokální prohledávání nebo-li hill climbing je metaheuristika, kterou si můžeme představit jako výletníka co se snaží dostat na nejvyšší vrchol, avšak nemá jinou formu navigace než jeho oči, tedy nejlepší strategií je pro něj jít směrem kde vidí nejvyšší bod. Jedná se o základní informovaný algoritmus, který je dále rozšiřován o další metaheuristiky.


V praxi se používají spádové metody jako gradient descent, saddle-point, ...; Výběr nejlepšího souseda; Náhodný výběr z lepších sousedů.

Takto jednoduchý algoritmus však trpí na uvíznutí v lokálních maximech/minimech, proto se používají vylepšení jako:
Simulované žíhání (simulated annealing) a tabu prohledávání.

Další problém může být rozsáhlost stavového prostoru. Na to se dá použít opakované prohledávání s různým počátkem či nastavením.
Nebo iterativní prohledávání (další prohledávání začnu kde jsem skončil minulé).

Další úpravy: proměnlivé okolí, řízené lokální prohledávání.

Oproti lokálnímu prohledávání je globální přístup a to jsou evoluční algoritmy, genetické algoritmy, atp.

*[proměnlivé okolí]: změna v parametru např. velikosti okolí

*[řízené lokální prohledávání]: změna v optimalizované funkci


### Plánování, reprezentace problému, plánování se stavovým prostorem.
#### Plánování
Cíle plánování mohou být:
* Dobytí cílového stavu
* Splnění cílové podmínky
* Optimalizace objektivní funkce



#### Reprezentace problému
Problém může být reprezentován množinovou či klasickou reprezentací.

##### Množinová reprezentace
Stav je popsán množinou výroků.
Akce je syntaktický výraz specifikující jaké výroky musí patřit do současného stavu a jaké výroky akce přidá / odebere.

##### Klasická reprezentace (STRIPS)
Zobecňuje množinovou reprezentaci směrem k predikátové logice.

Systém je složen z množin akcí A, stavů S, přechodové funkce y, počátečného stavu $S_0$ a množiny koncových stavů g.
$P = (\Sigma,s_0,g); \Sigma = (A,S,y)$
Přechodová funkce je pak y: S x A x E $\rightarrow$ P(S). Kde E jsou eventy neovlivnitelné systémem.

Stav je množina logických atomů, které jsou pravdivé či nepravdivé.
Akce je plánovacím operátorem (predikátem), který mění pravdivost/nepravdivost atomů, tak že je přidá/odebere z domén True, False. Zároveň každá akce má predikát s podmínkou, která musí platit pro provedení akce.


##### Temporální reprezentace
Rozdíl od klasického plánování je to, že akce mají navíc dobu trvání, můžou se překrývat a účelová funkce bývá typicky minimalizace dokončení všech akcí. Řešení není posloupnost ale rozvrh akcí.

#### Plánování se stavovým prostorem
Snažíme se transformovat prohledávaný prostor tak, aby odpovídal stavovému prostoru (z předchozí otázky). Stavy jsou uzly, akce jsou hrany a cílem je najít nejkratší cestu od počátečního stavu k nějakému stavu konečnému.

Typy prohledávání jsou dopředné, zpětné (STRIPS), problémově závislé.

##### Dopředné plánování
Začínáme v počátečním stavu a jdeme k některému cílovému stavu. Je potřeba umět pro každý stav: rozhodnout zda je cílový, najít aplikovatelné akce a spočítat stavy do kterých se dostaname po aplikaci možných akcí.
Pokud toto umíme, pak umíme jednoduše převést problém na prohledávání stav. prostoru.

Na následné prohlédávání v prostoru se nejčastěji používá A* s nějakou heuristikou.

Dobředné plánování trpí na veliký počet větvení -- vhodné použít prořezávání.

##### zpětné plánování
Začínáme od množiny cílových stavů a současně od nich prohledáváme (upravujeme je na podcíle) zpětně dokud nenarazíme na počáteční stav.
Analogicky k dopřednému je potřeba umět rozhodnout zda stav odpovídá cíli, pro daný cíl najít relevantní akce, vypočítat podcíl umožňující aplikovat akci podcíl $\rightarrow$ cíl.

Je korektní a úplná, avšak na úplnost potřebujeme detekci cyklů.

Větvení se řeší pomocí liftingu -- částečná inicializace akcí.
Další zmenšení prohledávacího prostoru je pomocí STRIPS -- STRIPS nejprve vyřešení podmínky právě přidané akce, pokud lze, tak se akce přidá a nemusí se řešit backtrackingem. STRIPS má však problém se Sussamanovou anomálií, kde při řešení nějakého cíle můžeme rozbít cíl druhý a pak ho musíme znovu opravit (redundance v řešení cíle).

### Práce s neurčitostí, odvozování v Bayesovských sítích, čas a neurčitost.
#### Práce s neurčitostí
Práce s neurčitostí se hodí pro interakci s reálným světem.

#### Odvozování v Bayesovských sítích
[Video na vysvětlení matiky](https://www.youtube.com/watch?v=TuGDMj43ehw)

Pravidla:
1. $P(x_1,\dots,x_n) = \prod_i P(x_i|parents(x_i))$
2. $P(a|b) = P(a,b)/P(b) = \alpha * P(a,b)$ -- *$\alpha$ je jenom normalizační* konstanta

Mějme model: $P(R,C) \rightarrow P(W) \rightarrow P(S)$, pak:
* $P(r|s) = \sum_w \sum_c P(r,c,w,s)/P(s)$ -- *suma přes náh. proměn. co nás nezajímají*
* $P(r|s) = \alpha * \sum_w \sum_c P(r,c,w,s)$ -- *aplikace pravidla 2.*
* $P(r|s) = \alpha * \sum_w \sum_c P(r) P(c)P(w|r,c)P(s|w)$ -- *aplikace pravidla 1.*

Avšak u takovéhoto výpočtu počítáme některé věcí vícekrát. Pro zefektivnění se dá využít struktury sítě a pamatovat si již spočítané položky (a.k.a dynamické programování).

Další způsob jak odhadnout danou pravděpodobnost je vzorkování pomocí metody monte carlo. Pomocí sítě vygenerujeme vzorky a danou hodnotu odhadneme statisticky.



#### Čas a neurčitost
Na základě vjemů agenta a pravděpodobností stavů (senzorický model) umíme identifikovat v jakém stavu se nacházíme (domnělý stav). Nyní je potřeba vymodelovat pravděpodobnosti přechodů mezi jednotlivými stavy (přechodový model).

![](https://i.imgur.com/QGM1rV8.png)

![](https://i.imgur.com/MtKP82f.png)

Když je pak spojíme dohromady tak dostaneme dynamickou bayesovskou síť:
![](https://i.imgur.com/BHnVXdC.png)


### Robotika, plánování pohybu robota
#### Robotika
Robot je fyzický agent, který vykonává úlohy interakcí s fyzickým světem.
Roboti se dělí na manipulátory (továrna, kuchař, ...), mobilní roboty (auto, autonomní drony, ...) a mobilní manipulátory (humanoidní, zvířecí, ...).

Robot je vybaven senzory a efektory (pohybové části).

##### Efektory
Efektory jsou hodnoceny tkzv. Degree Of Freedom DOFs. Kde počet DOFs odpovídá počtu možných rotací a posunů.
Non-holonomic chování je když počet ovladatelných prvků není stejný jako počet DOFs (auto).

##### Vnímání
Vnímání u robota je mapování dat ze senzorů na vnitřní reprezentaci prostředí. U toho je potřeba vyřešit šum a neúplnost pozorování.

Typy vnímání: lokalizace, mapování, teplota, pach, sluch, dotyk, ...

Vnímání se vyhodnocuje pomocí:
* Dynamických Bayesovských sítí,
* Kalmanových filtrů,
* strojové učení.




#### Plánování pohybu robota
Nejprve je potřeba vybrat reprezentaci prostoru, ve kterém se robot nachází.

Reprezentace pracovního prostoru -- celá pracovní plocha robota je popsána pomocí souřadnic. Výhodou je detekce snadná kolizí, ale zbytečně popisuje i části kam robot nedosáhne a díky spojitosti je náročené na výpočet při generování cest.

Reprezentace konfiguračního prostoru -- zde se řeší pouze všechny úhly kloubů a posuny ramen robota, který daný prostor definují. Problém může nastat pokud musíme cíle převést z pracovního prostoru, neboť se jedná o náročnou operaci (inverse kinematika), oproti kinematice (převod z konf. do prac. prostoru).

Konstrukce volného prostoru -- je velice komplikovaná (konfigurační prostor + pracovní prostor), proto se agent snaží zapamatovat konfigurace, při kterých nedochází ke kolizím v pracovním prostoru.


Převedení spojitého prostoru do diskrétního -- adaptivní diskretizace

Prohledávání diskrétního prostoru -- A*, JPS


## SZ2: Statistika

### Důkladná znalost základních statistických metod (bodové odhady, intervaly spolehlivosti, testování statistických hypotéz) 

- Funkce nad náhodným výběrem (sample, náhodný vektor) je **statistika**. Statistika, která bude pro různé náhodné výběry kolísat kolem nějakého parametru (střední hodnota, rozptyl apod.) se nazývá **bodovým odhadem** parametru. Požadovanou vlastností na bodový odhad je nestrannost bodového odhadu. Nestrannými odhady jsou např. výběrový průměr, výběrový rozptyl, výběrová směrodatná odchylka.

- Bodové odhady se budou téměř vždy lišit od skutečné hodnoty parametru. Budeme potřebovat lepší nástroj jak zjistit i přesnost odhadu. Použijeme proto **intervalové odhady**. Odhadovaný parametr bude ležet ve vytvořeném intervalu s nějakou hladinou rizika.
  $$
  P(T_d < \theta < T_h) = 1 - \alpha
  $$
  $1-\alpha$ je koeficient spolehlivosti, $\alpha$ je riziko odhadu, interval $(T_d, T_h)$ je $100 \cdot (1 - \alpha)$% interval spolehlivosti. Konstruujeme pomocí tzv. pivotových statistik, které jsou z rozdělení pravděpodobností, u kterých odhadovaný parametr známe.

- **Testování statistických hypotéz** nám slouží k vyvozování závěrů o hypotézách na základě statistických dat. Např. bychom chtěli otestovat zdali je vakcína proti COVIDU účinná. Otestujeme dvě skupiny: lidi co dostali vakcínu a lidi co dostali placebo. Pak budeme pozorovat rozdíl mezi nakaženými mezi těmito skupinami a testujeme zdali je rozdíl statisticky signifikantní.  Testujeme tak, že si stanovíme nulovou hypotézu (např. rovnost dvou různých středních hodnot), kterou buď budeme akceptovat nebo zamítat. Pokud zamítneme nulovou hypotézu, pak platí alternativní hypotéza. Konkrétně testujeme tak, že vypočteme testovací statistiku a koukneme jestli její hodnota patří do tzv. kritické oblasti, která závisí na hladině významnosti testu $\alpha$. Pokud ano, pak nulovou hypotézu zamítáme. Alternativně můžeme vypočítat tzv. p-hodnotu.
  ![img](https://media.discordapp.net/attachments/628626260423213106/710447009890304091/HypothesisPvalue1.png)

- Známé testy:

  ![img](https://i.imgur.com/rAETslX.png)

  

### ANOVA

- T-test slouží na porovnávání střední hodnoty dvou skupin. Pokud bychom chtěli porovnat střední hodnoty více než dvou skupin, nestačilo by nám použít t-test opakovaně. Protože by to zvětšovalo chybu 1. typu (false positive). Pro porovnávaní střední hodnot více než dvou skupin používáme **analýzu rozptylu (ANOVA)**.
- Pokud zkoumáme pouze skupiny v rámci jednoho faktoru (např. vzdělání = bez maturity, s maturitou, vysokoškolské tj. 1 faktor s 3 skupinami), pak mluvíme o **jednofaktorové (one-way) ANOVA**.
- Pokud zkoumáme skupiny v rámci více faktorů (např. vzdělání a cispohlaví tj. 3x2 skupin), pak obecně mluvíme o **vícefaktorové (n-way) ANOVA**. 
- Počítá se pomocí F statistiky, která počítá s odchylkami od celkového průměru, odchylkami od průměrů v rámci skupiny.

### Neparametrické testy hypotéz

- Prozatím jsme vždy pracovali s parametrickými testy. Ty se ovšem dají použít za nějakých předpokladů. Např. normalita dat, homogenita rozptylu (rozptyl musí být v populaci podobný jako ve vzorku), nezávislost dat. Pokud tyto předpoklady splněny nejsou, pak musíme použít neparametrické testy, které jsou **"slabší"**. Jsou z velké části založeny na **pořadí** jednotlivých hodnot. 
- t-test ~> Mann-Whitney U test, pokud jsou výběry závislé pak Wilcoxon signed-rank test
  ANOVA ~> Kruskalův-Wallisův test

### Mnohonásobná lineární regrese, autokorelace, multikolinearita

**Co je mnohonásobná lineární regrese?**

- "Jednoduchá" lineární regrese pracuje s jednou vysvětlující proměnnou (regresorem; kovariátem; prediktorem) tj.
  hledáme model $y = \beta_0 + \beta_1 x$. V mnohonásobné lineární regresi pracujeme s více proměnnými. Hledáme tedy model $y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_n x_n$. 
- Parametry $\beta$ odhadujeme pomocí **(ordinary) metody nejmenších čtverců** $\hat{\beta} = (X^TX)^{-1}X^T Y$.

**Co je multikolinearita?**

- Je to jev kdy v mnohonásobném regresním modelu nějaký prediktor je lineárně závislý na jiných prediktorech. Multikolinearita nesnižuje prediktivní sílu ani spolehlivost modelu. Ovlivňuje ovšem **výpočet** parametrů, protože lineární závislost prediktoru na nějakém jiném znamená, že hodnost matice $X$ bude nižší než je její dimenze. To mimo jiné znamená, že její determinant bude nulový a $(X^TX)^{-1}$ nepůjde invertovat. Přibližná multikolinearita způsobí velký rozptyl a numerickou nestabilitu.
- Detekce pomocí korelační matice.

**Co je autokorelace?**

- Při aplikaci lineárního regresního modelu na časovou řadu se často setkáme se vzájemnou korelovanosti chyb, které říkáme **autokorelace**. Důsledkem autokorelace je vliv náhodných chyb na budoucí pozorování. Častým typem autokorelace je tzv. **autoregrese 1. řádu**, kdy je chyba ovlivněna jednou předchozí chybou
  $$
  \epsilon_i = \theta_{\epsilon_{i-1}} + u_i
  $$
  , kde $\theta$ je tzv. autoregresní parametr, $|\theta| < 1$ a $u_i$ jsou nekorelované náhodné veličiny.

- Přítomnost autokorelace degraduje model. Detekuje se pomocí Durbinova-Watsonova testu.

### Analýza hlavních komponent (PCA)

- Slouží ke snížení dimenzí a pro odstranění multikolinearity. Funguje na principu ortogonalizaci báze vektorového prostoru původních náhodných veličin. Nové bázové náhodné veličiny (hlavní komponenty) jsou pak nekorelované.
  ![](https://i.imgur.com/cIYm95r.png)

Hlavní komponenty hledáme postupně tak, ať vysvětlují co nejvíce proměnné.


## SZ3: Superpočítače

### Superskalární, multijádrové a mnohojádrové (GPU, MIC) procesory, MIMD a SIMD paralelismus.

**Co je superskalární procesor?**

- Je to procesor, který implementuje paralelismus na úrovní HW. Zpracovává více instrukcí naráz v jednom tiku. Také se skládá z více procesních jednotek (Aritmetická logická jednotka, ALU), reálná čísla (floating point, FPU) a další. Využívá tzv. hlubokou superpipelinu.

**Co je multijádrový procesor?**

- Multijádrovými (vícejádrovými) procesory se rozumí procesory, které mají typicky 2-8 CPU jednotek na jednom čipu. Těm říkáme jádra.

**Co je mnohojádrový procesor?**

- Mnohojádrový (manycore) procesor je navržen pro vysoko propustné paralelní výpočty. Např. GPU.

**Jaký je rozdíl mezi multijádrovým a mnohojádrovým procesorem? (víceméně CPU vs GPU)**

- CPU vs GPU
  - U CPU se snažíme vykonat úlohu rychle (chceme snižovat latenci). U GPU chceme vyšší propustnost, tedy chceme masivně paralelizovat úlohy.
  - Stovky ALU v malém počtu jader vs tisíce ALU v desítkách multiprocesorů
  - MIMD, SIMD pro krátké vektory vs SIMT pro dlouhé vektory
  - velká cache vs malá cache pro čtení

**Co je MIC?**

- GPU je spojovaný s Nvidia. MIC (many integrated core) je odpovědí od Intelu na GPU od Nvidia. Nemá zdaleka tolik ALU jako GPU a snaží se být univerzálnější. Ale v poslední době se architektura přibližuje GPU. Pro lepší představu: Intel chtěl konkurovat NVIDIA Tesle se svým Xeon Phi, ale vypadá to, že to je dead a chtějí oznámit úplně novou architekturu. (zdroj https://en.wikipedia.org/wiki/Xeon_Phi#Knights_Hill)

**Co je MIMD a SIMD paralelismus?**

- **SIMD = Single Instruction Multiple Data** je výpočetní architektura pro paralelismus. Hlavní myšlenka je, že jsou procesory synchronizovány a vykonávají vždy stejnou instrukci na více datech. Mluvíme proto o tzv. **vektorových počítačích**. Architektura GPU odpovídá architektuře SIMD. CPU SIMD využívají pouze v malém rozsahu.
- **MIMD = Multiple Instruction Multiple Data** naopak od SIMD využívá asynchronní procesory, které pracují nezávisle na sobě. Spolu komunikují přes sdílenou nebo distribuovanou paměť. Jsou tedy flexibilnější, ale musí se explicitně synchronizovat, což ztěžuje programování.

### Organizace paměti, sdílená a distribuovaná, cache koherence.

**Jak organizujeme paměť?**

- Na té nejnižší úrovni organizujeme paměť do řádků a sloupců takže do matice. Adresy mají dvě části: číslo segmentu a offset. Naráz obvykle čteme související byty (paging mode). Pracujeme s logickými adresami, které překládáme do fyzických adres pomocí Translation look-aside buffer (TLB).

**Co je sdílená paměť?**

- Paměť, která je oddělená od procesorů. Přistupuje se k ní uniformně přes sběrnici. Složitě se prokládají výpočty a komunikace, protože se musí aktivně čekat.

**Co je distribuovaná paměť?**

- Každý procesor má vlastní paměť. Procesory mezi sebou komunikují pomocí předávání zpráv, což může stát větší cenu. Snáze se ale prokládají výpočty a komunikace.

**Co je cache koherence?**

- Chceme zabránit ostatním procesorům, aby pracovaly se zastaralými daty po změně dat v cache pamětích. Výpadek cache může způsobit např. když chce procesor data, které už neexistují; cache má nízkou kapacitu; cache má starou kopii dat; různé adresy jsou namapovány do stejného místa.
- Řešit to můžeme např. pomocí snoopy cache, která sleduje komunikaci po sběrnici a šíří informaci (broadcasting) o změně bloku po sběrnici. Všechny cache pak na změnu reagují buď zneplatněním daného bloku nebo okamžitou aktualizací dat. Špatně škáluje.
- Dalším řešením může být přes adresářové metody. Každá žádost o načtení dat z hlavní paměti do cache musí jít přes adresář, který udržuje informace o blocích v cache. Takže adresář ví o každých změnách a udržuje koherenci dat.

### Optimalizace kódu, optimalizující překladače.

**Co je optimalizující překladač?**

- Překladač, který minimalizuje či maximalizuje nějaké parametry počítačového programu (rychlost provedení, využití paměti, náročnost na výkon apod.). Nejčastěji program přeloží do nějakého mezijazyka, na kterém provede optimalizační transformace, které zachovají sémantiku programu.

**Jak probíhá optimalizace kódů?**

- Propagace proměnných kopírováním

  ```
  X = Y            	X = Y
  Z = 1 + X        ~> Z = 1 + Y
  ```

- Propagace konstant, odstranění mrtvého kódu (např. nedosažitelný kód)

- Přesun invariantního kódu z cyklů

- Reorganizace složitých výrazů, nadbytečné testy

- Podmíněné výrazy uprostřed cyklů nemusí závislé na cyklu

### Distribuované systémy, topologie síťového propojení.

**Co jsou distribuované systémy?**

- Systém více procesorů/počítačů, které jsou propojeny sítí. Komponenty spolu komunikují pomocí posílání zpráv. Má dobrou horizontální škálovatelnost (přidání dalšího uzlu do sítě). Chyba jednoho uzlu nemusí způsobit velké chyby.
  Příklady: Klient-Server, peer-to-peer, a další.

**Jak se liší distribuované systémy od paralelních systémů?**

- Distribuované systémy nemají sdílenou paměť. Události nejsou synchronizované a nastávají asynchronně.

**Jaké známe topologie síťového propojení?**
![](https://i.imgur.com/JKKBgnr.png)

- Můžeme rozdělit na 
  	jednorozměrné: lineární pole
  	dvourozměrné: kruh, hvězda, strom, dvourozměrná mřížka, torus
  	trojrozměrná: hyperkrychle

### Programování paralelních a distribuovaných systémů.

**Jak se navrhují paralelní algoritmy?**

- Dekompozicí problému na podproblémy: např. rozděl a panuj, prozkoumávání stavového prostoru,...
- Největším problémem je synchronizace dat:
  - Race condition: chyba, kdy jsou výsledky v nepředvídatelném nebo nesprávném pořadí.
  - Deadlock (uváznutí): chyba, kdy pro úspěšné dokončení první akce je podmíněno předchozím dokončením druhé akce, přičemž druhý akce může být dokončena až po dokončení první akce.
  - Hladovění (starvation, stárnutí, livelock): nastává, když je procesu neustále odmítán přidělit zdroj, je tak nevyužitý
- Řešením jsou mutexy, semafory, monitory.

**Jak se navrhují distribuované algoritmy?**

- ???

## SZ4: Databáze

### Ukládání dat

Fyzicky se ukládají v celé hierarchii pamětí/úložišť (*primární* -- cache, RAM; *sekundární* -- HDD, SSD; *terciární* -- pásky, disky).
V úložištích se ukládají do bloků pevných velikostí. 
Úložiště se dají chytřeji organizovat do diskových polí (RAID), které přináší např. striping (na úrovní bitů i bloků), zrcadlení dat, opravné kódy, paritu.

Jeden soubor je složen z několika bloků. Jeden blok je složen ze záznamů. Záznam je složen z datových elementů. Nejzákladnější typy datových elementů jsou: celá čísla, reálná čísla, boolean, časové typy, řetězce. Všechno až na bloky může mít pevnou i proměnlivou délku.

### Adresování záznamů

Nejnaivnější adresování je **přímá adresace** -- tj. uchováváme si fyzickou adresu záznamu. 
Chytřejší adresace je **nepřímá**, která používá **převodní tabulku** pro získání fyzické adresy. 
Dalším způsobem je **kombinace přímé a nepřímé adresace**, u které je fyzická adresa záznamu fyzická adresa bloku a pořadí záznamu v bloku (offset). 
Reálně ovšem využíváme **file system**. Adresa záznamu je ID souboru, číslo bloku a offset záznamu v bloku. Uložení bloku určuje file systém.


### Indexování a hašování více atributů
Indexování a hašování nám umožňuje přistupovat k datům pomocí dotazů. Každý způsob je jinak vhodný pro různé dotazy.

Pokud máme dvě podmínky na dvou atributech, tak můžeme použít index jednoho atributu a postupně odfiltrovávat podle podmínky druhého atributu.
Můžeme mít dva nezávislé indexy, které vrátí seznam kandidátů, ze kterých uděláme průnik.
Dále můžeme mít např. index, který indexuje indexy. Takže jde o nějaký "víceúrovňový" index.
U hašování můžeme využít tzv. dělené hašovací funkce. Zahašujou se dva různé klíče dvěmi různými funkcemi a haše se spojí do jedné adresy.

### Vyhodnocování dotazu

- Dotaz
- Syntaktická a sémantická kontrola
  - Strom dotazu
- Logický plán (relační algebra)
  - Úpravy plánu (optimalizace)
- Fyzický plán
- Vyhodnocení

### Algoritmy
- *Nevím přesně co by chtěli...HashJoin, MergeJoin apod.?*

### Statistiky a odhady nákladů

Nejčastější statistiky, které používáme k odhadům jsou: počet záznamů v relaci, velikost záznamů v relaci, počet obsazených bloků, počet unikátních hodnot atributů.

Např. odhad pro kartézský součin dvou relací $R$ a $S$ pro počet a velikost záznamů v relaci bude:
    - počet záznamů v relaci $R$ * počet záznamů v relaci $S$
    - velikost záznamů v relaci $R$ + velikost záznamů v relaci $S$
    
### Optimalizace dotazů
 - vygeneruji plány
 - profiltruji plány
 - ohodnotím plány
 - vyberu nejrychlejší 

### Transformace dotazů
 - Lokální změny = přepsání dotazu. Např.:
     - Místo `SELECT * FROM` vybereme konkrétní atributy, které chceme `SELECT attr1, attr2, ..., FROM`
     - Odstranění nadbytečného `DISTINCT`
     - Použití `t1 JOIN t2` místo kartézského součinu `FROM t1, t2`
 - Globální změny
     - Vytvoření indexu
     - Změna schématu 

### Optimalizace schémat a rozdělování dat.

- Normální formy:
    - 1NF = atomicita -- Každý atribut obsahuje pouze atomické hodnoty.
     - 2NF = 1NF + každý neklíčový atribut musí plně záviset na každém kandidátním klíči
        ![](https://i.imgur.com/Rd0xsKA.png)
        - Primární klíč tvoří ID kurzu a semestru. Jenže jméno kurzu závisí pouze na ID kurzu => není v 2NF. Stačí rozdělit na dvě tabulky.
    - 3NF = 2NF + nejsou tranzitivní funkční závislosti
        - ![](https://i.imgur.com/ppMlhW3.png)
        - Je ve 2NF, ale název žánru závisí na ID žánru => není ve 3NF. Rozdělíme na dvě tabulky
    - BCNF = 3NF + každá funkční závislost $X \to A$ platí, že X je (super)klíč

- Dělení
    - **Vertikální dělení** -- dělení na více tabulek
        - Zákazník(id, adresa, kredit)
              nebo  
            ZákazníkAdresa(id, adresa)
            ZákazníkKredit(id, kredit)
            jsou normalizované, ale hodí se na různé dotazy
    - **Horizontální dělení** -- rozkouskování tabulky na menší části (ale furt to je ta stejná tabulka). Záleží na DBMS. 

### Pravidla pro transformaci dotazů

Selekce a projekce by se měly vykonat co nejdříve (protože tím odfiltrujeme velkou část řádků). Pro join, kartézský součin, and a or platí asociativita a komutativita.

### Zpracování transakcí

Transakce je soubor akcí měnící data, které udržují konzsitenci dat (představ si zjednodušenou bankovní transakci). Základní operace transakce jsou:
    - Input(x)
    - Read(x, t)
    - Write(x, t)
    - Output(x)

### Výpadky transakcí

Výpadky transakcí může způsobit chyba transakce, chyba DB systému, výpadek hardwaru.

### Zotavení z výpadků

Máme dva hlavní způsoby prevence a řešení -- žurnálování a redundance.

Žurnálování během transakce produkuje záznamy (logguje) o změnách do žurnálu. Při výpadku se systém podívá do žurnálu a buď některé kroky zopakuje (REDO) nebo zruší (UNDO).

Redundance (RAID) umožní mít identická data. Načtou se data ze všech disků a hlasují o nejsprávnější (tedy nejspíš konzistentní) výsledek.

### Bezpečnost, přístupová oprávnění.

Potřebujeme zabezpečit, aby přístup k datům měly jen povolané osoby. Můžeme vytvořit účty k DB s různými přístupovými právy podobně jako ve file systému. Uživatelům nebo skupinám lze nastavit omezený přístup k různým relacím.

Zaměstnancům bychom např. chtěli skrýt platy svých kolegů, ale zároveň potřebují zjistit z relace ostatní data. To můžeme vyřešit např. pohledy. Znepřístupníme relaci `Zamestnanci(id, jmeno, adresa, plat)` a vytvoříme pohled `ZamestnanciAdresa(id, jmeno, adresa)`:
```sql=
CREATE VIEW ZamestnanciAdresa AS
    SELECT id, jmeno, adresa
    FROM Zamestnanci;
```
Případně pokud chceme zjistit např. průměrný plat zaměstnanců, tak se může vytvořit funkce bez zvěřejnění jednotlivých platů:
```sql=
CREATE FUNCTION avgsal() RETURNS real
AS 'SELECT avg(plat) FROM zamestnanci'
LANGUAGE SQL;
```
Uživatel pak použije `SELECT avgsal();`

Proti útokům na DB systém se můžeme bránit klasickými metodami pro zabezpečování např. serverů. Tedy firewall, silné heslo, SSL šifrované spojení, přístup pouze z VPN, práva k mazání tabulek jen u root účtu a mít těch účtů logicky více atd.



## SZ5: Neuronové sítě
### Vícevrstvé sítě a jejich výrazové schopnosti

#### 2-vrstvove NN
Vahy dokazu tvarovat sigmoid a bias ho dokaze posuvat v priestore. Kladna a zaporna sigmoida vytvara "kopcek". Jedna vrstva dokaze vytvorit ziadany pocet tychto utvarov Dalsia vstva dokaze urobit ich prienik. Takto dokazem 2-vrstvovov NN aproximovati hociaku [0,1]^n -> [0,1] funkciu na pozadovanu presnost.


![](https://i.imgur.com/shUV5zK.png)

[Vizualizator](https://www.desmos.com/calculator/ogxd0wmjje)

#### 3-vrstvove NN

3 vrstvy keď chceš spraviť bramboru:
Veľmi naivne -- rozsekáš si bramboru na ľubovoľne malé štvorečky. 
Prvá vrstva: Každý neuron ti ohraničuje jednu čiaru z štvorčeka.
Druhá vrstva: Vezme prienik medzi čiaramy zo štvorčeka a spraví štvorček.
Tretia vrstva: Sčíta štvorčeky dohromady.

![](https://i.imgur.com/SS9W25Z.png)

#### Rekurentne NN

Su ekvivalentne TM


### Učení neuronových sítí: Gradientní sestup, zpětná propagace, praktické otázky učení (příprava dat, inicializace vah, volba a adaptace hyperparametrů)


#### Zpětná propagace

Backpropagation je sposob ako vyratat parcialne derivacie loss function (napr. MSE) vzhladom pre kazdu vahu. 

[WIKI](https://en.wikipedia.org/wiki/Backpropagation)

#### Gradientní sestup

Algoritmus ktory vypocita update vah -> learning. Pouzije na to gradient (vektor parcialnych derivacii vyratanych Backprop). Gradient ukazuje smerom rastu priestoru a my hladame opacny smer -> kde funkcia klesa. Preto gradient od aktualnej vahy odpocitame vynasobeny learning rate.

  ![](http://hmkcode.github.io/images/ai/bp_update_formula.png)

 
Casto sa pouziva stochastic gradient descent kde iba nahodny set vah je updatnuty.
 

#### Priprava dat

Tradicne cistenie dat:
 - vyriesenie null values vynechanim alebo aproximaciou
 - odsekanie extremov
 - zakodovanie enumov
 - liearna transformacia -- PCA
 - ...

 
#### Hyperparametre

 Vsetko co zadavam do NN pri spustani ako Learning rate, dropout rate etc. Da sa odhadnut, pouzit grid search alevo hociake ine optimalizacne algoritmy. 
 
 [WIKI](https://en.wikipedia.org/wiki/Hyperparameter_optimization)
 

#### Inicializace vah
Bias sa inicializuje bezne na nulu. Vahy inicializujeme bud nahodne alebo z nejakym vhodnym algorithmom pre danu aktivacnu funkciu. Cielom je inicializovat ich okolo vstupu na ktorom  sklon funkcie nie je prilis  nizky (pomale trenovanie kvoli derivacii blizkej nule).

![](https://imgs.developpaper.com/imgs/MfIhi6.png)

### Regularizace
Regularizacia je set technik ako redukovat overfitting na trenovacie data pocas trenovania.

#### Dropout

Zapne pri trenovani na fully connected dense layer masku ktora nahodne deaktivuje set neuronou vo vrstve. Parameter p urcuje percento neuronou vo vrstve ktore sa maju pre dany priklad deaktivovat. 

![](https://i.stack.imgur.com/CewjH.png)

#### DropConnect 

Same ale nedeaktivuje neurony ale vstupne vahy

![](https://i.stack.imgur.com/D1QC7.png)

#### Weight Decay (L2 regularizacia, Ridge Regression)

Je po kazdom trenovacom kroku aplikovany na vahy a znizuje hodnotu vahy smerom k nule o nejake percento. Vahy ktore sa neupdatuju teda casom padnu na nulu a teda znizuje efekt nepodstatnych vah na model.

![](https://media.springernature.com/original/springer-static/image/chp%3A10.1007%2F978-3-319-75786-5_23/MediaObjects/453718_1_En_23_Fig1_HTML.gif)

#### Lasso regresia (L1 regularizacia)

Podobne ako wight decay ale pouziva sa absolutna hodnota vahy na update

Viac [TU](https://towardsdatascience.com/regularization-in-deep-learning-l1-l2-and-dropout-377e75acc036).


### Konvoluční sítě

![](https://i.imgur.com/LoUq4fD.png)

Konvolucne siete sa pouzivaju na hladanie vzorov v datach, ktore su na roznej pozicii (napr. features v roznej casti obrazku). 

Konvolucna siet sa sklada z:
 - Konvolucnych vsrtiev (feauture maps)
 - Pooling vrstiev

#### Konvolucna vsrtva (feauture maps)
Feauture maps prechadzaju vstup pomocou sliding window (kernel) o rozmere X*Y ktore sa posuva po vstupe o nejaky krok. V ramci jedneho kernelu sa zdielaju zdielaju vahy (kazda feature map hlada inu jednu feature inde v obraze). Tychto map sa vytvori pozadovany pocet a kazda ma vlasny kernel a teda sa uci (idealne) inu feature.

![](https://miro.medium.com/max/1000/1*GcI7G-JLAQiEoCON7xFbhg.gif)

#### Pooling vrstva

Tato vrstva sluzi na redukciu dimenzie feature map. Nie je povinna. Vrstva nema vahy ale cez svoje okno aplikuje funciu ako argMax alebo argAvg. 

![](https://miro.medium.com/max/792/1*uoWYsCV5vBU8SHFPAPao-w.gif)

### Rekurentní sítě (LSTM)

Rekurentne siete su siete ktore cast svojho vystupu vrcaju naspet na svoj vstup a kombinuju z dalsim vstupom. Dokazu pracovat zo sekvenciami roznej dlzky. LSTM siete su vhodne na spracovanie dejov ktore sa vyvijaju v case. LSTM Bunka sa sklada pamete (cell) a troch logickych bran. LSTM riesi problem vanishing and exploding gradient ktore maju obycajne RNN a preto dokaze napr. v texte si pametat informacie dlho ale aj menit kontext v pripade potreby.

![](https://pluralsight2.imgix.net/guides/8a8ac7c1-8bac-4e89-ace8-9e28813ab635_3.JPG)



## SZ6: Strojové učení
TODO

## SZ7: Dobývání znalostí
TODO

## SZ8: Vizualizace

### Základní metriky pro hodnocení kvality vizualizace (efektivita a expresivita), osm základních vizuálních proměnných. 

**Co je expresivita?**

- Je to poměr mezi zobrazenou informací a informací, kterou chceme sdělit. Tedy 1 je ideální expresivita, menší než 1 znamená, že zobrazujeme méně informací než jsme chtěli a víc než 1 znamená, že toho ukazujeme moc, což může být nebezpečné.

**Co je efektivita?**

- Vizualizace je efektivní, pokud se dá rychle vyrenderovat a interpretovat. Vypočítáme ji tedy jako $1/(1 + \text{cas interpretace} + \text{cas renderu})$

**Co jsou osm základních vizuálních proměnných?**

- Pozice, tvar, velikost, jas, barva, orientace, textura, pohyb.

### Základní vizualizační techniky pro 1D, 2D, 3D (explicitní a implicitní reprezentace povrchu) a 4D data (vizualizace toku pomocí streamlines a Line Integral Convolution). 

**Jaké jsou vizualizační techniky pro 1D data?**

- Sloupcové grafy (histogramy), distribuční graf 
  ![](https://i.imgur.com/4DRiI9E.png)


**Jaké jsou vizualizační techniky pro 2D data?**

- Bodový graf (scatterplot), obrázek, reliéf, mapa, kontura

**Jaké jsou vizualizační techniky pro 3D data?**

- Vizualizace explicitních povrchů je definována seznamem 3D vrcholů, seznamem hran mezi nimi a sadou parametrických rovnic (Bezier, B-Splajny).
- Vizualizace implicitních povrchů jsou definovány tzv. počáteční konturou (zero contour). Vhodnější pro blending a přeměny.
    ![enter image description here](https://www.fi.muni.cz/~xslanin/szz/vis_7.png)

**Jaké jsou vizualizační techniky pro 4D data?**

- Vizualizujeme dynamické chování tekutin a plynu. Tzv. vizualizace toku. Dělá se pomocí streamlines.

  ![](https://i.imgur.com/pIoaHHH.png)


- Line Integral Convolution vizualizuje vektorové pole. Vektorové pole "vyhladíme" a zprůměrujeme okolí jednotlivých vektorů pomocí konvoluce s náhodným šumem.

  ![](https://i.imgur.com/j6mSVUC.png)


### Techniky pro vizualizaci multidimenzionálních dat (paralelní souřadnice) a hierarchických struktur (treemaps, dimensional stacking). 

- Matice bodových grafů, radviz
- Paralelní souřadnice: 1 bod/záznam je zobrazen jako lomená čára
  ![](https://www.data-to-viz.com/graph/parallel_files/figure-html/unnamed-chunk-1-1.png)

- Hierarchická data můžeme vizualizovat jako treemaps
  ![](https://www.fi.muni.cz/~xslanin/szz/vis_10.png)
- Nebo pomoci techniky dimensional stacking
  ![](https://i.imgur.com/cUvKu3H.png)

### Základní třídy interakčních technik (fisheye, perspektivní stěny).

**Jak můžeme s vizualizaci interagovat?**

- Navigace (panning, zoom), výběr, filtrace

**Co je fisheye a perspektivní stěny?**
![enter image description here](https://www.fi.muni.cz/~xslanin/szz/vis_14.png)


## ML1: Pravděpodobnost v informatice

### Diskrétní pravděpodobnostní prostor

- Teorie pravděpodobnosti se zabývá **náhodnými pokusy**. Množina všech možných "nejelementárnějších" výsledků náhodných pokusů se jmenuje **prostor elementárních jevů / základní / výběrový prostor** ($\Omega$ případně $S$). 
- **Jev** $a$ je jakákoliv podmnožina prostoru elementárních jevů (tj. $a \in \mathcal{A} \subseteq 2^\Omega$, tj. množina všech jevů). (Mozna $\mathcal{A} = 2^\Omega$)
- **Pravděpodobnostní funkce** $P$ je funkce $P: \mathcal{A} \to [0, 1]$ .
- **Diskrétní pravděpodobnostní prostor** je trojice $(\Omega, \mathcal{A}, P)$, kde
  - $\Omega$ je výběrový prostor (např. hod kostkou $\to$ $\Omega = \{1,2,3,4,5,6\}$)
  - $\mathcal{A} = 2^\Omega$ je množina všech jevů (např. obsahuje jev $\text{Odd} = \{1,3,5\}$ značící lichá čísla na kostce)
  - $P: \mathcal{A} \to [0, 1]$ je pravděpodobnostní funkce

### Spojitý pravděpodobnostní prostor

- Na rozdíl od diskrétního prostoru elementárních jevů je $\mathcal{A} = 2^\Omega$ příliš velké a nejsme schopni rozumně přiřadit pravděpodobnost pro každý prvek $\mathcal{A}$. Použijeme proto podmnožinu $\mathcal{A} \subseteq 2^\Omega$, kterou nazýváme **jevovou $\sigma$-algebru nad $\Omega$** pokud platí:
  - $\emptyset \in \mathcal{A}$
  - $A \in \mathcal{A} \Rightarrow \bar{A} \in \mathcal{A}$ (uzavřenost na doplněk)
  - $A_1, A_2, ... \in \mathcal{A} \Rightarrow \bigcup\limits_{n=1}^{\infty} A_{n} \in A$ (je uzavřená na spočetná sjednocení)
- **Spojitý pravděpodobnostní prostor** je pak trojice $(\Omega, \mathcal{A}, P)$, kde
  - $\Omega$ je výběrový prostor
    - $\mathcal{A} \subseteq 2^{\Omega}$ je jevová $\sigma$-algebra nad $\Omega$ (nebo někdy **jevové pole**)
    - $P: \mathcal{A} \rightarrow [0,1 ]$ je pravděpodobnostní funkce

**Náhodná proměnná a její použití.** 

- **Diskrétní náhodná proměnná/veličina** $X$ definovaná nad výběrovým prostorem $\Omega$ je funkce $X: \Omega \to \mathbb{R}$. Přiřazuje každému elementárnímu jevu $\omega \in \Omega$ reálnou hodnotu $X(\omega)$.

  - Příklad. Házíme 2 kostkami a náhodná proměnná $X$ sleduje součet čísel na kostkách.
    $\Omega=\{(1,1), (1, 2), ..., (6,5), (6,6)\}$
    $X((1, 2)) = 3$

- **Pravděpodobnostní funkce** diskrétní náhodné proměnné $X$ je funkce
  $$
  p_X(x) = P(X = x) = \sum\limits_{\omega: X(w) = x} P(\omega)
  $$

  - Příklad. Jaká je pravděpodobnost, že součet na kostkách bude 4 tj. $P(X = 4)$
    $$
    \begin{array}{rl}
    	p_X(4) &= P(X = 4)\\ &= P(\{(1,3)\}) + P(\{(2,2)\}) + P(\{(3,1)\})\\ &= 1/36 + 1/36 + 1/36 \\&= 1/12
    \end{array}
    $$

- **Distribuční funkce** diskrétní náhodné proměnné $X$ je funkce
  $$
  F_X(x) = P(X \leq x) = \sum\limits_{t \leq x} p_X(t)
  $$

  - Je **neklesající**, **zprava spojitá**.
  - $\lim\limits_{x \to +\infty} F_X(x) = 1$ a $\lim\limits_{x \to -\infty} F_X(x) = 0$
  - $\forall x \in \mathbb{R}: 0 \leq F_X(x) \leq 1$

  ---

- **Spojitá náhodná proměnná** $X$ definovaná nad $(\Omega, \mathcal{A}, P)$ je funkce $X: \Omega \to \mathbb{R}$, která splňuje
  $$
  \forall r \in R: \{s \mid X(S \leq r)\} \in \mathcal{A}
  $$

- **Distribuční funkce** spojité náhodné proměnné $X$ je funkce $F_X(x) = P(X \leq x)$.

- **Hustota rozdělení pravděpodobnosti** náhodné spojité proměnné $X$ je funkce $f_X$ taková, že
  $$
  F_X(x) = \int\limits^x_{-\infty}f_X(t) dt
  $$
  tj.
  $$
  P(a \leq X \leq b) = \int\limits^b_af_X(t)dt
  $$

### Střední hodnota

- Střední hodnota diskrétní náhodné proměnné $X$ je
  $$
  E(X) = \sum\limits_{x} x \cdot p_X(x)
  $$

- Střední hodnota spojité náhodné proměnné $X$ je
  $$
  E(X) = \int\limits^\infty_{-\infty}x\cdot f_X(x)dx
  $$

- Vlastnosti

  - **Linearita**
    - $E(X + Y) = E(X) + E(Y)$
    - $E(cX) = cE(X)$
  - Pokud $X$ a $Y$ jsou **nezávislé** náhodné proměnné, pak
    $E(XY) = E(X)\cdot E(Y)$

### Rozptyl

- **Rozptyl** náhodné proměnné $X$ je
  $$
  Var(X) = E([X - E(X)]^2) = E(X^2) - [E(X)]^2
  $$
*"průměrná kvadratická chyba od střední hodnoty"*

- Vlastnosti

  - Nechť $a, b$ jsou reálná čísla, pak
    $$
    Var(aX + b) = a^2Var(X)
    $$

  - Pokud náhodné proměnné $X$ a $Y$ jsou **nezávislé**, pak
    $$
    Var(X + Y) = Var(X) + Var(Y)
    $$
    

- **Směrodatná odchylka** je $\sigma_X = \sqrt{Var(X)}$

- **Kovariance** je **mírou lineární závislosti** dvou veličin. Tj.
  $$
  Cov(X, Y) = E([X - E(X)]\cdot[Y-E(Y)]) = E(XY) - E(X) \cdot E(Y)
  $$

  - Pro dvě nezávislé náhodné veličiny je kovariance 0.

- Pokud náhodné proměnné $X$ a $Y$ nejsou nezávislé, pak
  $$
  Var(X + Y) = Var(X) + Var(Y) + 2\cdot Cov(X,Y)
  $$

- Kovariance nám sice měří míru lineární závislosti, ale hodnoty se **špatně interpretují**, protože se můžou velmi lišit. Proto si kovarianci normalizujeme pomocí součinu $\sigma_X \cdot \sigma_Y$. Dostaneme **korelační koeficient**, jehož hodnoty nabývají od -1 po 1.
  $$
  \rho = \frac{Cov(X, Y)}{\sigma_X \cdot \sigma_Y}
  $$
  
  #### Markovova (Čebyševova I. typu) nerovnost
  
- libovolnou nezápornou náhodnou veličinu $X$ se střední hodnotou $E[X]$ je pravděpodobnost, že veličina $X$ nabude alespoň hodnoty $\epsilon$ dána podmínkou
$$
P(X > \epsilon) \leq\frac{E[X]} {\epsilon}
$$

X: hodnota na kostce: Pravděpodobnost, že padne 6: eps = 5.9, E[X] = 3.5 =>
$$
P(X > 5.9) \leq\frac{3.5} {5.9} = 0.5932
$$
...je to odhlad, ale opravdu slabý

#### Čebyševova nerovnost (II. typu)
Pro libovolnou náhodnou veličinu {$X$ se střední hodnotou $E(X)$ a rozptylem $Var((X)$ je pravděpodobnost, že absolutní hodnota $|X- E(X)|$ nabude hodnoty menší než libovolné $\varepsilon >0$ omezena 

$$
P(|X- E (X)|< \varepsilon ) \geq 1-\frac {D(X)}{ \varepsilon ^{2}}
$$

X: hodnota na kostce: Pravděpodobnost, že nepadne 1, ani 6: eps = 2.5, E[X] = 3.5, D(X) = 2.9166 =>

$$
P(|X- 3.5| < 2.5 ) \geq 1-\frac {2.9166}{ 2.5 ^{2}} = 0.5333
$$
...je to odhlad, ale pořád slabý. Dobrý k teoretickým důkazům

### Náhodné procesy

  - **Náhodný (stochastický) proces** je množina náhodných veličin $X = \{X_t \mid t \in T\}$, kde $t$ nejčastěji reprezentuje čas a $X_t$ se říká stav $X$ v čase $t$. Procesy můžou být definovány s **diskrétním/spojitým časem** či **diskrétními/spojitými stavy**.
  - Příklady: stav tiskárny, programu, zvířecí populace, ...

  ### Markovovy řetězce

  - **Markovův řetězec** je náhodný proces s diskrétním časem $\{X_1, X_2, X_3, ...\}$ pokud platí
    $$
    P(X_t = a \mid X_{t-1} = b, X_{t-2}=a_{t-2},...,X_0 = a_0) = P(X_t = a \mid X_{t-1}= b)
    $$
    tj. hodnota $X_t$ je závislá pouze na předchozí hodnotě $X_{t-1}$ a ne celé historii. Této vlastnosti říkáme **Markovův předpoklad**.

  - Můžeme vizualizovat jako **konečný automat** a přechody $p_{i,j} = \{(X_t = j \mid X_{t-1} = i\}$ označují pravděpodobnost, že proces změní stav $i$ na stav $j$ v jednom kroku. Přechodové pravděpodobnosti můžeme zapsat do **matice přechodu**.
    ![](https://i.imgur.com/cI9IKSi.png)
  - $\vec{\lambda}= (\lambda_1(t), \lambda_2(t),...$ označuje pravděpodobnostní distribuci ve stavech v čase $t$.
    Pokud chceme zjistit jak se změní pravděpodobnostní distribuci po několika krocích, využijeme matici přechodu
    $\vec{\lambda}(t + m) = \vec{\lambda}(t) \cdot P^m$
  - U Markovovských řetězců můžeme chtít zjistit zdali se z nějakého stavu umíme dostat do nějaké podmnožiny stavů. Pravděpodobnost, že se v $H^A$ krocích dostaneme do některého ze stavu z $A$ je $h_i^A = P(X_t \text{ pro nějaké  t }\geq 0| X_0 = i)$
  - Stavy
    - **Absorpční** stav iff nejde již opustit, jakmile do něj vstoupíme.
    - **Rekurentní stav** iff pokud v něm začneme a vrátíme se do něj s pravděpodobnosti 1.
    - **Transientní (nerekurentní)** stav iff pokud je nenulová pravděpodobnost, že se proces nevrátí.
  - Markovův řetězec je **irreducible** právě když je **silně souvislá komponenta**.

  ### Teorie informace (entropie, vzájemná informace)

  - Teorie informace se zabývá měřením, přenosem, kódováním, ukládáním a následným zpracováním informací z kvantitativního hlediska.

  - **Entropie** náhodné proměnné s pravděpodobnostní funkcí $p_X(x)$ je *"míra nejistoty"*
    $$
    H(X) = E\left[\log\dfrac{1}{p_X(x)}\right] = - E[\log p_X(x)]= - \sum\limits_x p_X(x) \cdot \log p_X(x)
    $$

    - Vždy nezáporná.
    - Příklad. Hod mincí. Pokud je férová mince, pak je entropie nejvyšší. Pokud je "cinklá", tak víme, že nějaká strana bude padat častěji.

  - **Sdružená entropie** dvou náhodných proměnných se sdruženou pravděpodobnostní funkcí $p_XY(x, y) = P(X = x, Y=y)$ je
    $$
    H(X,Y) = E\left[\log\dfrac{1}{p_{XY}(x, y)}\right]= -E[\log p_{XY}(x, y)] = - \sum\limits_x \sum\limits_y p_{XY}(x, y) \cdot \log p_{XY}(x, y)
    $$

  - **Podmíněná entropie** dvou náhodných proměnných je míra nejistoty výsledku $X$, za předpokladu, že známe $Y$.
    $$
    H(X\mid Y) = -E[\log p_{X\mid Y}(X \mid Y)] = -\sum\limits_x\sum\limits_y p_{XY}(x, y) \cdot \log p_{X \mid Y}(x \mid y)
    $$

    ​	Podmíněná pravděpodobnost dvou náhodných proměnných se vypočítá jako
    $$
    p_{X\mid Y}(x \mid y) = \dfrac{p_{XY}(x, y)}{p_{X}(y)}
    $$
    ​	Podmíněnost logicky nezvyšuje entropii, protože máme nějakou informaci navíc, tedy
    $$
    H(X \mid Y) \leq H(X)
    $$
    ​		Ostrá nerovnost v případě, že nejsou nezávislé.

  - **Řetízkové pravidlo (chain rule)** podmíněné entropie
    $$
    H(X,Y) = H(Y) + H(X \mid Y)
    $$

    ---

  - **Relativní entropie (Kullback-Leibler divergence)** jak se liší odhadovaná/aproxminovaná distribuce $q(x)$ od skutečné distribuce $p(x)$
    $$
    D(p\|q) = E_p\left[\log\dfrac{p(X)}{p(Y)}\right]=\sum\limits_x p(x) \log\dfrac{p(x)}{q(x)}
    $$

  - **Vzájemná informace (mutual information)** měří kolik informace náhodná proměnná obsahuje o druhé náhodné proměnné
    $$
    I(X; Y) = D(p(x, y) \| p(x)p(y)) = E\left[\log\dfrac{p(X, Y)}{p(X)p(Y)}\right] =
    \sum\limits_x \sum\limits_y p(x, y) \cdot \log\dfrac{p(x, y)}{p(x)p(y)}
    $$
    Vztah s entropii
    $$
    I(X;Y) = H(X) - H(X\mid Y)
    $$
    Symetrie
    $$
    I(X;Y) = H(X) - H(X\mid Y) = H(Y) - H(Y\mid X)
    $$
    

  ### Teorie kódování (Huffmanovo kódování, kapacita chybových kanálů).

  - **Kód** náhodné proměnné je funkce $C: \text{Im}(X) \to D^*$, kde $D^*$ je slovo nad abecedou $D$.

  - **Prefixový kód** je takový kód, kde žádný kód není prefixem jiného kódu. Jde tedy jednoduše dekódovat.

  - **Huffmanův kód** je **optimální** prefixový kód. Kódování se vytváří hladově bottom-up. 
    https://www.youtube.com/watch?v=dM6us854Jk0

  - **Chybový kanál** je model komunikace. Je dán vstupní abecedou $\mathcal{X}$, výstupní abecedou $\mathcal{Y}$ a pravděpodobnostní maticí $p(y\mid x)$.
    ![](https://i.imgur.com/muIbHWk.png)


    - Používá se především u OCR, spell checkingu, speech recognition, machine translation.

    - Modelujeme chybu (noise, šum) kanálu, na základě kterého chceme umět dekódovat výstup a zjistit, co bylo vstupním slovem. Tedy zjednodušeně: pokud z kanálu vyšlo $y$, chceme zjistit, které $x$ to bylo. $\hat{x}$ budeme značit náš odhad $x$-ka.
      $$
      \hat{x} = \arg\max_x p(x \mid y)
      $$
      Umíme odhadnout $p(x)$, $p(y)$ a $p(y \mid x)$. Ovšem tyhle známé hodnoty se nikde nevyskytují ve výše uvedeným vztahu. Použijeme proto Bayesovou větu.
      $$
      \hat{x} = 
      \arg\max_x \dfrac{p(y \mid x) p(x)}{p(y)}
      $$
      

      Protože $p(y)$ je v argmaxu konstantní, můžeme ho vyhodit
      $$
      \hat{x} =
      \arg\max_x p(y \mid x) p(x)
      $$
      (Tohle je maximum likelihood estimation)

  - **Kapacita chybového kanálu** je jaké maximální množství informace lze přes kanál posílat s velmi malou chybou.
    $$
    C = \max\limits_{p_X(x)}I(X;Y)
    $$


## ML2: Výpočetní logika
### Složitost a výčíslitelnost problému splnitelnosti
Problém splnitelnosti (SAT) je problém rozhodnout zdali je daná formule splnitelná.
Ve výrokové logice a predikátové logice bez rovnosti se jedná o NP-úplný problém.
V predikátové logice je problém nerozhodnutelný.


### Rezoluční metoda ve výrokové a predikátové logice
Rezoluční metoda slouží k dokázání sporem, že daná formule je nesplnitelná. Princip je založen na ekvivalenci formulí: $((X,A_0,\dots), (\neg X, B_0,\dots)) \Leftrightarrow ((A_0,\dots, B_0,\dots))$.
Ve výrokové logice a predikátové logice bez rovnosti je korektní a úplná.
Pro výrokovou logiku musí být formule v konjunktivní normální formě (CNF).
Pro predikátovou logiku musí být v skolemově normální formě (SNF).


### Jazyk prolog, relační algebra a Datalog
#### Jazyk prolog
Je logický programovací jazyk. Prolog je založen na predikátové logice prvního řádu; konkrétně se omezuje na Hornovy klauzule. Základními využívanými přístupy jsou unifikace, rekurze a backtracking. Program prologu je databáze faktů a pravidel.
Pomocí dokazování cíle metodou unifikace a SLD rezoluce dostaneme výsledek pravda/nepravda, případně seznam hodnot volných proměnných, pro které je cíl pravdivý vzhledem k databázi faktů a pravidel.



#### Relační algebra
Relační algebra je v informatice formální systém pro manipulaci s relacemi, který se používá zejména na popis operací v relačních databázích. Operandy algebry jsou relace, operátory jsou množinové operátory (jelikož každá relace je současně i množinou) a speciální relační operátory, jako selekce (řádky), projekce (sloupce) nebo join (v doslovném překladu spojení). 

#### Datalog
Zjednodušená verze Prologu, která byla vyvinuta pro práci s dedukčními databázemi. Oproti Prologu nemá funkční symboly, řezy, negace apod.
Stejně jako u prologu je program datalogu tvořen hornovými klauzulemi, které rozšiřuje o odvozené.
Datalog terminuje v případě že neodvodí žádné nové relace.
Je vhodný pro dynamické programování.

### Tablové důkazy ve výrokové a predikátové modální logice.
Tableau je dokazovací metoda sporem, která je založena na odvozování subformulí pomocí odvozovacích pravidel z formule u které chceme vyvrátit splnitelnost. Jedná se o stromovou strukturu kde každý uzel odpovídá jedné subformuli, která byla dokázána či zamítnuta.
Pokud se nám povede ve všech větvích stromu dokázat a zamítnoust stejnou subformuli, pak jsme našli spor.

https://ktiml.mff.cuni.cz/~gregor/logics/VPL04.pdf

*Asi bych zde doporučil si zkusit nějaké tablo, protože nevím na co jiného by se tu mohli ptát krom toho že tam bude něco k vyřešení a dostaneš ty pravidla na papíře.*

### Natural deduction
Narozdíl od tableau se pomocí přirozené dedukce nedokazuje nesplnitelnost ale tautologii formule. Dokazovací systém je inspirovaný lidským uvažováním, odtud jméno přirozená dedukce. Danou formuli se pomocí odvozovacích pravidel snažíme dosáhnout axiomů.

### Induktivní inference ve výrokové a predikátové logice
Je inspirováno machine learning algoritmy. Jedná se o hledání obecných hypotéz na základě pozorovaných dat pomocí indukce.

#### Výroková
Ve výrokové logice jsou všechny atributy one-hot encoded (dummy proměnné) a predikce se provádí právě nad jedním atributem. Tedy se snaží aproximovat funkci $f: \{0,1\}^n\rightarrow \{0,1\}$.
Hypotézy jsou hledané v prostoru hypotéz.

Za zmíňku stojí především dva algoritmy.
Jeden je Find-S a druhý Candidate-elimination:
* Find-S prochází hypotézy od nejspecifičtější (žádný atribut $\rightarrow$ první instance $\rightarrow \dots$). Pokud narazí na nesoulad instance a současné hypotézy, tak hledá první obecnější která platí i pro tuto instanci. Find-S bere v úvahu pouze kladné instance.
* Candidate-elimination je vpodstatě rozšíření Find-S o záporné instance. Pokud narazíme na zápornou instanci, tak eliminujeme ty obecné hypotézy, ze kterých záporná instance nevyplývá.

#### Predikátová
ILP algoritmus.  TODO

#### Modální (specificky Temporal Logic)
- Jde převést na predikátovou (ne opačně, je tedy slabší)
- Přidává ◇φ ‘sometime in the future φ holds’
- ◻φ ‘always in the future φ holds’
- Nejčastě se kreslí jako orientovaný graf
    - Stavy jsou chvíle v čase 
    - Hrany jsou akce


##### Bisimulace
- Taková homografie mezi 2 přechodovými systémy.
- Mapování stavů na stavy, tak že jsou všechny formule zachovány na obou stranách.

*[korektní]: Každá formule dokazatelná v Systému přirozené dedukce výrokové logiky je logicky platná.

*[úplná]: Každá logicky platná formule výrokové logiky je dokazatelná v Systému přirozené dedukce výrokové logiky.

*[CNF]: Conjuctive normal form -- ((A or B) and (X or Y)).

*[SNF]: Skollem normal form -- bez existenčních kvantifikátorů, ostatní kvantifikátory vpředu.

*[Hornovy klauzule]: Právě jeden pravdivý literál tj.: (A,-B,-C,...). Všimni si že to je ekvivalentní s (A <- (B,C,...)) neboli v prologu: A :- B,C,...    



## ML3: Zpracování přirozeného jazyka

### Automatická morfologická analýza.
Úkolem morfologické analýzy je získat větší vhled do jednotlivých slov v textu. Morfologická analýza pro každé slovo vrátí:

* základní slovní tvar (lemma)
* tagy (slovní druh, osoba, pád, číslo, jmenný rod, ...)

#### Automatizace
Slova máme uložená v databázi nebo v nějaké struktuře např.: strom / automat. Tato struktura zjistí lemma pro dané slovo. K lematu pak můžeme v slovníku dohledat vzor {lemma:vzor}. Tagy lemmatu jsou totožné se vzorem.

Příklady užití: Ajka (starší), Majka (má automat -- rychlejší)

### Rozpoznávání a generování větné struktury, gramatiky, základní typy syntaktické analýzy
#### Rozpoznávání a generování větné struktury

Větné struktury se parsují (rozpoznávají) pomocí statistických metod, pravidlových (gramatika), nebo hybridních.

Závislostní:
![](https://i.imgur.com/CWR7ixJ.png)
Složková:
![](https://i.imgur.com/4BV7zGb.png)

Závislostní se používá více v Češtině. Složková v EN (jsou dána pravidla kde co má být tedy je to lepší).



#### Gramatiky
Gramatiky se především používají pro jazyky bezkontextové, jako např. programovací jazyky. Bezkontextové jazyky nejsou dostatečně silné aby popsaly tak komplexní jazyk jako je angličtina, ale jelikož je angličtina velice dobře větně strukturována, tak pro zachycení syntaktiky jsou dostačující (složková gramatika).
U češtiny je lepší použít statistickou nebo hybridní metodu parsování. Příkladem hybridní metody je závislostní gramatika, která hledá nejmenší kostru ve statisticky naučených vazbách věty.


#### Typy syntaktické analýzy
Podle parsování:
* statistikou
* gramatikou 
* hybridně


### Sémantická analýza věty, logická analýza přirozeného jazyka
#### Sémantická analýza věty
Využívá všech znalostí o struktuře slov a vět získaných z nižších rovin analýzy jazyka. Na sémantické rovině se zkoumají významy slov, slovních spojení, vět, textů a následně jejich účely. Tato rovina obsahuje mnoho otevřených teoretických problémů a překážkou v praktické realizaci jsou mimo jiné také nedokonalosti ve výsledcích morfologické a syntaktické analýzy.

#### Logická analýza přirozeného jazyka
Patří do oblasti aplikované logiky. Logika však poskytuje obecný rámec, jehož aplikací vzniká na základě kooperace s lingvistikou právě logická analýza za jednotlivých  problémů spjatých s přirozeným  jazykem.

##### Predikátová logika
Nevýhodou predikátové logiky je nedostatečná vyjadřovací schopnost.
Některé věci jsou nevyjádřitelné (dobrý den), některé věci jsou pravdivé jen v určitém časovém úseku a jen někde (Prezidentem je Zeman), ...
Výhodou je jednoduchost.

##### Transparentní intenzionální logika
Snaží se vyřešit nedostatečnou explicitnost 1. řádu.
Zavádí nové možnosti:
* Světy
* Čas

Např.: "Prezidentem je Zeman"


### Pragmatická rovina, komunikační situace
Pragmatická rovina jako vědní disciplína se zabývá ústním projevem, tedy promluvami a výpověďmi. V této rovině je realizováno přiřazování objektů reálného světa. 
Pragmatiku můžeme rozlišit do:
* Externí -- komunikační situace, obecně známá fakta
* Interní -- vztahy mezi komunikujícími

Dále existují další typy:
* Implikatury -- závěry kterých chce hovořící dosáhnout
* Griceho konverzační principy -- hovořící jednají podle nějakých pravidel

Koncep speech acts -- Svět se mění v závislosti na konverzaci.

#### Komunikační situace
Místo kde se nachází, čas, rok, objekty související s konverzací, ...

Jedná se o externí pragmatiku.

### Zpracování řeči, dialogové systémy.
#### Zpracování řeči
Zpracování řeči je disciplína, která se zabývá především rozpoznáváním řeči (poslouchající robot) a její syntézou (mluvící robot).

##### Syntéza řeči
Text to Speech (TTS). Ideální stavem je nerozpoznatelnost od člověka. Momentálně je nejdál implementace pomocí transformerů (attention is all you need). 

Starý způsob řešení syntézy:

* V časové oblasti -- přednahrávané úseky (difóny, trifóny), problém s neplynulostí
* Frekvenční oblasti -- skládání z jednotlivých frekvencí, problém: náročnost, umělost.

##### Dialogové systémy
Dialogový systém je systém navržen tak, aby komunikoval s uživatelem pomocí dialogu v přirozeném jazyce. A to mluveném, psaném, vizuálním a jiným přirozeným projevem.
Výhodou je rychlejší a přirozenější komunikace pro uživatele.
Nevýhoda (nyní) -- řešení anomálních problémů na který systém neumí reagovat kvůli nedostatečné znalosti.

![](https://i.imgur.com/xK6mcZA.png)

V praxi používá např. firma Lemonade na vyplácení pojistého.


### Korpusy, statistické a pravidlové značkování. 
#### Korpusy
Korpus je soubor textových dat v přirozeném jazyce.

Využívají se ke studiu přirozeného jazyka a statistickým nástrojům NLP.
Zdroj se liší od požadovaného účelu.

Např. pro překlad se používá speciální korpus kde každá věta reprezentovaná v obou jazycích. Nejrozšířenějším korpusem ČR -- EN je korpus vytvořen z jednání evropské unie.
 
 
#### Statistické a pravidlové značkování
http://nase-rec.ujc.cas.cz/archiv.php?art=7974

Korpusy bývají z pravidla hodně rozsáhlé, tedy pro snadnější orientaci a vyhledávání je potřeba jednotlivé materiály značkovat.

Proto je ve zmíněných korpusech každému slovu přiřazen jeho základní, slovníkový tvar (lemma) a morfologická značka (tag) popisující gramatické kategorie jako slovní druh, rod, číslo, pád atd. Díky tomu je možné zadávat dotazy s využitím základních tvarů slov nebo morfologických kategorií.

V podstatě jde o problém desambiguace slov.

Typ značky:
* morfologická -- slovní druh a gramatické kategorie
* syntaktická -- závislostní nebo složkový syntaktický strom
* semantická -- WSD, named entity recognition
* koreference -- určení anafory
* pragmatická -- označení hovořícího, komunikační situace


#####  značkovací metody

*Statistické metody:*

Základním principem statistických metod je tzv. trénování značkovacího programu (taggeru) na správně označkovaném vzorku dat, během něhož program zjišťuje, jak jsou které značky a jejich kombinace časté. Po natrénovaní využívá program informace získané na trénovacích datech pro značkování neznámého textu (korpusu), přičemž z možných kombinací značek volí tu nejpravděpodobnější.

Výhodou statistického taggeru je relativní nenáročnost jeho přizpůsobení pro konkrétní jazyk, dále rychlost a schopnost označkovat jakýkoli text včetně textů chybných nebo velmi komplikovaných. Během několika posledních let došlo k výraznému zlepšení úspěšnosti statistických taggerů (viz hodnocení úspěšnosti níže). Nevýhodou statistických taggerů je, že se mohou jen velmi omezeně zlepšovat na základě zjištěných chyb, mohou vytvořit i gramaticky zcela nesprávné interpretace a jsou závislé na manuálně označkovaných trénovacích datech.

 
*Pravidlové metody:*

„Pravidlová“ disambiguace je metoda, která k odstranění homonymie u slov využívá poznatky o jazyce ve formě „pravidel“. Tato pravidla v kontextu několika slov nebo celé věty odstraňují u jednotlivých slov morfologické značky, které odpovídají negramatické konstrukci. Pravidla vytváří tým lingvistů na základě znalostí jazykového systému ověřených na korpusových datech.


Výhodou pravidlové metody je malý počet chyb a možnost každou chybu způsobenou pravidly opravit (změnou dotyčného pravidla nebo zařazením dané konstrukce jako výjimky – např. „od nevidím do nevidím“). Nevýhodou pravidlové disambiguace je výrazně větší náročnost vytváření lingvistických pravidel, větší citlivost na textové chyby.


## ML4: Programování s omezujícími podmínkami

### Konzistence a algoritmy pro binární a nebinární podmínky. 

- **Co jsou omezující podmínky?**
  - Máme nějaké doménové proměnné $Y = \{y_1,...,y_k\}$ a jejich doménu $D = D_1 \cup ... D_j$.
    Omezením $c$ na $Y$ je relace nad doménou $D$.
- **Co je problém splňování podmínek?**
  - Je to trojice $(X, D, C)$, kde 
    $X$ je konečná množina proměnných $X = \{x_1, ..., x_n\}$
    $D$ je konečná množina hodnot (doména) $D = D_1 \cup ... D_n$
    $C$ je konečná množina omezení $C = \{c_1, ..., c_m\}$, kde jsou omezení definovány nad podmnožině $X$.
- **Jak se řeší CSP?**
  - Tím, že najdeme úplné ohodnocení proměnných, které splňuje všechna omezení. Můžeme najít jedno řešení, všechna řešení či optimální řešení vzhledem k účelové funkci (tj. optimalizační problém s podmínkami, constraint optimization problem).
  - CSP můžeme reprezentovat jako graf, kde vrcholy jsou proměnné a hrany podmínky.
  - Přístupy řešení: konzistenční algoritmy (postupně odstraňují nekonzistence), prohledávací algoritmy (graf).
- **Co je konzistence?**
  - Existuje několik druhů konzistence. Nejjednodušší konzistencí je **vrcholová konzistence**. Vrchol je konzistentní, když všechny hodnoty z aktuální domény splňují všechny unární podmínky vrcholu. Vrcholovou konzistenci můžeme rozšířit na **hranovou konzistenci**, kterou pak můžeme rozšířit i na **konzistenci po cestě**.
- **Jaké jsou algoritmy pro binární podmínky?**
  - Každý CSP se dá převést na binární CSP. Na binární CSP pak existují algoritmy, které revidují postupně hrany, aby byly hranově konzistentní (tzv. Arch Consistency, AC algoritmy) nebo konzistentní po cestě (tzv. Path Consistency, PC algoritmy).
- **Jaké jsou algoritmy pro nebinární podmínky?**
  - PC a AC algoritmy "rozšiřovaly" konzistenci do další proměnné. Obecně můžeme pokračovat i pro více proměnných. Takže si zavedeme tzv. k-konzistenci, která nám říká, že pokud máme konzistentní ohodnocení k-1 proměnných a můžeme jej rozšířit do k-té proměnné.Používají se na to směrové i-konzistence (DIC).
  - V praxi se převádí problémy na binární CSP.

### Stromové prohledávání, pohled dopředu, pohled zpět, neúplné prohledávání.

- **Co je stromové prohledávání?**
  - CSP reprezentujeme jako stromový graf podmínek, kde uzly jsou částečné konzistentní ohodnocení. Hledáme tedy úplná řešení. Naivním způsobem bychom graf prohledávali *backtrackingem*. Mezi možnými vylepšeními jsou algoritmy pohledu dopředu a zpět.
- **Co je pohled dopředu?**
  - Před přiřazením hodnoty další proměnné zkontrolujeme budoucí hodnoty (zpropagujeme omezení).
- **Co je pohled zpět?**
  - Způsoby jakými se vracet ve stromě po neúspěšném přiřazení. Např. *backjumping*, který se vrací zpět ke konfliktní proměnné; *jumpback learning* si pamatuje chybná přiřazení, aby se jim vyhnul v dalších částech stromu.
- **Co je neúplné prohledávání?**
  - Jsou to algoritmy, které prohledávají pouze omezený prostor grafu, protože reálný problém může být velmi obsáhlý. Jsou často odvozeny od backtrackingu. Můžeme využít randomizování (náhodně vybíráme cestu). Můžeme hledání utnout po nějakém čase nebo počtu návratů apod. Můžeme omezit hloubku prohledávání.
  - Dalším přístupem jsou lokální prohledávání: hill climbing, random walk, tabu seznam, simulované žíhání.

###  CPLEX OPL, modelování pomocí omezujících podmínek, globální podmínky, omezující podmínky pro rozvrhování.

- **Co je CPLEX OPL?**

  - CPLEX je IBM optimalizační software. Problémy se definují pomocí modelovacího jazyku OPL (Optimization Programming Language).

- **Jak se modeluje pomocí omezujících podmínek?**

  - ```
    using CP;
    
    dvar int+ gas;
    dvar int+ chloride;
    
    maximize
    40 * gas + 50 * chloride
    
    subject to {
    	gas + chloride <= 50;
    	3 * gas + 4 * chloride <= 180;
    	chloride <= 40;
    };
    ```

- **Co jsou globální podmínky?**

  - Definují se nad libovolným konečným počtem proměnných.
  - Např.
    - `allDifferent` -- všechny proměnné musí být různé
    - `noOverlap` -- zákaz překryvu intervalu

- **Jak vypadají omezující podmínky pro rozvrhování?**

  ```
  using CP;
  
  int pocetStroju = ...;
  int pocetRobotu = ...;
  int pocetZamestnancu = ...;
  int pocetVyrobku = ...;
  
  range Stroje = 1..pocetStroju;
  range Roboti = 1..pocetRobotu;
  range Vyrobky = 1..pocetVyrobku;
  
  // Doba trvani kazde operace
  int TrvaniOperaci[Vyrobky][Stroje] = ...;
  
  // Booleanovske pole, ktere nam rika, jake roboty muze dana operace pouzit
  int MozniRoboti[Vyrobky][Stroje][Roboti] = ...;
  
  // Kolik je treba zamestnancu na kazdou operaci
  int PotrebaZamestnancu[Vyrobky][Stroje] = ...;
  
  // Intervaly pro kazdou operaci, vypocitaji startovni cas
  dvar interval operace[vyrobek in Vyrobky][stroj in Stroje] size TrvaniOperaci[vyrobek][stroj];
  
  // Volitelne prirazeni robotu k dane operaci
  dvar interval prirazeniRobotu[vyrobek in Vyrobky][stroj in Stroje][Roboti] optional; 
  
  // Roboti pracuji sekvencne, vice operaci se muze prekryvat, pokud muze robot pracovat
  dvar sequence planRobotu[robot in Roboti] in all(vyrobek in Vyrobky, 
  												 stroj in Stroje: MozniRoboti[vyrobek][stroj][robot] == 1) prirazeniRobotu[vyrobek][stroj][robot];
  
  // Uchovava aktualni pocet pracujicich
  cumulFunction pracujiciZamestnanci = sum(vyrobek in Vyrobky, stroj in Stroje) pulse(operace[vyrobek][stroj], PotrebaZamestnancu[vyrobek][stroj]);
  
  // Chceme minimalizovat cas dokonceni vyroby
  minimize max (vyrobek in Vyrobky) endOf(operace[vyrobek][3]);
  
  subject to {
  
    // Pracuje naraz maximalne <pocetZamestnancu>
    pracujiciZamestnanci <= pocetZamestnancu;
      
    forall (vyrobek in Vyrobky) {
    
      // Operace musi byt vykonany postupne
      forall (stroj in 2..pocetStroju) endBeforeStart(operace[vyrobek][stroj - 1], operace[vyrobek][stroj]);
      
      // Prirazeni volitelneho intervalu (robota) kazde operaci
      forall (stroj in Stroje) 
        alternative(operace[vyrobek][stroj],
        			  all (robot in Roboti: MozniRoboti[vyrobek][stroj][robot] == 1) 
        			    prirazeniRobotu[vyrobek][stroj][robot]);
    }    
    
    // Roboti muzou soucasne pracovat pouze na jedne operaci 
    forall(robot in Roboti) noOverlap(planRobotu[robot]);  
    
  }
  ```
  
## ML5: Umělá inteligence ve zpracování obrazu
TODO


## ML6: Strojové učení
TODO
