Základy kombinatoriky a teorie grafů (NMIN331) - cvičení

Cvičení probíhá každé pondělí od 15:40 v učebně K4.

Cvičení povede Martin Balko. E-mail cvičícího: balko (AT) kam.mff.cuni.cz

Stránky přednášky.
Podmínky získání zápočtu:
  • Získání alespoň 20 bodů.
  • V průběhu semestru zadám několik sérií příkladů, kde každý příklad bude ohodnocen určitým počtem bodů podle obtížnosti. Všechny úlohy (domácí i ty řešené na cvičeních) budou dostupné zde na webu.
  • Termín pro vyřešení a sepsání úkolů bude zhruba do konce semestru, ale vyplatí se řešení odevzdávat průběžně.
  • Příklady je možné odevzdávat opakovaně, vždy se počítá nejlepší dosažený výsledek.
  • Účast na cvičeních je nepovinná.
  • Z důvodu ochrany osobních údajů u prvních odevzdaných řešení napište kromě jména i přezdívku, pod kterou chcete mít své body zveřejněny na webu. U dalších řešení už stačí psát buď jméno, nebo přezdívku. Pokud jste první sérii úkolů odevzdali jen pod svým jménem, bude uveřejněno na webu. Pokud Vám to nevyhovuje, napište mi email s přezdívkou a já to změním.
  • Aktuální seznam bodů:
Přezdívka:  1a   1b   2   3   4   5   6a   6b   7   8a   8b   9   10a   10b   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   Součet   Zápočet 
 Maxim Dokonalý  1 1 3 2 2 1 2 3 3 2 4 3 2 2 2 4 3 4 2 2 3 3 2 3 3 2 3 6 3 4 80 ---
 Feldmaršálek Duda  1 1 2 0.5 3 2 2 2 1 2 3 3 22.5 ANO
 tykvička  1 1 3 2 2 2 2 3 2 2 3 23 ANO
 X3H1M1  1 0.5 3 2 0 2 1 2 3 2 2.5 2 21 ANO
 Anotnín Češík   1 1 3 2 1 2 1 2 4 2 3 22 ANO
 Alexirhoé   0.5 1 3 1.5 0.5 2 3 2 2 2.5 2 2 3 25 ANO
 Magdaléna Žváčková   1 2 2 2 3 2 3 3 18
   
  • Zadání domácích úkolů: [PDF] (poslední aktualizace 14.5.2015)
Jednotlivá cvičení:
  • První cvičení (16.2.2015): Úvod, podmínky zápočtu, opakování z teorie grafů. Probrány příklady 1, 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Druhé cvičení (23.2.2015): Opakování z teorie grafů podruhé. Probrány příklady 1, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení (2.3.2015): Toky v sítích. Probrány příklady 1, 2, 3 a 4, ukázán příklad sítě, na které selže Ford-Fulkersonův algoritmus. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (9.3.2015): Aplikace Hallovy věty. Probrány příklady 1, 2, 3a a 4. Seznam příkladů ze cvičení [PDF].
  • Páté cvičení (16.3.2015): Grafová souvislost. Probrány příklady 1, 2, 3a a dokázáno Ušaté lemma. Seznam příkladů ze cvičení [PDF].
  • Šesté cvičení (23.3.2015): Rovinné grafy a jejich vlastnosti. Probrány příklady 1a, 1b, 2 (bez nakreslení K_7), 3 a 4. Seznam příkladů ze cvičení [PDF].
  • Sedmé cvičení (30.3.2015): Rovinné grafy podruhé, barevnost a vybíravost. Probrány příklady 1, 2, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Osmé cvičení (6.4.2015): Cvičení se nekonalo (Velikonoce).
  • Deváté cvičení (13.4.2015): Ramseyova teorie. Probrány příklady 1, 2 a 6. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (20.4.2015): Ramseyova teorie - pokračování. Probrány příklady 1, 2, 3b a 5. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (27.4.2015): Úvod do vytvořujících funkcí. Probrány příklady 1, 2, 3a, 3b, 3c, 4a, 5 a 6, vysvětlen kombinatorický důkaz binomické věty. Seznam příkladů ze cvičení [PDF].
  • Dvanácté cvičení (4.5.2015): Vytvořující funkce - aplikace. Probrány příklady 1, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Třinácté cvičení (11.5.2015): Konečné projektivní roviny a latinské čtverce. Probrány příklady 1, 2, 3, a 4a, ukázána konstrukce konečných projektivních rovin řádu mocniny prvočísla a náznak konstrukce konečné projektivní roviny řádu n z n-1 navzájem ortogonálních latinských čtverců řádu n. Seznam příkladů ze cvičení [PDF].
  • Čtrnácté cvičení (18.5.2015): NP-úplnost a polynomiální převoditelnost. Probrány příklady 1a, 1b, a 1d. Seznam příkladů ze cvičení [PDF].
Valid XHTML 1.0 Transitional