Title:

Discrete Mathematics

Code:IDA
Ac.Year:2017/2018
Term:Winter
Curriculums:
ProgrammeBranchYearDuty
IT-BC-3BIT1stCompulsory
Language:Czech
Credits:7
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:52120410
 ExaminationTestsExercisesLaboratoriesOther
Points:60010030
Guarantee:Kovár Martin, doc. RNDr., Ph.D., DMAT
Lecturer:Hliněná Dana, doc. RNDr., Ph.D., DMAT
Kovár Martin, doc. RNDr., Ph.D., DMAT
Instructor:Demchenko Hanna, Mgr., FEEC
Hliněná Dana, doc. RNDr., Ph.D., DMAT
Kovár Martin, doc. RNDr., Ph.D., DMAT
Rebenda Josef, Mgr., Ph.D., CEITEC
Staněk David, Mgr., FEEC
Svoboda Zdeněk, RNDr., CSc., DMAT
Faculty:Faculty of Electrical Engineering and Communication BUT
Department:Department of Mathematics FEEC BUT
Follow-ups:
Algorithms (IAL), DIFS
Computer Graphics Principles (IZG), DCGM
Formal Languages and Compilers (IFJ), DIFS
Mathematical Analysis (IMA), DMAT
Modelling and Simulation (IMS), DITS
Numerical Methods and Probability (INM), DMAT
Schedule:
DayLessonWeekRoomStartEndLect.Gr.St.G.EndG.
MonlecturelecturesD10508:0009:501BIA
MonlecturelecturesD020708:0009:501BIA
MonlecturelecturesD10508:0009:502BIAxxxx
MonlecturelecturesD10508:0009:502BIBxxxx
Moncomp.lab - Svobodaodd weekT8/52209:0010:501BIB3031
Monexercise - Svobodaeven weekT8/31209:0010:501BIB3031
Moncomp.lab - Svobodaodd weekT8/52209:0010:502BIAxxxx
Moncomp.lab - Svobodaodd weekT8/52209:0010:502BIBxxxx
Monexercise - Svobodaeven weekT8/31209:0010:502BIAxxxx
Monexercise - Svobodaeven weekT8/31209:0010:502BIBxxxx
Monexam - předtermín2017-12-18E11209:0010:501BIA
Monexam - předtermín2017-12-18E11209:0010:501BIB
Monexam - předtermín2017-12-18E11209:0010:502BIA
Monexam - předtermín2017-12-18E11209:0010:502BIB
MonlecturelecturesT12/2.17311:0012:501BIB
MonlecturelecturesT12/2.17311:0012:502BIAxxxx
MonlecturelecturesT12/2.17311:0012:502BIBxxxx
Monexam - předtermín - hodnocení2017-12-18E10411:0015:501BIA
Monexam - předtermín - hodnocení2017-12-18E10411:0015:501BIB
Monexam - předtermín - hodnocení2017-12-18E10411:0015:502BIA
Monexam - předtermín - hodnocení2017-12-18E10411:0015:502BIB
Moncomp.lab - Kovárodd weekT8/50313:0014:501BIB3233
Monexercise - Kováreven weekT8/50313:0014:501BIB3233
Moncomp.lab - Kovárodd weekT8/50313:0014:502BIAxxxx
Moncomp.lab - Kovárodd weekT8/50313:0014:502BIBxxxx
Monexercise - Kováreven weekT8/50313:0014:502BIAxxxx
Monexercise - Kováreven weekT8/50313:0014:502BIBxxxx
TuelecturelecturesD10508:0009:501BIA
TuelecturelecturesD020708:0009:501BIA
TuelecturelecturesD10508:0009:502BIAxxxx
TuelecturelecturesD10508:0009:502BIBxxxx
Tueexam - předtermín2017-12-19E11209:0015:501BIA
Tueexam - předtermín2017-12-19E11209:0015:501BIB
Tueexam - předtermín2017-12-19E11209:0015:502BIA
Tueexam - předtermín2017-12-19E11209:0015:502BIB
TuelecturelecturesT12/2.17311:0012:501BIB
TuelecturelecturesT12/2.17311:0012:502BIAxxxx
TuelecturelecturesT12/2.17311:0012:502BIBxxxx
Tueexam - 2. oprava2018-01-30T8/01011:0013:501BIA
Tueexam - 2. oprava2018-01-30T8/01011:0013:501BIB
Tueexam - 2. oprava2018-01-30T8/01011:0013:502BIA
Tueexam - 2. oprava2018-01-30T8/01011:0013:502BIB
Tueexam - 2. oprava2018-01-30D10511:0013:501BIA
Tueexam - 2. oprava2018-01-30D10511:0013:501BIB
Tueexam - 2. oprava2018-01-30D10511:0013:502BIA
Tueexam - 2. oprava2018-01-30D10511:0013:502BIB
Tuecomp.lab - Hliněnáeven weekT8/50313:0014:501BIA1011
Tuecomp.lab - Svobodaodd weekT8/50313:0014:501BIB3637
Tueexercise - Svobodaeven weekT8/31213:0014:501BIB3637
Tueexerciseodd weekT8/31213:0014:501BIA1011
Tuecomp.lab - Svobodaodd weekT8/50313:0014:502BIAxxxx
Tuecomp.lab - Svobodaodd weekT8/50313:0014:502BIBxxxx
Tueexercise - Svobodaeven weekT8/31213:0014:502BIAxxxx
Tueexercise - Svobodaeven weekT8/31213:0014:502BIBxxxx
Tuecomp.lab - Hliněnáeven weekT8/50313:0014:502BIAxxxx
Tuecomp.lab - Hliněnáeven weekT8/50313:0014:502BIBxxxx
Tueexerciseodd weekT8/31213:0014:502BIAxxxx
Tueexerciseodd weekT8/31213:0014:502BIBxxxx
Tuecomp.lab - Kovárodd weekT8/50315:0016:501BIB3839
Tueexercise - Kováreven weekT8/31215:0016:501BIB3839
Tuecomp.lab - Kovárodd weekT8/50315:0016:502BIAxxxx
Tuecomp.lab - Kovárodd weekT8/50315:0016:502BIBxxxx
Tueexercise - Kováreven weekT8/31215:0016:502BIAxxxx
Tueexercise - Kováreven weekT8/31215:0016:502BIBxxxx
Tueexercise - Kováreven weekT8/31217:0018:501BIB4041
Tuecomp.labodd weekT8/50317:0018:501BIB4041
Tueexercise - Kováreven weekT8/31217:0018:502BIAxxxx
Tueexercise - Kováreven weekT8/31217:0018:502BIBxxxx
Tuecomp.labodd weekT8/50317:0018:502BIAxxxx
Tuecomp.labodd weekT8/50317:0018:502BIBxxxx
Wedexercise - Kovárodd weekT8/31211:0012:501BIB3435
Wedcomp.lab - Kováreven weekT8/52211:0012:501BIB3435
Wedcomp.lab - Staněkodd weekT8/52211:0012:501BIA1213
Wedexercise - Staněkeven weekT8/31211:0012:501BIA1213
Wedcomp.lab - Kováreven weekT8/52211:0012:502BIAxxxx
Wedcomp.lab - Kováreven weekT8/52211:0012:502BIBxxxx
Wedexercise - Kovárodd weekT8/31211:0012:502BIAxxxx
Wedexercise - Kovárodd weekT8/31211:0012:502BIBxxxx
Wedcomp.lab - Staněkodd weekT8/52211:0012:502BIAxxxx
Wedcomp.lab - Staněkodd weekT8/52211:0012:502BIBxxxx
Wedexercise - Staněkeven weekT8/31211:0012:502BIAxxxx
Wedexercise - Staněkeven weekT8/31211:0012:502BIBxxxx
Wedcomp.lab - Staněkodd weekT8/50315:0016:501BIA1415
Wedexercise - Staněkeven weekT8/31215:0016:501BIA1415
Wedcomp.lab - Staněkodd weekT8/50315:0016:502BIAxxxx
Wedcomp.lab - Staněkodd weekT8/50315:0016:502BIBxxxx
Wedexercise - Staněkeven weekT8/31215:0016:502BIAxxxx
Wedexercise - Staněkeven weekT8/31215:0016:502BIBxxxx
Wedexercise - Staněkeven weekT8/50317:0018:501BIA1617
Wedcomp.lab - Staněkodd weekT8/50317:0018:501BIA1617
Wedexercise - Staněkeven weekT8/50317:0018:502BIAxxxx
Wedexercise - Staněkeven weekT8/50317:0018:502BIBxxxx
Wedcomp.lab - Staněkodd weekT8/50317:0018:502BIAxxxx
Wedcomp.lab - Staněkodd weekT8/50317:0018:502BIBxxxx
Thuexam - řádná2018-01-11T8/03009:0011:501BIB
Thuexam - řádná2018-01-11T8/03009:0011:502BIB
Thuexam - řádná2018-01-11T12/2.17309:0011:501BIB
Thuexam - řádná2018-01-11T12/2.17309:0011:502BIB
Thuexam - řádná2018-01-11D10509:0011:501BIA
Thuexam - řádná2018-01-11D10509:0011:502BIA
Thuexam - řádná2018-01-11D020609:0011:501BIA
Thuexam - řádná2018-01-11D020609:0011:502BIA
Thuexam - řádná2018-01-11T8/01009:0011:501BIB
Thuexam - řádná2018-01-11T8/01009:0011:502BIB
Thuexam - řádná2018-01-11E11209:0011:501BIA
Thuexam - řádná2018-01-11E11209:0011:502BIA
Fricomp.lab - Hliněnáodd weekT8/50309:0010:501BIA1819
Friexercise - Hliněnáeven weekT8/31209:0010:501BIA1819
Fricomp.lab - Hliněnáodd weekT8/50309:0010:502BIAxxxx
Fricomp.lab - Hliněnáodd weekT8/50309:0010:502BIBxxxx
Friexercise - Hliněnáeven weekT8/31209:0010:502BIAxxxx
Friexercise - Hliněnáeven weekT8/31209:0010:502BIBxxxx
Fricomp.lab - Hliněnáodd weekT8/50311:0012:501BIA2021
Friexercise - Hliněnáeven weekT8/31211:0012:501BIA2021
Fricomp.lab - Hliněnáodd weekT8/50311:0012:502BIAxxxx
Fricomp.lab - Hliněnáodd weekT8/50311:0012:502BIBxxxx
Friexercise - Hliněnáeven weekT8/31211:0012:502BIAxxxx
Friexercise - Hliněnáeven weekT8/31211:0012:502BIBxxxx
Friexam - 1. oprava2018-01-19D10511:0013:501BIA
Friexam - 1. oprava2018-01-19D10511:0013:502BIA
Friexam - 1. oprava2018-01-19D020611:0013:501BIA
Friexam - 1. oprava2018-01-19D020611:0013:502BIA
Friexam - 1. oprava2018-01-19T8/01011:0013:501BIB
Friexam - 1. oprava2018-01-19T8/01011:0013:502BIB
Friexam - 1. oprava2018-01-19T8/03011:0013:501BIB
Friexam - 1. oprava2018-01-19T8/03011:0013:502BIB
 
