MP1/MP*: Option Informatique
Devoir surveillé du jeudi 20 avril 2000
Distance de Hamming; attraction et itération



Présentation

  • Ce sujet est organisé en deux problèmes indépendants. Le premier présente la notion de distance de Hamming entre deux mots de même longueur, puis vous invite à établir diverses propriétés des langages, et en particulier des langages rationnels, liées à cette distance. Au menu: automates finis, lemme de l'étoile, induction structurelle, programmation en Caml.
  • Le deuxième texte définit la notion de bassin d'attraction d'une fonction itérable et établit quelques propriétés simples; on étudie ensuite un exemple pratique. Ne demande pas de connaissances spécifiques; quelques questions de programmation en Caml.

Ce texte a été soumis ą la sagacité des étudiants le jeudi 20 avril 2000.