Zkouška

Seznam

1. Prohledávání stavového prostoru (Search)

• Krokování algoritmů: Umět ručně projít a zapsat pořadí expanze uzlů.
  • BFS (Prohledávání do šířky) - FIFO fronta
  • DFS (Prohledávání do hloubky) - Zásobník (LIFO)
  • UCS (Uniform Cost Search) - Nejmenší cena $g(n)$
  • Greedy (Hladové) - Nejmenší heuristika $h(n)$
  • A* (A-star) - Nejmenší $f(n)=g(n)+h(n)$
• Vlastnosti algoritmů: Znát úplnost, optimalitu, a časovou/prostorovou složitost (zejména rozdíl v paměti mezi DFS a BFS/A*).
• Tree Search vs. Graph Search: Chápat rozdíl (využití “closed list / explored set” u hledání v grafu).
• Chytáky a vlastnosti algoritmů (Typické Testové Otázky):
  • BFS najde nejkratší cestu počtem hran, ale nemusí to být nejlevnější cesta (pokud mají hrany různou cenu).
  • UCS je vylepšené BFS (nikoliv DFS) pro ohodnocené grafy. Najde optimální řešení, pokud jsou ceny hran $\ge 0$.
  • DFS může kvůli omezení hloubky nenajít řešení.
  • BFS a DFS nenajdou vždy stejné řešení (BFS jde po vrstvách, DFS vezme první větev do hloubky).
• Vlastnosti heuristiky: Umět matematicky ověřit na zadaném grafu:
  • Přípustnost (Admissibility): $h(n)\le h^{\ast }(n)$ (nikdy nenadceňuje)
  • Konzistence (Monotónnost): $h(A)\le c(A,C)+h(C)$ (trojúhelníková nerovnost)

2. Adversariální prohledávání (Hry pro dva hráče)

• Minimax: Umět vyhodnotit herní strom (hráč MAX bere maximum, MIN bere minimum).
• Alfa-beta prořezávání: (Absolutní priorita - počítá se vždy!)
  • Krok za krokem projít strom zleva doprava a aktualizovat intervaly $(\alpha ,\beta )$.
  • Aplikovat podmínku pro řez: Odříznout větve, jakmile $\alpha \ge \beta$.
• Heuristické ohodnocení: Pochopit ukončení prohledávání v určité hloubce a vyhodnocení stavu (evaluační funkce).

3. Hry s neurčitostí (Expectimax)

• Expectimax algoritmus: Vyhodnocení stromů s náhodnými (chance) uzly.
• Výpočet: Očekávaná hodnota (vážený průměr) náhodného uzlu: $E=\sum (p_i\cdot h_i)$.
• Základy pravděpodobnosti: Podmíněná pravděpodobnost, sjednocení a průnik nezávislých jevů.

4. Markovovy rozhodovací procesy (MDP)

• Definice prostředí: Stavy $S$, akce $A$, odměna $R(s)$, diskontní faktor $\gamma$, přechodový model $P(s^{\prime }|s,a)$.
• Bellmanovy rovnice: Value Iteration (Iterace hodnot) - ruční výpočet $V(s)$ ve 2-3 krocích na bludišti.
  • Vzorec: $V(s)=R(s)+\gamma \cdot {\max }_a\sum P(s^{\prime }|s,a)V(s^{\prime })$
• Extrakce strategie: Výpočet Q-hodnot $Q(s,a)$ ze zadaných $V(s)$ a určení optimální akce.
• Nekonečné řady: Výpočet hodnoty stavu při cyklení se nebo setrvání na místě: $V=\frac{R}{1-\gamma }$.
• Interpretace chování agenta (Testové otázky):
  • Co udělá agent při extrémně záporné živoucí odměně (např. -10)? (Páchá sebevraždu skokem do nejbližší pasti, aby ukončil penalizaci).
  • Co se stane, když $\gamma \to 0$? (Agent ignoruje budoucnost a jde jen po okamžité odměně).

5. Učení posilováním (Reinforcement Learning - RL)

• Monte Carlo metody: Odhad hodnot z epizod (First-visit vs. Every-visit).
  • Rozdíl a výpočet pomocí metod First-visit vs. Every-visit.
• Q-learning (Off-policy): Aktualizační pravidlo z jednoho kroku agenta.
  • Vzorec: $Q(s,a)\leftarrow Q(s,a)+\alpha [R+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a)]$
• Rozdíl Q-learning vs. SARSA (Testový chyták):
  • Q-learning updatuje podle teoreticky nejlepší budoucí akce (${\max }_{a^{\prime }}$).
  • SARSA (On-policy) updatuje podle akce, kterou agent v dalším kroku skutečně provede (včetně případných náhodných kroků z $ϵ$-greedy strategie).
• Průzkum vs. Využití (Exploration vs. Exploitation): Výpočet pravděpodobností chování s využitím $ϵ$-greedy strategie.

6. Bayesovské rozhodování (Zaručeno v testu!)

• Definice úlohy: Správně určit množinu skrytých stavů ($S$), pozorování ($X$) a rozhodnutí ($D$).
• Bayesova věta: Výpočet aposteriorní pravděpodobnosti $P(s|x)=\frac{P(x|s)P(s)}{P(x)}$.
• Matice ztrát/odměn & Strategie:
  • Sestavit matici a spočítat podmíněné riziko.
  • Najít strategii, která riziko minimalizuje.