Learning objectives:
  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 computer science.
Description:
  The sets, relations and mappings. Equivalences and partitions. Posets. The structures with one and two operations. Lattices and Boolean algebras.The propositional calculus. 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.
Knowledge and skills required for the course:
  Secondary school mathematics.
Learning outcomes and competences:
  The students will obtain the basic orientation in discrete mathematics and linear algebra, and an ability of orientation in related mathematical structures.
Syllabus of lectures:
 
  1. The formal language of mathematics. A set intuitively. Basic set operations. The power set. Cardinality. The set of numbers. Combinatoric properties of sets. The principle of inclusion and exclusion. Proof techniques and their illustrations.
  2. Binary relations and mappings. The composition of a binary relation and mapping. Abstract spaces and their mappings. Real functions and their basic properties. Continuity and discontinuity. The functions defined by recursion.
  3. More advanced properties of binary relations. Reflective, symmetric and transitive closure. Equivalences and partitions. The partially ordered sets and lattices. The Hasse diagrams.
  4. Algebras with one and two operations. Morphisms. Groups and fields. The lattice as a set with two binary operations. Boolean algebras.
  5. The basic properties of Boolean algebras. The duality and the set representation of a finite Boolean algebra.
  6. Predicates, formulas and the semantics of the propositional calculus. Interpretation  and  classification of formulas. The structure of the algebra of non-equivalent formulas. The syntaxis of the propositional calculus. Prenex normal forms of formulas. 
  7. Matrices and matrix operations. Determinant. Inverse and adjoint matrices. Determinant calculation methods.
  8. The vector space. Subspaces. The basis and the dimension. The coordinates of a vector. The transformation of the coordinates and the change of the basis. Linear mappings of vector spaces.
  9. Systems of linear equations. The Gauss and Gauss-Jordan elimination. The Frobenius theorem. The Cramer's Rule.
  10. The inner product. Orthonormal systems of vectors.  The orthogonal projection on a vector subspace. The cross product and the triple product.
  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.
