Course syllabus

Diskret matematik
Discrete Mathematics

FMAA25, 7,5 credits, G1 (First Cycle)

Valid for: 2016/17
Decided by: Education Board B
Date of Decision: 2016-03-29

General Information

Elective for: C4, D4-pv, E4, F1, Pi1
Language of instruction: The course will be given in English on demand

Aim

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.

Learning outcomes

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, functions and relations, graph theory, and the theory of field extensions.
• 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 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.

 

Contents

Number theory: Divisibility. Prime numbers. The Euclidean algorithm. Diofantine equations. Modular arithmetic.

Sets, functions and relations: Injective, surjective and bijective functions. Inverse function. Equivalence relations. Partial order 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.

 

Examination details

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

Admission

Required prior knowledge: Elementary linear algebra and analysis (FMAA01/05 and FMA420).
The number of participants is limited to: No
The course overlaps following course/s: FMA091, FMA661, FMAA15, MATB13

Reading list

• Grimaldi, Ralph: Discrete and Combinatorial Mathematics, An Applied Introduction. Pearson, 2014, ISBN: 9781292022796.

Contact and other information

Course coordinator: Anders Holst, studierektor@math.lth.se
Course homepage: http://www.maths.lth.se/course/nynydiskret/