Mathématiques pour l'informatique

Présentation

Ce module a comme objectif principal de faire le lien entre l’informatique et les notions théoriques d’automates et de langages formels, et d'avoir les éléments mathématiques nécessaires pour suivre des études d'informatique généralistes.

Descriptif

Langages et automates 30h (CM 12 h, TD 12 h, TP 6 h)

  • Langages formels: alphabets, mots, facteurs, ordres sur les mots, opérations ensemblistes et algébriques sur les langages, fermeture des langages, langages réguliers, expressions régulières.
  • Automates : automates déterministes et non déterministes, calculs d'un automate, langages reconnaissables, automates complets, produits d'automates, déterminisation des automates, automates asynchrones, théorème des éliminations des epsilon-transitions, exemples de langages reconnus, théorème de Kleene, algorithme de Brzozowski et Mac Cluskey, minimisation des automates. Exemples d'applications d'automates.

Mathématiques (CM 12h, TD 12, TP 6h)

  • Arithmétiques et combinatoire : propriété du modulo, dénombrement simple. Applications : codage en complément à deux, notions de cryptographie. 
  • Analyse : propriétés des fonctions logarithmique et exponentiel. Croissance et comparaison de fonctions. Notation et analyse asymptotique. Application à la complexité de programmes.

Bibliographie

  1. Fondements mathématiques de l'informatique. J. Stern Mc Graw Hill.
  2. A. Arnold et I. Guessarian - Mathématiques pour l'informatique - EdiScience
  3. P. Bellot et J. Sakarovitch - Logique et automates - Ellipses
  4. P. Dehornoy - Mathématiques de l'informatique - Editions Dunod

Modalités de contrôle des connaissances

Session 1 ou session unique - Contrôle de connaissances

Nature de l'enseignementModalitéNatureDurée (min.)NombreCoefficientRemarques
UECTEcrit - devoir surveillé12011

Session 2 : Contrôle de connaissances

Nature de l'enseignementModalitéNatureDurée (min.)NombreCoefficientRemarques
UECTEcrit - devoir surveillé12011