# Mat. prog. a polyedr. kombinatorika Loebl 22. 1. 2013

<{ForumPost(poster="mathemage", timestamp=2013-01-22 16:41:13)}>
1) **Hladový algoritmus pro (poly)matroid** \[základní definice - matroid, submodulární funkce, (rozšířený) polymatroid; hladový algoritmus - popis, souvislost s matroidy; hladový algoritmus optimalisující nad rozšířeným polymatroidem]  
  
Optimalisaci nad $EP_f$ jsem popsal jenom znění, k důkazu jsem se už nedostal (45 min už mu přišlo jako velmi dlouho).  
  
Souvislost HA s matroidy (tj. *HA funguje vždy právě na matroidech*) jsem málem nedal - v důkazu jedním směrem jsem si nemohl vzpomenout na pomocné lemma $\forall i \in \mathbb{N}: z'(\{1,\cdots,i\}) >= z(\{1,\cdots,i\})$ a rovněž jsem měl víceméně *(ale spíš více)* komplikace s teleskopickou sumou. Málem to vypadalo, že vyletím, ale nakonec jsem si vzpomněl na obrázek a vše dopsal a dořešil, což mu úplně stačilo na 1.  
  
Ponaučení: U pana prof. Loebla se téměř zdá, že neexistují známky 2 a 3. Buď napíšete vše do detailů (pan profesor nechce nic slyšet ústně) - nebo je na vás posuzováno, jako byste nenapsali nic :twisted:
<{/ForumPost}>