Zkouška Dvořák 5/31/2012

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

Zkouška Dvořák 5/31/2012

Příspěvek od nahodny kolemjdouci »

Tak jsem dneska byl na zkousce. Vytahl, respektive na me zbylo:
1. Princip inkuze a exkluze
2. k regularni bipartitni -> existuje perfektni parovani

ad 1 : Napsal jsem mu vzorec, dukaz spravnosti a satnarku. Ne nejak detailne, vsechno jsem mu pak asi rozumne popsal. K tomu se nic neptal.
ad 2 : Asi jeho oblibena ulozka, tu sem si ani nepripravil a rovnou mu to rekl, dukaz pres tok. Zeptal se me proc plati v grafu s celociselnyma hranama, ze kdyz tam je nejvetsi tok vel. n tak tam je i celociselny velikosti n(je to videt z algoritmu).

Potom asi dve minuty mlcel, a ja cekal co z nej vypadne za hnusarnu. Nakonec to byl jen dalsi priklad na IE - kolik cisel 1-9000 je nesoudelnych s 9000 coz je vcelku snadne a kdyz jsem mu naznacil jak to resit tak to ani nechtel numericky dopocitat a dal mi za 1.

Nevim co meli ostatni ale totok se mi zdalo vpohode. Asi to netreba mit uplne presne formalne sepsane, hlavne tomu rozumnet, protoze i kdyz mu clovek rekne "vse" tak se zepta na nejakou drobnost ktera odhali jestli to nemate jen zamemorovane.
Abby
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 4. 9. 2011 12:57
Typ studia: Informatika Mgr.

Re: Zkouška Dvořák 5/31/2012

Příspěvek od Abby »

Tak pridam moje dnesne zazitky:

1. Toky v sitich,
2. Vytvorujici funkce pro pocet zpusobu, jak N vyjadrit jako soucet jednicek, trojek a petek.

K sietam som spisala definicie, Ford-Fulkersona, celociselne siete, rovnost vzniknutneho toku v zdroji a zaniknuteho v stoku a vyuzitie tokov v niektorych vetach (Hall, Menger, perfektne parovanie v k-regularnom bipartitnom grafe). Pytal sa este na dokaz toho, ze tok, ktory najde Ford-Fulkerson je skutocne maximalny (najst z vysledku minimalny rez).
K druhej ulohe som napisala riesenie, potom sa spytal, ako z vytvorujucej funkcie dostaneme vzorec pre pocet sposobov (parcialne zlomky a binomicka veta), ale kedze to bola presne tema, ktoru som nechcela a nevedela, tak mi dal ako nahradu dokazat, ze v konecnej projektivnej rovine, kde ma priamka p + 1 bodov je p^2 + p + 1 bodov. Napokon tiez za jedna :)
Hekit
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 1. 6. 2012 11:02
Typ studia: Informatika Bc.

Re: Zkouška Dvořák 5/31/2012

Příspěvek od Hekit »

Já měl:
1. Odhady faktoriálu a kombinačních čísel.
2. Dokázat, že v 2-souvislém grafu leží každé dvě hrany na stejné kružnici.

K odhadům není moc co dodat, snad jen, že u kombinačních čísel ho zajímal i odhad přes binomickou větu, u kterého jsem mu řekl princip, sepsat to přesněji ani nechtěl.
Důkaz je přes ušaté lemma, já se do toho trochu zamotal, tak mi dal dokázat ještě ušaté lemma. U toho jsem si vzpomněl jen na jednu implikaci, druhou mi musel napovědět - po slovech "najdeme podgraf" jsem už věděl, ale to bylo málo. Tak se ptal na obarvení přirozených čísel k barvami takové, že existují různá x,y,z obarvená stejnou barvou a x+y=z. To jsem netušil, tak se zeptal, jestli za 2 a já souhlasil.

Jinak, jak už psali kolegové, Dvořák byl hodný, nechtěl to nijak moc formálně, ale kladl detailní dotazy na přezkoumání porozumění.
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“