Cvičení z Kombinatoriky a grafů I, LS 2016/2017

Podmínkou k udělení zápočtu je získání aspoň 1600 zkušeností (exp) celkem za vyřešené domácí příklady; 1 bod odpovídá 100 exp.

Domácí příklady budu průbežně zveřejňovat na této stránce, případně zadávat i přímo na cvičeních. Během semestru bude zadáno zhruba 20 příkladů, koncem semestru ještě dalších 5-10, které bude možno řešit i během zkouškového období.
Svá čitelná řešení můžete odevzdávat na papíře, případně posílat v elektronické podobě na mou adresu (kyncl zavináč kam.mff.cuni.cz), a to ve formátu pdf. Pro převod do pdf se může hodit např. nástroj na stránce freepdfconvert.com nebo online2pdf.com apod. (ale nedoporučuji jpg2pdf.com). Řešení můžete odevzdávat do příštího cvičení od zadání, zpravidla tedy do 1 týdne.
Zvolte si nějakou přezdívku, pod kterou chcete mít zveřejněny výsledky na webu, a napište ji na první odevzdávané řešení (včetně svého skutečného jména). Můžete také napsat, že si svoje výsledky nepřejete zveřejňovat. Na dalších řešeních stačí uvést jméno nebo přezdívku.

O domácích příkladech můžete diskutovat s ostatními, řešení ale musíte zformulovat a napsat samostatně.

Všechna tvrzení ve svých řešeních řádně zdůvodněte, a to i když v zadání není slovo "dokažte". Můžete samozřejmě již bez důkazu používat tvrzení a věty dokázané na přednášce nebo na cvičení. Nebojte se odevzdat i jen částečná řešení.

Na případných konzultacích se můžeme domluvit osobně nebo e-mailem.

informace o přednášce

Domácí příklady

Témata cvičení

• Cvičení 0: (21.-23. 2. 2017) - kombinační čísla (opakování), asymptotické porovnávání funkcí pomocí O, o, Theta
• Cvičení 1: pdf, ps (24. 2. - 2. 3. 2017) - asymptotické porovnávání funkcí a odhadování řad
• Cvičení 2: pdf, ps (3.-9. 3. 2017) - generující funkce a operace s nimi, určování posloupnosti z GF
• Cvičení 3: pdf, ps (10.-16. 3. 2017) - určování generující funkce posloupnosti, částečné součty posloupnosti
• Cvičení 4: (17.-23. 3. 2017) - určování koeficientů, sčítání pomocí GF, výpočet explicitního vyjádření členů posloupností zadaných lineární rekurencí
• Cvičení 5: (24.-30. 3. 2017) - rekurentně zadané posloupnosti, počet rozkladů speciálního typu
• Cvičení 6: pdf, ps (31. 3. - 6. 4. 2017) - počítání objektů Catalanovými čísly
• Cvičení 7: pdf, ps (7.-13. 4. 2017) - kombinatorický výpočet n-tého Catalanova čísla, počítání koster
• Cvičení 8: pdf, ps (18.-21. 4. 2017) - počítání dvěma způsoby, konečné projektivní roviny
• Cvičení 9: pdf, ps (25.-28. 4. 2017) - toky v sítích
• Cvičení 10: pdf, ps (2.-5. 5. 2017) - toky v sítích, Hallova věta a její aplikace
• Cvičení 11: (9.-12. 5. 2017) - Hallova věta a její aplikace
• Cvičení 12: pdf, ps (16.-19. 5. 2017) - Dilworthova věta, 2-souvislost a hranová 2-souvislost
• Cvičení 13: (23.-26. 5. 2017) - k-souvislost a hranová k-souvislost, Ramseyova věta

Výsledky

Řešitel	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	exp
AIXI	2	2	2	2	5	3	4	3	3	2	2	6	3	2	3	2	2	3	2	2	2	2	2	3	4	5	2	7	6	5	9300
Eigennickname	2	1.5	2											1		1.5	1.5		1		2	1	2				1				1650
Martesing	2	2	2	2		3	3.5							1				3													1850
?		2	2	2		3	1.5			2	1.5					1.5															1550
DJ	1.5	2	2	2	2	3	4																								1650
Marek Motyčka	1		2		1	2.5		1.5	3					1.5																	1250
TiGi	2	2	2	2	2.5	3	4																								1750
patuchen	1.5	2	2	2	2	3	3.5	1.5																							1750
pan Inkognito	2	2	1.5	1.5		1.5		3		2	1.5	0		2																	1700
Jakub Tětek	2		1				4	1	3	0			3	1			2														1700
MrGlaucus	1.5	1.5			0.5	3	4	3		0.5	1.5																1				1650
Datel	1.5	2	2	2	3	3	4																								1750

Achievementy:

čt 10:40

Řešitel	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	exp
mammaloupostel	2	2	2	1	1	3	3	3																							1700
drozdo	1.5	0.5	2	1.5	1.5	3		2		2												2									1600
ABC	1	1.5	2	0	4.5	2.5	4	0.5																							1600
Gingerbread	2	2	2	2	3	3	0	2																							1600
?	1.5		2	2	1.5	3	4	2																							1600
Adys		2	1			1.5	3	1		2				1							1	1.5					2				1600
Caprin	2																														200
Budějovičák	2	2	2	2	1.5	3	3.5																								1600
??																					0.5	0.5	0	1			0.5	1.5			400
Zatencas	1.5		0.5		3	1.5		1.5		0				0		0	1.5				2	0.5			3		2			0	1700
Ado	2	2	1	2	1.5	2.5	3.5	1		2																					1750
Alfonz	2		2	2	3																2	2	2	1.5							1650
???							0.5			2																					250
Y						3	3.5																								650
zlatovláska	2	2	2		1	3	4				1	2																			1700
kámen	2	1														0.5	0.5														400
????		1.5	1.5	2	1	1.5	0	3		0.5	1.5	3						2				0									1750
Sushi	1.5	2	2	2	5	3				1.5																					1700
2dumb4this	0																														0
Nech ε<0	2	2	2	2	3	3	4																								1800
Vybité poistky	2	2	2	2	1.5	3	4																								1650
kaktus	2	2	2	1	2	3	3.5	2																							1750
Sunflower	2	2	2	1	3	3	3.5																								1650
zajda20	0.5							1.5		2				0	0.5					2	1	2	1				1	3	1.5	1	1700
tmavovláska	1.5	2	2	2	2.5	2	0	1		0.5		3																			1650

Achievementy:

pá 10:40

Řešitel	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	exp
Ando	1	1	2	2		1	2.5	2.5		0.5	1.5	1	0.5	0				3													1850
Heisenberg								3		2		4				2	2	3													1600
δ<0	0.5	1	1	0				0.5		0																					300
klokan	1.5	0.5	1	1.5			4	3	0	2	0		3	0			0														1650
Patros	2	1.5	1				3.5	2								1.5	2				2	0.5									1600
Tantalos	2	2	1	2		1.5	3.5	2		0.5			2																		1650
Sisyfos	2	2	1	2		1.5	3.5	2		0.5						1.5	2														1800
Idefix	2	1.5	1	2				1.5		1.5		1.5	3	1	1.5																1650

Achievementy: