Semestre 4 – Mathématiques discrètes 2 – Langages formels

Cette unité d’enseignement est composée de deux éléments constitutifs (EC) :

Mathématiques discrètes 2

Objectifs – acquis d’apprentissage

Applications des graphes.

Prérequis

L’unité de programmation de mathématiques discrètes 1.

Contenu pédagogique

  • Graphes orientés : représentations, théorème d’Euler, Kuratowvski, connexité, chemins, cycles.
  • Explorations des graphes : parcours en profondeur; largeur, décomposition par niveaux, recherche des composantes connexes et fortement connexes, graphe réduit.
  • Graphes valués : algorithmes de Djikstra, 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.

Langages formels

Objectifs – acquis d’apprentissage

Construire et manipuler des automates finis.

Prérequis

Aucun.

Contenu pédagogique

  • Notion de langage formel.
  • Langages réguliers et automates.
  • Expressions régulières.
  • Déterminisation d’un automate non déterministe.
  • Minimisation d’un automate déterministe
  • Grammaires et langages algébriques.
  • Automates à piles
  • Analyse syntaxique ascendante et descendante.