Cours de M.-P. Béal 2005-2006

Examen

date : 22 novembre
lieu : salle de cours
durée : 2 heures
Notes de cours autorisées mais pas les livres. le sujet .

Références

  • [1] Maxime Crochemore, Christophe Hancart, et Thierry Lecroq, Algorithmique du Texte, Vuibert, Paris, 2001. (Bibliothèque Guy Auliac, voir aussi ici).
  • [2] Maxime Crochemore, Structures for indexes, Lothaire 3, ici.
  • [3] Jean Berstel et Dominique Perrin, Theory of Codes, Academic Press, 1985, ici.

Cours 1 du 11/10

Définition de bases, mots, facteurs. Définition de la période d'un mot non vide. Proposition 1.4 p. 10 [1] sur la caractérisation des périodes. Définition d'un bord d'un mot non vide, du Bord d'un mot non vide. Correspondance entre la suite des longueurs du mot moins la longueur d'un itéré du Bord du mot, et la suite des périodes du mot. Calcul de la table des bords d'un mot non vide en temps linéaire, p. 38 [1].

Cours 2 du 18/10

Calcul de la table des préfixes d'un mot non vide, p. 40 [1]. Calcul de la table des bords à partir de la table des préfixes. Calcul de l'automate des suffixes d'un mot en temps linéaire [1].

Cours 3 du 25/10

Calcul de l'automate des suffixes d'un mot en temps linéaire [1], suite.
Définition d'un code. Tester si un ensemble fini est un code en testant si l'automate en pétales d'un code est non-ambigu (voir [3]).
Tester si un ensemble fini est un code par l'algorithme de Sardinas-Patterson (voir [3]).

Cours 4 du 08/11

Mots interdits minimaux. Calcul en temps linéaire d'un automate déterministe reconnaissant l'ensemble des mots évitant un ensemble fini antifactoriels de mots. Extension au cas où l'ensemble est non antifactoriel. Test de l'antifactoralité d'un ensemble fini de mots [1].
Calcul de l'ensemble des mots interdits minimaux d'une séquence. Borne sur le nombre de mots interdits minimaux en fonction de la taille de la séquence et de l'alphabet [1].

Cours 5 du 15/11

Définition d'un code circulaire. Définition et caractérisation d'un automate (m,a)-local. Tester si un automate est local. Tester sur un ensemble fini est un code circulaire en testant si l'automate en pétales d'un code est un automate local. Un langage L= A^* -A*FA^*, où F est un ensemble fini de mots est reconnu par un automate local.