Detail předmětu

Diskrétní matematika

IDM Ak. rok 2021/2022 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.

Aktuální informace

 

Garant předmětu

Koordinátor předmětu

Jazyk výuky

česky, anglicky

Zakončení

zápočet+zkouška (písemná)

Rozsah

26 hod. přednášky, 26 hod. cvičení

Bodové hodnocení

64 bodů zkouška, 25 bodů půlsemestrální test, 6 bodů cvičení, 5 bodů projekty

Zajišťuje ústav

Přednášející

Cvičící

Stránky předmětu

Aktuální informace k předmětu naleznete zde: web stránka


Streaming přednášek: zde

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.

Literatura studijní

  • Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010.
  • Kovár, M.,  Diskrétní matematika, FEKT VUT, Brno, 2013
  • 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.
  • 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.

Osnova přednášek

  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.

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 25 bodů).

Kontrolovaná výuka

  • Znalosti studentů jsou ověřovány na cvičeních (max. 6 bodů), vypracováním pěti písemných testů po 5 bodech, vypracováním domácího úkolu za 5 bodů  a závěrečnou zkouškou za 64 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ň 12 bodů z písemných testů.

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Útpřednáškavýuky D0206 D105 08:0009:50 1BIB 2BIA 2BIB xx 30 - 49 Hliněná, Holík, Lengál
Útpřednáškavýuky D0206 D105 12:0013:50 1BIA 2BIA 2BIB xx 10 - 29 Hliněná, Holík, Lengál
Útcvičenívýuky D0207 14:0015:50 1BIA 1BIB 2BIA 2BIB xx Harmim
Útcvičenívýuky D0207 16:0017:50 1BIA 1BIB 2BIA 2BIB xx Holík
Stcvičenívýuky T8/T 5.03 07:0008:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Stcvičenívýuky G202 09:0010:50 1BIA 1BIB 2BIA 2BIB xx Síč
Stcvičenívýuky T8/T 3.22 09:0010:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Stcvičenívýuky G202 11:0012:50 1BIA 1BIB 2BIA 2BIB xx Síč
Stcvičenívýuky T8/T 3.22 11:0012:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Stcvičenívýuky A113 18:0019:50 1BIA 1BIB 2BIA 2BIB xx Harmim
Čtcvičenívýuky G202 08:0009:50 1BIA 1BIB 2BIA 2BIB xx Lengál
Čtcvičenívýuky T8/T 3.22 11:0012:50 1BIA 1BIB 2BIA 2BIB xx Fuchs
Čtcvičenívýuky A113 12:0013:50 1BIA 1BIB 2BIA 2BIB xx Havlena
Čtcvičenívýuky T8/T 3.22 13:0014:50 1BIA 1BIB 2BIA 2BIB xx Fuchs
cvičenívýuky T8/T 3.22 07:0008:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
cvičenívýuky A113 08:0009:50 1BIA 1BIB 2BIA 2BIB xx Hliněná
cvičenívýuky T8/T 3.22 09:0010:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
cvičenívýuky A113 10:0011:50 1BIA 1BIB 2BIA 2BIB xx Hliněná
cvičenívýuky G202 13:0014:50 1BIA 1BIB 2BIA 2BIB xx Lengál
cvičenívýuky G202 15:0016:50 1BIA 1BIB 2BIA 2BIB xx Síč

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

  • Program BIT, 1. ročník, povinný
  • Program IT-BC-3, obor BIT, 1. ročník, povinný
Nahoru