Title:

Discrete Mathematics

Code:IDA
Ac.Year:2018/2019
Sem:Winter
Curriculums:
ProgrammeFieldYearDuty
IT-BC-3BIT1stCompulsory
Language of Instruction:Czech
Credits:7
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:5220006
 ExamsTestsExercisesLaboratoriesOther
Points:60250015
Guarantor: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:Čejka Rudolf, Ing. (CC)
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)
Vážanová Gabriela V., Mgr. (FEEC)
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.Groups
Monlecture - KovárlecturesT12/2.173 11:0012:501BIB 2BIA 2BIB xx
Monlecture - HliněnálecturesD0207 D105 11:0012:501BIA 2BIA 2BIB xx
Monexam - 1. oprava2019-01-21D0206 D0207 D105 T8/010 12:0013:501BIA 1BIB 2BIA 2BIB
Monexercise - KovárlecturesT8/312 13:0014:501BIB 2BIA 2BIB xx 30 - 31
Tueexercise - StaněklecturesT8/312 09:0010:501BIB 2BIA 2BIB xx 40 - 41
Tuelecture - KovárlecturesT12/2.173 11:0012:502BIA 2BIB xx
Tuelecture - HliněnálecturesD0207 11:0012:502BIB xx
Tuelecture - KovárlecturesT12/2.173 11:0012:501BIB
Tuelecture - HliněnálecturesD0207 D105 11:0012:501BIA 2BIA 2BIB xx
Tueexercise - KovárlecturesT8/312 15:0016:501BIB 2BIA 2BIB xx 32 - 33
Tueexercise - KovárlecturesT8/312 17:0018:501BIB 2BIA 2BIB xx 34 - 35
Wedexercise - ostatní aktivity, Hliněná KonzullecturesA218 08:0009:502BIA 2BIB xx
Wedexam - předtermín2018-12-19D105 09:0015:501BIA 2BIA
Wedexercise - HliněnálecturesA113 12:0013:501BIA 2BIA 2BIB xx 14 - 15
Wedexam - 2. oprava2019-01-30D105 T8/010 12:0013:501BIA 1BIB 2BIA 2BIB
Wedexercise - VážanoválecturesT8/312 15:0016:501BIA 2BIA 2BIB xx 10 - 11
Wedexercise - VážanoválecturesT8/312 17:0018:501BIA 2BIA 2BIB xx 12 - 13
Thuexercise - HliněnálecturesA113 09:0010:501BIA 2BIA 2BIB xx 16 - 17
Thuexercise - HliněnálecturesA113 12:0013:501BIA 2BIA 2BIB xx 18 - 19
Thuexercise - HliněnálecturesA113 14:0015:501BIA 2BIA 2BIB xx 20 - 21
Thuexercise - KovárlecturesT8/312 15:0016:501BIB 2BIA 2BIB xx 36 - 37
Thuexercise - KovárlecturesT8/312 17:0018:501BIB 2BIA 2BIB xx 38 - 39
Friexam - řádná2019-01-11D0206 D0207 D105 E112 T12/2.173 09:0010:501BIA 1BIB 2BIA 2BIB
 
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 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.
Knowledge and skills required for the course:
  Secondary school mathematics.
Learning outcomes and competencies:
  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 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.
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.
 

Your IPv4 address: 54.82.10.219
Switch to IPv6 connection

DNSSEC [dnssec]