2021-2022 / MATH2032-1

Introduction aux mathématiques discrètes

Durée

14h Th, 10h Pr

Nombre de crédits

 Bachelier en sciences de l'ingénieur, orientation ingénieur civil2 crédits 

Enseignant

Michel Rigo

Langue(s) de l'unité d'enseignement

Langue française

Organisation et évaluation

Enseignement au deuxième quadrimestre

Horaire

Horaire en ligne

Unités d'enseignement prérequises et corequises

Les unités prérequises ou corequises sont présentées au sein de chaque programme

Contenus de l'unité d'enseignement

Ce cours initie aux mathématiques discrètes en présentant essentiellement des thèmes issus de la théorie des graphes :

  • graphes, multi-graphes, graphes orientés/non orientés, chemins, circuits
  • connexité, sous-graphes, arbres, arbres couvrants
  • recherche d'un chemin de coût minimum
  • chemins et graphes eulériens ou hamiltoniens
  • rudiments de théorie algébrique des graphes, matrice d'adjacence, problèmes de dénombrement, illustration de l'algorithme de PageRank
  • planarité et formule d'Euler
  • problèmes de flot dans un réseau
L'accent est mis sur les concepts et leur formalisation mathématique. Ces concepts seront le plus souvent motivés par des problèmes réels : routage, assignation d'adresses, recherche de communautés dans de grands graphes, problèmes de transport, allocation de ressources, etc.
Ce cours a également pour but de mettre à profit les techniques vues au cours d'algèbre. Enfin, les problèmes de dénombrement débouchent sur l'étude des suites linéaires récurrentes qui sont ensuite généralisés aux équations aux différences.

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

Au terme de ce cours, l'étudiant maîtrisera des notions fondamentales issues des mathématiques discrètes et de la théorie des graphes. Il/elle sera capable de modéliser un problème en termes de graphes. L'étudiant sera en mesure d'argumenter ses affirmations et pourra mettre en oeuvre plusieurs résultats et méthodes du cours pour résoudre, de façon structurée, un exercice de réflexion.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, III.1, III.2 du programme de bachelier ingénieur civil.

Savoirs et compétences prérequis

Des bases en calcul matriciel et en algèbre linéaire suffisent (cf. cours d'algèbre : rudiments de calcul matriciel, polynôme caractéristique, notions de vecteur propre et valeur propre).

Activités d'apprentissage prévues et méthodes d'enseignement

Le cours hybride se compose de cours ex-cathedra (14 heures en présentiel) et de séances de répétitions (10 heures à distance). Les nouveaux concepts et résultats sont introduits dans les cours théoriques. Les séances de répétition sont destinées aux exercices. Elles permettent également d'illustrer et de revenir sur les notions vues aux cours. Les résolutions des exercices seront fournies sous forme de capsules vidéo (podcast). Le temps dégagé permettra d'organiser des séances de réponses aux questions.
 

Mode d'enseignement (présentiel, à distance, hybride)

Combinaison d'activités d'apprentissage en présentiel et en distanciel


Explications complémentaires:

Cours théorique "classique" en présentiel tableau + support informatique en interaction avec les étudiants. Dans la mesure du possible, le cours est "podcasté" (les étudiants auront donc accès aux enregistrements). Pour les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre seuls. Des tutoriels vidéos seront mis à disposition pour la corresction des exercices. Ils seront complétés par un forum de discussion et quelques séances de question/réponse.

Lectures recommandées ou obligatoires et notes de cours

Modalités d'évaluation et critères

Examen(s) en session

Toutes sessions confondues

- En présentiel

évaluation écrite ( questions ouvertes )


Explications complémentaires:

Un examen écrit à livre fermé est organisé en session. Lors de cet examen, l'étudiant doit pouvoir énoncer et exploiter les définitions et résultats vus au cours. Cet examen comprendra également la résolution de plusieurs exercices se rapportant à l'ensemble de la matière vue aux cours théoriques et aux séances de répétition. L'étudiant doit être en mesure de justifier les méthodes employées et de mettre en oeuvre des raisonnements semblables à ceux suivis pendant le cours.  Il ne sera pas demandé de restituer de longues démonstrations.
Un examen de rattrapage est organisé pour la session d'août/septembre. Les modalités sont identiques à celui de mai/juin. La nouvelle note remplace la note obtenue précédemment.

Stage(s)

Remarques organisationnelles

Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ 
Pour les séances de répétitions, les étudiants seront répartis en groupes.

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