Course syllabus for Introduction to discrete mathematics

The course syllabus contains changes
See changes

Course syllabus adopted 2021-02-26 by Head of Programme (or corresponding).

Overview

  • Swedish nameInledande diskret matematik
  • CodeTMV211
  • Credits7.5 Credits
  • OwnerTKDAT
  • Education cycleFirst-cycle
  • Main field of studyMathematics
  • DepartmentMATHEMATICAL SCIENCES
  • GradingTH - Pass with distinction (5), Pass with credit (4), Pass (3), Fail

Course round 1

  • Teaching language Swedish
  • Application code 49117
  • Open for exchange studentsNo
  • Only students with the course round in the programme overview.

Credit distribution

0120 Examination 7.5 c
Grading: TH		7.5 c
  • 23 Okt 2021 pm J
  • 04 Jan 2022 am J
  • 26 Aug 2022 pm J

In programmes

Examiner

Go to coursepage (Opens in new tab)

Eligibility

General entry requirements for bachelor's level (first cycle)
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.

Specific entry requirements

The same as for the programme that owns the course.
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.

Aim

This introduction gives basic knowledge about some discrete mathematical structures in different contexts, in particular those that have connection to and are suitable for computing.

Learning outcomes (after completion of the course the student should be able to)

- use the language of logic to formulate propositions and determine truth-values
- conduct a line of mathematical reasoning or proof in simple cases
- use induction in proofs
- use fundamental mathematical concepts such as sets, functions and relations to formulate relationships and solve problems
- define sequences recursively
- express and compute sums and products, in particular arithmetic and geometric series
- prime factorise integers and determine greatest common divisors
- solve linear diophantic equations and calculate with congruences
- solve simple combinatorical problems and corresponding probability problems
- identify various types of graphs and determine whether two graphs are isomorphic

Content

- Logic and proof technique: Basic proposition and predicate logic. Direct proofs and proof by contradiction. Induction.
- Sets, functions and relations: Basic set theory. Injective and surjective functions. Unary and binary operators. Equivalence relations. Partial and total orders.
- Sequences, sums and products: Arithmetic and geometric series. Recursion
- Integer arithmetic: Division algorithm, Euclidean algorithm. Fundamental theorem of arithmetic. Linear diophantic equations. Calculation with congruences. Chinese remainder theorem. Euler's theorem and Fermat's little theorem. RSA cryptosystem.
- Combinatorics: Addition and multiplication principles. Permutations. Ordered and unordered selections (combinations). Binomial coefficients and binomial theorem. Multinomial coefficients. Pigeon hole principle. Inclusion–Exclusion principle.
- Graph theory: Basic terminology. Bipartite and complete graphs. Trees. Directed graphs. Eulerian trails and circuits. Hamiltonian trails and circuits. Isomorphic graphs.

Organisation

The teaching is conducted in the form of lectures and tutorials. Students are also expected to work independently (individually or in groups).

Literature

Course literature is announced via the course website at least two weeks before the course starts.

Examination including compulsory elements

Written exam. Quizzes and assignments may give bonus points.

The course examiner may assess individual students in other ways than what is stated above if there are special reasons for doing so, for example if a student has a decision from Chalmers on educational support due to disability.

The course syllabus contains changes

  • Changes to course rounds:
    • 2021-04-19: Examinator Examinator changed from Jonathan Nilsson (jonathn) to Peter Hegarty (hegarty) by Viceprefekt
      [Course round 1]