Informatique fondamentale à l'université de La Réunion

• Cours de L3 mention mathématiques
• Cours
  • mardi 27 avril 9h-12h
  • mercredi 29 avril 9h-12h
  • lundi 4 mai 9h-12h
  • mercredi 6 mai 9h-12h
  • lundi 11 mai 9h-12h
• Présentation du cours
• Bibliographie
• Support de cours (premier chapitre)

Programme prévisionnel

• Mots
  • alphabet, lettre, mot, longueur d'un mot, notation |u|, mot vide, notation A^*
  • concaténation de deux mots, monoïde libre
  • morphisme de monoïdes libres
• Opération rationnelles
  • langages
  • exemples L = { u | |u| pair } et L' = { u | |u| impair }
  • union, produit, étoile
  • exemples LL, LL', L'L', { a, ba }^*
  • expression rationnelle
  • exemples A^*, aA^*, (aa+b)^*, (ab^*a+b)^*
• Automates finis
  • définition A = (Q, A, E, I, F)
  • exemple A = ({0, 1}, {a, b}, {(0,a,1), (0,b,0), (1,a,0), (1,b,1)}, {0}, {0})
  • chemin, chemin acceptant, mot accepté, langage accepté
  • théorème de Kleene
    • automates normalisés pour le passage d'une expression à un automate
• Théorème de Kleene (suite)
  • algorithme de McNaugthon-Yamada
  • élimination d'états sur l'exemple précédent
  • résolution d'un système sur l'exemple précédent
• Automates déterministes
  • déterminisation
  • exemple A = ({0, 1, 2}, {a, b}, {(0,a,0), (0,b,0), (0,a,1), (1,b,2), (2,a,2), (2,b,2)}, {0}, {2})
  • complétion d'un automate
  • complémentation
  • exemple de A^*abaA^*
• Minimisation (cf. [BBC03])
  • automates des quotients
  • congruence d'automates
  • congruences de Nerode
    • calcul par raffinement successifs
• Lemmes de l'étoile et ses variantes