Detail předmětu

Diskrétní matematika

FEKT-BPC-DMAAk. rok: 2024/2025

Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Boolovy algebry. Sémantika a syntaxe výrokového počtu v kontextu tříd formulí predikátového počtu. Normální tvary formulí. Základní pojmy teorie grafů. Souvislost grafů. Podgrafy a morfismy grafů. Problém rovinnosti. Stromy a jejich vlastnosti. Jednoduché grafové algoritmy.

Jazyk výuky

čeština

Počet kreditů

6

Garant předmětu

doc. RNDr. Martin Kovár, Ph.D.

Zajišťuje ústav

Ústav matematiky (UMAT)

Vstupní znalosti

Je požadováno zvládnutí učiva předmětu BMA1 Matematika 1. Absolvování předmětu BMAS Matematický seminář je doporučeno.

Pravidla hodnocení a ukončení předmětu

Během semestru je ve cvičení možné získat 30 bodů (10 bodů za písemky, 20 bodů za projekty a jejich úspěšnou obhajobu). Zápočet získá každý student, který dosáhne ve cvičení nejméně 10 bodů. V oddůvodněných případech může cvičící udělit zápočet i při nesplnění této podmínky. Zkouška probíhá písemnou formou a lze za ni získat maximálně 70 bodů.  Zkouška může probíhat prezenčně nebo distančně. Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu.

 

 

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 informačních a komunikačních technologiích.
Studenti získají potřebné znalosti z diskrétní matematiky a schopnost orientace v souvisejících matematických strukturách.

Základní literatura

Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984. (EN)
Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989. (CS)
Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992. (CS)
Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982. (CS)

Doporučená literatura

Acharya D. P., Sreekumar, Fundamental Approach to Discrete Mathematics, New Age International Publishers, New Delhi, 2005. (EN)
Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001. (EN)
Garnier R.,  Taylor J., Discrete Mathematics for New Technology, Institute of Physics Publishing, Bristol and Philadelphia 2002. (EN)
Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004. (EN)
Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002. (EN)
Chartrand G., Zhang Ping, Discrete Mathematics, Waveland Pr Inc, 2011. (EN)
Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001. (EN)
Lipschutz, S., Lipson, M.L., Theory and Problems of Discrete Mathematics, McGraw-Hill, New York, 1997. (EN)
Lovász L., Pelikán J., Vesztergombi, Discrete Mathematics, Springer-Verlag, New York 2003. (EN)
Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008. (EN)
Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000. (EN)
O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006. (EN)
Rosen, K. H. et al., Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton 2000. (EN)
Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988. (EN)
Ross, S. M. Topics in Finite and Discrete Mathematics, Cambridge University Press, Cambridge 2000. (EN)

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

  • Program BPC-IBE bakalářský 1 ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

doc. RNDr. Martin Kovár, Ph.D.

Osnova

Formální jazyk matematiky. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Kombinatorické vlastnosti množin. Princip inkluze a exkluze. Techniky důkazů a jejich ilustrace.
Binární relace a zobrazení. Skládání relací a zobrazení. Vlastnosti zobrazení. Indexované systémy množin a jejich zobrazení. Abstraktní prostory. Reálné funkce a jejich vlastnosti. Spojitost a nespojitost. Rekurzívně definované funkce.
Další vlastnosti binárních relací. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hasseovské diagramy.
Algebry s jednou a dvěma operacemi a jejich morfismy. Grupy a tělesa. Svaz jako množina se dvěma operacemi. Booleova algebra.
Hlavní vlastnosti a zákony Boolových algeber. Dualita a množinová reprezentace konečných Boolových algeber.
Formule a sémantika výrokového počtu. Interpretace a klasifikace formulí. Boolova algebra neekvivalentních formulí. Syntaxe výrokového počtu. Věta o kompaktnosti. Normální tvary formulí.
Matice a maticové operace. Determinant čtvercové matice. Inverzní a adjungovaná matice. Metody výpočtu determinantu.
Vektorový prostor a jeho podprostory. Báze a dimenze. Vyjádření vektoru v bázi. Transformace souřadnic. Lineární zobrazení vektorových prostorů.
Soustavy lineárních rovnic. Gaussova eliminace. Frobeniova věta. Cramerovo pravidlo.
Skalární a unitární součin. Ortonormální systémy vektorů. Ortogonální průmět vektoru do podprostoru. Vektorový a smíšený součin.
Grafy a jejich různé reprezentace. Sledy, tahy a cesty. Algoritmus nalezení nejkratší cesty. Souvislost grafů.
Podgrafy. Izomorfismus a homeomorfismus grafů. Eulerovské a hamiltonovské grafy. Problém rovinnosti.
Stromy, kostry a jejich vlastnosti. Binární stromy a jejich prohledávání. Tok v orientovaném grafu.

Cvičení s počítačovou podporou

26 hod., povinná

Vyučující / Lektor

doc. RNDr. Martin Kovár, Ph.D.

Osnova

Budou procvičena témata z přednášek ve vhodném rozsahu.