MP/MP*: Option Informatique
Devoir surveillé du mardi 13 décembre 2005
Trois exercices



Présentation

Le sujet se compose de trois exercices.

Le premier exercice propose l'étude d'un langage non rationnel. Une bonne occasion de mettre en œuvre le lemme de l'étoile.

Le deuxième exercice propose l'étude d'un langage rationnel L: construction d'un automate fini reconnaissant L, et d'une expression rationnelle décrivant L. On étudie la suite dont le terme général nk est le nombre de mots de longueur k de L.

Le troisième exercice prend comme thème d'étude le casse-tête de l'été 2005, Sudoku, qui sert de prétexte à diverses questions de combinatoire, d'algorithmique et de programmation.