Le barème est donné à titre indicatif et est susceptible d'être adapté. Lisez attentivement les explications. Commentez vos fonctions.
On note \(\Sigma^*\) l'ensemble (infini) des mots définis sur un alphabet fini \(\Sigma\), on note \(.\) la concaténation des mots et \(\epsilon\) le mot vide, élément neutre pour cette loi. On dit qu'un mot \(u\) est un préfixe d'un mot \(v\) si et seulement s'il existe un mot \(w\) tel que \(u.w = v\) (si \(w\neq\epsilon\), le préfixe est strict). Si un mot \(u\neq\epsilon\), on note \(u'\) le plus long préfixe strict de \(u\) et \(\epsilon'=\epsilon\).
Soit \(u\) et \(v\) deux mots de \(\Sigma^*\) de longueurs respectives \(n\) et \(m\). On dit que \(u\) est une sous-séquence de \(v\) si et seulement si \(n\leq m\) et s'il existe une application croissante \(j:\ab{1}{n}\rightarrow\ab{1}{m}\) telle que \[\forall i\in\ab{1}{n}\quad u_i=v_{j(i)}.\]
Soit \(u\) et \(v\) deux mots sur \(\Sigma\). Un mot \(w\) sur \(\Sigma\) est une plus longue sous-séquence commune de \(u\) et \(v\), (PLSC en abrégé), si \(w\) est une sous-séquence de \(u\) et de \(v\) et qu'aucune autre PLSC de \(u\) et \(v\) n'est de longueur strictement supérieure. On note \(\Lambda(u,v)\) la longueur d'une plus longue sous-séquence commune de \(u\) et \(v\).
Exemples : Soit \(\Sigma:=\{a,b,c,\ldots,z\}\) l'alphabet latin. Le mot \(u:=bon\) est un préfixe strict du mot \(bonjour\) et \(u'=bo\). Le mot \(v:={\color{yellow}b\,a\,b\,c}\) est une sous-séquence du mot \(u=a\,{\color{yellow}b}\,c\,{\color{yellow}a\,b}\,a\,{\color{yellow}c}\). Il faut noter qu'il peut y avoir plusieurs applications croissantes \(j\) qui déterminent une même sous-séquence. Les mots \(u:={\color{yellow}a}\,{\color{blue}l}\,g\,o\,{\color{orange}r}\,i\,t\,h\,{\color{orange}m\,e}\) et \(v:={\color{blue}l}\,{\color{yellow}a}\,{\color{orange}r\,m\,e}\) ont les mots \(\color{yellow}a\,{\color{orange}r}\,{\color{orange}m}\,{\color{orange}e}\) et \(\color{blue}l\,{\color{orange}r}\,{\color{orange}m}\,{\color{orange}e}\) comme plus longues sous-séquences communes. On a donc \(\Lambda(algorithme,larme) = 4\).
L'objectif est de déterminer quelle est la longueur Λ(\(u\), \(v\)) des plus longues sous-séquences communes de deux mots \(u\) et \(v\) de longueurs respectives \(n\) et \(m\). Pour cela, on peut démontrer que
\begin{equation} \Lambda(u,v)=\begin{cases} 0&\text{si}\ u=\epsilon\ \text{ou}\ v=\epsilon.\\ \Lambda(u',v')+1&\text{si}\ u_n=v_m.\\ \text{max}\{\Lambda(u',v),\Lambda(u,v')\}&\text{sinon}. \end{cases} \end{equation}De cette égalité on déduit que pour calculer \(\Lambda(u,v)\), il suffit de connaître les trois quantités \(\Lambda(u,v')\), \(\Lambda(u',v)\) et \(\Lambda(u',v')\). En notant \(u_{[i]}:=u_1u_2\ldots u_i\) et \(u_{[0]}:=\epsilon\) le mot vide, on peut construire itérativement une table \(L[i,j]\) de taille \((n+1)\times (m+1)\) définie par \begin{equation*} L[i,j] := \Lambda(u_{[i]},v_{[j]})\quad\text{pour}\quad (i,j)\in\ab{0}{n}\times\ab{0}{m}. \end{equation*}
Exemple : Avec les mots \(u\) =algorithme et \(v\) =larme :
L | ε l a r m e ---|------------------ ε | 0 0 0 0 0 0 a | 0 0 1 1 1 1 l | 0 1 1 1 1 1 g | 0 1 1 1 1 1 o | 0 1 1 1 1 1 r | 0 1 1 2 2 2 i | 0 1 1 2 2 2 t | 0 1 1 2 2 2 h | 0 1 1 2 2 2 m | 0 1 1 2 3 3 e | 0 1 1 2 3 4
La construction de la table \(L\) se fait dans l'ordre de lecture. Une fois les valeurs nulles initialisées pour \(i=0\) ou \(j=0\), le terme \(L[i,j]\) pour \(i>0\) et \(j>0\) ne dépend plus que des termes \(L[i-1,j]\), \(L[i,j-1]\) et \(L[i-1,j-1]\).
Sauvegardez le fichier PLSC.c . Le fichier source contient des déclarations de types, de variables de fonctions prédéfinies commentées, dont certaines sont à compléter et font l'objet de ce contrôle. Ne modifiez pas les noms des variables, types, fonctions, etc.
Une fois ces fonctions complétées et le programme compilé par la commande
$ gcc -o PLSC PLSC.c -WallL'appel
$ ./PLSC algorithme larmeaffichera (par exemple):
L | ε l a r m e ---|------------------ ε | 0 0 0 0 0 0 a | 0 0 1 1 1 1 l | 0 1 1 1 1 1 g | 0 1 1 1 1 1 o | 0 1 1 1 1 1 r | 0 1 1 2 2 2 i | 0 1 1 2 2 2 t | 0 1 1 2 2 2 h | 0 1 1 2 2 2 m | 0 1 1 2 3 3 e | 0 1 1 2 3 4 PLSC = arme
Indications : Initialisez un mot \(w\) au mot vide \(\epsilon\). Partez de la case de coordonnées \((i,j):=(n,m)\) de la table L puis allez sur la case qui contient la plus grande valeur des cases à gauche \((i,j-1)\) et au-dessus \((i-1,j)\) (au choix si les deux contiennent la même valeur), sauf si \(u_n=v_m\) auquel cas \(w\leftarrow u_n.w\) et vous remontez en diagonale sur la case \((i-1,j-1)\). Recommencez ce processus jusqu'à arriver à une case contenant \(0\), le mot \(w\) est une PLSC de \(u\) et \(v\).