Cvičení z Kombinatoriky a grafů I (pondělí a úterý)

Zde jsou informace ohledně cvičení z Kombinatoriky a grafů (2017/2018), které cvičím. Hlavní přednáška je vyučována panem docentem Fialou.


Aktuality

7. května v čase pondělního cvičení proběhne nadstavbové cvičení na vytvořující funkce. 


Výslekdy

Pokud výsledky nesedí s tím, co jste dostali, dejte mi vědět. Reklamace se přijímají do začátku zkouškového období.

Výsledky.


Mail

    Maily se snažím kontrolovat alespoň jednou denně večer, avšak o víkendu a v pátek neslibuji, že se k nim vždy dostanu. Upozornění. Poslední dobou jsem zahlcen spamy. Proto při komunikaci mailem, vložte do jeho předmětu kód přednášky, tj. NDMI011.


Podmínky zápočtu

    Pro získání zápočtu je potřeba získat 2/3 z celkového počtu možných bodů z písemek a domácích úkolů. Je plánováno 9 krátkých písemek a 9 domácích úkolů. Domácí úkoly a písemné práce budou za 8-9 bodů. Celkově bude možné z písemných prací a domácích úkolů získat 150 bodů, tzn. pro získání zápočtu je potřeba alespoň 100 bodů.

    Písemky se píší na každém cvičení, pokud nebude řečeno jinak. Písemka se zadá na začátku cvičení a čas na její řešení je 15 minut. Okruh témat, ze kterého se bude písemná práce psát, se řekne týden před danou písemnou prací a také se vyvěsí zde na stránce. Na pozdní příchod se nebere ohled, tzn. pokud přijdete pozdě, pořád platí, že písemku musíte odevzdat ve stejnou dobu jako Vaši kolegové, kteří nepřišli pozdě. Na posledním cvičení bude možnost si opravit 6 písemných prací, tzn. pokud se Vám některá písemka nepovedla nebo jste na některé písemce chyběli, je možné si je znovu napsat na posledním cvičení. (Ale zadání opravné písemky se bude lišit.) Pokud si budete chtít opravit některou písemku, dejte mi vědět do předposledního cvičení, ze kterého okruhu si chcete opravit písemku. Dejte mi to vědět buď ústně na cvičení nebo mailem. Do celkového výsledku se započítají výsledky z opravných písemek, i kdyby výsledky z opravných písemek byly horší.

    Domácí úkoly se zadávají pravidelně na každém cvičení. Na jejich vypracování jsou dva týdny. Pokud si nevíte rady s řešením příkladů, v prvním týdnu po zadání je možné se zeptat na radu. Ptejte se mailem nebo ústně na cvičení. Nutnou podmínkou pro získání rady je, že úkážete, že už jste vyčerpali všechny možnosti řešení, tzn. požaduji, abyste přesně zformulovali tu část, se kterou máte problém, a navíc, že ukážete na papíře vše, co už jste zkusili. Domácí úkoly je možné odevzdávat přes mail nebo písemně na papíře, který mi dáte na cvičení. Při odevzdání přes mail použijte formát pdf. Při odevzdání na papíře musí být řešení napsáno na listech papíru velikosti A4. O papíry můžete požádat na cvičení.

    Dále je možné získat body za aktivitu na cvičení, avšak maximální počet bodů za aktivitu je omezen na 5 bodů za jedno cvičení.

    Při speciálních příležitostech se  zadají bonusové příklady.

    Body z bonusových příkladů a z aktivit se počítají do celkové sumy bodů pro získání zápočtu. Nemusíte se obávat, že tyto body vám změní hranici potřebnou pro získání zápočtu. Body z bonusových příkladů a aktivit se neberou v úvahu pří počítání hranice 2/3 bodů potřebných pro získání zápočtu. Pro počítání 2/3 hranice se berou v potaz pouze body z písemek a domácích úkolů, tzn. hranice 100 bodů potřebná pro zápočet se nemění.


Jak napsat řešení

    Abyste mohli dostat body za řešení příkladů, musíte odůvodnit každé svoje tvrzení, které napíšete. Jinka bude řešení považováno za nesprávné a nedostanete za něho body. Avšak platí, že věty odpřednesené na přednášce lze používat v řešení bez důkazu. Protože máte za sebou předmět Diskrétní matematika, lze věty z tohoto předmětu používat také bez důkazu. Aby bylo jasno, které věty z předmětu Diskrétní matematika je možné používat bez důkazu, jsou určeny níže.

