Cvičení z diskrétní matematiky (zim. sem. 17/18)

Podmínky zápočtu

K získání zápočtu je třeba získat dostatek bodů z domácích úkolů a písemek. Domácí úkoly budou zadávány průběžně na každém cvičení (plus mínus drobné výjimky) a je potřeba získat 70 bodů z celkových 100 bodů. Písemky se budou psát v předem ohlášených termínech v průběhu semestru (každou písemku ohlásím alespoň cvičení předem, ale pokusím se dříve). Celkem se budou psát tři písemky ze kterých je třeba získat 210 bodů z 300 možných. Dále se pro zájemce bude psát jedna opravná písemka.

Dále je možno získat bonusové body a to především za aktivitu na cvičeních a docházku (za nejvýše tři absence je možno získat deset bodů, za čtyři nebo pět absencí lze získat pět bodů). Docházka ale není povinná (pouze doporučená)

Odevzdávání domácích úkolů

Domácí úkoly mají termín do začátku následujícího cvičení. Odevzdávat je můžete jako pdf e-mailem (nezapomeňte do předmětu e-mailu uvést kód předmětu) nebo fyzicky mé osobě (typicky na začátku cvičení), případně je můžete hodit do mé schránky na koleji (ale to jen spíš v případě nouze).

Mechanismus bonusových bodů

Bonusové body získané v průběhu semestru (za docházku a aktivitu) budou na konci semestru přetransformovány na body za úkoly nebo za písemky. Přičemž jeden bonusový bod odpovídá buď jednomu bodu za úkol, nebo dvěma bodům za písemku. Body budou transformovány tak, aby maximalizovaly váš prospěch -- tedy tak, abyste dosáhli limitů na zápočet, pokud to lze.

Opravná písemka

Pokud jste nezískali dostatečný počet bodů z písemek, můžete na konci semestru napsat ještě jednu opravnou písemku. Ta může nahradit vaši nejhorší písemku (pokud si tím polepšíte). Přesněji, ze všech vámi psaných písemek, včetně opravné, se vezmou tři nejlepší a z ty se budou počítat do limitu na zápočet. Termín opravné písemky dohodneme na posledním, nebo předposledním cvičením, případně, pokud nebudete moci dorazit, se dohodneme mailem.

Středeční paralelka

Druhá písemka se bude psát 29. 11., třetí potom 3.1.

1. cvičení: Úvodní info, připomenutí a osvětlení věcí z přednášky, příklady na operace s množinami a matematickou indukci. Zadán 1.DÚ.

Příklady z 1. cvičení (do příkladů, které jsem na cvičení rozdával se vloudilo několik chyb, konkrétně do příkladu 2. Zde by měly být opraveny).

3. cvičení: Opakování důkazů a relací, převážně ekvivalencí. Zadán 3.DÚ.

5. cvičení: Kombinatorické počítání, kombinační čísla. Zadán 4.DÚ, jelikož příští cvičení odpadá, odevzdávejte ho buď do schránky, nebo mailem.

7. cvičení: Hrátky s binomickou větou. Metody a triky jak s její pomocí dokazovat identity o kombinačních číslech, konkrétně dosazení, násobení polynomů a derivace. Úvod do principu inkluze a exkluze. Zadán 5.DÚ.

8. cvičení: Zmíněny multinomické koeficienty a multinomická věta spolu s ideou, jak ji dokázat. Úvod do uspořádání -- co je to uspořádání, částečně uspořádaná množina, lineární uspořádání, Hasseho diagramy, minimální a nejmenší prvky (viz Kapitoly, kapitoly 2.1 a 2.2 ve čtvrtém vydání z r. 2009). Zadán 6.DÚ.

10. cvičení: Řetězce a anitřetězce v usporádání. Vztah mezi velikostí pokrytí uspořádání řetězci a velikosti největšího antiřetězce. Úvod do grafů -- co to je graf, skóre, eulerovský tah, isomorfismus grafů, stromy, cykly, cesty, kostry. Zadán 8.DÚ.

11. cvičení: Pokračování grafů a trocha stromů. Indukovaný podgraf a matice sousednosti a incidence. Zadán 9.DÚ.

12. cvičení: Kruskalův hladový algoritmus. Algoritmus pro testování isomorfismu stromů -- kódováné pěstovaných, zakořeněných a obyčejných stromů. Zadán 1. Bonusový DÚ.

13. cvičení: Psala se 3. písemka. Naťukly se rovinné grafy a obarvení.

Body atp.

Pokud se zde nevidíte, pak je to nejspíše tím, že jste mi neposlali svou přezdívku.

Čtvrteční paralelka

Druhá písemka se bude psát 30. 11., třetí potom 4.1.

1. cvičení:Úvodní info, připomenutí a osvětlení věcí z přednášky, příklady na operace s množinami a matematickou indukci. Zadán 1.DÚ.

Příklady z 1. cvičení (do příkladů, které jsem na cvičení rozdával se vloudilo několik chyb, konkrétně do příkladu 2. Zde by měly být opraveny).

5. cvičení: Kombinatorické počítání, kombinační čísla. Zadán 4.DÚ.

6. cvičení: Hrátky s binomickou větou. Metody a triky jak s její pomocí dokazovat identity o kombinačních číslech, konkrétně dosazení, násobení polynomů a derivace. Letmý úvod do principu inkluze a exkluze. Zadán 5.DÚ.

7. cvičení: Pokračování principu inkluze a exkluze a obecně kombinatorického počítání. Zmíněny multinomické koeficienty a multinomická věta spolu s ideou, jak ji dokázat. Zadán 6.DÚ.

8. cvičení: Úvod do uspořádání -- co je to uspořádání, částečně uspořádaná množina, lineární uspořádání, Hasseho diagramy, minimální a nejmenší prvky (viz Kapitoly, kapitoly 2.1 a 2.2 ve čtvrtém vydání z r. 2009). Zadán 7.DÚ.

9. cvičení: Psala se 2. písemka. Řetězce a anitřetězce v usporádání. Vztah mezi velikostí pokrytí uspořádání řetězci a velikosti největšího antiřetězce. Zadán 8.DÚ.

10. cvičení: Úvod do grafů -- co to je graf, skóre, eulerovský tah, isomorfismus grafů, stromy, cykly, cesty, kostry. Zadán 9.DÚ.

11. cvičení: Pokračování grafů a trocha stromů. Kruskalův hladový algoritmus, jak a proč funguje. Zadán 10.DÚ.

12. cvičení: Kruskalův hladový algoritmus. Algoritmus pro testování isomorfismu stromů -- kódováné pěstovaných, zakořeněných a obyčejných stromů. Zadán 11. DÚ a 1. Bonusový DÚ.

13. cvičení: Psala se 3. písemka. Naťukly se rovinné grafy a obarvení.

Body atp.

Pokud se zde nevidíte, pak je to nejspíše tím, že jste mi neposlali svou přezdívku.

Cvičení z diskrétní matematiky pro matematiky (NMIN105)

Středa od 17:20 a čtvrtek od 10:40

Podmínky zápočtu

Odevzdávání domácích úkolů

Mechanismus bonusových bodů

Opravná písemka

Středeční paralelka

Druhá písemka se bude psát 29. 11., třetí potom 3.1.

Body atp.

Čtvrteční paralelka

Druhá písemka se bude psát 30. 11., třetí potom 4.1.

Body atp.