MP/MP*: Option Informatique
DS du jeudi 7 avril 2005

La suite de Kimberling

Une suite trouvée dans le livre Automatic sequences, de Jean-Paul Allouche et Jeffrey Shallit. Un court exercice, avec quelques questions élémentaires de programmation.

Quelques résultats simples sur les codes; l'algorithme de Sardinas et Patterson

Un code est un ensemble X (fini ou infini) de mots possédant la propriété suivante: si des mots u(1)...u(n) et v(1)...v(p) de X vérifient

u(1) u(2) ... u(n) = v(1) v(2) ... v(p)

alors n=p, et u(k)=v(k) pour tout k compris entre 1 et n.

L'algorithme de Sardinas et Patterson permet de décider si un ensemble fini de mots est un code. Nous décrivons cet algorithme et justifions son fonctionnement.