Course syllabus

# Diskret matematik

Discrete Mathematics

## FMAB75, 7,5 credits, G1 (First Cycle)

## General Information

## Aim

## Learning outcomes

## Contents

## Examination details

## Admission

## Reading list

## Contact and other information

Discrete Mathematics

Valid for: 2020/21

Decided by: PLED F/Pi

Date of Decision: 2020-04-01

Elective for: BME4, C4-pv, D4-pv, E4, F1, Pi1

Language of instruction: The course will be given in English on demand

The aim of the course is to treat some basic parts of discrete mathematics, of importance in computer science, information theory, signal processing, physics and many other subjects in technology and science. The aim is also to develop the students' ability to solve problems and to assimilate mathematical text. The course should also provide general mathematical education.

Knowledge and understanding

For a passing grade the student must

- be able to understand and in his or her own words clearly define the central concepts in combinatorics, number theory, graph theory, functions and relations, and the theory of finite fields.
- in his or her own words be able to describe the logical connections between the occurring concepts (theorems and proofs).
- with confidence be able to carry out routine calculations within the framework of the course.
- in practical situations, with confidence be able to identify different combinatorial selections: with/without repetition, with/without regard to order.
- understand how results about finite fields and linear algebra may be used for coding.

Competences and skills

For a passing grade the student must

- be able to demonstrate ability to identify problems which can be solved with methods from discrete mathematics and to choose an appropriate method.
- in connection with problem solving be able to demonstrate ability to integrate results from various parts of the course.
- with proper terminology, in a well-structured way and with clear logic be able to explain the solution to a problem.
- be able to use basic theorems of graph theory to draw conclusions about a given graph (of moderate size).

*Number theory*: Divisibility. Prime numbers. The
Euclidean algorithm. Chinese remainder theorem. Modular
arithmetic.

*Sets, functions and relations*: Injective, surjective
and bijective functions. Inverse function. Equivalence
relations.

*Combinatorics*: The four cases of counting with or
without repetition and with or without regard to order. Binomial
coefficients. The principle of inclusion and exclusion. The method
of generating functions.

*Recursion:* Recursion formulae and difference
equations.

*Rings and fields*: Definition. Applications to
coding.

*Graph theory:* Terminology and basic concepts. Eulerian
and Hamiltonian graphs.

Grading scale: TH - (U,3,4,5) - (Fail, Three, Four, Five)

Assessment: Written exam followed by an oral exam for those who pass the written exam.

The examiner, in consultation with Disability Support Services, may deviate from the regular form of examination in order to provide a permanently disabled student with a form of examination equivalent to that of a student without a disability.

Assumed prior knowledge: Elementary linear algebra and analysis (FMAA01/05 and FMAB20).

The number of participants is limited to: No

The course overlaps following course/s: MATB13, FMA091, FMA661, FMAA15, FMAA25

- Karl-Gustav Andersson: Finite Fields and Error-Correcting Codes. Matematikcentrum, 2015. Available as a pdf-file on the web. 54 pages.
- Sigmundur Gudmundsson: Linear Difference Equations. Matematikcentrum, 2017. Available on the web as a pdf-file. 5 pages.
- Grimaldi, Ralph: Discrete and Combinatorial Mathematics, An Applied Introduction. Pearson, 2014, ISBN: 9781292022796.

Course coordinator: Anders Holst, studierektor@math.lth.se

Course administrator: Studerandeexpeditionen, expedition@math.lth.se

Teacher: Anna Torstensson, annat@maths.lth.se

Course homepage: http://www.maths.lth.se/course/fmab75discrete/