MP/MP*: Option Informatique
Sous-mots, distance d'édition, plus long sous-mot commun
Présentation
On définit la notion de sous-mot , puis on détermine le nombre maximal de sous-mots d'un mot de longueur n sur un alphabet à deux lettres a et b; on montre que les mots pour lesquels le maximum est atteint sont ceux dans lesquels les lettres a et b alternent.
On définit ensuite la distance d'édition de deux mots: c'est le nombre minimal d'insertions et/ou de suppressions de lettres pour passer du premier mot au deuxième; on étudie l'algorithme classique de calcul de cette distance par la programmation dynamique .
On définit le plus long sous-mot commun (PLSMC) à deux mots donnés, et on s'intéresse à trois algorithmes de calcul du PLSMC: le premier reprend la méthode de programmation dynamique, sa complexité spatiale est proportionnelle au produit des longueurs des deux mots.
On se propose ensuite de voir comment diminuer cette complexité: on étudie d'abord l'algorithme de Hirschberg, puis l'algorithme de Hunt et Szymanski.