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

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Mat. prog. a polyedr. kombinatorika Loebl 22. 1. 2013

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

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 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:

Nahoru