Diskrétní matematika

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

• 64 bodů závěrečná zkouška (písemná část)
• 25 bodů půlsemestrální test (písemná část)
• 6 bodů numerická cvičení
• 5 bodů projekty

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 vystihnou 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 říci, ž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.

1. Formální jazyk matematiky. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze. 
2. Binární relace a zobrazení, jejich skládání a vlastnosti.
3. Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
4. Uspořádání. Hasseovské diagramy. Zobrazení
5. Binární operace a jejich vlastnosti.
6. Algebry s jednou operaci, zejména grupy. Kongruence a morfismy.
7. Algebry se dvěma operacemi, svazy jako algebry. Booleovy algebry.
8. Výroková logika. Syntaxe a sémantika. Splnitelnost a platnost. Logická ekvivalence a logický důsledek. Ekvivalentní formule. Normální formy.
9. Predikátová logika. Jazyk predikátové logiky prvního řádu. Syntaxe, termy a formule, volné a vázané proměnné. Realizace.
10. Predikátová logika. Sémantika, Tarského definice pravdy. Logická platnost, logický důsledek. Teorie. Ekvivalentní formule. Normální formy.
11. Formální systém logiky. Axiomatický systém Hilbertova typu pro výrokovou a predikátovou logiku. Dokazatelnost, rozhodnutelnost, úplnost, neúplnost.
12. Pojem grafu, základní pojmy. Isomorfismus grafů, souvislost, stromy, cesty a eulerovské grafy (jednotažky).
13. Hledání nejkratší cesty. Dijkstrův algoritmus. Problém minimální kostry. Algoritmy Kruskala a Jarníka. Rovinné grafy.

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

• Ohodnocení pěti písemných testů  (max 25 bodů).

• Znalosti studentů jsou ověřovány na cvičeních (max. 6 bodů), vypracováním pěti písemných testů po 5 bodech, vypracováním domácího úkolu za 5 bodů  a závěrečnou zkouškou za 64 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 (na což dotyčného cvičícího upozorní). 
• Hranice pro úspěšné složení zkoušky je získání alespoň 50 bodů z celkového maxima 100 bodů, získaných v průběhu semestru (za domácí úlohy a vnitrosemestrální zkoušky) a za závěrečnou zkoušku, podle pravidel ECTS.

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