Detail předmětu

Diskrétní matematika

IDM Ak. rok 2023/2024 zimní semestr 4 kredity

Aktuální akademický rok

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

česky, anglicky

Zakončení

zápočet+zkouška (písemná)

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í

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

  1. Formální jazyk matematiky. Základní formalismy - věta, důkaz, výroková a predikátová logika.
  2. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze.
  3. Důkazové techniky.
  4. Binární relace, jejich vlastnosti a skládání.
  5. Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
  6. Relace uspořádání, svazy. Hasseovské diagramy. Zobrazení.
  7. Pojem grafu, základní pojmy. Isomorfismus grafů, stromy, cesty a eulerovské grafy.
  8. Grafové algoritmy pro hledání nejkratší cesty a minimální kostry. Rovinné grafy.
  9. Orientované grafy.
  10. Binární operace a jejich vlastnosti.
  11. Algebry s jednou operaci, grupy.
  12. Kongruence a morfismy.
  13. 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

Nahoru