Fórum studentů MFF UK

Jak jsem slíbil, přikládám svou kompletní sbírku nafocených vyřešených příkladů ze cvika pro ty, kdo to dneska nedali..
Kdybyste měli připomínky k mému rukopisu, napište, osvětlim vám to, co nebudete moct přečíst..

Najdete to i ve Studnici, ve Složitosti I. ve složce cviceni_priklady_jindra... Webzdarma dost často nešlape tak, jak má..

Díky! Můžeš prosím ještě naznačit, jak včerejší test vypadal? Byly tam přesně tyhle příklady? A co nějaké úlohy na "kuchařku", jako byly v minulých letech?

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.

Skoro až zbytečné upřesnění zadání 2:
1) Je TAUT v co-NP? Jaká je složitost TAUT, pokud je formule v DNF?
2) Algoritmus, který najde optimální VP pro les v polynomiálním čase.
3) Složitost hledání nejkratší cesty v grafu se zápornými hranami.