This course is designed to introduce students to the techniques, algorithms, and reasoning processes involved in the study of discrete mathematical structures. Students will be introduced to set theory, deductive and inductive reasoning, elementary counting techniques, ordering, functional and equivalence relations, graphs, and trees. The aim is to give them knowledge and skills that would enable to use the basic methods of discrete mathematics in subsequent courses, in the design and analysis of algorithms, computability theory, software engineering, and computer systems.
Topics to be covered
- Elementary set theory (basic definitions and set operations, the power set and Cartesian products);
- Basic connectives in propositional logic and their properties with emphasis on some of the methods of proving mathematical results;
- Quantifiers in predicate logic and in infinitely large domain sets;
- Mathematical induction;
- Binary relations and, in particular, the equivalence relation; partial order relations;
- Basic counting techniques, combinations, permutations;
- Binomial coefficients, Pascal’s triangle;
- Graphs, vertices, edges, paths, cycles;
- Eulerian and Hamiltonian graphs, travelling-salesman problem;
- Basic definitions and properties of trees;
- Planar graphs, graph colouring.
- Õpetaja/Teacher: Tiina Zingel