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.

Garant předmětu

doc. RNDr. Dana Hliněná, Ph.D.

Zajišťuje ústav

Ústav matematiky (UMAT)

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

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

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

  • 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

doc. RNDr. Dana Hliněná, Ph.D.

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

doc. RNDr. Dana Hliněná, Ph.D.

Osnova

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