SF1610 Discrete Mathematics 7.5 credits

• Educational level

  First cycle

• Academic level (A-D)

  A

• Subject area

  Mathematics
  Techonology
  

• Grade scale

  A, B, C, D, E, FX, F

• Link to homepage

• Course page on KTH Social

Learning outcomes

TThe overall goal is to give basic knowledge in Discrete mathematics, in particular a good knowledge in elementary combinatorics, knowledge of some abstract algebraic structure and the use of it, and a good knowledge of some selected topics in graph theory.
After the course it is expected that the student will have achieved a better ability for learning, treating and applying mathematics in general. As the solution of mathematical problems is a method used to learn mathematics, it is expected that the student also will have got a better ability to solve problems in general.

Course main content

TThe fundamental theorem of arithmetics, the Euclidian algorithm and a Diophantine equation. Modular arithmetics, Fermat's theorem and RSA. Sets, functions, infinite sets and cardinal numbers, the pigeonhole principle. Proof by induction and recursions. Elementary group theory as the theorem of Lagrange and in particular the symmetrical group. Boolean algebra. Error correcting codes and in particular Hamming codes. Combinatorics, binomial and multinomial numbers, Stirling numbers, the sieve principle. Elementary graph theory, Eulerian and Hamiltonian graphs, matchings in bipartite graphs, planar graphs.

Eligibility

Elementary linear algebra.

Literature

K.Eriksson och H.Gavel: Diskret matematik och diskreta modeller.

H.Gavel;K.Eriksson/Diskret matematik fördjupning.

Examination

• TEN1 - Examination, 7.5 credits, grade scale: A, B, C, D, E, FX, F

TEN1 - Examination, 7.5 credits, grade scale: A, B, C, D, E, FX, F

Offered by

SCI/Mathematics

Examiner

Olof Heden <olohed@kth.se>

Version

Course plan valid from: Spring 09.
Examination information valid from: Autumn 07.