od JiriD » 11. 1. 2011 11:58
Zadání 1:
1) dokažte, že je to matroid (zadání b z cvičení, disj. podmnožiny a v I množiny obsahující z každé max. 1 prvek)(1.cvičení)
2) algoritmus na hledání stoku v O(n) (2.cvičení)
3) Navrhněte alg., který pomocí Blackboxu na VP najde nějaké minimální VP (3. cvičení)
Zadání 2:
neměl jsem, ale myslím že:
TAUT bez otázky, zda je v NP (cvičení 3)
Navrhněte alg., který pro les, strom nalezne optimální VP (5. cvičení)
nejkratší cesta mezi s a t se zápornými hranami (4. cvičení)
Případně mě někdo opravte.
60 minut času, osobně si myslím, že po 40 minutách už není co řešit.
Zadání 1:
1) dokažte, že je to matroid (zadání b z cvičení, disj. podmnožiny a v I množiny obsahující z každé max. 1 prvek)(1.cvičení)
2) algoritmus na hledání stoku v O(n) (2.cvičení)
3) Navrhněte alg., který pomocí Blackboxu na VP najde nějaké minimální VP (3. cvičení)
Zadání 2:
neměl jsem, ale myslím že:
TAUT bez otázky, zda je v NP (cvičení 3)
Navrhněte alg., který pro les, strom nalezne optimální VP (5. cvičení)
nejkratší cesta mezi s a t se zápornými hranami (4. cvičení)
Případně mě někdo opravte.
60 minut času, osobně si myslím, že po 40 minutách už není co řešit.