Detail předmětu
Diskrétní matematika
IDM Ak. rok 2020/2021 zimní semestr 5 kreditů
Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Boolovy 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, toky v sítích.
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í
- 60 bodů závěrečná zkouška (písemná část)
- 40 bodů půlsemestrální test (písemná část)
Zajišťuje ústav
Přednášející
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Cvičící
Černocký Jan, prof. Dr. Ing. (UPGM)
Fuchs Petr, RNDr., Ph.D. (UMAT)
Havlena Vojtěch, Ing., Ph.D. (UITS)
Herout Adam, prof. Ing., Ph.D. (UPGM)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Hynek Jiří, Ing., Ph.D. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Mrázek Vojtěch, Ing., Ph.D. (UPSY)
Očenášek Pavel, Mgr. Ing., Ph.D. (UIFS)
Síč Juraj, Mgr. (UITS)
Smrčka Aleš, Ing., Ph.D. (UITS)
Strnadel Josef, Ing., Ph.D. (UPSY)
Svoboda Zdeněk, doc. RNDr., CSc. (UMAT)
Švec Ján, Ing. (UPGM)
Vážanová Gabriela, Mgr., Ph.D. (UMAT)
Zemčík Pavel, prof. Dr. Ing., dr. h. c. (UPGM)
Stránky předmětu
Získané dovednosti, znalosti a kompetence z předmětu
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.
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.
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 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.
Požadované prerekvizitní znalosti a dovednosti
Středoškolská matematika.
Osnova přednášek
- Formální jazyk matematiky. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze.
- Binární relace a zobrazení, jejich skládání a vlastnosti.
- Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
- Uspořádání. Hasseovské diagramy. Zobrazení
- Binární operace a jejich vlastnosti.
- Algebry s jednou operaci, zejména grupy. Kongruence a morfismy.
- Algebry se dvěma operacemi, svazy jako algebry. Booleovy algebry.
- Výroková logika. Syntaxe a sémantika. Splnitelnost a platnost. Logická ekvivalence a logický důsledek. Ekvivalentní formule. Normální formy.
- Predikátová logika. Jazyk predikátové logiky prvního řádu. Syntaxe, termy a formule, volné a vázané proměnné. Realizace.
- Predikátová logika. Sémantika, Tarského definice pravdy. Logická platnost, logický důsledek. Teorie. Ekvivalentní formule. Normální formy.
- Formální systém logiky. Axiomatický systém Hilbertova typu pro výrokovou a predikátovou logiku. Dokazatelnost, rozhodnutelnost, úplnost, neúplnost.
- Pojem grafu, základní pojmy. Isomorfismus grafů, souvislost, stromy, cesty a eulerovské grafy (jednotažky).
- Hledání nejkratší cesty. Dijkstrův algoritmus. Problém minimální kostry. Algoritmy Kruskala a Jarníka. Rovinné grafy.
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
- Ohodnocení pěti písemných testů (max 40 bodů).
Podmínky zápočtu:
Získání alespoň 15 bodů z písemných testů.
Kontrolovaná výuka
- Znalosti studentů jsou ověřovány na cvičeních, vypracováním pěti písemných testů po 8 bodech a závěrečnou zkouškou za 60 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.
Podmínky zápočtu
Získání alespoň 15 bodů z písemných testů.
Zařazení předmětu ve studijních plánech