470-8728/01 – Diskrétní matematika (DIM AVAT)

Předmět seznamuje studenty se základními pojmy diskrétní matematiky a teorie grafů, se kterými se nejčastěji pracuje v různých oblastech teoretické a aplikované informatiky. Na přednáškách budou vždy definovány a vysvětleny základní používané pojmy matematické teorie vztahující se k dané kapitole. Do každé kapitoly jsou zařazeny praktické aplikace probírané látky. V dalším budou vymezeny základní a nejdůležitější vlastnosti nadefinovaných pojmů (objektů) ve formě tvrzení, přičemž některá z nich budou dokázána. Důraz je kladen na konstruktivní důkazy. Po absolvování přednášky by tedy student měl umět: - reprodukovat, ekvivalentně přeformulovat, popřípadě zobecnit dané definice, - rozpoznat a odlišovat objekty reálného světa a poznaných matematických teorií, které definici vyhovují, a které ne, - klasifikovat tyto objekty dle předem známých a řádně objasněných vlastností, - shrnout poznatky dané kapitoly. Cvičení by mělo u studenta rozvinout tyto schopnosti: - formulovat úlohu slovy probrané matematické teorie, - aplikovat teoretické poznatky na řešení konkrétních praktických úloh a problémů, - navrhnout více metod řešení a tyto porovnávat a kriticky vyhodnocovat, - přezkoumat správnost výběru metody řešení, - přenášet či přenést metodu řešení jedné úlohy na úlohy jiné.

Předmět seznamuje studenta se základními pojmy, konstrukcemi a postupy diskrétní matematiky v oblasti kombinatoriky a teorie grafů. (Slovo "diskrétní" je v názvu míněno jako opak "spojitého".)

J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000. (Konkrétně: Kapitoly 1,2 a část kapitoly 9 pro Část I přednášky. Kapitoly 3,4,5 pro Část II přednášky.)

Semestrální písemky. Každý týden v semestru (s výjimkou prvních dvou týdnů) se na cvičeních budou psát krátké zápočtové písemky (deset písemek, každá za 2 nebo za 3 body). Během písemek není možné používat literaturu, ani zápisky. Na konci semestru cvičící sečte body ze čtyř "nejlepších" dvoubodových a čtyř nejlepších tříbodových písemek. Maximum je 20 bodů. Témata písemek jsou vždy vyvěšena na stránkách diskrétní matematiky (resp. garanta předmětu), minimálně týden před písemkou. Na písemky budou zadány příklady obdobné. Samostatný projekt. Bude zadán v druhé půli semestru. Běžný projekt bude obsahovat několik příkladů, přičemž zhruba polovina bude z kombinatoriky a polovina z teorie grafů. Příklady budou hodnoceny buď 0-2 nebo 0-3 body (dle obtížnosti) tak, aby byl celkový maximální součet 10 bodů. Na webu mohou být také uveřejněny projekty pro zájemce, které budou obsahovat dva obtížnější úkoly (kombinatorika + teorie grafů). Každý student má možnost přidělený běžný projekt zaměnit za některý z projektů pro zájemce. Projekt pro zájemce bude mít úkoly hodnoceny 0/3/5 bodů, v případě výjimečně pěkného řešení až 10 bodů. Zkouška. Ke zkoušce můžete student jít, pokud získal zápočet. Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce můžete získat až 70 bodů. Během zkoušky můžete používat také jedinou stranu A4 rukou psaných poznámek. Na tomto "zlegalizovaném taháku" mohou být definice, věty, vztahy. ALE NE ŘEŠENÉ PŘÍKLADY!!! Podmínky udělení zápočtu: Získat během semestru alespoň 10 bodů a samostatný referát musí být PŘIJAT. Referát bude přijat, pokud bude splňovat formální podmínky, tj. formát, úvodní stranu atd. Přijat může být i projekt, který je obsahově na 0 bodů.