Faculty of Information Technology, BUT

Course details

Discrete Mathematics

IDA Acad. year 2018/2019 Winter semester 7 credits

The sets, relations and mappings. Equivalences and partitions. Posets. The structures with one and two operations. Lattices and Boolean algebras.The propositional and predicate calculus. Matrices and determinants. Systems of linear equations. Vector spaces and subspaces. Quadratic forms and conic sections. The elementary notions of the graph theory. Connectedness. Subgraphs and morphisms of graphs. Planarity. Trees and their properties. Simple graph algorithms.

Guarantor

Language of instruction

Czech

Completion

Examination (written)

Time span

52 hrs lectures, 20 hrs exercises, 6 hrs projects

Assessment points

60 exam, 25 half-term test, 15 projects

Department

Lecturer

Instructor

Čejka Rudolf, Ing. (CC FIT BUT)
Demchenko Hanna, Mgr. (FEEC BUT)
Hliněná Dana, doc. RNDr., Ph.D. (DMAT FEEC BUT)
Kovár Martin, doc. RNDr., Ph.D. (DMAT FEEC BUT)
Rebenda Josef, Mgr., Ph.D. (CEITEC BUT)
Staněk David, Mgr. (FEEC BUT)
Svoboda Zdeněk, RNDr., CSc. (DMAT FEEC BUT)
Vážanová Gabriela V., Mgr. (FEEC BUT)

Subject specific 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.

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.

Prerequisite kwnowledge and skills

Secondary school mathematics.

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.

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.

Syllabus of lectures

  1. The formal language of mathematics. A set intuitively. Basic set operations. The power set. Cardinality. The sets 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 binary relations and mappings. Reflective, symmetric and transitive closure. Equivalences and partitions. The partially ordered sets and lattices. The Hasse diagrams.
  3. General algebras and algebras with one and two operations. Lattices as algebras with two operations. Boolean algebras.
  4. Propositional logic, its syntaxis and semantics. The formal system of the proposional calculus. The completeness of propositional logic.
  5. Predicate logic, its syntaxis and semantics. The formal system of the first-order predicate logic. The problem of completeness in predicate logic.
  6. Demonstration of usage and utility of propositional and predicate logic in proofs.
  7. Matrices and matrix operations. Systems of linear equations. Gaussian elimination. Determinant. Inverse and adjoint matrices. The Cramer's Rule.
  8. The vector space and its subspaces. The basis and the dimension. The coordinates of a vector relative to a given basis. The transformation of the coordinates and the change of the basis. The sum and intersection of vector spaces. Linear mappings of vector spaces.
  9. The inner product. Orthonormal systems of vectors. Orthogonal projection and approximation. The eigenvalues and eigenvectors. The orthogonal projections onto eigenspaces.
  10. Quadratic forms and conic sections.
  11. The elementary notions of the graph theory. Various representations of a graph.The Dijkstra 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

  • Practising and modelling of selected items of lectures.

Syllabus - others, projects and individual work of students

Three individual, structured home-tasks (works) - an instructor will inform.

Progress assessment

Pass out the practices in the prescribed range.

Controlled instruction

Pass out the practices.

Schedule

DayTypeWeeksRoomStartEndLect.grpGroupsInfo
Monlecturelectures T12/2.173 11:0012:50 1BIB Kovár
Monlecturelectures D0207 D105 11:0012:50 1BIA 2BIA 2BIB xx Hliněná
Monlecturelectures T12/2.173 11:0012:50 2BIA xx Kovár
Monlecturelectures D105 11:0012:50 1BIA Hliněná
Monlecturelectures T12/2.173 11:0012:50 2BIB xx Kovár
Monexam2019-01-21 T12/2.173 12:0013:50 1BIB 1. oprava - Kovár
Monexam2019-01-21 D105 12:0013:50 1BIA 2BIA 1. oprava - Hliněná
Monexam2019-01-21 T12/2.173 12:0013:50 2BIB 1. oprava - Kovár
Monexerciselectures T8/312 13:0014:50 1BIB 2BIA 2BIB xx 30 - 31 Kovár
Tueexerciselectures T8/312 09:0010:50 1BIB 2BIA 2BIB xx 40 - 41 Staněk
Tuelecturelectures T12/2.173 11:0012:50 1BIB 2BIA xx Kovár
Tuelecturelectures D105 11:0012:50 1BIA Hliněná
Tuelecturelectures T12/2.173 11:0012:50 2BIB xx Kovár
Tuelecturelectures D0207 D105 11:0012:50 1BIA 2BIA 2BIB xx Hliněná
Tueexerciselectures T8/312 15:0016:50 1BIB 2BIA 2BIB xx 32 - 33 Kovár
Tueexerciselectures T8/312 17:0018:50 1BIB 2BIA 2BIB xx 34 - 35 Kovár
Wedexerciselectures A218 08:0009:50 2BIA 2BIB xx ostatní aktivity, Hliněná Konzul
Wedexam2018-12-19 D105 09:0015:50 1BIA 2BIA předtermín
Wedexam2019-01-30 D105 12:0014:50 1BIA 2BIA 2. oprava Doc. Hliněná
Wedexam2019-01-30 T8/030 12:0013:50 1BIB 2BIB 2. oprava Doc. Kovár
Wedexerciselectures A113 12:0013:50 1BIA 2BIA 2BIB xx 14 - 15 Hliněná
Wedother2019-01-30 A113 14:0017:50hodnocení 2. opravy,doc. Hliněná
Wedexerciselectures T8/312 15:0016:50 1BIA 2BIA 2BIB xx 10 - 11 Vážanová
Wedexerciselectures T8/312 17:0018:50 1BIA 2BIA 2BIB xx 12 - 13 Vážanová
Thuexerciselectures A113 09:0010:50 1BIA 2BIA 2BIB xx 16 - 17 Hliněná
Thuexerciselectures A113 12:0013:50 1BIA 2BIA 2BIB xx 18 - 19 Hliněná
Thuexerciselectures A113 14:0015:50 1BIA 2BIA 2BIB xx 20 - 21 Hliněná
Thuexerciselectures T8/312 15:0016:50 1BIB 2BIA 2BIB xx 36 - 37 Kovár
Thuexerciselectures T8/312 17:0018:50 1BIB 2BIA 2BIB xx 38 - 39 Kovár
Friexam2019-01-11 E112 09:0010:50 1BIA řádná - Hli. st 12:00,Váž. st 17
Friexam2019-01-11 T8/030 09:0010:50 1BIB řádná - cv. po a čt Kovár
Friexam2019-01-11 D0206 09:0010:50 1BIA řádná - Vážanová, st., 15:00
Friexam2019-01-11 D105 09:0010:50 2BIA řádná - Hliněná čt. všechny sk.
Friexam2019-01-11 T10/1.36 09:0010:50 1BIB 2BIB řádná - cv. v úterý
Friexam2019-01-11 D105 09:0010:50 1BIA řádná - Hliněná čt. všechny sk.

Course inclusion in study plans

  • Programme IT-BC-3, field BIT, 1st year of study, Compulsory
Back to top