Course detail
Discrete Mathematics
FEKT-TDMAAcad. year: 2018/2019
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
Czech
Number of ECTS credits
6
Mode of study
Not applicable.
Guarantor
Department
Learning outcomes of the course unit
The students will obtain the necessary knowledge in discrete mathematics and an ability of orientation in related mathematical structures.
Prerequisites
The knowledge of the content of the subject BMA1 Matematika 1 is required. The previous attendance to the subject BMAS Matematický seminář is warmly recommended.
Co-requisites
Not applicable.
Planned learning activities and teaching methods
Teaching methods depend on the type of course unit as specified in the article 7 of BUT Rules for Studies and Examinations.
Assesment methods and criteria linked to learning outcomes
Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.
Course curriculum
1. The formal language of mathematics. A set intuitively. Basic set operations. The power set. Cardinality. The set of numbers.
2. Combinatoric properties of sets. The principle of inclusion and exclusion. Proof techniques and their illustrations.
3. Binary relations and mappings. The composition of a binary relation and mapping.
4. Abstract spaces and their mappings. Continuity and discontinuity.
5. Real functions and their basic properties. The functions defined by recursion.
6. More advanced properties of binary relations. Reflective, symmetric and transitive closure. Equivalences and partitions.
7. The partially ordered sets and lattices. The Hasse diagrams.
8. Algebras with one and two operations. Morphisms. Groups and fields. The lattice as a set with two binary operations. Boolean algebras.
9. The basic properties of Boolean algebras. The duality and the set representation of a finite Boolean algebra.
10. Formulae classes of the propositional and predicate calculus. Interpretation and classification of formulas. The structure of the algebra of non-equivalent formulas. The syntaxis. Prenex normal forms of formulas.
11. The elementary notions of the graph theory. Various representations of a graph.The Shortest path algorithm. The connectivity of graphs.
12. The subgraphs. The isomorphism and the homeomorphism of graphs. Eulerian and Hamiltonian graphs. Planar and non-planar graphs.
13. The trees and the spanning trees and their properties. The searching of the binary tree. Selected searching algorithms. Flow in an oriented graph.
2. Combinatoric properties of sets. The principle of inclusion and exclusion. Proof techniques and their illustrations.
3. Binary relations and mappings. The composition of a binary relation and mapping.
4. Abstract spaces and their mappings. Continuity and discontinuity.
5. Real functions and their basic properties. The functions defined by recursion.
6. More advanced properties of binary relations. Reflective, symmetric and transitive closure. Equivalences and partitions.
7. The partially ordered sets and lattices. The Hasse diagrams.
8. Algebras with one and two operations. Morphisms. Groups and fields. The lattice as a set with two binary operations. Boolean algebras.
9. The basic properties of Boolean algebras. The duality and the set representation of a finite Boolean algebra.
10. Formulae classes of the propositional and predicate calculus. Interpretation and classification of formulas. The structure of the algebra of non-equivalent formulas. The syntaxis. Prenex normal forms of formulas.
11. The elementary notions of the graph theory. Various representations of a graph.The Shortest path algorithm. The connectivity of graphs.
12. The subgraphs. The isomorphism and the homeomorphism of graphs. Eulerian and Hamiltonian graphs. Planar and non-planar graphs.
13. The trees and the spanning trees and their properties. The searching of the binary tree. Selected searching algorithms. Flow in an oriented graph.
Work placements
Not applicable.
Aims
The modern conception of the subject yields a fundamental mathematical knowledge which is necessary for a number of related courses. The student will be acquainted with basic facts and knowledge from the set theory, topology and especially the discrete mathematics with focus on the mathematical structures applicable in information and communication technologies.
Specification of controlled education, way of implementation and compensation for absences
Pass out the practices.
Recommended optional programme components
Not applicable.
Prerequisites and corequisites
Not applicable.
Basic literature
Acharjya 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)
Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004. (EN)
Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984. (EN)
Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001. (EN)
Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004. (EN)
Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984. (EN)
Recommended reading
Garnier R., Taylor J., Discrete Mathematics for New Technology, Institute of Physics Publishing, Bristol and Philadelphia 2002. (EN)
Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002. (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. (SK)
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., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000. (CS)
O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006. (EN)
Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982. (SK)
Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988. (EN)
Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002. (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. (SK)
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., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000. (CS)
O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006. (EN)
Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982. (SK)
Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988. (EN)
Classification of course in study plans
Type of course unit
Lecture
26 hod., optionally
Teacher / Lecturer
Syllabus
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.
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.
Fundamentals seminar
26 hod., compulsory
Teacher / Lecturer
Syllabus
Budou procvičena témata z přednášek ve vhodném rozsahu.