[an error occurred while processing this directive]

Kombinatorický seminář

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.

Program

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

Zamluvené články

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: C₃-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

Úloha na tento týden

I tento semestr budeme společně řešit problémy z knihy pana Lovásze: Combinatorial problems and exercises. Na konci jednoho semináře si řekneme zadání, na začátku příštího někdo, kdo problém vyřešil, řekne řešení. Tady na webu se kromě zadání dočtete i malou nápovědu.

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ý.

Nápověda

Minulé úlohy

Historie semináře

minulý semestr [an error occurred while processing this directive]