Semestre 4 – Option – Mathématiques discrètes 2

Objectifs

L’objectif de ce cours est d’initier les étudiants aux connaissances de base en arithmétique modulaire et aux applications informatiques des graphes.

Prérequis

Mathématiques discrètes 1 du semestre 3.

Contenu pédagogique de l’UE

Arithmétique modulaire :

  • Divisibilité : Algorithmes d’Euclide, Bezout, Théorème de Gauss, équations diophantiennes linéaires
  • Nombres premiers : Théorème fondamental de l’arithmétique, systèmes de numération, Théorème d’Euclide
  • Arithmétique modulaire : Théorème des restes chinois, petit théorème de Fermat, fonction-théorème d’Euler

Applications des graphes :

  • Graphes orientés – non-orientés: Théorèmes d’Euler, Kuratowvski, connexité, chemins-cycles
  • Explorations des graphes : parcours en profondeur, largeur, décomposition par niveaux, Recherche des composantes connexes et fortement connexes
  • Graphes valués : algorithmes de Dijkstra, Bellman, Programmation Dynamique et applications : chemin de débit maximal, le plus sûr, …
  • Introduction au Problème d’Ordonnancement : méthodes potentiels-tâches, PERT, ordonnancement de projet