od marxin » 20. 1. 2011 11:03
Dnešní zkouška:
1) Řešil jsem pomocí
, potom už stačí vzít f ze s-m-n věty, nechce se mi dále ukazovat
3) stačí jednoduše použít větu z přednášky, kde je vyjádřen počet všech konfigurací TS
4) lehce se převede na VP, za hranu e=(x,y) ve VP vložím orientované hrany (x,y) a (y,x) a k nechám
5) převede se položením K=B a s(a) = v(a) na batoh, pro který máme pseudopolynomiální algoritmus a díky omezení cen je
a tedy se ten algoritmus stává polynomiálním a proto je i Omezený součet podmnožiny polynomiální.
Pro úspěšnou písemnou část je potřeba mít alespoň 3 příklady, pak se jde na ústní a člověk si vylosuje jednu otázku ze Složitosti a jednu z Vyčíslitelnosti. Pokud někdo napíše na 4 příklady, pak si může z jedné hromádky 2 otázky a zodpoví jenom jednu. Při 6 příkladech si vybere po 2 kartičkách z obojího a opět zodpoví jenom jednu.
Hodně štěstí
- Přílohy
-
Dnešní zkouška:
1) Řešil jsem pomocí [latex]\psi(x,y) \cong o(x) . \varphi_x(x) + y[/latex], potom už stačí vzít f ze s-m-n věty, nechce se mi dále ukazovat
3) stačí jednoduše použít větu z přednášky, kde je vyjádřen počet všech konfigurací TS
4) lehce se převede na VP, za hranu e=(x,y) ve VP vložím orientované hrany (x,y) a (y,x) a k nechám
5) převede se položením K=B a s(a) = v(a) na batoh, pro který máme pseudopolynomiální algoritmus a díky omezení cen je [latex]V \leq n^2[/latex] a tedy se ten algoritmus stává polynomiálním a proto je i Omezený součet podmnožiny polynomiální.
Pro úspěšnou písemnou část je potřeba mít alespoň 3 příklady, pak se jde na ústní a člověk si vylosuje jednu otázku ze Složitosti a jednu z Vyčíslitelnosti. Pokud někdo napíše na 4 příklady, pak si může z jedné hromádky 2 otázky a zodpoví jenom jednu. Při 6 příkladech si vybere po 2 kartičkách z obojího a opět zodpoví jenom jednu.
Hodně štěstí