Zkouška - 18. 1. 2007 – Pangrác

Zanatic
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 15. 1. 2007 16:16
Typ studia: Informatika Bc.
Bydliště: Prosek
Kontaktovat uživatele:

Zkouška - 18. 1. 2007 – Pangrác

Příspěvek od Zanatic »

1) Kombinační číslo; bez důkazů
2) Algoritmus na hledání minimální kostry; s důkazem
3) Dokázat, že rovinný graf neobsahující trojúhelník má barevnost 4, to jsem netrefil, tak přišla otázka
4) Počet nečtvercových (jehož dělitelem není čtvercové číslo, tj. n^2, tj. 4, 9, 16...) čísel od 1 do 120. (Hint: PIE)

Tam už jsem se seknul jenom o 1, takže celkem za 3. Tuhle zkoušku musí dát každej!
Naposledy upravil(a) Zanatic dne 18. 1. 2007 16:11, celkem upraveno 1 x.
dmt
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 7. 5. 2006 21:52
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od dmt »

1. definovat antiretazec + spernerova veta (vypyoval sa okolo toho veci ale dokaz nechcel)
2. usate lemma + dokaz
3 priklad: kolko cisel z {1..120} nie je delitelne ziadnou 2 mocninou nejakeho prir. cisla (okrem 1), na princip inkluze a exkluze

a inak Pangrac je super... ak napriklad neviete 1 z otazok tak vam da doplnujucu a stale mate sancu na jednotku
dmt
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 7. 5. 2006 21:52
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od dmt »

takze priklad sme mali rovnaky... :)
tie priklady ma na papierikoch a stale dava tie iste takze sa asi oplati pozriet si tych zopar co je tu na fore
lukino

Příspěvek od lukino »

Zdravim!

Tak tu ich mate:

1. Def. EKVIVALNCIU (reflex., sym., trans.) plus Def. TRIEDU EKVIVALENCIE; Kolko ekvivalencii je na 4 prvkovej mnozine {1,2,3,4}
[odp.: Rozobrat na jednotlive podmnoziny vrcholov ktore su / nie su v ekv.]

2. Veta o skore G + dokaz.
[Tu Pangrac trafil moju achillovu patu - jedna z dvoch viet, ktore som so zatajenym dychom slusne povedane "odignoroval" - reku, sanca, ze ju dostanem je mala... no nie neexistujuca, ako sa ukazalo na skuske. Takze sa nepokusajte vyvratit "pravidlo schvalnosti" stareho strycka Murphyho, nestoji to za to... pocit, ze ste mohli mat lepsiu znamku, keby ste polhodinku navyse venovali jednemu ubohemu dokazu za to skutocne nestoji...alebo ano?]

3. Je dany G = K_5 (uplny graf na 5 vrcholoch):

a) Kolko podgrafov G NIE je rovinnych?
[Tu lahko nahliadneme, ze len jeden - samotny K_5]

b) Kolko 4-komponentovych podgrafov G obsahuje?
[(5 nad 2) - co je vyber lubovolnej dvojice vrcholov,
ktore patria jednej komponente, ostatne vrcholy, samozrejme,
tvoria samostatne komponenty]

c) Kolko indukovanych podgrafov G obsahuje?
[Postupne spocitat IG na 1,2, 3, 4, 5 vrcholoch, co je (n nad 1) +
(n nad 2) atd. atp.]

d) Kolko stromov obsahujucich hranu {1, 2} obsahuje?
[Tu je nutne si uvedomit, ze strom ~ kostra a pocitame pocet kostier
v grafe tvorenom hranou {1,2} a postupne 1, 2, 3 zvysnymi vrcholmi,
opat klasicky vyberame (n nad 1), (n nad 2), (n nad 3) a potom
prenasobime este poctom kostier - cize (n nad 1) * 3^1, (n nad 2) *
4^2 atd. atp. skratka vzdy pocet vybratych vrcholov + 2 vrcholy z
hrany {1, 2} tvoria kostru...]

Ked som na (skoro) vsetkom, okrem poriadneho dokazu Vety o Skore exceloval, Pangrac pochopil, ze aspirujem na jednotku a tak mi velkodusne ponukol slamku, ktoru by sa ocakavalo, ze zdrapim vsetkymi desiatimi... (bohuzial sa tak nestalo a ostali sme na "velmi dobre", podstatny je vsak fakt, ze je to za mnou 8) )

a tu je ta spominana "slamka":
"MY ONE SHOT AT GLORY" :D : Maximalne kolko hran ma graf bez K_3 (trojuholnika). POZOR! zadanie nehovori, ze musi byt rovinny...
[...keby som take nieco nepocul prvykrat dnes na skuske, snad aj nieco pozliepam...]

Na zaver snad len konstatovanie, ze skuska je po patricnej priprave lahko zvladnutelna (ja som sa napriklad pripravoval asi 2 dni netto), Pangrac vam da casu habadej a okrem toho moznost sa aj opravit,
v dokazoch nepozaduje presne formalizmy, ale upozornujem, ze to MUSITE CHAPAT - vas komentar musi jednoducho mat logiku, potom staci aj primitivny obrazok. Ak si vsak niekto mysli, ze ho obalamuti 5 indexami a nabiflovanym dokazom z kapitol, tak sa pravdepodobne pletie - domnievam sa, ze musi mat pocit, ze tomu chapete...

Zopakujem, co uz vsetci povedali: Pangrac je maximalne ferovy a vobec nepochybujem, ze 2 som si za svoju lenivost zasluzil... (Ta skuska sa fakt s prehladom DA dat aj na 1...)

Tot vsjo! I do hope it helps!
Odpovědět

Zpět na „2005“