t

[cours-maths-dis.git] / automates / OptimisationAutomatesFinis.tex

Des automates différents peuvent être associés au même langage.\\

L'optimisation des programmes d'analyse syntaxique (dont certains sont des réalisations concrètes d'automates finis) rend nécessaire la construction d'un automate minimal (en nombre d'états) qui reconnaissent un langage donné.\\

On se limitera dans ce chapitre à la simplification d'un automate de Moore (puisque la méthode de construction par sous-ensemble permet de se ramener d'un AFND à un AFD).

\section{Congruences d'automates}

Soit $(E,I,t)$ un AFD et $\mathcal{R}$ une relation d'équivalence sur $E$.

\subsection{Quelques rappels}

On rappelle que $\mathcal{R}$ est une relation binaire sur l'ensemble $E$ des états, qui a en plus les propriétés suivantes...
\begin{description}
\item[- réfléxivité.] Pour tout état $e \in E, ~ e \mathcal{R} e$,
\item[- symétrie.] Pour tout couple d'états $(e_1, e_2) \in E^2$ : si $e_1 \mathcal{R} e_2$, alors $e_2 \mathcal{R} e_1$,
\item[- transitivité.] Pour tout triplet d'états $(e_1, e_2, e_3) \in E^3$ : si $e_1 \mathcal{R} e_2$ et $e_2 \mathcal{R} e_3$, alors $e_1 \mathcal{R} e_3$.
\end{description}

\medskip


\begin{Exo}
On considère l'automate :

\unitlength = 0.9mm 
\begin{center}
\begin{picture}(143,75)(-50,-75)
\put(0,-75){}
\node[NLangle=0.0,Nmarks=i](n0)(16.0,-20.0){$e_0$}

\node[NLangle=0.0,iangle=128.23](n1)(44.0,-20.0){$e_1$}

\node[NLangle=0.0](n2)(16.0,-44.0){$e_2$}

\node[NLangle=0.0,Nmarks=r](n3)(44.0,-44.0){$e_3$}

\drawloop[ELdist=1.7,loopangle=37.45](n1){1}

\drawloop[ELdist=2.2,loopangle=225.0](n2){0}

\drawedge[ELdist=2.8](n0,n1){0}

\drawedge[ELdist=1.5](n1,n3){0}

\drawedge[ELside=r,ELdist=2.7](n2,n3){1}

\drawedge[ELside=r,ELdist=3.4](n0,n2){0,1}

\drawedge[ELside=r,ELdist=2.1](n0,n3){1}
\end{picture}
\end{center}
\noindent et la relation binaire $e_i \mathcal{R} e_j$ si et seulement si $i$ et $j$ ont la même parité.

Montrez que $\mathcal{R}$ est bien une relation d'équivalence sur $E$.
\end{Exo}


On rappelle encore que  $t : E \times I \rightarrow E$ est la fonction de transition. Par la suite, par souci de concision, on notera $t_{x}(e)$  pour $t(e,x)$.

\subsection{Définition}

\begin{Def}[Congruence d'automates]
On dit que $\mathcal{R}$ est une \emph{congruence d'automates}\index{congruence d'automates} si et seulement si
$$\forall (r,s) \in E^2, \forall x \in I, (r \mathcal{R} s) \Longrightarrow (t_x(r) \mathcal{R} t_x(s))$$ 
C'est-à-dire si toute paire d'états équivalents modulo $\mathcal{R}$ est transformée par toute entrée en une paire d'états équivalents modulo $\mathcal{R}$.
\end{Def}


\begin{Exo}
La relation d'équivalence $\mathcal{R}$ de l'exercice précédent est-elle une congruence d'automates ?
\end{Exo}

\subsection{Ensemble quotient}

Soit $\mathcal{R}$ une congruence d'automates sur l'AFD $(E,I,t)$.

\begin{Notation}
On note $\tilde{E}$, l'ensemble quotient $E/\mathcal{R}$.\\
\end{Notation}



\begin{Exo}
 Représenter le graphe de l'automate $M$ dont la table de transition des états est
$$\begin{array}{|c|cc|}
   \hline
 t & a & b \\
 \hline
e_0 & e_0 & e_4\\
e_1 & e_1 & e_0 \\
e_2 & e_2 & e_4 \\
e_3 & e_5 & e_2 \\
e_4 & e_4 & e_3 \\
e_5 & e_3 & e_2 \\
\hline
  \end{array}
$$

Soit $\mathcal{R}$ la relation d'équivalence pour laquelle $E/ \mathcal{R} = \{ \{ e_0, e_2 \}, \{ e_1, e_3, e_5 \}, \{ e_4 \} \}.$

\begin{enumerate}
\item Donner la table de transition d'états de l'automate-quotient.
\item Représenter son graphe
\end{enumerate}
\end{Exo}


\noindent Réponses : 

$$\begin{array}{|c|c|c|}
\hline
E & a & b\\
\hline
A = \{e_0, e_2\} & \{e_0, e_2\} & \{e_4\} \\
B = \{e_1, e_3, e_5 \}  & \{e_1, e_3, e_5 \} &  \{e_0, e_2\}\\
C = \{e_4\} & \{e_4\} & \{e_1, e_3, e_5 \} \\
\hline
  \end{array}
$$

\begin{center}
\unitlength=1mm
\begin{picture}(74,83)(0,-83)
\put(0,-83){}
\node[NLangle=0.0](n7)(24.0,-36.0){C}

\node[NLangle=0.0](n8)(52.0,-16.0){A}

\node[NLangle=0.0](n9)(52.0,-56.0){B}

\drawedge[ELdist=2.0](n8,n7){b}

\drawedge[ELdist=2.0](n7,n9){b}

\drawedge(n9,n8){b}

\drawloop[ELdist=1.7,loopangle=53.62](n8){a}

\drawloop[ELdist=1.7,loopangle=-60.55](n9){a}

\drawloop[ELdist=1.7,loopangle=176.01](n7){a}
\end{picture}
\end{center}

\begin{Exo}
 Soit $M$ l'automate fini dont la table de transition des états est

$$\begin{array}{|c|cc|}
   \hline
 t & 0 & 1 \\
 \hline 
1 & 1 & 4 \\
2 & 3 & 5 \\
3 & 2 & 5 \\
4 & 4 & 1 \\
5 & 3 & 4 \\
\hline
  \end{array}
$$

Soit $\mathcal{R}$ la relation d'équivalence sur $E = \{1,2,3,4,5\}$ telle que $1 \mathcal{R} 4$ et $3 \mathcal{R} 2$.
\begin{enumerate}
\item Que vaut $E/\mathcal{R}$?
\item Montrer que $\mathcal{R}$ est une congruence d'automates.
\item Donner la table de transition des états de l'automate-quotient.
\item Représenter son graphe.
\end{enumerate}
\end{Exo}



\begin{Exo}
 Soit $M$ l'automate fini dont le graphe est représenté par la figure\\

\begin{center}
\unitlength = 1mm 
 \begin{picture}(103,62)(0,-62)
\put(0,-62){}
\node[NLangle=0.0](n16)(16.0,-16.0){0}

\node[NLangle=0.0](n17)(40.0,-16.0){1}

\node[NLangle=0.0](n18)(40.0,-40.0){3}

\node[NLangle=0.0](n19)(64.0,-16.0){5}

\node[NLangle=0.0](n20)(64.0,-40.0){4}

\drawedge[ELside=r,ELdist=2.2](n17,n19){1}

\drawedge[ELside=r,ELdist=2.8,syo=1.0,eyo=1.0](n19,n17){ 1}

\node[NLangle=0.0](n22)(88.0,-16.0){2}

\drawedge[ELdist=2.1](n20,n19){1}

\drawedge[ELdist=2.1](n19,n22){O}

\drawedge[ELdist=2.1](n22,n20){1}

\drawedge[ELdist=2.1](n17,n18){0}

\drawedge[ELdist=2.1](n18,n16){1}

\drawedge[ELdist=2.1](n16,n17){1}

\drawloop[ELside=r,ELdist=2.1](n22){0}

\drawloop[ELside=r,ELdist=2.1](n16){0}

\drawloop[ELside=r,ELdist=2.1,loopangle=-87.44](n18){0}

\drawloop[ELside=r,ELdist=2.1,loopangle=-90.0](n20){0}



\end{picture}
\end{center}

Le tableau ci-dessous figure une relation binaire $\mathcal{R}$ dans l'ensemble des états $E = \{ 0,1,2,3,4,5 \}$ :

$$\begin{array}{|c|cccccc|}
   \hline
  & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline
0 & 1 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 \\
2 & 0 & 0 & 1 & 1 & 0 & 0 \\
3 & 0 & 0 & 1 & 1 & 0 & 0 \\
4 & 1 & 0 & 0 & 0 & 1 & 0 \\
5 & 0 & 1 & 0 & 0 & 0 & 1 \\
\hline
  \end{array}
$$

Un chiffre 1 à l'intersection de la ligne $i$ et de la colonne $j$ signifie que $i \mathcal{R} j$, et un chiffre 0 que ces deux éléments ne sont pas en relation.
\begin{enumerate}
 \item Montrer que $\mathcal{R}$ est une relation d'équivalence sur $E$.
 \item Montrer que $\mathcal{R}$ est une congruence d'automates.
\item Représenter le graphe de l'automate-quotient $M/\mathcal{R}$.
\end{enumerate}
\end{Exo}

\noindent Réponses :

$$\begin{array}{c|c|c}
E & 0 & 1 \\
\hline
A = \{0, 4 \} & \{0, 4 \} & \{1, 5\} \\
B = \{1, 5\} & \{3, 2\} & \{1, 5\} \\
C = \{3, 2\} & \{3, 2\} & \{0, 4 \}\\
  \end{array}
$$

\begin{center}
 \unitlength=1mm

\begin{picture}(74,83)(0,-83)
\put(0,-83){}
\node[NLangle=0.0](n7)(24.0,-36.0){C}

\node[NLangle=0.0](n8)(52.0,-16.0){A}

\node[NLangle=0.0](n9)(52.0,-56.0){B}

\drawedge[ELdist=2.0](n7,n8){1}

\drawedge[ELdist=2.0](n9,n7){0}

\drawedge(n8,n9){1}

\drawloop[ELdist=1.7,loopangle=53.62](n8){0}

\drawloop[ELdist=1.7,loopangle=-60.55](n9){1}

\drawloop[ELdist=1.7,loopangle=176.01](n7){0}
\end{picture}
\end{center}

\begin{Rem}
On peut définir une application $\tilde{t}_x : \tilde{E} \rightarrow \tilde{E}$ par $\tilde{t}_x (\dot{e}) = \dot{[t_x(e)]}$, puis une application $\tilde{t} : \tilde{E} \times I \rightarrow \tilde{E}$ par $(\dot{e},i) \longmapsto \tilde{t}_x(\dot{e})$.
\end{Rem}

\section{\'Equivalence de Nérode}

\subsection{L'équivalence}

Soit $M = (E,I,t,e_0,A)$ un automate de Moore, deux états $q$ et $s$ de $E$, et $w \in I^*$ un mot d'entrée.

\begin{Def}[w-compatibles]
 $q$ est $s$ sont \emph{$w$-compatible}\index{w-compatible} si et seulement si $$t_w(q) \in A \Longleftrightarrow t_w(s) \in A$$
\end{Def}

Cette définition permet de définir une relation $\sim$ dans $E$ par

$$(q \sim s) \Longleftrightarrow \left(\forall w \in I^*, q \textrm{ et } s \textrm{ sont } w \textrm{-compatibles} \right)$$

\begin{Def}[\'Equivalence de Nérode]
Cette relation est manifestement une relation d'équivalence, elle est appelée \emph{\'equivalence de N\'erode}\index{équivalence!de Nérode} associée à $M$.
\end{Def}


On démontre facilement que cette équivalence est une congruence d'automates. Tout automate de Moore peut donc être remplacé par son quotient par l'équivalence de Nérode.

Dans ce quotient, le nombre d'états est évidemment plus petit, l'automate obtenu est donc plus \og simple\fg{}.






\subsection{L'algorithme}

\subsubsection{La théorie}

Pour obtenir l'équivalence de Nérode associée à un automate, on dispose de l'algorithme suivant...\\\\

Soit $M=\{E,I,t,e_0,A\}$ un automate de Moore.

On définit, pour tout $k \in \mathbb{N}$, une relation $\mathcal{R}_k$ sur E en posant

$$[ q \mathcal{R}_k s ] \Longleftrightarrow \left[ (\forall w \in I^*), (l(w) \leqslant k \Longrightarrow q \text{ et } s \text{ sont } w\text{-compatibles}) \right]$$

Donc $q$ et $s$ sont en relation par $\mathcal{R}_k$ lorsqu'ils sont $w$-compatibles, pour tout mot $w$ de longueur inférieure ou égale à $k$.\\

Cette relation est clairement une relation d'équivalence, et $\mathcal{R}_{k+1}$ est plus fine que $\mathcal{R}_k$. L'équivalence de Nérode est l'intersection de ces relations $\mathcal{R}_k$, pour toutes les valeurs de $k$ entier.

\subsubsection{La pratique}

Cet algorithme n'est pas utilisable dans la pratique. On fait plutôt...

\begin{enumerate}
 \item Prendre comme partition de départ $P_0 = \{A, E \setminus A \}$.
 \item Si $P_k=\{E_1, \hdots, E_n \} $ est la partition correspondant à la relation $\mathcal{R}_k$, morceler éventuellement chaque classe $E_i$ en sous-classes $E_{i1}, E_{i2}, \hdots, E_{ip}$ de manière que deux états $q$ et $s$ appartiennent à la même sous-classe si, pour toute entrée $x$, les états $t_x(q)$ et $t_x(s)$ appartiennent à la même classe $E_j$ (pouvant dépendre de $x$).

L'ensemble des sous-classes obtenues constitue la partition correspondant à la relation $\mathcal{R}_{k+1}$
\item Répéter l'étape précédente jusqu'à ce que $P_{k+1}=P_k$. La relation $\mathcal{R}_k$ est alors l'équivalence de Nérode associée à M.
\end{enumerate}

\begin{Rem}
L'étape (3) est nécessairement atteinte, puisque les relations $\mathcal{R}_k$ sont de plus en plus fines.

Au pire, $P = \{ \{q \} \|q \in E \}$, la relation est l'égalité : ceci signifie que l'automate n'est pas simplifiable.
\end{Rem}


\begin{Ex}
 Un automate de Moore et l'automate simplifié.
\scriptsize
\begin{center}
\unitlength = 0.8mm 
\begin{picture}(174,77)(0,-77)
\put(0,-77){}
\node[NLangle=0.0,Nmarks=i](n24)(12.0,-12.0){1}

\node[NLangle=0.0](n25)(40.0,-12.0){2}

\node[NLangle=0.0,Nmarks=r](n26)(68.0,-12.0){3}

\node[NLangle=0.0,Nmarks=r](n27)(12.0,-36.0){4}

\node[NLangle=0.0](n28)(68.0,-36.0){7}

\node[NLangle=0.0,Nmarks=r](n29)(40.0,-60.0){5}

\node[NLangle=0.0](n30)(68.0,-60.0){6}

\drawedge[ELdist=2.0](n24,n25){a}

\drawedge[ELside=r,ELdist=2.0](n24,n27){b}

\drawedge[ELdist=2.0](n27,n28){b}

\drawedge[ELside=r,ELdist=2.0](n25,n28){b}

\drawedge[ELside=r,ELdist=2.0](n26,n28){a}

\drawedge[ELdist=2.0](n29,n28){a}

\drawedge[ELdist=2.0](n30,n28){b}

\drawedge[ELdist=2.0](n27,n29){a}

\drawedge[ELside=r,ELdist=3.1,syo=1.0,eyo=1.0](n26,n25){ b}

\drawedge[ELside=r,ELdist=2.0](n25,n26){a}

\drawedge[ELdist=3.0,syo=1.0,eyo=1.0](n29,n30){ b}

\drawedge[ELdist=2.0](n30,n29){a}

\drawloop[ELdist=2.5,loopangle=1.1](n28){a,b}

\node[NLangle=0.0,Nmarks=i](n31)(96.0,-20.0){1}

\node[NLangle=0.0,Nmarks=r](n32)(96.0,-52.0){4}

\node[NLangle=0.0,Nmarks=r](n33)(128.0,-52.0){3,5}

\node[NLangle=0.0](n34)(128.0,-20.0){2,6}

\node[NLangle=0.0](n35)(152.0,-36.0){7}

\drawloop[ELdist=2.0,loopangle=0.0](n35){ a,b}

\drawedge[ELside=r,ELdist=2.0](n31,n32){b}

\drawedge[ELdist=2.0](n31,n34){a}

\drawedge[ELdist=2.0](n32,n33){a}

\drawedge[ELdist=2.0](n34,n35){b}

\drawedge[ELdist=2.0](n33,n35){a}

\drawedge[ELdist=2.0,sxo=1.0,exo=1.0](n34,n33){ a}

\drawedge[ELdist=2.0](n33,n34){b}

\drawbpedge[ELside=r,ELdist=2.0](n32,-90,19.99,n35,-89,37.16){b}

\end{picture}
\end{center}
\end{Ex}

\normalsize

\begin{Exo}
 On donne un AFD par la table de transition des états suivante :
$$\begin{array}{|c||c|c|}
   \hline
t & a & b\\
\hline
0 & 1 & 2 \\
1 & 5 & 3 \\
2 & 5 & 1 \\
3 & 4 & 5 \\
4 & 5 & 4 \\
5 & 5 & 5 \\
\hline
\end{array}$$

\'Etat initial : 0

\'Etats d'acceptation : 4


\noindent Cet automate reconnaît le langage défini par l'expression régulière $(a|bb)bab^*$.

\noindent Appliquer la méthode de l'équivalence de Nérode pour trouver l'automate minimal reconnaissant le langage.
\end{Exo}


\begin{Exo}
Faire de même avec l'automate de Moore dont la table de transition est :
$$\begin{array}{|c||c|c|}
   \hline
t & a & b\\
\hline
a & a & c \\
b & g & d \\
c & f & e \\
d & a & d \\
e & a & d \\
f & g & f \\
g & g & c \\
\hline
\end{array}
$$
\end{Exo}


\section{Méthode du dual}

\subsection{Dual d'un automate}

Soit $M = (E,I,t,S,A)$ un automate quelconque (AFD ou AFND).

\begin{Def}
L'automate dual de $M$ est l'automate $M^{-1} = (E,I,t',A,S)$, où $t'$ est la relation sur $E$ obtenue en renversant toutes les flèches sur le graphe de $M$, c'est-à-dire si $R' \subset (E \times I) \times E$ est le graphe de la relation $t'$, alors que le graphe de $t$ est $R$, on a
$$((e,i),e') \in R' \Longleftrightarrow ((e',i),e) \in R$$
\end{Def}

Il est clair que $M$ reconnaît un mot $w \in I^*$ si et seulement si $M^{-1}$ reconnaît le mot $w^{-1}$ (si $w = a_1 a_2 \hdots a_n$, alors $w^{-1} = a_n a_{n-1} \hdots a_1$).

Le dual d'un automate à comportement déterminé n'est pas nécessairement à comportement déterminé.


\subsection{Méthode du dual}

Soit $M$ un automate de Moore :

\begin{enumerate}
 \item Construire l'automate dual $M^{-1}$ de $M$.
 \item Appliquer la construction par sous-ensembles à $M^{-1}$ pour le transformer en automate $M'$ de Moore.
 \item Construire le dual ${M'}^{-1}$ de $M'$.
 \item Appliquer la construction par sous-ensemble à ${M'}^{-1}$ pour obtenir l'automate de Moore $M''$.
\end{enumerate}

L'automate $M''$ est l'automate minimal tel que $\mathcal{L}(M'') = \mathcal{L}(M)$.



\begin{Exo}
 On donne un AFD par la table de transition des états suivante :
$$\begin{array}{|c||c|c|}
   \hline
t & a & b\\
\hline
0 & 1 & 2 \\
1 & 3 & 4 \\
2 & 3 & 4 \\
3 & 5 & 6 \\
4 & 5 & 6 \\
5 & 7 & 8 \\
6 & 7 & 8 \\ 
7 & 9 & 10 \\
8 & 9 & 10 \\
9 & 11 & 12 \\
10 & 11 & 12 \\ 
11 & 1 & 2 \\
12 & 1 & 2 \\
\hline
  \end{array}
$$

\'Etat initial : 0

\'Etats d'acceptation : 0 3 4 5 6 7 8 11 12


\noindent Cet automate reconnaît le langage défini par l'expression régulière $((a|b)^2)^* | ((a|b)^3)^*$.

\noindent  Appliquer la méthode du dual pour trouver l'automate minimal reconnaissant le langage.
\end{Exo}



\begin{Exo}
 On donne un automate non déterministe, à transitions instantannées, par la table de transition suivante :
$$\begin{array}{|c||c|c|c|}
   \hline
t & \varepsilon & a & b\\
\hline
0 & 1,11 &   & \\
1 & 2, 7 &   & \\
2 &      &   & 3 \\
3 & 4, 6 &   & \\
4 &      & 5 & \\
5 & 4, 6 &   & \\
6 & 10   &   & \\ 
7 &      & 8 & \\
8 &      &   & 9 \\
9 & 10   &   & \\ 
10 & 22  &   & \\ 
11 & 12,14 & & \\
12 &     & 13 & \\
13 &     &    & \\
14 & 17    &    & 15 \\
15 &     &    & 16 \\
16 &  17   &    & \\
17 &     & 18   & \\
18 & 19,21    &    & \\
19 &     &    & 20 \\
20 & 19,21    &    & \\
21 &  22   &    & \\
22 &     &    & \\
\hline
  \end{array}
$$

\'Etat initial : 0


\'Etat d'acceptation : 22



\noindent Cet automate reconnaît le langage défini par l'expression régulière $ba^* | ab | (a | bb) ab^*$.

\noindent Le déterminiser, puis lui appliquer la méthode de votre choix pour obtenir l'automate minimal reconnaissant le langage.
\end{Exo}






\begin{Exo}
 On donne la table de transition suivante pour un automate fini :
$$\begin{array}{|c||c|c|}
\hline
   t & a & b \\
 \hline
0 & 1 & 2 \\
\hline
1 & 3 & 4 \\
\hline
2 & 5 & 6 \\
\hline
3 & 1 & 2 \\
\hline
4 & 7 & 8 \\
\hline
5 & 7 & 8 \\
\hline
6 & 1 & 2 \\
\hline
7 & 9 & 10 \\
\hline
8 & 10 & 11 \\
\hline
9 & 7  & 8 \\
\hline
10 & 10 & 10 \\
\hline
11 & 7 & 8 \\
\hline
  \end{array}
$$

L'état initial est 0, et les états d'acceptation sont 4, 5, 9 et 11.\\

\noindent Appliquer à cet automate l'algorithme de votre choix pour obtenir l'automate minimal reconnaissant le même langage (équivalence de Nérode ou dual).

(L'automate minimal possède 7 états).
\end{Exo}

\section{Synthèse}

\subsection{Outils}

\subsubsection{Construction par sous-ensemble}


\begin{description}
\item[Domaine d'application : ] Cette méthode s'applique aux automates finis non déterministes. Il est aussi possible de l'utiliser sur un AFD, mais c'est sans intérêt.
\item[Résultat : ] Automate reconnaissant le même langage.
\item[But : ] Obtenir un AFD reconnaissant le même langage.
\item[Autre utilisation : ] Peut permettre d'obtenir l'automate minimal reconnaissant le même langage (méthode du dual).
\end{description}

\subsubsection{\'Equivalence de Nérode}

\begin{description}
\item[Domaine d'application : ] Cette méthode ne s'applique qu'aux automates finis dé\-ter\-mi\-nis\-tes (AFD).
\item[Résultat : ] Le quotient de l'automate considéré par l'équivalence de Nérode ; un automate ne reconnaissant généralement pas le même langage.
\item[But : ] Simplifier l'automate considéré, si c'est possible, grâce à la méthode des quotients.
\end{description}

\subsection{Méthodes d'optimisation}

\subsubsection{Méthode des quotients}

\begin{description}
\item[Domaine d'application : ] Cette méthode ne s'applique qu'aux automates finis dé\-ter\-mi\-nis\-tes (AFD).
\item[Moyens : ] \'Equivalence de Nérode.
\item[Résultat : ] On obtient l'automate minimal reconnaissant le même langage.
\end{description}

\subsubsection{Méthode du dual}

\begin{description}
\item[Domaine d'application : ] Cette méthode ne s'applique qu'aux automates finis dé\-ter\-mi\-nis\-tes (AFD).
\item[Moyens : ] Construction par sous-ensembles.
\item[Résultat : ] L'automate de Moore minimal reconnaissant le même langage.
\item[Efficacité : ] \'Elégant, mais pas efficace.
\end{description}


\gsaut
\centerline{\x{Fin du Chapitre}}