Discrete mathematics

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

The aim of the course is to introduce students to some areas of mathematics outside of the customary continuous mathematics. The common denominator here is a discrete approach, combinatorial thinking and insight into mathematical reasoning and notation. The course will explore notions of cardinality and properties of natural numbers, relations on sets, binomial theorem and combinatorics, mathematical induction and recurrence.

Requirements:

none

Syllabus of lectures:

1. Sets and mappings, cardinality, countable sets.

2. Mathematical induction and recursion.

3. Binary relations on a set, equivalence.

4. Partial ordering, well-ordered sets.

5. Divisibility, (extended) Euclid's algorithm.

6. Congruence, operations modulo on integers.

7. Binary operations and groups.

8. Advanced operations modulo.

9. Combinatorics, principle of inclusion and exclusion.

10. Recurrence equations. Linear homogeneous case.

11. Solving non-homogeneous recurrence equations with constant coefficients.

12. The Master theorem.

13. Back-up class.

Syllabus of tutorials:

1. Sets, combinatorics.

2. Sets, mappings and cardinality with proofs.

3. Proofs by mathematical induction.

4. Properties of binary relations.

5. Posets, proving properties of relations.

6. (Extended) Euclid's algorithm, proving facts on divisibility.

7. Calculations modulo n.

8. Proving facts about relations and operations.

9. Solving equations modulo.

10. Principle of inclusion and exclusion.

11. Solving homogeneous linear recurrence equations.

12. Solving non-homogeneous linear recurrence equations.

13. Back-up class.

Study Objective:

Study materials:

[1] Lecture notes on lecturer's official homepage.

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

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Otevřená informatika - Počítačové systémy (compulsory course in the program)
• Otevřená informatika - Informatika a počítačové vědy (compulsory course in the program)
• Otevřená informatika - Softwarové systémy (compulsory course in the program)
• Otevřená informatika, před rozřazením do oborů (compulsory course in the program)