Predtermin 6.1.

Uživatelský avatar
Isidor
Adoptoval Tutcheka
Adoptoval Tutcheka
Příspěvky: 247
Registrován: 8. 12. 2004 23:22
Typ studia: Informatika Mgr.
Bydliště: mám
Kontaktovat uživatele:

Predtermin 6.1.

Příspěvek od Isidor »

Zdar,

tak som sa (hadam viac ako menej :D uspesne) zucastnil dnesneho predterminu.. pisalo sa to v S3 na Malej strane, 12:15, 90 min. casu, 4 ulohy. Zajtra rano vysledky a pripadne ustne doskusanie (ak niekto nebude suhlasit so znamkou :))

Takze priklady (pokial si pamatam)

1, (a) napiste definici kostry souvisleho grafu.
kolik koster ma C_n (kruznice na n vrcholech)? Zduvodnete
kolik koster ma K_n? [bez dokazu...aspon dufam :D]
(b) definujte permutaci na obecne mnozine X
kolik existuje permutaci na mnozine X={1,2,3,4,5,6,7}, ktere sudym cislem prirazuji sude a lichym liche? kolik jich existuje takovych, ktere sudym prirazuji liche a lichym sude? zduvodnete.
(c) definujte indukovany podgraf
uvedte priklad grafu na 6 vrcholech, ktereho kazdy podgraf je zaroven indukovany podgraf.

2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

3, Definujme graf Q_n tak, ze V={0,1}^n (vsechny usporadane n-tice jednicek a nul) a vrcholy (x_1,x_2...x_n), (y_1,y_2...y_n) jsou spojeny hranou prave tehdy pokud se lisi pouze v jedne souradnici.
Urcete, pro ktere n existuje v grafu Q_n uzavreny tah, ktery prochazi vsemi hranami. Zduvodnete.

4, Urcte, pro ktere n existuje graf se skore (2,3,3,3...3) (jedna dvojka, n-1 trojek). Zduvodnete.

Kua, je to dobry pocit mat to za sebou... :lol:
Naposledy upravil(a) Isidor dne 21. 1. 2005 00:58, celkem upraveno 1 x.
Inteligentních lidí je menšina. Demokracie je vláda většiny.
Saff
Matfyz(ák|ačka) level II
Příspěvky: 63
Registrován: 19. 11. 2004 21:45
Typ studia: Informatika Bc.
Bydliště: Stonava / Troja

Re: Predtermin 6.1.

Příspěvek od Saff »

Isidor píše:Zdar,

tak som sa (hadam viac ako menej :D uspesne) zucastnil dnesneho predterminu.. pisalo sa to v S3 na Malej strane, 12:15, 90 min. casu, 4 ulohy. Zajtra rano vysledky a pripadne ustne doskusanie (ak niekto nebude suhlasit so znamkou :))

Takze priklady (pokial si pamatam)

1, (a) napiste definici kostry souvisleho grafu.
kolik koster ma C_n (kruznice na n vrcholech)? Zduvodnete
kolik koster ma K_n? [bez dokazu...aspon dufam :D]
(b) definujte permutaci na obecne mnozine X
kolik existuje permutaci na mnozine X={1,2,3,4,5,6,7}, ktere sudym cislem prirazuji sude a lichym liche? kolik jich existuje takovych, ktere sudym prirazuji liche a lichym sude? zduvodnete.
(c) definujte indukovany podgraf
uvedte priklad grafu na 6 vrcholech, ktereho kazdy podgraf je zaroven indukovany podgraf.

2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

3, Definujme graf Q_n tak, ze V={0,1}^n (vsechny usporadane n-tice jednicek a nul) a vrcholy (x_1,x_2...x_n), (y_1,y_2...y_n) jsou spojeny hranou prave tehdy pokud se lisi pouze v jedne souradnici.
Urcete, pro ktere n existuje v grafu Q_n uzavreny tah, ktery prochazi vsemi hranami. Zduvodnete.

4, Urcte, pro ktere n existuje graf se skore (2,3,3,3...3) (jedna dvojka, n-1 trojek). Zduvodnete.

