Discrete Mathematics

Course guarantor:

Petr Habala

Lecturer:

Petr Habala

Tutor:

Petr Habala

Supervisor:

Department of Mathematics

Synopsis:

In this course students meet some important topics from the field of discrete mathematics. Namely, they will explore divisibility and calculations modulo n, diophantine equations, binary relations, mappings, cardinality of sets, induction, and recurrence equations. The second aim of this course is to teach students the language of mathematics, both passively and actively, and introduce them to mathematics as science.

Requirements:

High-school mathematics and ability to think.

Syllabus of lectures:

1. Divisibility, Euclid's algorithm.

2. Calculations modulo n, the set Zn of integers modulo n.

3. Diophantine equations, congruence equations and systems.

4. Binary relations and their basic properties.

5. Special relations: partial ordering and equivalence.

6. Mappings. Cardinality of sets, countable and uncountable sets.

7. Matematical induction and its applications.

8. Sequences and sums, asymptotic gowth.

9. Linear recurrence equations.

10. Computatinal complexity of algorithms, the Master theorem.

11. The inclustion and exclusion principle.

Syllabus of tutorials:

1. Divisibility, Euclid's algorithm.

2. Calculations modulo n, the set Zn of integers modulo n.

3. Diophantine equations, congruence equations and systems.

4. Binary relations and their basic properties.

5. Special relations: partial ordering and equivalence.

6. Mappings. Cardinality of sets, countable and uncountable sets.

7. Matematical induction and its applications.

8. Sequences and sums, asymptotic gowth.

9. Linear recurrence equations.

10. Computatinal complexity of algorithms, the Master theorem.

11. The inclustion and exclusion principle.

Study Objective:

Study materials:

[1] K.H.Rosen: Discrete matematics and its aplications, McGraw-Hill, 1998.

Note:

Further information:

https://math.fel.cvut.cz/cz/lide/habala/teaching/dma.html

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon	roomT2:C3-51 Habala P. 09:15–10:45 (lecture parallel1 parallel nr.104) Dejvice T2:C3-51roomT2:C3-51 Habala P. 14:30–16:00 (lecture parallel1 parallel nr.101) Dejvice T2:C3-51roomT2:C3-51 Habala P. 16:15–17:45 (lecture parallel1 parallel nr.102) Dejvice T2:C3-51 roomT2:C3-51 Habala P. 09:15–10:45 (lecture parallel1 parallel nr.107) Dejvice T2:C3-51roomT2:C3-51 Habala P. 11:00–12:30 (lecture parallel1 parallel nr.103) Dejvice T2:C3-51roomT2:C3-51 Habala P. 14:30–16:00 (lecture parallel1 parallel nr.105) Dejvice T2:C3-51roomT2:C3-51 Habala P. 16:15–17:45 (lecture parallel1 parallel nr.108) Dejvice T2:C3-51 roomT2:C3-51 Habala P. 11:00–12:30 (lecture parallel1 parallel nr.106) Dejvice T2:C3-51roomT2:C4-157 Habala P. 12:45–14:15 (lecture parallel1 parallel nr.109) Dejvice Cvičebna / studovna room 12:45–14:15 (lecture parallel1 parallel nr.110)
Tue	roomKN:E-107 Habala P. 11:00–12:30 (lecture parallel1) Karlovo nám. Zengerova posluchárna K1room 12:45–14:15 (lecture parallel1 parallel nr.111)
Wed
Thu
Fri

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Open Informatics - Computer Science 2016 (compulsory course in the program)
• Open Informatics - Internet of Things 2016 (compulsory course in the program)
• Open Informatics - Software 2016 (compulsory course in the program)
• Open Informatics - Computer Games and Graphics 2016 (compulsory course in the program)
• Open Informatics (compulsory course in the program)
• Open Informatics (compulsory course in the program)
• Open Informatics - Artificial Intelligence and Computer Science 2018 (compulsory course in the program)
• Open Informatics - Internet of Things 2018 (compulsory course in the program)
• Open Informatics - Software 2018 (compulsory course in the program)
• Open Informatics - Computer Games and Graphics 2018 (compulsory course in the program)