Duration
14h Th, 10h Pr
Number of credits
| Bachelor of Science (BSc) 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.
This course contributes to the learning outcomes I.1, I.2, III.1, III.2 of the BSc in engineering.
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 hybrid course consists of ex-cathedra lectures (14 hours) and exercise sessions (10 hours). New concepts and results are introduced in the theoretical lectures. The exercises sessions, in amphitheatre, are intended for exercises. They are also used to illustrate and revisit the notions seen in the lectures. A pre-recorded version is also available online.
Mode of delivery (face to face, distance learning, hybrid learning)
Face-to-face course
Additional information:
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). For the exercise sessions, students are faced with exercises. Video tutorials are provided for correcting these exercises. They will be complemented by question/answer sessions.
Recommended or required readings
Exam(s) in session
Any session
- In-person
written exam ( open-ended questions )
Additional information:
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)
Organisational remarks and main changes to the course
Further information is available on the eCampus dedicated web page.
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