Title:

Discrete Mathematics

Code:IDM
Ac.Year:2019/2020
Sem:Winter
Curriculums:
ProgrammeField/
Specialization
YearDuty
BIT-1stCompulsory
IT-BC-3BIT1stCompulsory
Language of Instruction:Czech
Credits:5
Completion:credit+exam (written)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:2626000
 ExamsTestsExercisesLaboratoriesOther
Points:60300010
Guarantor:Hliněná Dana, doc. RNDr., Ph.D. (DMAT)
Deputy guarantor:Holík Lukáš, Mgr., Ph.D. (DITS)
Lecturer:Fuchs Petr, RNDr., Ph.D. (DMAT)
Hliněná Dana, doc. RNDr., Ph.D. (DMAT)
Holík Lukáš, Mgr., Ph.D. (DITS)
Lengál Ondřej, Ing., Ph.D. (DITS)
Instructor:Čejka Rudolf, Ing. (CC)
Fuchs Petr, RNDr., Ph.D. (DMAT)
Havlena Vojtěch, Ing. (DITS)
Hliněná Dana, doc. RNDr., Ph.D. (DMAT)
Holík Lukáš, Mgr., Ph.D. (DITS)
Lengál Ondřej, Ing., Ph.D. (DITS)
Vážanová Gabriela V., Mgr. (FEEC)
Faculty:Faculty of Electrical Engineering and Communication BUT
Department:Department of Mathematics FEEC BUT
Substitute for:
Discrete Mathematics (IDA), DMAT
Schedule:
DayLessonWeekRoomStartEndLect.Gr.Groups
Moncomp.lab - HliněnálecturesD0207 08:0009:501BIB 2BIA 2BIB xx
Moncomp.lab - HolíklecturesD0207 14:0015:501BIB 2BIA 2BIB xx
Moncomp.lab - HolíklecturesD0207 16:0017:501BIB 2BIA 2BIB xx
Moncomp.lab - HolíklecturesA113 18:0019:501BIB 2BIA 2BIB xx
Tuelecture - HliněnálecturesD0206 D105 08:0009:501BIB 2BIA 2BIB xx
Tuecomp.lab - HavlenalecturesA113 08:0009:501BIA 2BIA 2BIB xx
Tuecomp.lab - FuchslecturesT8/322 11:0012:501BIB 2BIA 2BIB xx
Tuelecture - HliněnálecturesD0206 D105 13:0014:501BIA 2BIA 2BIB xx
Tuecomp.lab - LengállecturesD0207 16:0017:502BIA 2BIB xx
Wedcomp.lab - VážanoválecturesT8/503 07:0008:501BIA 2BIA 2BIB xx
Wedcomp.lab - FuchslecturesT8/522 13:0014:501BIB 2BIA 2BIB xx
Wedcomp.lab - HliněnálecturesA113 16:0017:501BIA 2BIA 2BIB xx
Thucomp.lab - FuchslecturesT8/522 13:0014:501BIA 2BIA 2BIB xx
Thucomp.lab - LengállecturesA113 18:0019:501BIA 2BIA 2BIB xx
Fricomp.lab - VážanoválecturesT8/522 07:0008:501BIA 2BIA 2BIB xx
Fricomp.lab - HavlenalecturesD0207 14:0015:501BIB 2BIA 2BIB xx
Friexam - 1. písemka2019-10-18D0206 D105 E104 E105 E112 17:0020:501BIA 1BIB 2BIA 2BIB
Friexam - 2. písemka2019-11-29D0206 D105 E104 E105 E112 17:0020:501BIA 1BIB 2BIA 2BIB
 
Learning objectives:
  This course provides basic knowledge of mathematics necessary for a number of following courses. The students will learn elementary knowledge of algebra and discrete mathematics, with an emphasis on mathematical structures that are needed for later applications in computer science.
Description:
  Sets, relations, and mappings. Equivalences and partitions. Posets. Structures with one and two operations. Lattices and Boolean algebras. Propositional and predicate calculus. Elementary notions of graph theory. Connectedness. Subgraphs and morphisms of graphs. Planarity. Trees and their properties. Basic graph algorithms. Network flows.


