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.

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

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

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

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

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

Příspěvekod 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?
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ěvekod 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.
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!
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ěvekod 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.
MarPol
Matfyz(ák|ačka) level I
 
Příspěvky: 28
Registrován: 11. 10. 2006 10:01


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron