Mathematics 2C: Discrete Mathematics

The course gives an introduction to mathematical logic and set theory, elementary number theory with modular arithmetic, and cryptology, including RSA and discrete logarithms. Other central topics are: Sequences, recurrence relations, mathematical induction, and combinatorial counting methods with applications. Moreover, the course gives an introduction to the theory of relations, graphs and trees, as well as formal languages and finite automata.

1. Knowledge: The student has a basic knowledge of elementary logic, set theory, and combinatorial counting methods. The student is familiar with elementary number theory, including the Chinese remainder theorem and Fermat's little theorem. The student knows how number theory is applied in systems for encryption and authentication, such as RSA and discrete log. The student has knowledge of recursion and induction, as well as relations, graphs, and trees. The student also has basic knowledge of formal languages, grammars and finite automata.

2. Skills: The student is able to make practical use of elementary logic and set theory, can apply Euclid's algorithm, and is proficient in modular arithmetic, and knows how to apply number theory to encrypt messages. The student can solve systems of linear congruences using the Chinese remainder theorem, can write simple proofs using induction, and is able to recognize, understand, and apply concepts such as relations, graphs and trees in applications, for example in information technology. Moreover, the student is able to apply combinatorial counting methods to solve practical problems and can make practical use of finite automata.

Lectures and compulsory exercises.