Discrete mathematics

linfo1114  2021-2022  Louvain-la-Neuve

Discrete mathematics
5.00 credits
30.0 h + 15.0 h
Q2
Teacher(s)
Saerens Marco;
Language
French
Prerequisites
This course assumes that the student already masters notions of algebra covered by the course LINFO1112

The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.
Main themes
Set theory
  • Set notations and operations
  • Binary relations between sets: applications and link with functions in analysis
  • Cardinality of a set (finite and infinite) and notion of inclusion-exclusion
  • Equivalence, equivalence classes
Logic
  • Introduction to the logic of the proposals
  • Introduction to the logic of predicates
  • Prove methods
  • Mathematical induction
  • Notions of Boolean Algebra
Introduction to number theory
  • Natural integer numbers, principle of recurrence, prime numbers, etc.
  • Euclidean division, representation in a base, modulo arithmetic, representation of the integers in the computer
  • Gcd, Euclid's algorithm
  • Basic notions of cryptography
Combinatorial mathematics
  • counting
  • permutations
  • arrangements
  • Recurrence relations
  • Solutions of recurrence equations
Introduction to graph theory
  • Oriented and non-oriented graphs and their matrix representations
  • Bipartite graphs and matching problems
  • Paths on a graph and Eulerian / Hamiltonian circuits
  • Planar graphs and coloring
  • Problems of shorter path
  • Ranking of the nodes of a graph: PageRank
Learning outcomes

At the end of this learning unit, the student is able to :

1
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
  • S1.I1, S1.G1
  • S2.2
Students who have successfully completed this course will be able to:
  • Use the terminology of functions, relationships and together well and perform related operations when the context requires it
  • Explain the basic structure of the main proof techniques (direct proof, counterexample, proof by the absurd, induction, recurrence)
  • Apply the various proof techniques in a convincing way by selecting the most adapted to the problem posed
  • Analyze a problem to determine the underlying recurrence relationships
  • Calculate counts, permutations, arrangements on sets as part of an application.
  • Modeling various real-world problems encountered in computer science using the appropriate forms of graphs
  • Explain the problem of the shortest path in a graph and apply classical algorithms to solve this problem
 
Teaching methods
About 30 hours of lectures, on-site or remotely depending on the situation.
A mandatory project/case study on the implementation of an algorithm.
Evaluation methods
A mandatory project/case study that counts for 2 out of 20 points. If the project report is not done (no report submitted), the student will not be allowed to pass the exam.
A written exam organized in session counting for 18 out of 20 points. Organized on-site or remotely, depending on the health situation.
Online resources
On Moodle
Bibliography
Rosen K., Discrete mathematics and its applications, 8th edition, 2019. Mc Graw Hill.
Teaching materials
  • Slide du cours
  • Mathématiques discrètes de K. Rosen
Faculty or entity
INFO


Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Sigle
Credits
Prerequisites
Learning outcomes
Bachelor in Computer Science
SINF1BA
5
LINFO1112
Master [120] in Data Science : Statistic
DATS2M
5