[Zap] 14.1.2009
Napsal: 14. 1. 2009 16:48
Dneska jsme dostali tuto sadu prikladu:
1) Reseni dvou rekurentnich rovnic
a) T(n) = 2T(n/2) + n^3
b) T(n) = 2T(2n/3) + T(n/3) + n * sqrt(n)
2) priklad z 3. cviceni cislo 3 (podle toho dokumentu co ma p. Cepek na webu)
tj. ze DFS minimalizuje pocet inkonzistentnich hran.... - dokazat nebo vyvratit
3) Problem TAUT
a) Je TAUT ve tride co-NP?
b) Jaka je slozitost TAUT pokud je F CNF?
1) Reseni dvou rekurentnich rovnic
a) T(n) = 2T(n/2) + n^3
b) T(n) = 2T(2n/3) + T(n/3) + n * sqrt(n)
2) priklad z 3. cviceni cislo 3 (podle toho dokumentu co ma p. Cepek na webu)
tj. ze DFS minimalizuje pocet inkonzistentnich hran.... - dokazat nebo vyvratit
3) Problem TAUT
a) Je TAUT ve tride co-NP?
b) Jaka je slozitost TAUT pokud je F CNF?