# Algoritmická teorie her: cvičení

- cvičení nebude úplně pravidelně
	- bude oznámeno, když cviko odpadne
- https://kam.mff.cuni.cz/~cizek/ath2425/ath.html
- dotazy na/po cviku nebo mailem
- zápočet
	- 4 sady domácích úkolů, v každé 3–4 příklady
	- celkem 36 bodů, z nich potřebujeme 18 na zápočet
	- zápočtový test byl zrušen
	- všichni musejí na zkoušku, ale zkoušející bude přihlížet k vyššímu počtu bodů z příkladů
	- odevzdávání přes Sovu
	- deadline vždycky za 2 týdny
	- čím dřív odevzdáme, tím je větší šance, že dostaneme zpětnou vazbu včas a budeme si moct řešení opravit

## Lineární programování

- soustava $n$ lineárních nerovnic (podmínek) $p_1,\dots,p_n$ o $m$ neznámých
	- podmínka $p_i:a_{i1}x_1+a_{i2}x_2+\dots+a_{im}x_m\leq b_i$
	- řešení … $x=(x_1,\dots,x_m)\in\mathbb R^m$
	- maximalizujeme účelovou funkci $c_1x_1+c_2x_2+\dots+c_mx_m$
- u řešení lineárních rovnic – lineární rovnice reprezentují nadroviny, hledáme jejich průniky
- lineární nerovnice reprezentují poloroviny, určují nějaký mnohostěn (nemusí být omezený)
	- účelová funkce roste ve směru vektoru $c$
	- nadrovina kolmá na $c$ určuje řešení se stejnou hodnotou účelové funkce
	- „zametáme“ nadrovinou, najdeme optimální řešení $x^*$
	- pozorování: aspoň jedno optimální řešení se nachází ve vrcholu mnohostěnu
- co se může stát
	- lineární program nemá řešení – průnik (mnohostěn) je prázdný
	- má řešení, ale není omezené
	- má maximální řešení
- simplexová metoda
	- začne v nějakém vrcholu, pak cestuje po hraně dokud nedojde do dalšího vrcholu
	- podle pivotovacího pravidla si vybírá další směr
	- simplexová metoda může běžet až exponenciálně
		- ale průměrně je velmi rychlá
		- jsou i polynomiální způsoby řešení
- kanonická forma (tvar) … viz handout
- existuje také ILP, celočíselné lineární programování
	- řešení se nacházejí na celočíselné mřížce uvnitř mnohostěnu
	- tento problém je NP těžký