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.

Zapisky ze cviceni

Příspěvekod Him » 4. 1. 2011 20:21

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) 206 krát
Cviceni.pdf
Verze 4
(418.25 KiB) 102 krát
Cviceni.pdf
Verze 3
(398.64 KiB) 83 krát
Cviceni.pdf
Verze 2
(384.51 KiB) 83 krát
Cviceni.pdf
Reseni vybranych uloh ze cviceni
(360.89 KiB) 120 krát
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ěvekod Jindra » 7. 1. 2011 18:25

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.. :-)
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: Zapisky ze cviceni

Příspěvekod Wolda » 9. 1. 2011 22:54

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
Wolda
Matfyz(ák|ačka) level I
 
Příspěvky: 27
Registrován: 25. 10. 2006 21:27
Typ studia: Informatika Ph.D.
Login do SIS: volej6am

Re: Zapisky ze cviceni

Příspěvekod Dr.Zlo » 9. 1. 2011 22:57

Jak to vypada?
Posledni cviceni by se tuze hodila.
Dr.Zlo
 

Re: Zapisky ze cviceni

Příspěvekod Him » 9. 1. 2011 23:04

@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 ;)
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ěvekod Wolda » 10. 1. 2011 01:42

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
Wolda
Matfyz(ák|ačka) level I
 
Příspěvky: 27
Registrován: 25. 10. 2006 21:27
Typ studia: Informatika Ph.D.
Login do SIS: volej6am

Re: Zapisky ze cviceni

Příspěvekod Him » 10. 1. 2011 14:39

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 ;)
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ěvekod pasky » 12. 1. 2011 00:07

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 pasky dne 12. 1. 2011 00:15, celkově upraveno 1
Next lecture on time travel will be held on previous Monday.
pasky
Matfyz(ák|ačka) level II
 
Příspěvky: 89
Registrován: 4. 1. 2005 22:57

Re: Zapisky ze cviceni

Příspěvekod Him » 12. 1. 2011 00:14

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 ;)
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ěvekod pasky » 12. 1. 2011 00:15

Hura, diky!
Next lecture on time travel will be held on previous Monday.
pasky
Matfyz(ák|ačka) level II
 
Příspěvky: 89
Registrován: 4. 1. 2005 22:57

Re: Zapisky ze cviceni

Příspěvekod Him » 12. 1. 2011 14:26

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ěvekod Him » 13. 1. 2011 11:35

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


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