Programme résumé : Langages réguliers et automates d'états finis

* Thème 0 : Définition inductive et preuve par induction
o Théorème de Kleene et points fixes
o Schéma de preuve par induction

o Reconnaissance d'un langage régulier par un automate d'états fini
o Propriétés algébriques des langages réguliers
o Notion de non déterminisme, déterminisation d'un automate
o Problèmes de décision : langage vide, langage infini


Compétences visées : 

La maîtrise de la programmation s'appuie sur l'étude des langages et moyens d'expression utilisés en informatique et sur la compréhension des modèles de calcul sous-jacents.
Les automates sont des structures finies qui permettent de décrire des phénomènes infinis, par exemple l'ensemble des comportements d´un programme ou l'ensemble des phrases d'un langage. 
La théorie des automates fait partie des fondements de l'informatique. Dans ce cours nous l'abordons avec les objectifs suivants :
* Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF231)
* Apprendre à analyser formellement les propriétés d'un langage


  • Étude d'algorithmes classiques :
    • Présentation et manipulation de structures de données courantes
    • Connaissance de modèles d'algorithmes de traitement des séquences
  • Apprendre à programmer "juste du 1er coup".
  • Vérifier formellement :
    • des hypothèses sur l'environnement à tout moment dans l'exécution du programme
    • une propriété à tout endroit du programme
  • Connaitre et savoir manipuler des notions comme :
    • Les assertions
    • les invariants d'itérations
    • la preuve de programme
  • Comprendre et savoir manipuler les langages objets :
    • les objets
    • les classes d'objets
    • les contrats
    • ...

Public : étudiants en 2eme année de licence en Bio/Chi à Valence
Contenu : Initiation à l'informatique et plus particulièrement à l'algorithmique.
Langage : Le cours s'appuie sur le langage de programmation JAVA.