| AE4B01DMA | Discrete mathematics | Rozsah výuky: | 2+2s | ||
|---|---|---|---|---|---|
| Garant: | Typ předmětu: | P | Zakončení: | Z,ZK | |
| Vyučující: | |||||
| Zodpovědná katedra: | 13101 | Kreditů: | 7 | Semestr: | Z |
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.
Osnovy 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. |
Osnovy 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. |
Literatura:
| [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. |
Požadavky:
none
|
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 19. 5. 2013, semestry: L/2011-2, L/2012-3, L/2010-1, Z/2011-2, Z/2010-1, Z/2013-4, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |