| Area of Mathematics: | Computational and Applied Mathematics (ECAM) | ||
| Semester: | 3 | ||
| Course ID: | 32401 | ||
| Course Type: | Elective | ||
| Teaching hours per week: | Theory: 4 | Practice: 0 | Laboratory: 0 |
| ECTS : | 5 | ||
| Eclass: | For the course material, click here. | ||
| Instructors: | Aretaki Aikaterini | ||
Description
- Natural numbers (mathematical induction, recursive sequences, divisibility). Set theory, mappings and membership relations.
- Counting: The basics of counting, permutations and combinations.
- Inclusion-exclusion principle and applications
- Extremal combinatorics: the pigeonhole principle, set partitions, chains and antichains in partial orderings, Sperner’s Theorem.
- Graph theory: Introduction to graphs, graph terminology, representing graphs and graph isomorphism, connectivity, trees, Cayley-Sylvester’s Theorem, graph coloring and matching. Bipartite graphs, Hall’s Theorem, chromatic polynomial, Euler and Hamilton paths, planar graphs.
- Ordinary and exponential generating functions.
- Elements of discrete probability theory and computational geometry (triangulating a polygon, the Art Gallery and Pick’s Theorem, Sperner’s Lemma).
Bibliography
- Rosen K.H., Discrete Mathematics and its Applications (6th Edition), McGraw-Hill, Inc., New York, 2007
- Liu C. L, Elements of Discrete Mathematics, McGraw-Hill Inc., 1985.
- Bondy J.A., Murty U.S.R., Graph Theory, Springer, 2008.
