od mathemage » 18. 5. 2014 14:14
Hans si sedl před tabuli na chodbě na KAMu a dělal, že je studentem, kterého mám naučit jeho předmět. V angličtině jsem začal u tabule přednášet:
- polytop, extended formulation, extended comlexity
- slack matrix, non-negative rank, jejich souvislost
- protokol, souvislost s rankem
- aplikace pro spanning tree polytope (tady jsem popleltl s cut-polytope, pak totiz šel řešit NP-úplný max-cut v poly-čase, ale nakonec to přešel)
- konkrétně protokol pro span. tree polytope
Doplňující otázky (přemýšlecí, co nebylo na přednášce):
- jak upravit protokol pro čistě 1-směrnou komunikaci
[Jeden hráč "simuluje" zaslané bity 2. hráče pravděpodobnostně a pošle informaci o simulovaných bitech druhému. Pokud je byl býval nemohl zaslat, vydá nulový výstup, jinak je zakomponuje do výpočtu. - viz příklad dále]
- 1-směrný protokol pro span. tree polytope.
[Bob simuluje pravděpodobnostně Alicin výběr kořene 
, a pošle ho společně s orientovanou hranou Alice. Pokud ona měla 
, započítá do výstupu, jinak vrátí 
. Ke konci se musí upravit pravděpodobnosti, vynásobením vhodného faktoru úměrného velikosti 
- Bipyramida
(polytop 
s horní a spodní špičkou v přidané dimenzi, něco jako 2 homog. kužele nahoru a dolu) -> jeji ext. complexity oproti původnímu polytopu
(zespoda aspoň )
, protože je projekce . Zeshora nejvýše +2)
, důsledek věty o ext. complexity konvexního sjednocení.
I když jsem některé doplň. ot. nevěděl, dostal jsem nakonec za 1, páč je to fakt nová oblast matematiky.
Hans si sedl před tabuli na chodbě na KAMu a dělal, že je studentem, kterého mám naučit jeho předmět. V angličtině jsem začal u tabule přednášet:
[list]
[*]polytop, extended formulation, extended comlexity
[*]slack matrix, non-negative rank, jejich souvislost
[*]protokol, souvislost s rankem
[*]aplikace pro spanning tree polytope (tady jsem popleltl s cut-polytope, pak totiz šel řešit NP-úplný max-cut v poly-čase, ale nakonec to přešel)
[*]konkrétně protokol pro span. tree polytope[/list]
Doplňující otázky (přemýšlecí, co nebylo na přednášce):
[list]
[*]jak upravit protokol pro čistě 1-směrnou komunikaci
[Jeden hráč "simuluje" zaslané bity 2. hráče pravděpodobnostně a pošle informaci o simulovaných bitech druhému. Pokud je byl býval nemohl zaslat, vydá nulový výstup, jinak je zakomponuje do výpočtu. - viz příklad dále]
[*]1-směrný protokol pro span. tree polytope.
[Bob simuluje pravděpodobnostně Alicin výběr kořene [latex]u[/latex], a pošle ho společně s orientovanou hranou Alice. Pokud ona měla [latex]u\in U[/latex], započítá do výstupu, jinak vrátí [latex]0[/latex]. Ke konci se musí upravit pravděpodobnosti, vynásobením vhodného faktoru úměrného velikosti [latex]U[/latex]
[*]Bipyramida [latex]B[/latex] (polytop [latex]P[/latex] s horní a spodní špičkou v přidané dimenzi, něco jako 2 homog. kužele nahoru a dolu) -> jeji ext. complexity oproti původnímu polytopu [latex]P[/latex]
(zespoda aspoň [latex]xc(P)[/latex], protože [latex]P[/latex] je projekce [latex]B[/latex]. Zeshora nejvýše [latex]xc(P)+2[/latex], důsledek věty o ext. complexity konvexního sjednocení.[/list]
I když jsem některé doplň. ot. nevěděl, dostal jsem nakonec za 1, páč je to fakt nová oblast matematiky. :twisted: