Objectifs & bibliographie

Objectifs

L’objectif de ce cours est de présenter les outils mathématiques qui sont à la base des techniques utilisées dans la plupart des domaines de l’informatique. En particulier, plusieurs des notions vues sont en lien avec les problèmes de terminaison de programme, la récursion et la compilation, l’autre thème abordé téant celui de la logique. Pour cette dernière partie, le cours se restreint au calcul propositionnel, la suite sera traitée dans l’UE de L3 dédiée.

  • relations d’ordres, ordres bien fondés,
  • induction sur les entiers naturels,
  • induction structurelle,
  • modèles de calcul, automates finis,
  • langages reconnaissables et langages rationnels,
  • calcul propositionnel.

Certaines des opérations sur les automates finis ainsi que des éléments de logique seront vus en TME à travers deux logiciels permettant une approche pratique et visuelle et des exercices de programmation en python.

Compléments

Les étudiants ayant oublié python peuvent réviser les notions vues dans le cadre de l’UE de première année.

Bibliographie

Le premier ouvrage est un panorama très général qui recouvre toutes les notions étudiées. Irène Guessarian, co-auteur de l’ouvrage, a d’ailleurs été pendant plusieurs annéées responsable de l’UE. Les deux suivants, qui couvrent aussi une grande partie du cours, sont plus orientéés vers les modàles de calcul, les automates finis et la logique. Le troisième ouvrage est épuisé mais doit se trouver à la bibliothèque. La quatrième référence présente, de manière très pédagogique et imagée, des questions d’algorithmique et leurs liens avec certains éléments du cours et la cinquième comporte, en plus du cours et des exercices, une mise en oeuvre des notions sous forme de programmes.

  1. Mathématiques pour l’Informatique. A. Arnold, I. Guessarian. Dunod 2005. Il en existe une version numérique, en anglais.
  2. Introduction à la calculabilité. P. Wolper, 2ème édition, Dunod 2001.
  3. Fondements mathématiques de l’informatique. J. Stern. Ediscience 1990.
  4. Algorithmics. The spirit of computing. D. Harel (with Y. Feldman). 3ème édition, Addison Wesley 2004.
  5. Éléments de mathématiques discrètes. M. Jaume. Ellipses, 2016.