Syllabus of numerical exercises:
 
  1. Practising and modelling of selected items of lectures.
Syllabus of computer exercises:
 Practising and modelling of selected items of lectures 8, 9 and 10.
Syllabus - others, projects and individual work of students:
 Five individual home-tasks/works - an instructor will inform.
Fundamental literature:
 
  • Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
  • Acharjya D. P., Sreekumar, Fundamental Approach to Discrete Mathematics, New Age International Publishers, New Delhi, 2005.
  • Faure R., Heurgon E., Uspořádání a Booloeovy algebry, Academia, Praha 1984 (in Czech).
  • Gantmacher, F. R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
  • Garnier R.,  Taylor J., Discrete Mathematics for New Technology, Institute of Physics Publishing, Bristol and Philadelphia 2002.
  • Gratzer G., General Lattice Theory, Birkhauser Verlag, Berlin 2003.
  • Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
  • Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
  • Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984. 
  • Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989 (in Czech).
  • Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992 (in Slovak).
  • Kolman B., Elementary Linear Algebra, Macmillan Publ. Comp., New York 1986.
  • Kolman B., Introductory Linear Algebra, Macmillan Publ. Comp., New York 1993.
  • 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.
  • Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983 (in Czech).
  • Lipschutz, S., Lipson, M.L.,  Theory and Problems of Discrete Mathematics, McGraw-Hill, New York, 1997.
  • Lovász L., Pelikán J., Vesztergombi, Discrete Mathematics, Springer-Verlag, New York 2003.
  • Mannucci M. A., Yanofsky N. S., Quantum Computing For Computer Scientists, Cambridge University Press, Cambridge 2008.
  • Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000 (in Czech).
  • Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
  • Nahara M., Ohmi T., Qauntum Computing: From Linear Algebra to Physical Realizations, CRC Press, Boca Raton 2008.
  • O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006.
  • Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982 (in Slovak).
  • Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
  • Rosen, K. H. et al., Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton 2000.
  • Ross, S. M. Topics in Finite and Discrete Mathematics, Cambridge University Press, Cambridge 2000.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001 (in Czech).
  • Švejdar, V., Logika, neúplnost, složitost a nutnost, Academia, Praha 2002 (in Czech).
  • Vickers S., Topology via Logic, Cambridge University Press, Cambridge 1990.
Study literature:
 
  • Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
  • Kolman B., Introductory Linear Algebra, Macmillan Publ. Comp., New York 1993.
  • Lipschutz, S., Lipson, M.L.,  Theory and Problems of Discrete Mathematics, McGraw-Hill, New York, 1997.
  • Lipschutz, S., Lipson, M.L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992.
  • 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.
  • Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
Controlled instruction:
  Pass out the practices.
Progress assessment:
  Pass out the practices in the prescribed range.