Věty, které se nacházejí v knize Kapitoly z diskrétní matematiky a to v kapitolách

  • 1, Základní pojmy a označení,
  • 2, O uspořádaných množinách,
  • 3, Kombinatorické počítání,
  • 4, Gfafy: úvod, kromě podkapitol 4.7 a 4.8,
  • 5, Stromy, a
  • 6, Rovinné kreslení grafů.

Lze používat i věty, které se nacházejí ve cvičeních na konci výše povolených kapitol.


Absence

Dlouhodobou absenci řešte ihned, tzn. dejte o sobě co nejdřive vedět, abych viděl Váši aktivní snahu vyřešit danou situaci. Pokud bude absence opodstatněná, je možné se domluvit na možnosti napsat si dodatečné domácí úkoly.


Písemné práce

  • 1. písemná práce (pondělní skupina: 5.3.2018, úterní skupina: 6.3.2018): Odhady: binomické koeficienty a faktoriály. Viz také příklady.
  • 2. písemná práce (pondělní skupina: 12.3.2018, úterní skupina: 13.3.2018): Vytvořující funkce. Viz také příklady.
  • 3. písemná práce (pondělní skupina: 19.3.2018, úterní skupina: 20.3.2018): Vytvořující funkce: Zobecněná binomická věta, homogenní lineární diferenční rovnice k-tého stupně s konstatními koeficienty (viz Kapitoly).
  • 4. písemná práce (pondělní skupina: 26.3.2018, úterní skupina: 27.3.2018): Projektivní roviny: definice, řád projektivní roviny, věty. Vztah projektivní roviny a konečného tělesa.
  • 5. písemná práce (pondělní skupina: 9.4.2018, úterní skupina: 3.4.2018): Počítání dvěma způsoby: viz první čtyři příklady z příklady.
  • 6. písemná práce (pondělní skupina: 16.4.2018, úterní skupina: 10.4.2018): Počítání dvěma způsoby + Souvislost (pouze definice): hranový a vrcholový řez, hranová a vrcholová souvislot, viz. skripta, kapitola 3. Míra souvislosti grafů.
  • 7. písemná práce (pondělní skupina: 23.4.2018, úterní skupina: 17.4.2018): Míra souvislosti grafů, věty: Ford-Fulkerson, Menger
  • 8. písemná práce (pondělní skupina: 30.4.2018, úterní skupina: 24.4.2018): Toky v sítích, viz příklady, BONUS: grafy - vše.  U bonusové části nebude možnost opravy.
  • 9. písemná práce (pondělní skupina: 14.5.2018, úterní skupina: 15.5.2018): Toky v sítích, míra souvislosti grafů, maximální párování.

Zadání domácích úkolů

  • 1. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 12.3.2018, úterní skupina - 14:00 13.3.2018
  • 2. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 19.3.2018, úterní skupina - 14:00 20.3.2018
  • 3. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 26.3.2018, úterní skupina - 14:00 27.3.2018
  • 4. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 9.4.2018, úterní skupina - 14:00 3.4.2018. UPDATE: 31.3.2018
  • 5. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 16.4.2018, úterní skupina - 14:00 10.4.2018
  • 6. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 23.4.2018, úterní skupina - 14:00 17.4.2018
  • 7. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 30.4.2018, úterní skupina - 14:00 24.4.2018
  • 8. domácí úkol: Termíny odevzdání: pondělní skupina - 15:40 14.5.2018, úterní skupina - 14:00 15.5.2018
  • 9. domácí úkol: Termíny odevzdání: pondelní skupina - 15:40 21.5.2018, úterní skupina - 14:00 22.5.2018


Další příklady

  • Dobrým zdrojem řešených příkladů je stránka kamu s příklady.
  • Pokud vám příklady ze sbírky na kamu připadají jednoduché, zkuste si počítat jedno- a dvou-hvězdičkové příklady v Kapitolách z diskrétní matematiky od prof. Matouška a prof. Nešetřila.
  • Pokud vám i příklady z Kapitol připadají primitivní, můžete zkusit sbírku příkladů Lásló Lovász: Combinatorial problems and exercises. Ale předem varuji, že je to pro pokročilé.

© 2017 Josef Amemori