SF2736 Discrete Mathematics 7.5 credits

• Educational level

  Second cycle

• Academic level (A-D)

  C

• Subject area

  Mathematics
  

• Grade scale

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

• Link to homepage

• Course page on KTH Social

Learning outcomes

The 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 knowledge of some selected topics in graph theory.
After the course it is expected that the student will have achieved a better ability for treating and applying mathematics in general.

Course main content

The fundamental theorem of arithmetics, the Euclidian algorithm and a Diophantine equation. Modular arithmetics, Fermat's theorem and RSA. Functions, infinite sets and cardinal numbers. Elementary group theory, the theorem of Langrange, the symmetrical group and the lemma of Burnside. Error correcting codes, Hamming codes. Generating functions and partitions of integers. Combinatorics, multinomial numbers, Stirling numbers, the sieve principle and the Moebius inversion formula. Elementary graph theory, coloring problems, matchings in bipartite graphs, flows and cuts.

Eligibility

Elementary linear algebra, for example SF1604.

Literature

Biggs: Discrete Mathematics, 2:nd ed.

Examination

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

TEN1-written examination, 7.5 hp, Grades A-F.

Offered by

SCI/Mathematics

Contact

Olof Heden

Examiner

Olof Heden

Version

Course plan valid from: Autumn 10.
Examination information valid from: Autumn 10.