Detail předmětu
Diskrétní matematika
FIT-IDMAk. rok: 2019/2020
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.
Jazyk výuky
čeština, angličtina
Počet kreditů
5
Garant předmětu
Zajišťuje ústav
Výsledky učení 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.
Prerekvizity
Středoškolská matematika.
Způsob a kritéria hodnocení
- Ohodnocení dvou domácích úloh vypracovaných ve skupinách (max 10 bodů).
- Ohodnocení dvou vnitrosemestrálních zkoušek (max 30 bodů).
Podmínky zápočtu:
Získání alespoň 10 bodů z vnitrosemestrálních zkoušek. Pokud bude odhaleno plagiátorství nebo nedovolená spolupráce na projektu, zápočet nebude udělen a dále bude zváženo zahájení disciplinárního řízení.
Učební cíle
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.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
- Znalosti studentů jsou ověřovány na cvičeních, vypracováním a obhajobou dvou domácích úloh, každá po 5 bodech, vypracováním dvou vnitrosemestrálních zkoušek, každá po 15 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.
Zařazení předmětu ve studijních plánech
Typ (způsob) výuky
Přednáška
26 hod., nepovinná
Vyučující / Lektor
Osnova
- 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.
Cvičení s počítačovou podporou
26 hod., povinná
Vyučující / Lektor
Osnova
Příklady probírané na cvičeních jsou voleny tak, aby vhodným způsobem doplňovaly přednášky.