Organisation

Le cours de TL1 contient 11 cours, 10 TD  et un TP/projet noté. Sauf semaine exceptionnelle, il y a un cours et un TD/TP par semaine. Le contenu des cours est décrit ci-dessous avec des liens vers les supports de cours.

Des quizzs rapides (5-10 min), à passer entre le cours et le TD, vous permettent de valider votre compréhension du cours. Ils sont disponibles pendant 15 jours après le cours dans l'outil Exercices de Chamilo (lien en bas de cette page).

Les exercices traités en TDs sont pris du recueil de TD qui vous a été distribué à la première séance.

Pour faciliter vos révisions, des annales d'examen couvrant les trois dernières années sont disponibles dans le répertoire Documents/Annales du cours.

 

Notions abordées

Partie Automates et langages

Partie Grammaires

  • Cours 8 : Grammaire et hiérarchie de Chomsky
  • Cours 9 : Grammaire hors-contexte : Propriété de décomposition, Ambiguité. principe de preuve sur les grammaires
  • Cours 10 : Modélisation et Expressivité : Description des LP, grammaire étendues, Hiérarchie de chomsky : inclusion et lemme de la pompte pour les HC
  • Cours 11 : Langages et décidabilité. Modélisation par automate : Résultat de décidabilité, algorithmes de reconnaissance, Application des automates à la vérification

 

Contenu des TD

Les exercices traités en TDs sont pris du recueil de TD. Les exercices et questions marqués [À savoir faire] ou [Avancé] ne sont en général pas traités en séances. Ils vous servent à déterminer où vous en êtes dans votre apprentissage.
Voici les exercices qui sertont traités à chaque séance, la partie entre parenthèse est optionnelle :

  • TD 1 : exercices 1, 2, 3, (4, 8)
  • TD 2 : exercices 6, 7, 11, 12, 13 (le 13 sera repris au TP)
  • TD 3 : exercices 20, 21, 24, (25, 26)
  • TD 4 : exercices 28, 29, 35, (33, 34, 36)
  • TP 5 : sujet et fichiers source à récupérer dans Documents/TP
  • TD 6 : exercices 38, 39, 40, 41, (42, 43)
  • TD 7 : exercices 46, 47, 48, 49, (43) (lemme de l'étoile et fermeture)
  • TD 8 : exercices 52, 53, 54 (grammaires)
  • TD 9 : exercices 58, 60 (hors-contexte)
  • TD 10 : exercices 59, 55
  • TD 11 : exercice 56 + exercices précédents non terminés sur  grammaires / propriétés de fermeture

La correction d'une partie de ces exercices est disponible dans les exercices corrigés.

 

TP / projet

Il est à faire soit en binôme soit en monôme. Dans les deux cas, vous devez créer une équipe dans le projet Teide créé pour l'occasion, voir https://teide.ensimag.fr/ (VPN nécessaire si vous êtes hors de l'Ensimag). Les deux membres d'une équipe doivent appartenir au même groupe de TD et chaque groupe de TD possède son propre projet Teide. La date limite de création d'une équipe est le 15/11/23 à 11h.

Votre rendu devra être une archive contenant deux fichiers : le fichier tp.py (récupéré lors du TP) complété et un fichier pdf contenant les réponses aux questions demandant de la rédaction. Le rendu se fera sur Teide, au plus tard le 8/12/23 AoE (Anywhere on Earth), c.-à-d. le 9/12/23 à 13h, heure de Paris. Il doit y avoir un rendu par équipe, qui comptera pour tous les membres de l'équipe.
Pour information :
- les questions 0, 1, 3, 4 ne sont pas évaluées, elles sont là pour vous guider ;
- les questions 2, 5, 6, 7, 8, 10, 11, 12, 14, 15 sont à réaliser dans le fichier tp.py ;
- les questions 9, 13 et 16 sont à rédiger dans le fichier pdf.

Les questions à rédiger nécessitent des parties du cours que vous allez voir dans les semaines à venir (CM7 pour la question 13, CM9 pour les question 9 et 16) mais le reste peut être fait dès maintenant.

La question 11 a été explicitée par rapport à votre TP, pensez à récupérer le sujet mis à jour depuis Chamilo (dossier Documents/TP).

Nouveau : les questions 14 et 15 ont été précisées.

DocumentsDocuments
ExercicesExercices