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

Počet kreditů

5

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.

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

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

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

    obor BIT , 1 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

doc. RNDr. Dana Hliněná, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
RNDr. Petr Fuchs, Ph.D.
Ing. Ondřej Lengál, 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

Ing. Rudolf Čejka
Mgr. Gabriela Vážanová, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
Ing. Vojtěch Havlena, Ph.D.
doc. RNDr. Dana Hliněná, Ph.D.
RNDr. Petr Fuchs, Ph.D.
Ing. Ondřej Lengál, Ph.D.
doc. RNDr. Zdeněk Svoboda, CSc.

Osnova

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