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 49113
- Open for exchange studentsNo
- Only students with the course round in the programme overview.
Credit distribution
Module | Sp1 | Sp2 | Sp3 | Sp4 | Summer | Not Sp | Examination dates |
|---|---|---|---|---|---|---|---|
| 0120 Examination 7.5 c Grading: TH | 7.5 c |
|
In programmes
- TIDAL - COMPUTER ENGINEERING, Year 2 (compulsory)
- TKDAT - COMPUTER SCIENCE AND ENGINEERING, Year 1 (compulsory)
Examiner
Christian Johansson- Senior Lecturer, Algebra and Geometry, Mathematical Sciences
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. InclusionExclusion 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.