Faites une preuve d'arrêt de cet algorithme. Démontrez que l'algorithme est valide.

Nous allons évaluer la complexité en fonction du nombre de comparaisons entre lettres des deux mots. Notons \(n:=|u|\) et \(m:=|v|\). Dans le meilleur des cas, la première lettre suffit pour conclure, ainsi \(\check T(n,m)=\Theta(1)\) et dans le pire des cas il faut parcourir toutes les lettres du mot le plus court donc \(\hat T(n,m)=\Theta(\min\{n,m\})\).

Le cas moyen, comme toujours, est plus délicat à obtenir. On suppose que \(n\leq m\) et on partitionne l'ensemble \(E\) des instances de tailles \(n,m\) en fonction du nombre de lettres à comparer pour décider, ce nombre variant entre \(1\) et \(n+1\), en effet, on tient compte de la situation où \(u\) est un préfixe strict de \(v\) auquel cas il faut une comparaison supplémentaire pour conclure, même s'il n'y a pas à proprement parler de lettre dans le mot le plus court. Notons \(E_k\) la partie de \(E\) contenant toutes les instances qui nécessitent \(k\) comparaisons, \(1\leq k\leq n+1.\) On a \begin{equation}\label{eq:compmoyenne} \bar T(n,m)=\frac{1}{\#E}\sum_{k=1}^{n+1}k.\#E_k \end{equation} Si l'alphabet est de taille \(q\) alors \(\#E=q^{n+m}\) puisqu'il s'agit du nombre de couples de mots de tailles \(n\) et \(m\) possibles. Dénombrons les ensembles \(E_k\) pour \(1\leq k\leq n\), le cas particulier de la partie \(E_{n+1}\) où \(u\) est un préfixe de \(v\) sera traité à part. Si la décision est prise en comparant \(u_k\) et \(v_k\) pour \(1\leq k\leq n\), cela signifie que les mots \(u\) et \(v\) ont un préfixe commun de \(k-1\) lettres et que \(u_k\not=v_k\). Le mot \(u\) est arbitraire, on a donc \(q^{n}\) possibilités pour \(u\). Les \(k-1\) premières lettres de \(v\) sont fixées par celles de \(u,\) la \(k\)-ème lettre \(v_k\) doit être distincte de \(u_k\) et les \(m-k\) restantes sont quelconques, soit \((q-1)q^{m-k}\) possibilités pour constituer \(v\), finalement: \begin{equation}\label{eq:Ek} \forall k,\ 1\leq k\leq n,\quad \#E_k = q^{n+m-k}(q-1). \end{equation} Il reste à calculer \(\#E_{n+1}\). Dans ce cas \(u\) est préfixe de \(v\) et il y a \(q^m\) possibilités pour constituer \(v\) (mais une seule pour \(u\)), donc \begin{equation}\label{eq:En} \#E_{n+1} = q^m \end{equation} Notons, en guise de vérification, que la somme des cardinaux des \(E_k\) est bien le cardinal de \(E\): \begin{align*} \#E_{n+1}+\sum_{k=1}^{n+1}\#E_k &=q^m+\sum_{k=1}^{n}q^{n+m-k}(q-1)\\ &=q^m+q^m(q-1)\sum_{k=1}^{n}q^{n-k}\\ &=q^m+q^m(q-1)\frac{q^n-1}{q-1}\\ &=q^{n+m}\\ &=\#E \end{align*} On peut remplacer les valeurs \(\#E_k\) déterminées en (\ref{eq:Ek}) et (\ref{eq:En}) dans l'expression (\ref{eq:compmoyenne}) pour obtenir \begin{equation}\label{eq:compfinale} \bar T(n,m) = \frac{(n+1)}{q^n} + (q-1)\underbrace{\color{yellow}\sum_{k=1}^{n}kq^{-k}}_{\color{yellow}S(q^{-1})} \end{equation} Et comme on devait s'y attendre, l'expression montre que la complexité ne dépend que de la plus petite des deux longueurs, ici \(n\) par hypothèse. Il reste à évaluer la somme \(\color{yellow}S(q^{-1})\) et on applique la même preuve que celle du Lemme prouvé au chapitre Fonctions de complexité  :

\(S(q^{-1})= \displaystyle\frac{q^{n+1}-q(n+1)+n}{q^n(q-1)^2}\)

Puisque la complexité ne dépend que de la longueur du plus petit mot, on peut alors conclure

La complexité moyenne de la comparaison lexicographique entre deux mots de longueurs \(n\) et \(m\) est \begin{equation} \label{trilexasympt} \bar T(n,m) = \frac{q}{q-1}-\frac{1}{q^{\min\{n,m\}}(q-1)} \end{equation}

Écrivez une fonction Python PPL(u, v) qui renvoie 0 si \(u=v\), -1 si \(u < v\) et 1 si \(u > v\).