Cours et TD

• Langages rationnels : un cours et la feuille de TD.
  
• Automates finis : une feuille de travail Maple pour présenter la déterminisation des automates finis (sans epsilon-transitions, qui compliquent la lecture), un cours pas encore terminé mais déjà magnifique, et des exercices. Quelques devoirs :
  • 2001/2002 : Un DS remarquable (posé le 23 Octobre 2001, qui parle de codes et de constructions sur les langages), et son corrigé qui l'est plus encore.
  • 2002/2003 : Le premier DS (posé le 22 octobre 2002) revisite le Théorème de Kleene, et établit le caractère rationnel des facteurs itérants d'un langage lui-même rationnel. Son corrigé .
  • 2005/2006 : La première partie du DS (posé le 8 novembre 2005) : Construction d'une expression régulière à partir d'un AF, avec Lemme d'Arden. Le code et le corrigé
• Algorithmique et complexité : une feuille d'exos très fournie.
  et le le code de l'algorithme de dijkstra... BONUS TRACK : Un 5/2 m'a cuisiné sur des algorithmes autour du "compte est bon". Voici la feuille Maple réalisée il ya quelques années pour comparer mon algorithme avec celui d'un collègue : l'analyse de la complexité s'avère très intéressante.
  
• Arbres : une première feuille d'exercice qui concerne essentiellement la programmation des arbres en Caml (son corrigé Caml est ici). Une seconde concerne les arbres binaires de recherche (son corrigé Caml est ici). On termine avec un TD sur le tri par tas (son corrigé Caml est ici).
  On pourra aler voir la très belle animation sur le tri par tas ici
  Quelques devoirs :
  • 2004/2005 : un devoir sur le "compte est bon" et diverses choses sur les arbres.
  
  
• Syntaxe et sémantique : le TD concerne quelques grammaires, et un mini-problème de récupération de données : dans ce fichier on trouve un programme générant des fichiers "avec un peu de bruit", et l'objectif est d'éliminer ce bruit. Le code solution est ici.

Quelques épreuves de concours

• Ulm/Lyon 99, sur les automates cellulaires.
• Lyon/Cachan 99, sur les polynômes à coefficients entiers.
• L'épreuve commune 2000 sur les transducteurs.
• L'épreuve commune 2001 sur les L-systèmes.
• Le corrigé de l'épreuve d'Informatique MP 2002 de Centrale est disponible ici
• L'oraux 1999 : divers exos d'algorithmique sur la page d'Yves Robert.
• L'oraux 2000 sur la page de Pascal Koiran.
• Le beta-sujet d'épreuve devant machine des ENS ainsi qu'une proposition de correction (par Laure Gonnord).
• Une épreuve d'oral du concours 3A 2002 : Presburger.

Quelques liens

• Le cours d'algorithmique de Yves Robert à l'Ens Lyon, enfin typographié.
• L'archive des cours suivis par Laure à l'ENS Lyon. Voir notamment les pages Algorithmique, Langages formels et Graphes.