od mathemage » 22. 1. 2013 16:41
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
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
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
1) [b]Hladový algoritmus pro (poly)matroid[/b] [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 [latex]EP_f[/latex] 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. [i]HA funguje vždy právě na matroidech[/i]) jsem málem nedal - v důkazu jedním směrem jsem si nemohl vzpomenout na pomocné lemma [latex]\forall i \in \mathbb{N}: z'(\{1,\cdots,i\}) >= z(\{1,\cdots,i\})[/latex] a rovněž jsem měl víceméně [i](ale spíš více)[/i] 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.
[u]Ponaučení:[/u] 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: