ENS Paris-Saclay
Département
Informatique
Formations LIESSE









Formulaire d'inscription aux formations LIESSE 2014

Le département informatique de l'ENS Cachan organise des formations d'informatique pour les professeurs des classes préparatoires aux grandes écoles dans le cadre des stages LIESSE.

*

*

*

Choix de formations

Chaque formation ne sera assurée que s'il y a au moins 10 inscrits. Chaque formation a une limite de 20 places.

Langages formels et applications

Sylvain Schmitz, ENS Cachan

Jeudi 24 avril 2014, 9h30–12h30

Les notions de langages et d'automates fournissent des outils formels utilisés dans de nombreuses applications. Elles sont présentées dans le programme d'option informatique par le prisme de la recherche de motifs dans un texte. L'objectif de cette formation est de présenter d'autres applications : en analyse lexicale des langages de programmation, morphologie des langues naturelles, et vérification des systèmes à états à la SysML.

Niveau de la formation :
Option informatique en MP
Contenu :
  1. rappels sur les expressions rationnelles et les automates finis ; construction de l'automate de Glushkov,
  2. analyse lexicale : exemple de la syntaxe de Python ou d'OCaml, algorithme dynamique,
  3. analyse morphologique : modélisation, sélection des affixes et morpho-tactiques, exemple du français,
  4. systèmes à états : propriétés de sûreté et de vivacité, algorithmes de vérification.

Bases de données relationnelles

Serge Abiteboul, INRIA & ENS Cachan

Jeudi 24 avril 2014, 14h00–17h00

Les bases de données sont au cœur des activités humaines. Elles permettent de gérer des données dans une entreprise, une administration, des données scientifiques, des données personnelles. La technologie des bases de données relationnelles s'appuie sur des bases mathématiques que nous présenterons. Le but est de mettre en perspective le cours de bases de données au programme de CPGE.

Niveau de la formation :
Informatique pour tous
Contenu :
  1. La gestion de données, information, connaissances (leçon inaugurale au Collège de France)
  2. Le calcul relationnel
  3. L'algèbre relationnelle
  4. Le langage SQL
Ressources :
Polycopié écrit avec Benjamin Nguyen et Yannick Le Bras.

Preuves de correction d'algorithmes

Paul Gastin, ENS Cachan

Vendredi 27 juin 2014, 10h–13h

Comment savoir si un algorithme est correct ? Il y a deux aspects bien différents dans cette question, d'une part le problème de la terminaison de l'algorithme, et d'autre part celui de sa correction partielle : à chaque fois qu'il termine, est-ce que l'algorithme fait bien ce qu'on attend de lui (satisfait sa spécification). L'objectif de cette formation est de fournir les clés pour étudier la correction partielle des algorithmes.

Niveau de la formation :
Informatique pour tous
Contenu :
  1. Exemples de preuves d'algorithmes, invariants.
  2. Logique de Hoare : sémantique, système de preuves, plus faible pré-condition.
  3. Exemples : boucles, procédures, récursivité.

Preuves de terminaison d'algorithmes

Philippe Schnoebelen, CNRS & ENS Cachan

Vendredi 27 juin 2014, 14h30–17h30

Les preuves de terminaison des algorithmes s'appuient en général sur des notions fondamentales de théorie des ordres et de combinatoire : ordres bien fondés, calculs sur les ordinaux, etc. Le but de la formation proposée est de présenter ces notions fondamentales, de les illustrer sur quelques exemples tirés de l'informatique, et de fournir des pointeurs bibliographiques pour qui souhaiterait approfondir.

Contenu :
  1. quelques exemples de (non?)-terminaison ;
  2. ordres bien fondés, beaux préordres, ordinaux ;
  3. lemme de Higman, applications en théorie des langages ;
  4. théorème de Kruskal, théorème de Robertson-Seymour, applications en algorithmique des graphes.


Contacter le Département Informatique
Dernières modifications : le 20/06/2014