Vyřešené příklady ze cvičení

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Vyřešené příklady ze cvičení

Re: Vyřešené příklady ze cvičení

od MarPol » 11. 1. 2011 23:16

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.

Re: Vyřešené příklady ze cvičení

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.

Re: Vyřešené příklady ze cvičení

od m4rty » 11. 1. 2011 10:23

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í

od Jindra » 10. 1. 2011 22:11

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

Vyřešené příklady ze cvičení

od Jindra » 10. 1. 2011 22:00

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

Nahoru