Stránka 1 z 1
Vyřešené příklady ze cvičení
Napsal: 10. 1. 2011 22:00
od Jindra
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..
Kód: Vybrat vše
http://jindrahelcl.wz.cz/_stored/matfyz/Slozitost_I_Cviceni_vyresene_priklady_Jindra_Helcl.rar
Re: Vyřešené příklady ze cvičení
Napsal: 10. 1. 2011 22:11
od Jindra
Najdete to i ve Studnici, ve Složitosti I. ve složce cviceni_priklady_jindra... Webzdarma dost často nešlape tak, jak má..
Re: Vyřešené příklady ze cvičení
Napsal: 11. 1. 2011 10:23
od m4rty
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?
Re: Vyřešené příklady ze cvičení
Napsal: 11. 1. 2011 11:58
od JiriD
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.
Re: Vyřešené příklady ze cvičení
Napsal: 11. 1. 2011 23:16
od MarPol
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.