IF241 (groupe MAIF)
Présentation
Les objectifs de ce cours sont:
-
Savoir manipuler les automates finis et les expressions rationnelles, en connaître les résultats théoriques de base et présenter leur intérêt d'un point de vue informatique.
- Ces acquisitions seront matérialisées par la réalisation de petits programmes écrit en JAVA.
Le contenu du cours est:
- Mots et produit de concaténation, monoïde libre.
- Langages, opérations ensemblistes, produit, passage à l'étoile.
- Représentations des langages (descriptives, par expression, par machine, par grammaire);
- Expressions rationnelles; l'exemple des expressions régulières dans Unix (grep, édition de textes).
- Automates déterministes et automates non déterministes. Algorithme de déterminisation.
- Théorème de Kleene : équivalence des représentations de langages par expressions rationnelles et par automates finis.
- Algorithme de minimisation d'un automate fini.
- Lemme d'itération.
- Réalisation en Java d'un ensemble d'outils de manipulations des automates finis et/ou des expressions rationnelles.
Organisation
- Cours :
Le responsable est
Jean-Marie Rifflet.
Le Cours a lieu en amphi X1 le Mardi de 10h30 à 12h30.
- TD :
Le responsable est
Stéphanie Delaune.
Le TD a lieu en salle P42 - N1 le Mercredi de 8h30 à 10h30.
Deux interrogations en TD sont prévues:
- Mercredi 9 Novembre
- Mercredi 7 Décembre
- TP :
Le responsable est
Stéphanie Delaune.
Le TP a lieu en salle 65-66, 3ème, N le Jeudi de 10h30 à 12h30.
Deux interrogations de TP sont prévues:
- Le jeudi 17 Novembre (au plus tard), vous devez me rendre le TP2 ou un début d'implémentation des automates (les classes Automates, Etats, ... ainsi que les méthodes permettants de les manipuler). Vous devez pour cela m' envoyer un mail contenant:
- votre nom, votre prénom,
- le code source (.java) comprenant une interface (en mode texte),
- des fichiers tests (.aut),
- une documentation de quelques pages (.ps, .pdf), mais pas de .doc. Vous pouvez également choisir de me rendre
votre documentation manuscrite lors de la séance de TP.
- Il s'agira d' un TP en temps limité (inscription à effectuer au préalable).
Calendrier et polycopiés des TD/TP
- Séance du Jeudi 29 Septembre (TP1):
- Séance du Mercredi 5 Octobre (TD1):
- Séance du Jeudi 6 Octobre (TP2):
- Séance du Mercredi 12 Octobre (TD2):
- Résiduels, Automates non-déterministes, liste chaînées (.ps) (.pdf)
- Séance du Jeudi 13 Octobre (TP3):
- Séance du Mercredi 19 Octobre (TD3):
- Séance du Jeudi 20 Octobre (TP4):
- Implémentation des automates (suite) (.ps) (.pdf)
- Pour ceux qui sont en retard java
- Séance du Mercredi 26 Octobre (TD4):
- Construction d'automates et Lemme d' Itération (.ps) (.pdf)
- Séance du Jeudi 27 Octobre (TP5):
- Implémentation des automates (suite)
- Séance du Mercredi 2 Novembre (TD5):
- Séance du Jeudi 3 Novembre (TP6):
- Implémentation des automates (suite)
- Séance du Mercredi 9 Novembre (TD6):
- Séance du Jeudi 10 Novembre (TP7):
- Implémentation des automates (suite)
- Séance du Mercredi 16 Novembre (TD7):
- correction Interrogation 1
- correction du Devoir Maison
- distribution de la feuille TD7 (à faire à la maison) (.ps) (.pdf)