Zkouska 26.5.2008 - Kratochvil

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Medved
Admin(ka) level I
Příspěvky: 168
Registrován: 30. 5. 2006 21:18

Zkouska 26.5.2008 - Kratochvil

Příspěvek od Medved »

1) Mate graf

Kód: Vybrat vše

x - x - x - x - x
|   |   |    |   |
x - x - x - x - x

...

Atd., proste mrizku a mate napsat, jaka je dimenze prostoru cyklu a najit nejakou bazi.

2) Najit vytvorujici funkci neceho jako (1,-2,3,-4,5,-6,7,-8,...)
3) Najdete maximalni nezavislou mnozinu v grafu (a bylo tam neco jako skoro uplny bipartitni graf B(5,5), akorat mel tak polovinu hran, nez by mel uplny :D
4) Mate mrizku 6x6 ve ktere je vyplneny 1.,3. a 5. radek a mate rict, jestli to jde doplnit na latinsky ctverec a doplnit to, nebo zduvodnit, proc to nejde. Cisla si fakt nepamatuju.
5) Dokaz, ze v 3-regularnim grafu plati, ze k_v(G) = k_e(G). Plati to i v 4-regularnim?
6) Dokaz, ze graf, ktery ma maximalni stupen 3 lze zorientovat tak, ze ze zadneho vrcholu nevede vice nez 2 hrany.
7) Dokaz, ze mame li k,n prirozene, tak existuje N takove, ze kdyz v rovine mate N bodu, z nichz kazde dva jsou rovnobezne s maximalne k smery, tak existuje primka, na ktere lezi n bodu...nebo tak neco.
8) Napiste vetu z prednasky, ktere se vam zdala nejtezsi a proc. Ustne doplnil, ze tam je napsane, at napiseme vetu, takze si mame dat pozor, ze tam opravdu napiseme vetu a ze bude dobre.

5,6,7 - pocitaji se jen dva nejlepe bodovane priklady
bodovani - 5,5,5,5,10,10

Hodina a pul cas, zacinalo se v 9, pisemna konci 10:30, ustni zacina v 1, pokud nechcete bojovat o lepsi znamku, tak jdete v 1, pokud chcete bojovat o lepsi znamku, tak zalezi, kdy jdete na ustni. Ta pry jeste nikdy nekoncila pozdeji, nez v 9 vecer. Hranice bodovani se upravi az na zaklade toho, jak moc to bylo tezke (teda jsem to pochopil tak, aby znamky byly cca rovnomerne rozlozene).

Tolik info k dnesni pisemce.
Medved
Admin(ka) level I
Příspěvky: 168
Registrován: 30. 5. 2006 21:18

Re: Zkouska 26.5.2008 - Kratochvil

Příspěvek od Medved »

Jeste hodnoceni:
33 a vic: 1
vyhazov byl neco kolem 17ti, ale myslim, ze na ustnim to pak snad musi dat kazdy, kdo si aspon precte den predtim vsechny vety a vi +- o cem to je...coz je stejne zaklad uspesneho navrhu algoritmu :))
rudot

Re: Zkouska 26.5.2008 - Kratochvil

Příspěvek od rudot »

Este by som pridal (zial z vlastnej skusenosti) taku malu radu. Ak uloha znie najdite generujucu funkciu pre postupnost (1,-2,3,-4,5,-6,7,-8) tak nestaci napisat 1/(1+x)^2 (alebo staci to na 1 bod z 5) A tiez ak je uloha najdite nezavislu mnozinu v danom grafe tak nestaci oznacit vrcholy ktore do tejto mnoziny patria. (Respektive staci to na 2 body z 5)
Takze si treba davat pozor a do akokolvek jednoduchych uloh treba pisat postup...
hardwire2
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 5. 1. 2008 19:57
Typ studia: Informatika Bc.

Re: Zkouska 26.5.2008 - Kratochvil

Příspěvek od hardwire2 »

Jeste k tomu casu...odchazel sem z ustniho posledni a byly 4 hodiny, takze to je opravdu pred devatou :)
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“