Obsah
Cvičení z Kombinatoriky a grafů II 2020/21
Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst.
Při emailové komunikaci se mnou prosím vždy uveďte do předmětu text [KG2]
.
Zadání úloh na cvičení i domácích úkolů bude v zde na webu. Pro komunikaci kolem DÚ budu používat systém OWL. Pokud vám do něj nepřišel ode mě kód, napište mi email.
- 11. cvičení - zrušeno, rektorský den
Domácí úkoly
Požadavky na zápočet
Zápočet vám udělím, získáte-li celkově 70 bodů.
Váš aktuální počet bodů naleznete v OWLu.
Body lze získávat následujícími způsoby:
- Řešení úkolů: po každém cvičení budou zadány domácí úkoly. Každý úkol má termín, typicky dva týdny od zadání, později jej nelze odevzdat. Více o vypracovávání domácích úloh…
- Opravování úkolů: pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, máte možnost získat navíc až pětinásobek bodů tím, že se stanete korektorem pro tuto úlohu. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr. Více o korektorství…
- Myšlenková mapa předmětu: považuji za velice užitečné budovat si myšlenkovou mapu předmětu. Doporučuji to dělat průběžně, ale hodnotit to budu až na konci. Za velmi dobrou myšlenkovou mapu můžete získat až 20 bodů. Více o myšlenkových mapách…
Další informace
Vypracovávání domácích úloh
- Úkoly odevzdávejte pouze elektronicky přes OWL a to buď jako prostý text, markdown s matematikou (nejlepší varianta), nebo PDF soubor. PDFko může být vytvořené z prostého textového dokumentu, MS Wordu, LibreOffice Writeru, vysázeno (La)TeXem , nebo to může být i dobře čitelný scan nebo fotka (použijte appku Office Lens (iOS, Android) nebo podobnou, zejména chcete-li ilustrovat řešení obrázkem.)
- Pokud není řečeno jinak, vyřešením úlohy myslím, že dokážete dané tvrzení.
- Důkaz musí být korektní, přehledný a srozumitelný.
- V důkazu smíte používat bez důkazu tvrzení z přednášek.
- Pokud se začnete ve formulacích zamotávat, zaveďte si značení. Označte objekty nebo kvantity přesnými názvy nebo proměnnými a v textu používejte tyto proměnné, nikoliv ukazovací zájmena. (Je častá chyba, že autor důkazu mluví o té a tamté množině a cvičící je v okamžiku ztracen. Proč ne množina $A$ a množina $B$?). V prostém textu dolní index označujte pomocí podtržítka (tzn. $a_1$ je
a_1
), horní pomocí stříšky ($a^2$ jea^2
). - Za dobré (korektní, přehledné, srozumitelné) řešení příkladu dostanete plný počet bodů. Pokud něco chybí, ale důkaz obsahuje dobrou myšlenku, nebo pokud je důkaz správný, ale nepřehledný či nesrozumitelný, dostanete přibližně poloviční počet bodů. Pokud úlohu nevyřešíte nebo je důkaz zcela špatně (včetně myšlenky), dostanete 0 bodů.
- Silně doporučuji naučit se používat základy sazby matematiky pomocí systému LaTeX. Asi jako nejlepší zdroj se mi osvědčila wikikniha o LaTeXu. Nejjednoduší způsob, jak se do toho pustit, je přímo v OWLu (funkce preview) nebo v hackmd.io, kde můžete vidět živý náhled po straně se zdrojem (malá ukázka syntaxe (klikněte na „edit“, abyste viděli kód.)) Případně můžete používat nějaký webový LaTeXový editor (rozchodit LaTeX na vlastním počítači může být oříšek) – např. Overleaf.
- Při řešení úkolů doporučuji spolupráci, ALE:
- Vždy doporučuji, abyste příklad nejdřív zkusili vyřešit sami, více se toho naučíte.
- Přestože jste na úkolu s někým spolupracovali, musíte řešení vypracovat a zformulovat sami. Pokud ve mně vaše řešení vzbudí podezření, že příkladu vlastně nerozumíte, ale řešení jste opsali, a mé podezření se potvrdí, nedostanete žádné body a příště budu do vašich úkolů obzvlášť šťourat (abych si byl jistý, že jste je pochopili).
Korektorství
Pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, po odevzdání úlohy mi napište email s předmětem [DM/ADS1/KG1][korektor] název-úlohy
(první část podle předmětu, vyberte samozřejmě jen jedno). Já vaše řešení zhodnotím přednostně a pokud bude v pořádku, za opravení řešení vašich kolegů navíc až pětinásobek bodů. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr.
Technicky to bude fungovat tak, že korektorovi zpřístupním danou úlohu v OWL, kde on opravuje a uděluje body, ale já vše taky vidím a můžu případně korigovat :) Korektor si tedy řešení pečlivě přečte a zhodnotí ho. Je toto řešení korektní? Pokud ne, kde udělal autor chybu? Čemu nerozumí a jak mu můžu pomoci – jakou otázkou ho nakopnu správným směrem? Dále – je toto řešení přehledné a srozumitelné? Prospělo by řešení rozdělit do více/méně odstavců? Zavést nějaké značení? Atd. Na základě tohoto zhodnocení pak korektor navrhne bodové ohodnocení. Například:
Řešení je v zásadě správné, ale doporučil bych místo značení A, B, C, … používat indexované značení A_1, A_2, A_3, … Jinak byl důkaz poměrně přehledný.
2b
Já zhodnotím řešení úlohy a korekturu, případně se k oběma vyjádřím a přehodnotím body (ale to se často neděje).
Povinností korektora je opravit všechny přidělené úlohy do týdne od chvíle, kdy se v OWLu objeví.
Myšlenkové mapy
V průběhu semestru projdeme různá témata. Protože je čas lineární, nevyhnutelně je probíráme v nějakém pořadí. Ve skutečnosti jsou ale témata propojena složitěji. Považuji za velice užitečné tato propojení objevit a „udělat si pořádek v hlavě“ tím, že zaznamenáte strukturu témat, tak, jak ji chápete (jak ji máte ve své hlavě). Velmi doporučuji nástroj OrgPad, protože vás nenutí strukturovat témata hierarchicky (do stromu). Svět skoro nikdy není tak jednoduchý, aby se dal roztřídit do uhlazeného stromu; OrgPad vám dává svobodu zaznamenat věci tak, jak je opravdu vnímáte.
Úloha mindmap
jednoduše znamená, že si průběžně vytváříte myšlenkovou mapu předmětu, kterou mi na konci semestru odevzdáte a pak ji společně probereme. Můžete takto získat až 20b. (Mapu můžete samozřejmě vytvořit naráz až na konci semestru, ale myslím si, že se tak připravujete o velký přínos průběžného urovnávání myšlenek.)
Užitečné zdroje KG2
- Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
- [Sh] A. Shoemaker: Edmonds' Blossom Algorithm (notes)
- [VM] T. Valla, J. Matoušek: Kombinatorika a grafy I
- [P] J. Plank: Edmonds' General Matching Algorithm Lecture Notes
- [Ba] P. Bartlett: Chordal graphs (zápisky z přednášky)
- [Bo] B. Bollobás: Modern Graph Theory
- [D] R. Diestel: Graph Theory
- [Dv1] Z. Dvořák: Prezentace o kreslení grafů na plochy, poznámky o kreslení na plochy
- [MT] B. Mohar, C. Thomassen: Graphs on Surfaces
- [Dv2] Z. Dvořák: Prezentace o Brooksově a Vizingově větě, poznámky
- [HR] Y. Haimovitch, A. Raviv: Chordal graphs (ppt prezentace)
- [W] H. Wilf: Generatingfunctionology
- [R] G. Ringel: Map Color Theorem