Syllabus academic year 2007/2008
DISCRETE MATHEMATICSFMA091

Higher education credits: 6. Grading scale: TH. Level: G1 (First level). Language of instruction: The course will be given in Swedish. FMA091 overlap following cours/es: FMA661 och FMA661. Optional for: C3, D3, E2, F1, Pi1. Course coordinator: Director of Studies, Lars-Christer.Böiers, Lars_Christer.Boiers@math.lth.se, Matematik. Recommended prerequisits: Elementary linear algebra and analysis (FMA410 and FMA420). Assessment: Written test comprising theory and problem solving. Home page: http://www.maths.lth.se/matematiklth/vitahyllan/vitahyllan.html.

Aim
The aim of the course is to treat some basic parts of discrete mathematics, of importance in computer science, signal processing, information theory, physics and many other subjects in technology and science. The aim is also to develop the student's ability in problem solving and in assimilating 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, functions and relations, graph theory.

in his or her own words be able to describe the logical connections between the concepts (theorems and proofs).

with confidence be able to do routine computations 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.

Skills and abilities
For a passing grade the student must

be able to show capability 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 show capability 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. Diofantic equations. Modular arithmetic.

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

Graph theory: Terminology and basic concepts. Eulerian and Hamiltonian graphs. Planar graphs. Graph colouring.

Literature
Böiers, L-C: Diskret matematik, Studentlitteratur 2003. ISBN 91-44-03102-5