Kua, je to dobry pocit mat to za sebou... :lol:
Jak jsi dopadl ? A jak dopadli ti co s to psali s tebou a vis jejich vysledky ?
Uživatelský avatar
Isidor
Adoptoval Tutcheka
Adoptoval Tutcheka
Příspěvky: 247
Registrován: 8. 12. 2004 23:22
Typ studia: Informatika Mgr.
Bydliště: mám
Kontaktovat uživatele:

Re: Predtermin 6.1.

Příspěvek od Isidor »

Saff píše:Jak jsi dopadl ? A jak dopadli ti co s to psali s tebou a vis jejich vysledky ?
O ostatnych neviem nic, pisali sme to asi 40ti, potom rano na 9:00 prislo tak 10-15 ludi (ostatni 10:00 a 11:00), viem akurat ze aspon styria sme mali za 1 a potom som uz zdrhol "domov"...
Uživatelský avatar
Ferro_the_King
Matfyz(ák|ačka) level II
Příspěvky: 61
Registrován: 15. 11. 2004 19:49

Re: Predtermin 6.1.

Příspěvek od Ferro_the_King »

Isidor píše: 2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).
Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.
Uživatelský avatar
Ferro_the_King
Matfyz(ák|ačka) level II
Příspěvky: 61
Registrován: 15. 11. 2004 19:49

Re: Predtermin 6.1.

Příspěvek od Ferro_the_King »

Isidor píše: 2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).
Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.
Návštěvník

Re: Predtermin 6.1.

Příspěvek od Návštěvník »

Ferro_the_King píše: Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.
No myslím, že počet nezávislých podmnožin je roven počtu prvků množiny, asi takhle to vypadá {1} {1,2} {1,2,3} {1,2,3,4} ... {1,2...,2005}. tzn 2005, pak myslím, že stačí vytáhnout každou pátou podmnožinu tzn 2005/5 a výsledek asi bude 401. Doufám, že jsem to dobře pochopil a že to tak je, abych tu nemát. Tak to prosím berte s jistou rezervou, a jestli má někdo jiný názor, nechť ho sem prosím napíše!
mike04
Donátor
Donátor
Příspěvky: 79
Registrován: 23. 9. 2004 12:00
Typ studia: Informatika Mgr.
Bydliště: Děčín/ Praha
Kontaktovat uživatele:

Re: Predtermin 6.1.

Příspěvek od mike04 »

Ferro_the_King píše:
Isidor píše: 2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).
Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.
My jsme tohle řešili na cviku. Maximální počet nezávislých podmnožin je kombinační číslo: 2005 nad (celá část(2005/2)). Ale mohutnost těch podmnožin není dělitelná 5, proto si vybereš množiny, který jsou dělitelný 5.
Jejich počet je kombinační číslo: (2005 nad 1000) nebo (2005 nad 1005)

P.S. Neuměl jsem napsat ty vzorce, tak jsem je musel takhle popsat "slovy" :)
slepy John
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 11. 1. 2005 18:00

Příspěvek od slepy John »

to kokso, ani som si nevsimol, ze v 1 po b sme mali aj sude na sude a liche naliche, ja som spravil len s na l a l na s a cudoval sa preco mam pol boda :idea:
Uživatelský avatar
Trupik
Matfyz(ák|ačka) level III
Příspěvky: 251
Registrován: 3. 1. 2005 14:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Predtermin 6.1.

Příspěvek od Trupik »

Anonymous píše:
Ferro_the_King píše: Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.
No myslím, že počet nezávislých podmnožin je roven počtu prvků množiny, asi takhle to vypadá {1} {1,2} {1,2,3} {1,2,3,4} ... {1,2...,2005}. tzn 2005, pak myslím, že stačí vytáhnout každou pátou podmnožinu tzn 2005/5 a výsledek asi bude 401. Doufám, že jsem to dobře pochopil a že to tak je, abych tu nemát. Tak to prosím berte s jistou rezervou, a jestli má někdo jiný názor, nechť ho sem prosím napíše!
No tak takhle to neni, delal jsi to presne opacne - mas vybrat takovej system system podmnozin, ze pro zadne dve mnoziny z tohoto systemu neplati ze jedna je podmnozinou druhe... misto antiretezce jsi napsal retezec...
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz

Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Odpovědět

Zpět na „2004“