Diskrétní matematika

• 26 hod. přednášky
• 26 hod. cvičení

• 80 bodů závěrečná zkouška
• 20 bodů numerická cvičení

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.

Středoškolská matematika.

• 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.

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.

Příklady probírané na cvičeních jsou voleny tak, aby vhodným způsobem doplňovaly přednášky.

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ů.