• Změna strategie: Chápat úvahu, co se stane s rozhodnutím, když extrémně zdražíme falešně negativní případ (např. přehlédnutí nemoci $\to$ budeme diagnostikovat jako nemocné skoro všechny).
• Rozhodovací strategie:
  • Výpočet podmíněného rizika.
  • Hledání optimální strategie minimalizující riziko nebo maximalizující očekávaný zisk.
  • MAP (Maximum A Posteriori) a ML (Maximum Likelihood) hypotézy.

7. Strojové učení a klasifikátory (Machine Learning)

• k-Nejbližší sousedé (k-NN):
  • Klasifikace bodu na základě hlasování $k$ sousedů.
  • Výpočty vzdáleností (zejména Manhattanská $L_1$ a Euklidovská $L_2$).
• Lineární klasifikátory:
  • Dosazení bodu do lineární funkce a odvození rovnice rozhodovací hranice (nadroviny).
  • Dosazení bodu do lineární diskriminační funkce $g(x)=w_0+w_1{x}_1+\dots$
  • Výpočet rovnice rozhodovací hranice (nadroviny).
• Vyhodnocení klasifikátoru (Confusion Matrix):
  • Zkonstruovat matici záměn (TP, TN, FP, FN).
  • Umět z hlavy vzorce pro: Accuracy, Precision a Recall.
• Interpretace metrik (Otevřená otázka za hodně bodů):
  • Vysoký Recall, Nižší Precision: Vhodné pro Medicínu (nechci minout nemocného, falešný poplach tolik nevadí). Nevhodné pro vojenské systémy.
  • Vysoká Precision, Nižší Recall: Vhodné pro Spam filter (když už něco smažu, musím si být jistý). Nevhodné pro detekci kritických hrozeb.
• Naivní Bayesův klasifikátor: Predikce třídy (a nutnost znát Laplaceovo vyhlazování pro řešení nulových pravděpodobností).
• Vyhodnocení klasifikátoru (Evaluace):
  • Sestavení matice záměn (Confusion Matrix: TP, TN, FP, FN).
  • Výpočet metrik: Accuracy, Precision, Recall (Sensitivity), Specificity.
  • Pochopení ROC křivky.

1. Prohledávání

Vlastnosti prohledávacích algoritmů

Algoritmus	Zkratka	Úplnost (Najde řešení?)	Optimalita (Nejlevnější?)	Časová složitost	Paměťová (Prostorová) složitost
Prohledávání do šířky	BFS	✅ Ano*	✅ Ano* (jen pokud mají všechny hrany stejnou cenu)	$O(b^d)$	$O(b^d)$ 🔴 (Velmi špatná, pamatuje si celou vrstvu)
Prohledávání do hloubky	DFS	❌ Ne (může uvíznout v nekonečné větvi)	❌ Ne	$O(b^m)$	$O(b\cdot m)$ 🟢 (Skvělá! Pamatuje si jen 1 větev)
Iterativní prohlubování	ID-DFS	✅ Ano	✅ Ano* (jako BFS)	$O(b^d)$	$O(b\cdot d)$ 🟢 (Spojuje výhody BFS a DFS)
Hledání uniformních cen	UCS	✅ Ano*	✅ Ano	$O(b^{1+\lfloor C^{\ast }/ϵ\rfloor })$	$O(b^{1+\lfloor C^{\ast }/ϵ\rfloor })$ 🔴 (Pamatuje si celou frontu)
Hladové prohledávání	Greedy	❌ Ne	❌ Ne	$O(b^m)$ (v nejhorším případě)	$O(b^m)$ (v nejhorším případě)
Algoritmus A*	A*	✅ Ano*	✅ Ano (musí mít přípustnou heuristikou)	Exponenciální (závisí na kvalitě heuristiky)	Exponenciální 🔴 (Ukládá všechny prozkoumané uzly)

🔑 Vysvětlivky proměnných (Zkouškový slovníček):

• $b$ (branching factor): Faktor větvení – kolik má jeden uzel průměrně dětí (sousedů).
• $d$ (depth): Hloubka, ve které se nachází nejmělčí cíl (nejkratší cesta).
• $m$ (maximum depth): Maximální hloubka celého stavového prostoru (může být nekonečná).
• $C^{\ast }$: Skutečná cena optimálního řešení.
• $ϵ$: Nejmenší možná cena jednoho kroku (aby se algoritmus nezacyklil na hranách s nulovou cenou).

Typické chytáky do testu (True/False):

1. Proč se vůbec používá DFS, když není optimální ani úplné?
   • Protože má lineární paměťovou složitost $O(b\cdot m)$. Zkrátka nezaplní RAMku počítače, na rozdíl od BFS nebo A*, kterým paměť při velkých grafech okamžitě dojde.
2. Kdy je BFS optimální?
   • BFS nehledá nejlevnější cestu, ale cestu s nejmenším počtem hran (kroků). Pokud by měly hrany různou cenu (např. 1, 5, 10), BFS optimální není.
3. *Kdy selže úplnost algoritmů (to jsou ty hvězdičky )?
   • UCS a A* nenajdou řešení, pokud v grafu existují cesty se zápornou cenou, nebo s cenou menší než nějaké velmi malé číslo $ϵ$ (algoritmus by mohl dělat nekonečně mnoho mikrokroků a nedojít do cíle).

todo tabulku z těchto témat

BFS

Úplnost

Optimalita

Časová náročnost

Paměťová náročnost

DFS

ID-DFS

UCS

Greedy

A${}^{\ast }$

konec tabulky

Přípustnost

Konzistence

2. Adversariální prohledávání

MiniMax

Alfa-beta

Heuristicé ohodnocení

3. Hry s neurčitostí

4. MDP