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í

Studenti 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 budou umět přesně formulovat vlastní tvrzení a jejich důkazy.

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.

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.

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

• Znalosti studentů jsou ověřovány na cvičeních vypracováním pěti písemných testů po 4 bodech a závěrečnou zkouškou za 80 bodů.
• Pokud se student nemůže cvičení z vážného důvodu (například pro nemoc) zúčastnit a tento důvod doloží v souladu s Článkem 55 Studijního a zkušebního řádu VUT, může se cvičení se stejným tématem zúčastnit s jinou skupinou (pokud s tím cvičící souhlasí).

Získání alespoň 8 bodů z písemných testů.