Detail předmětu

Diskrétní matematika

FIT-IDMAk. rok: 2020/2021

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.

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.

Doporučená nebo povinná literatura

Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010. (CS)
Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010. (in Czech).
Kovár, M., Diskrétní matematika, FEKT VUT, Brno, 2013. (in Czech).
Kovár, M.,  Diskrétní matematika, FEKT VUT, Brno, 2013 (CS)
Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992. (CS)
Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992. (in Slovak).
Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001.
Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, Springer-Verlag, Berlin 2006.
Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007. (in Czech).
Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006.
Sochor, A., Klasická matematická logika, Karolinum, Praha 2001. (CS)
Sochor, A., Klasická matematická logika, Karolinum, Praha 2001. (in Czech).

Způsob a kritéria hodnocení

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

Jazyk výuky

čeština, angličtina

Cíl

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

Zařazení předmětu ve studijních plánech

  • Program BIT bakalářský, 1. ročník, zimní semestr, 5 kreditů, povinný

  • Program IT-BC-3 bakalářský

    obor BIT , 1. ročník, zimní semestr, 5 kreditů, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Osnova

  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.

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.

eLearning