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

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Jindra
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 20. 1. 2010 13:26
Typ studia: Informatika Bc.

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

Příspěvek 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
Jindra
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 20. 1. 2010 13:26
Typ studia: Informatika Bc.

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

Příspěvek 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á..
m4rty
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 11. 1. 2011 10:19
Typ studia: Informatika Mgr.

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

Příspěvek 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?
JiriD
Matfyz(ák|ačka) level I
Příspěvky: 44
Registrován: 2. 2. 2008 09:35
Typ studia: Informatika Bc.

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

Příspěvek 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.
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.

Und das wird er mir wohl verzeihen!
MarPol
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 11. 10. 2006 11:01

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

Příspěvek 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.
Odpovědět

Zpět na „TIN062 Složitost I“