Detail předmětu
Diskrétní matematika
IDM Ak. rok 2023/2024 zimní semestr 4 kredity
Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Booleovy algebry. Výroková a predikátová logika. Základní pojmy teorie grafů. Souvislost grafů. Podgrafy a morfismy grafů. Problém rovinnosti. Stromy a jejich vlastnosti. Základní grafové algoritmy. Orientované grafy.
Garant předmětu
Koordinátor předmětu
Jazyk výuky
Zakončení
Rozsah
- 26 hod. přednášky
- 26 hod. cvičení
Bodové hodnocení
- 80 bodů závěrečná zkouška
- 20 bodů numerická cvičení
Zajišťuje ústav
Přednášející
Cvičící
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Tůma Martin, Mgr., Ph.D. (UMAT)
Stránky předmětu
Cíle předmětu
Předmět poskytuje základní znalosti z matematiky potřebné pro řadu navazujících předmětů. Studenti se seznámí s elementárními poznatky z algebry a diskrétní matematiky s důrazem na matematické struktury, které jsou potřebné pro pozdější aplikace v informatice. Získají schopnost orientace v základních diskrétních matematických strukturách a schopnost porozumět logické struktuře matematického textu. Budou schopni vysvětlit matematické struktury a umět přesně formulovat vlastní tvrzení a jejich důkazy.
Proč je předmět vyučován
Matematika a matematické myšlení jsou historickým základem informatiky a jsou jádrem většiny současného pokroku v informatice.
Diskrétní matematika se soustřeďuje na porozumění objektům a jevům reálného světa, které jsou pro informatiku nejzásadnější. Jedná se o koncepty jako množina (např. soubor dat, aktérů), relace a graf (např. vztahy mezi daty, popis komunikace) a operace nad prvky množiny (zejména aritmetické operace a jejich zobecnění). Matematická logika pak dává efektivní nástroje pro strukturované a jasné vyjadřovaní, argumentaci a odvozovaní a je hlavním principem, na kterém stojí "myšlení počítačů".
Obecně diskrétní matematika učí základům abstrakce - jak vystihnout aspekty reálného světa důležité pro řešení problému a jak s nimi pracovat. Poskytuje univerzální jazyk, kterým o těchto aspektech dokážeme výstižně a efektivně komunikovat a který pomáhá strukturovat myšlení do přesně vymezených pojmů a vztahů. Tato efektivita a přesnost je nezbytná při návrhu a vývoji rozsáhlých a komplikovaných IT systémů a pro vývoj souvisejících inovací.
Aparát diskrétní matematiky například poskytuje základní nástroje potřebné k vyjádření, co program dělá; jak na vstupu závisí výstup nebo množství potřebných zdrojů; jak jsou organizována data v datových strukturách a co reprezentují; jak program komunikuje s okolím; co znamená, že program funguje správně. Podobné aplikace diskrétní matematiky a jejího jazyka v informatice jsou všudypřítomné. Dá se říct, že programátor/informatik bez matematiky je jako klavírista bez znalosti not. Může mít úspěšnou kariéru pokud má talent, ale jeho možnosti jsou omezené, zejména pokud se jedná o řešení komplikovaných problémů.
Protože naším cílem je hlavně naučit studenty matematicky myslet a systematicky se vyjadřovat, klademe velký důraz právě na nácvik použití matematiky a matematického myšlení k řešení problémů - stejně jako se programování člověk naučí jen programováním, i ke zvládnutí matematiky je nezbytné matematiku dělat vlastníma rukama.
Požadované prerekvizitní znalosti a dovednosti
Středoškolská matematika.
Literatura studijní
- Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010.
- Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007.
- Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
Osnova přednášek
- Formální jazyk matematiky. Základní formalismy - věta, důkaz, výroková a predikátová logika.
- Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze.
- Důkazové techniky.
- Binární relace, jejich vlastnosti a skládání.
- Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
- Relace uspořádání, svazy. Hasseovské diagramy. Zobrazení.
- Pojem grafu, základní pojmy. Isomorfismus grafů, stromy, cesty a eulerovské grafy.
- Grafové algoritmy pro hledání nejkratší cesty a minimální kostry. Rovinné grafy.
- Orientované grafy.
- Binární operace a jejich vlastnosti.
- Algebry s jednou operaci, grupy.
- Kongruence a morfismy.
- Algebry se dvěma operacemi, svazy jako algebry. Booleovy algebry.
Osnova numerických cvičení
Příklady probírané na cvičeních jsou voleny tak, aby vhodným způsobem doplňovaly přednášky.
Průběžná kontrola studia
Písemné testy během semestru (pět 4bodových testů). Výuka je povinná. Na přednáškách účast nebude kontrolována, ale znalost probírané látky bude následně na cvičeních vyžadována, neúčast na cvičeních musí být omluvena. Závěrečná písemná zkouška 80 bodů.
Podmínky zápočtu
Podmínka zápočtu je zisk alespoň 8 bodů z písemek během semestru a aktivní práce na cvičení.
Zařazení předmětu ve studijních plánech
- Program BIT, 1. ročník, povinný
- Program BIT (anglicky), 1. ročník, povinný
- Program IT-BC-3, obor BIT, 1. ročník, povinný