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.