Fórum studentů MFF UK

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.

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..

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.

Jak to vypada?
Posledni cviceni by se tuze hodila.

@Wolda: Diky za feedback! Prepisu to. Pridal jsem do puvodniho prispevku novou verzi dokumentu s dalsimi priklady, ale stejne tam priklady chybi.

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: Mas pravdu, opravil jsem to.

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!

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..

Hura, diky!

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 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.

Je tam ta pata verze, kdybyste nasli nejakou chybu, tak ji prosim ohlaste, uz to cist znovu nebudu.