V zimním semestru 2005/2006 se seminář koná pravidelně (modulo svátky) v úterý od 9:00 v posluchárně S4. Seminář vedou Martin Mareš a Robert Šámal.
Kombinatorický seminář (DMI022) je seminář pro studenty 2.-5. ročníku, zaměřený na řešení jednoduchých (ale často dosud nevyřešených) úloh z kombinatoriky a příbuzných oborů, jako je třeba teorie grafů a kombinatorická geometrie. Podstatnou součástí semináře je rovněž četba a referování odborných článků účastníky semináře. Každoročně je pro studenty Kombinatorického semináře pořádána Jarní škola kombinatoriky.
18.10. | Jan Kynčl | Variace na Hedetniemiho hypotezu |
25.10. | J.K./Ondra Plášil | pokr. z minula + Grafy bez krátkých sudých kružnic |
1.11. | Ondra Plášil | Grafy bez krátkých sudých kružnic |
8.11. | Tomáš Bartoš | Ortogonality graf (aneb bez kvantové komunikace se téžko žije) |
15.11. | pokračování z minula | |
22.11. | Josef Cibulka | Korelace v náhodných kostrách a pokrývacích lesích |
29.11. | Bernard Lidický | in-place merging |
6.12. | Tomáš Gavenčiak | Nimoidní hry |
13.12. | Robert Sasák | Trojúhelníkově nasycené grafy |
20.12. | Vánoční seminář | |
3.1.2006 | Michal Ferov | Optimal pebbling on paths and cycles |
10.1.2006 | Marek Tesař | Analýza míchání karet |
Tomáš Bartoš | Godsil, Newman: Colouring an ortogonality graph |
Michal Ferov | optimal pebbling of paths and cycles |
Jan Kynčl | Duffus, Sauer: Chromatic numbers and products |
Ondra Plášil | Lam, Verstraëte: A note on graphs without short even cycles |
Ondra Plášil | Blass, Braun: Random orders and gambler's ruin |
Robert Sasák | Ashkenazi: C3-saturated graphs |
Rudolf Stolař | Bender et al.: Insertion Sort is O(n*log n) |
Ondra Suchý | Tuza et al.: The cover pebbling number of graphs |
Marek Tesař | Hammarström: Card-shuffling analysis with Markov chains |
Zadání: Máme několik přirozených čísel, jejich bitový xor je nenulový. Dokažte, že lze jedno z nich zmenšit (a ostatní nechat) tak, aby bitový xor získaných čísel byl nulový.
Odtud plyne řešení hry Nim: hru hrají dva hráči s několika hromádkami zápalek. Tah spočívá v odebrání libovolného počtu zápalek z jedné z hromádek, kdo nemůže táhnout, prohrál. Shora uvedené tvrzeníčko je nejtěžší část důkazu toho, že hra je vyhraná pro prvního hráče právě tehdy, když xor počtu sirek na jednotlivých hromádkách je nenulový.
minulý semestr [an error occurred while processing this directive]