Vous êtes ici

  1. Accueil
  2. Outils formels pour l'informatique

Outils formels pour l'informatique

Outils formels pour l'informatique

En pratique :

Volume horaire de cours : 24
Volume horaire global de TD : 24
Volume horaire pour d'autres type d'enseignement : 6
Langue principale : français
Nombre de crédits européens : 6

Description du contenu de l'enseignement

Le cours vise à mettre les étudiants en situation de modéliser une problématique à l’aide d’outils formels. Il prépare aux enseignements de logique, langages formels et compilation de L3 informatique et/ou Miage.

  1. Éléments de logique
  2. Ensembles discrets, finis ou infinis
  3. Relations
  4. Fonctions
  5. Relations d’ordre, ensembles ordonnés
  6. Récurrence et induction
  7. Langages et grammaires
  8. Automates finis

Compétences à acquérir

L’objectif principal de ce cours est la modélisation de situations concrètes à l’aide de divers outils de description. Ces moyens de description, ou « langages », seront de nature compréhensible par la communauté informatique, et dans la mesure du possible par les machines elles-mêmes (munies du langage adéquat). La rigueur des descriptions est fondamentale.

  • À la fin du cours, les étudiants savent exprimer des propriétés dans deux langages logiques et dans le langage de la théorie des ensembles.
  • Ils savent identifier et construire divers types de relations : relations d’ordre, d’équivalence.
  • Ils savent définir des structures par induction : c’est la base de la plupart des descriptions informatiques structurées (arbres, formules, listes, ...) et raisonner sur de telles structures.
  • Ils savent juger si une description formelle est conforme ou non à la description proposée en langage naturel.
  • Ils savent décrire de plusieurs manières l’ensemble des mots constituant un langage formel.
  • Ils ont amélioré la clarté et la rigueur de leur expression écrite.
  • Ils ont amélioré leur capacité d’abstraction.

Modalités d’organisation et de suivi

L’enseignement fonctionne sur la base d’un cours magistral suivi d’une séance de travaux dirigés d’application. Les sujets de TD sont distribués en CM. Deux séances de cours sont en mode « classe alternée ». Des exercices en ligne sont proposés en autonomie.


Bibliographie, lectures recommandées

Un espace (http://etudiant.istic.univ-rennes1.fr/current/l2ie/ofi/) est à la disposition des étudiants. Il contient des documents de cours et TD.

  • Mathématiques pour l’informatique, A. Arnold et I. Guessarian (Dunod, 4ème édition 2005), 300 exercices corrigés
  • Méthodes mathématiques pour l’informatique, J. Vélu, (Dunod, 5ème édition 2013)
  • Introductory Logic and Sets for Computer Scientists, N. Nissanke (Addisson Wesley, 1998)
  • Théorie des langages et des automates, J-M. Autebert (Dunod, 1997)
  • Introduction to automata theory, languages and computation, J.E. Hopcroft, J.D. Ullman (Addison-Wesley, 2007)
  • Concepts fondamentaux de l’informatique, A. Aho, J. D. Ullman (Dunod, 1996)
  • La Logique ou l'art de raisonner, Y. Delmas-Rigoutsos et R. Lalement (Le Pommier, 2002)
  • Logique sans peine, Lewis Carroll, (Hermann, 1966, 1992) - extraits tirés de The Game of Logic, 1887, et de Symbolic Logic, 1896 -
  • GODEL, ESCHER, BACH. Les Brins d’une Guirlande Eternelle, D. Hofstadter (InterEditions, 1985 - Dunod, 2008)

Pré-requis

Pré-requis obligatoires

Le seul prérequis est le niveau terminale S.


Profils attendus

De solides bases de mathématiques sont indispensables, même si elles ne sont pas directement exploitées. L’étudiant doit être doté d’un regard curieux et critique, d’une bonne capacité d’abstraction, il devra être naturellement tenté d’analyser la pertinence respective des solutions proposées.