Zapisky ze cviceni

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.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Zapisky ze cviceni

Příspěvek od Him »

Ahoj,

prepsal jsem par uloh, ktere jsme resili na cviceni s doc. Cepkem a tady je vysledek. Snad to nekomu poslouzi. Jinak omluvte, prosim, chyby, nikdo to po me zatim necetl..

btw: Nenasel by se nekdo, kdo by nafotil sve poznamky z cviceni, aby se to dalo jeste rozsirit?

EDIT: Pridal jsem updatovanou verzi, ktera obsahuje dalsi ulohy, stale nejsou vsechny, ale co se da delat. Enjoy.

M.
Přílohy
Cviceni.pdf
Verze 5
(420.09 KiB) Staženo 371 x
Cviceni.pdf
Verze 4
(418.25 KiB) Staženo 273 x
Cviceni.pdf
Verze 3
(398.64 KiB) Staženo 269 x
Cviceni.pdf
Verze 2
(384.51 KiB) Staženo 265 x
Cviceni.pdf
Reseni vybranych uloh ze cviceni
(360.89 KiB) Staženo 293 x
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Jindra
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 20. 1. 2010 13:26
Typ studia: Informatika Bc.

Re: Zapisky ze cviceni

Příspěvek od Jindra »

momentalne pracuju na souboru resenych uloh na zapoctovej test... behem vikendu bych to mel mit hotovy a nafoceny a dam to sem.. snad to jeste nekomu poslouzi.. :-)
Wolda
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 25. 10. 2006 22:27
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Zapisky ze cviceni

Příspěvek od Wolda »

Him píše:Ahoj,

prepsal jsem par uloh, ktere jsme resili na cviceni s doc. Cepkem a tady je vysledek. Snad to nekomu poslouzi. Jinak omluvte, prosim, chyby, nikdo to po me zatim necetl..

btw: Nenasel by se nekdo, kdo by nafotil sve poznamky z cviceni, aby se to dalo jeste rozsirit?

M.
Ahoj, za nas neporadne, co na cviceni moc nechodili, moc diky! Jinak jen takova poznamka (str. 4) -- intervalove grafy uplny graf na 4 vrcholech (aka K_4) mohou obsahovat jednoduse -- v reci uloh mas proste 4 ulohy, se vsechny prekryvaji v nejakem casovem useku. Nicmene co intervalove grafy obsahovat uz nemuzou je napr. indukovana C_4, nebo obecneji jakykoli cyklus delky alespon 4.
--
Wolda
Dr.Zlo

Re: Zapisky ze cviceni

Příspěvek od Dr.Zlo »

Jak to vypada?
Posledni cviceni by se tuze hodila.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zapisky ze cviceni

Příspěvek od Him »

@Wolda: Diky za feedback! Prepisu to. Pridal jsem do puvodniho prispevku novou verzi dokumentu s dalsimi priklady, ale stejne tam priklady chybi.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Wolda
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 25. 10. 2006 22:27
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Zapisky ze cviceni

Příspěvek od Wolda »

Him píše:@Wolda: Diky za feedback! Prepisu to. Pridal jsem do puvodniho prispevku novou verzi dokumentu s dalsimi priklady, ale stejne tam priklady chybi.
Čtu to dost nepořádně, ale všiml jsem si následujícího (na správnosti se nic nezmění, jen mám raději logn nežli n :-) ), a tak jen hnidopišsky poznamenám: když mám skříňku na rozhodovací problém, řekněme ex. vrcholové pokrytí velikosti K, tak mi stačí jen logn dotazů na zjištění velikosti nejmenšího VP (či obecně min/max hodnoty daného problému).
--
Wolda
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zapisky ze cviceni

Příspěvek od Him »

Wolda: Mas pravdu, opravil jsem to.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zapisky ze cviceni

Příspěvek od pasky »

Chybi ve verzi 3 alespon zminka o jeste jine uloze nez optimalni VP lesa v PTIME? Je to jedine, co jsem tam nenasel, ale nevim, jestli seznam uloh u Cepka je up-to-date...

Tedy, ono je to celkem snadne - zrejme staci ignorovat listy, vzit vsechny jejich rodice, tech bude mene a jiz jiste ve VP museji byt; pak listy i rodice utrhneme a iterujeme.

EDIT: Koukam do konkurencnich poznamek, ze tam maji jeste 6. cviceni na bin-packing, a je to nejake dlouhe... a to uz jsem chtel jit spat!
Naposledy upravil(a) pasky dne 12. 1. 2011 00:15, celkem upraveno 1 x.
Next lecture on time travel will be held on previous Monday.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zapisky ze cviceni

Příspěvek od Him »

pasky píše:Chybi ve verzi 3 alespon zminka o jeste jine uloze nez optimalni VP lesa v PTIME?
Nevim, uz jsem moc unavenej, ale dal jsem tam verzi 4, ktera obsahuje snad vsechno. Psal jsem to z tech Jindrovych skenu..
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zapisky ze cviceni

Příspěvek od pasky »

Hura, diky!
Next lecture on time travel will be held on previous Monday.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zapisky ze cviceni

Příspěvek od Him »

nz :)

Jen varuju, ze ten priklad TAUT je spatne ... v tretim bode ma byt, ze staci v kazde klauzuli alespon jeden komplementarni par. Hadam, ze jste na to prisli, ale kdyby nahodou. Jeste, ze jsem to opravil v zapoctove pisemce :D Polosouvislost a celociselne programovani je dobre (z vysledku meho zapoctu).

Zapocet doma, juhuu.

PS: Mam doma jeste par oprav, tak to vydam jako dalsi verzi dokumentu a pak slavnostne vyvoj ukoncim :) Jinak nabizim, ze poskytnu zdrojaky komukoli, kdo mi napise PM a slibi, ze mi oznami nalezene chyby.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zapisky ze cviceni

Příspěvek od Him »

Je tam ta pata verze, kdybyste nasli nejakou chybu, tak ji prosim ohlaste, uz to cist znovu nebudu.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Odpovědět

Zpět na „TIN062 Složitost I“