Course detail
Discrete Mathematics
FEKT-BPC-DMAAcad. year: 2024/2025
The sets, relations and mappings. Equivalences and partitions. Posets. The structures with one and two operations. Lattices and Boolean algebras.The propositional calculus in the context of the formulae classes of the predicate calcullus. The normal forms of formulas. Matrices and determinants. Vector spaces. Systems of linear equations.The elementary notions of the graph theory. Connectedness. Subgraphs and morphisms of graphs. Planarity. Trees and their properties. Simple graph algorithms.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Entry knowledge
Rules for evaluation and completion of the course
The content and forms of instruction in the evaluated course are specified by a regulation issued by the lecturer responsible for the course and updated for every academic year.
Aims
The students will obtain the necessary knowledge in discrete mathematics and an ability of orientation in related mathematical structures.
Study aids
Prerequisites and corequisites
Basic literature
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)
Recommended reading
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)
Elearning
Classification of course in study plans
- Programme BPC-IBE Bachelor's 1 year of study, summer semester, compulsory
Type of course unit
Lecture
Teacher / Lecturer
Syllabus
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.
Computer-assisted exercise
Teacher / Lecturer
Syllabus
Elearning