Discrete mathematics

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

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.

Požadavky:

none

Osnova přednášek:

1. Sets and their cardinality, countable and uncountable sets.

2. Integers, primes, Euclid's algorithm.

3. Binary operations and their properties.

4. Binary relations on a set, equivalence.

5. Modulo n relation on the set of integers.

6. Partial ordering.

7. Matrix of relation, relation database.

8. Binomial theorem and its applications, properties of combinatorial numbers.

9. Estimating binomial coefficients, principle of inclusion and exclusion.

10. Matematical induction and its applications.

11. Matematical induction as a tool for solving recurrence relations.

12. Evaluating time complexity of recursive algorithms, solving homogeneous recurrence equations with constant coefficients.

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

14. Back-up class.

Osnova cvičení:

1. Bijections, countable sets.

2. Properties of numbers.

3. Properties of binary operations.

4. Counting modulo n.

5. Properties of binary relations.

6. Equivalence and partial ordering.

7. Relation matrix, relation database.

8. Combinatorics, binomial theorem.

9. Combinatorics.

10. Proofs by mathematical induction.

11. Matematical induction and recurrence.

12. Complexity of algorithms. solving homogeneous recurrence equations.

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

14. Back-up class.

Cíle studia:

Studijní materiály:

[1] M. Demlová: Mathematical Logic. ČVUT Praha, 1999.

[2] R. Johnsonbauch: Discrete Mathematics, 4th edition, 1997,

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

[4] Lecturer's official homepage.

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6s

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Open Informatics - Computer Systems (povinný předmět programu)
• Open Informatics - Computer and Information Science (povinný předmět programu)
• Open Informatics - Software Systems (povinný předmět programu)
• Open Informatics (povinný předmět programu)