Knowledge and skills required for the course:
  Secondary school mathematics.
Learning outcomes and competencies:
  The students will acquire basic knowledge of discrete mathematics  and the ability to understand the logical structure of a mathematical text. They will be able to explain mathematical structures and to formulate their own mathematical claims and their proofs.
Why is the course taught:
  Mathematics stood at the birth of computer science and since then has always been in the core of almost all of its progress.

Discrete mathematics aims at understanding the aspects of the real world that are the most fundamental from the point of view of computer science.
It studies such concepts as a set (e.g. a collection of data, resources, agents), 
relations and graphs (e.g. relationships among data or description of a communication),
and operations over elements of a set (especially basic arithmetical operations and their generalization).
The mathematical logic then gives means of expressing ideas and reasoning clearly and correctly and is, moreover, the foundation of "thinking of computers".

Generally speaking, discrete mathematics teaches the art of abstraction -- how to apprehend the important aspects of a problem and work with them.
It provides a common language for talking about those aspects precisely and effectively. Besides communication of ideas, it helps to structure thought into exactly defined notions and relationships, which is necessary when designing systems so large and complex as today's software and hardware.

For example, discrete math gives the basic tools for expressing what a program does; what its data structures represent; how the amount of needed resources depends on the size of the input; how to specify and argue that a program does what it should do. Similarly essential uses can be found everywhere in computer science. One could say that a programmer without mathematics is similar to a piano player who cannot read notes: if he is talented, he can still succeed, but his options are limited, especially when it comes to solving complex problems. 

In order to teach mathematical thinking to students, we emphasize practising mathematics by using it to solve problems -- in the same way as programming can be only learnt through programming, mathematics also can be learnt only by doing it.


Syllabus of lectures:
 
  1. The formal language of mathematics. A set intuitively. Basic set operations. Power set. Cardinality. Sets of numbers. Combinatoric properties of sets. The principle of inclusion and exclusion.
  2. Binary relations and mappings. The composition of binary relations and mappings. Reflective, symmetric, and transitive closure. Equivalences and partitions. Partially ordered sets and lattices. Hasse diagrams.
  3. Sequences and recursive formulas.
  4. Basic concepts of graph theory.  Graph Isomorphism. Trees and their properties. Trails, tours, and Eulerian graphs.
  5. Finding the shortest path. Dijkstra's algorithm. Minimum spanning tree problem. Kruskal's and Jarnik's algorithms. Planar graphs.
  6. Directed graphs, network flows, finding maximum flow, applications.
  7. Propositional logic, its syntax and semantics.
  8. Predicate logic, its syntax and semantics.
  9. Demonstration of usage and utility of propositional and predicate logic in proofs. Proof techniques and their illustrations.
  10. Binary operations and their properties.
  11. General algebras and algebras with one operation. Groups as algebras with one operation. Congruences and morphisms.
  12. General algebras and algebras with two operations. Lattices as algebras with two operations.
  13. Boolean algebras.
Syllabus of numerical exercises:
 Examples at tutorials are chosen to suitably complement the lectures.
Fundamental literature:
 
  • Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
  • Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
  • Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
  • Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992. (in Slovak).
  • 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.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007. (in Czech).
  • 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.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001. (in Czech).
Study literature:
 
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007. (in Czech).
  • Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
  • Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010. (in Czech).
  • Kovár, M., Diskrétní matematika, FEKT VUT, Brno, 2013. (in Czech).
Controlled instruction:
  
  • The knowledge of students is tested at exercises; including two homework assignments worth for 5 points each, at two midterm exams for 15 points each, and at the final exam for 60 points.
  • If a student can substantiate serious reasons for an absence from an exercise, (s)he can either attend the exercise with a different group (please inform the teacher about that). 
  • Passing boundary for ECTS assessment: 50 points.
Progress assessment:
  
  • Evaluation of the two home assignments solved in the groups (max 10 points).
  • Evaluation of the two mid-term exams (max 30 points).
Exam prerequisites:
  The minimal total score of 10 points gained out of  the mid-term exams. Plagiarism and not allowed cooperation will cause that involved students are not classified and disciplinary action may be initiated.
 

Your IPv4 address: 54.161.118.57