LMAT1111E, LSINF1101
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.
1 . Logic , sets and functions
- Equivalence ,
- Predicates and quantifiers ,
- Sets and set operations ,
- Sequences and summations ,
- Growth of functions
2 . Algorithms, integers and matrix
- Algorithmic complexity ,
- Integers and divisions ,
- Rudiments of the theory of numbers,
- Recalls of matrix calculation ,
- Application to Markov chains
3 . Logical and mathematical reasoning
- Methods of proof ,
- Mathematical induction ,
- Recursion and recursive algorithms ,
- Correctness of a program
4 . Combinatorial mathematics
- Counting
- Permutations,
- Arrangements
- Recurrence relations ,
- Solving recurrence equations
5 . graphs
- Representation of graphs and graph isomorphism ,
- Connectivity
- Hamiltonian paths ,
- Problems of the shortest path
6 . Trees
- Introduction
- Applications trees,
- Tree paths,
- Trees and sorting,
- Minimum spanning trees
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 completing successfully this course will be able to
- use of the terminology related to functions, relations and all associated operations and realize where the context requires
- explain the basic structure of the main proof techniques ( direct proof , counterexample , proof by contradiction , induction, recursion)
- apply the different proof techniques convincingly by selecting the most suitable to the problem
- analyze a problem to determine the relationships underlying recurrence
- determine counts , permutations , arrangements sets within an application.
- apply various methods of graphs and trees path ( including the prefix , postfix and infix tree path )
- model various real-world problems encountered in computer science using the appropriate forms of graphs and trees, eg the representation of network topology , the hierarchical organization of files, ...
- explain the problem of the shortest path in a graph and apply on simple graphs Dijkstra's algorithm and Bellman- Ford's algorithm
- explain how to construct the minimum spanning tree of a graph
- eetermine if two graphs are isomorphic
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
- A project / case study accounting for 2 on 20 points.
- A written exam held in session accounting for 18 points on 20.
- 30 hours of magistral courses.
- A project / case study on the implementation of an algorithm.
The course is constructed around the following basic topics:
- Mathematical structures: finite and infinite sets, relations, functions - Proof techniques: induction, elementary logic
- Enumeration: binomial coefficients, recurrences, generating functions - Algebraic structures: monoids, groups, morphisms, lattice, Boolean algebras
- Graph theory: trees, paths, matchings, tours
- Analysis of algorithms, plynomial algorithms, etc.
Course material :
- teacher slides
- recommanded book : K. Rosen, "Mathématiques discrètes". 2006.
Background:
- Good knowledge of general mathematics (especially linear algebra) and of basic concepts in programming is required to start this course in good conditions.
