Základy kombinatoriky a teorie grafů 2018/19 – cvičení

Cvičení pro přednášku Základy kombinatoriky a teorie grafů [NMIN331] (vyučující Jan Kratochvíl a Pavel Valtr). Scházíme se v pátek od 10.40 v K5 (tj. po přednášce).

• Účast je (samozřejmě) nepovinná.
• Budou nějaké úkoly za nějaké body (celkem alespoň 80) a na zápočet budete muset trochu projevit zájem (20 bodů).
• Úlohy prosím odevzdávejte mailem na matej-at-kam.mff.cuni.cz (ideálně samozřejmě v LaTeXu). Pokud o LaTeXu moc nevíte, na stránkách PraSete je návod, jak ho nainstalovat a i nějaké základy. Odtud si můžete stáhnout ukázkovou templatu na domácí úkoly. Kdyby něco, pište.
• Úlohy můžete odevzdávat kdykoliv, ale každá série bude mít nějaký deadline, před ním budete dostávat dvojnásobek bodů.
• Cvičení (úkoly atd.) bude inspirováno cvičeními z minulých let.
• Ten, kdo bude na posledním cvičení mít nejvíce bodů za domácí úkoly, získá nádhernou a sběratelsky hodnotnou věcnou cenu!!! (Fakt.)
• Matoušek, Valla: Kombinatorika a grafy I.

Co jsme dělali

Datum	Obsah
22. 2. 2019	Úvodní hodina, grafy atp. (příklady). Povídání o kombinatorice. Zadán nultý úkol.
1. 3. 2019	Toky v sítích (příklady). Povídání o lineárním programování (skripta, dualita min-cut=max-flow). Zadána první série domácích úkolů.
8. 3. 2019	Toky v sítích a souvislost grafů (příklady).
15. 3. 2019	Deadline prvního úkolu. Hallova věta (příklady). Krátké povídání o náhodných grafech.
22. 3. 2019	Ušaté lemma & rovinné grafy (příklady). Povídání o minorech.
29. 3. 2019	Rovinné grafy a jejich barevnost (příklady). Povídání o "sparsitě". Zadána druhá série domácích úkolů.
5. 4. 2019	Ramseyova teorie (příklady). Povídání o homomorfismech a CSP.
12. 4. 2019	Deadline druhé série úkolů. Ramseyova teorie podruhé (příklady). Povídání o ramseyovkách.
19. 4. 2019	Nikdo nepřišel.
26. 4. 2019	Vytvořující funkce (příklady). Zadána třetí série domácích úkolů. Povídali jsme si o grafonech.
3. 5. 2019	Přednáška a cvičení o složitosti a NP úplnosti. Povídali jsme si o různých složitostních třídách (hlavně P a NP) a o NP-úplných problémech.
10. 5. 2019	Deadline třetí série úkolů. Přednášku i cvičení měl doc. Valtr.
17. 5. 2019	Závěrečná hodina. Vyhlášení soutěže o nejvíce bodů ze cvičení. Plán: DFT a FFT (discrete/fast Fourier transform), Q/A.

Výsledky

Pokud tady chcete vidět i svoje výsledky, pošlete mi s tím souhlas a nějakou přezdívku :).

Přezdívka	#0	#1.1	#1.2	#1.3	#1.4	#2.1	#2.2	#2.3	#3.1	#3.2	#3.3	#3.4	#3.5	Součet
Pál Erdős	5	4	4	6	8	8	8	4	6	4	6	4	12	79
Chopin meister	5		4					4						13
Židle	5		4	6	8									23
Heathcliff	5													5
Žaneta	5	4	4	6	8									27
Emil	5	4	4	6			4							23
110	5	4	4	6	8									27
900	5	4		6			8							23
štvorlístok	5	4	4		8									21
Spišo	5	4	4	6	8									27
backinblack	5	4	4	6	8									27
Honza	5	2	2	3		4	4							20
skorik	5	4	4	6	8									27
ES002	5	4	4	6				4						23
Cthulhu	5	4	4	6										19
unikátní číslo apod.	5	4	4	6						4		4		27
DB	5	4	4	6		8								26
Jeroným	5	4	4	6	8									27
Banito	5	4	4	6			1							20
rmartin	5	2	2	3			8	4						24
ahoj	5	2	2	3	4									16