Duration
14h Th, 10h Pr
Number of credits
| Bachelor in engineering | 2 crédits |
Lecturer
Language(s) of instruction
French language
Organisation and examination
Teaching in the second semester
Schedule
Units courses prerequisite and corequisite
Prerequisite or corequisite units are presented within each program
Learning unit contents
This course is an introduction to Discrete Mathematics by presenting some selected thopics from graph theory:
- graphs, multi-graphs, oriented / undirected graphs, paths, circuits
- connectivity, subgraphs, trees, covering trees
- search for a path with minimal weight
- Eulerian or Hamiltonian paths and graphs
- Algebraic graph theory, adjacency matrix, enumeration problems, PageRank algorithm
- planarity and Euler's formula
- flow problems in a network
This course also aims to use techniques seen in the algebra course (eigenvalues and eigenvectors, diagonalization, ...). Finally, enumeration problems will lead to the study of linear recurrent sequences and are generalized to difference equations.
Learning outcomes of the learning unit
At the end of this course, students will master fundamental notions arising from discrete mathematics and graph theory. They will be able to model a problem in terms of a graph. The students will be able to give arguments for their assertions and will be able to use several results and methods of the course to solve, in a structured way, a complex exercise.
Prerequisite knowledge and skills
Basic knowledge of matrix computations and linear algebra is enough (see the algebra course: rudiments of matrix computations, characteristic polynomial, notions of eigenvector and eigenvalue).
Planned learning activities and teaching methods
The course consists of ex-cathedra lectures (14 hours) and exercises sessions (10 hours). New concepts and results are introduced in the theoretical lectures. The exercises sessions also allow to illustrate and to return on the notions seen in the lectures.
Mode of delivery (face-to-face ; distance-learning)
Classical lectures are face-to-face with computer support interacting with students. When available, the course is "podcasted" (students will have access to the recordings). In the exercise sessions, students are faced with exercises that they must solve under supervision.
Recommended or required readings
Assessment methods and criteria
A written exam is organized in session (with no access to the lecture notes). During this examination, the student must be able to state and use the definitions and results seen during the course. This examination will also include the resolution of several exercises covering the whole material of the theoretical courses and the exercise sessions. The student must justify the chosen methods and should be able to implement reasonings similar to those followed during the courses. It will not be asked to provide long proofs.
A second exam is organized for the August/September session. The terms are the same as in May/June. The new score replaces the one previously obtained.
Work placement(s)
Organizational remarks
Further information is available on http://www.discmath.ulg.ac.be/
For exercise sessions, students will be divided into groups.
Contacts
M. Rigo - Institut de Mathématique (B37) - Allée de la Découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.87 - E-mail : M.Rigo@uliege.be