\documentclass[10pt,a4paper]{article}
\input Maths.sty
\usepackage{francais,%enumerate,
amsfonts,amssymb,
amsmath}
%\usepackage[active]{srcltx}
%\usepackage[T1]{fontenc}
%\usepackage[french]{babel}
\pagestyle{empty}
%\setlength{\footrulewidth}{0.4pt}
%   Param\`etres de Fancyheading : 
%\lhead{}   \chead{}   
%\lfoot{}    \cfoot{}    \rfoot{}
\parindent=0cm
\leftskip-2cm\rightskip-1.5cm
\setlength{\headheight}{0pt}%
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\textheight}{730pt}
\setlength{\marginparwidth}{0pt}
\setlength{\marginparsep}{0pt}
\setlength{\textwidth}{380pt}

\begin{document}
\partietitre{Tri d\'enombrement}
\question
$\bullet$ Construire un tableau  $C$ de longueur MAX\_VAL+1, ne contenant que des $0$.

$\bullet$ Parcourir dans l'ordre croissant le tableau $T$ \`a trier  en incr\'ementant la case $p$ de $C$ chaque fois qu'on rencontre l'entier $p$ dans $T$.

$\bullet$ Modifier le tableau $C$ , en ajoutant au contenu de  chaque case celui de la case pr\'ec\'edente, en commen\c{c}ant par la premi\`ere case.
On obtient ainsi dans la case $i$ de $C$ le nombre d'\'el\'ements $\le i$ contenus dans $T$.

$\bullet$ Mettre les \'el\'ements \`a leur place.


Il y a trois parcours de $C$ en plus de sa cr\'eation, avec trois op\'erations \'el\'ementaires au plus \`a chaque case (lecture, addition, \'ecriture), deux parcours de $T$ avec une op\'eration \'el\'ementaire \`a chaque case.
Donc co\^ut $n$.
\question
\begin{verbatim}
let tri_simple tableau  = 
            let k = MAX_VAL + 1 in
            let n = t.(0) and c = make_vect k 0 in
	       for i = 1 to  n do let p=tableau.(i) in
	                   c.(p) <- c.(p) + 1 done;
   	       for p = 1 to k-1 do 
	                   c.(p) <- c.(p) + c.(p-1) done;
	       for j = 1 to c.(0) do tableau.(j) <- 0 done;
	       for p = 1 to k-1 do  
	    	    for j = c.(p-1)+1 to c.(p) do
		          tableau.(j) <- p done done;;       	        			   
\end{verbatim}
 
\partietitre{Gestion de tables}\qno2
\question
\begin{verbatim}
let vider T = T.(0) <- 0;;  
\end{verbatim}
\question
\begin{verbatim}
let ajouter T p = T.(0) <- T.(0) + 1; T.(T.(0)) <- p;; 
\end{verbatim}
\question
\begin{verbatim}
let concatener T1 T2 = 
          for i = 1 to T2.(0) do ajouter T1 T2.(i) done;;
\end{verbatim}
\question
La complexit\'e de concat\'ener est de l'ordre de $n2$, longueur de $T2$. En effet ajouter comporte $5$ op\'erations \'el\'ementaires, et on l'applique $n2$ fois. Les co\^uts marginaux \'etant born\'es.
\question
\begin{verbatim}
let max_valeurs T = 
      let n = T.(0) in
      let m = ref (-1) in
      for i=1 to n do 
              m:= max T.(i) !m done; 
      !m;; 
\end{verbatim}
\question
\begin{verbatim}
let rec nombre_chiffres  = fun
     p when p<10 -> 1
    |p -> 1 + nombre_chiffres (p/10);;  
\end{verbatim}
\question
\begin{verbatim}
let max_chiffres T = match T.(0) with
              0 -> 0
	            |_ -> nombre_chiffres (max_valeurs T);; 
\end{verbatim}
\question
La complexit\'e est de l'ordre de grandeur de $maxc+n$. En effet \verb|nombre_chiffres| comporte $maxc-1$ divisions et 
\verb|max_valeurs| $n-1$ comparaisons et $n$ acc\`es en m\'emoire.
\eject
\partietitre{Tri par baquets} \qno10
\question
A l'\'etape suivante, on a \verb/baquet[0]:[|603;7|]/ , \verb/baquet[2]:[|20;423;27|]/,
\verb/baquet[5]:[|50;453;57|]/ et \verb/T:[|603;7;20;423;27;50;453;57|]/.
A la derni\`ere \'etape, on a \verb/baquet[0]:[|20;27;50;57|]/ , \verb/baquet[4]:[|423;453|]/ ,
\verb/baquet[6]:[|603|]/ , et \verb|T| sera tri\'e.
\question
Invariant de boucle: \`a l'issue de la boucle d'indice $r$, les \'el\'ements sont class\'es dans l'ordre lexicographique croissant de leurs $r$ derniers chiffres. La boucle suivante  reprend ces \'el\'ements dans le tableau dans l'ordre croissant du $(r+1)$-i\`eme chiffre.
\question
\begin{verbatim}
let distribuer T r baquets =
        let rieme_chiffre  a r = 
	         let b = puiss10 (r-1) in (a/b) mod 10 in
        for i = 1 to T.(0) do  
	             let p = T.(i) in 
		              let k = rieme_chiffre p in
		              ajouter baquets.(k) p done;;
\end{verbatim}
\question
\begin{verbatim}
let tri_baquets T = 
        let maxc = max_chiffres T in
	for r = 1 to maxc do
	    for i = 0 to 9 do
	          vider baquets.(i) done;
	    distribuer T r baquets;
	    vider T;
	    for i = 0 to 9 do 
	          concatener T baquets.(i) done	done;;   
\end{verbatim}
\question
\verb|max_chiffres| est de co\^ut $maxc+n$ , \verb|vider|  et \verb|rieme_chiffre| sont de co\^ut constant, 
\verb|distribuer| est donc de co\^ut $n$. La concat\'enation de tous les \verb|baquets.(i)| est de co\^ut $n$ puisque la somme des longueurs des \verb|baquets.(i)| est $n$.
Chacune des boucles $r$ est donc de co\^ut $n$, d'o\`u le r\'esultat.
\question
$n\times\ln n$ : $maxc$ est au moins de l'ordre de $\ln n$ si tous les nombres sont distincts. Ce co\^ut est atteint s'il s'agit de tous les entiers de $1$ \`a $n$.
\question
On traite s\'epar\'ement les nombres en fonction de leur nombre de chiffres. On concat\`enera les r\'esultats: un nombre de $p$ chiffres est plus petit qu'un nombre de $p+1$ chiffres.
 On ne s'occupe donc plus des $0$ en t\^ete des nombres.
\begin{verbatim}
let couper r U V W =
    vider V; vider W
    for i = 1 to U.(0) do
          let k = U.(i) in
          if  k < puiss10 r then ajouter V k
	                           else ajouter W k;;  
\end{verbatim}
Cette fonction coupe le vecteur $U$ en deux: dans $V$ on place tous les entiers ayant au plus $r$ chiffres, et dans $W$ les autres.
\begin{verbatim}
let tri_baquets_bis T =
        let r = ref 0 in 
        let U = copy_vect T in
	        vider T;
	        while U.(0) <> 0 do
	            	couper !r U V W;
	            	tri_baquets V;
	      			   concatene  T V;
	      			   let U = copy_vect V;
	      			   incr r      done;;
\end{verbatim}
Je ne suis pas vraiment les indications de l'\'enonc\'e, et j'utilise trois tableaux auxiliaires...

Mais le co\^ut est le bon: couper est de co\^ut $U.(0)$ et la somme de tous les $U.(0)$ qui interviennent est exactement le nombre total de chiffres.
L'ensemble des \verb|copy_vect| est de m\^eme co\^ut, celui des \verb|tri_baquets| \'egalement, celui des \verb|concatene| est de co\^ut $n$.

\pno0
\partietitre{Approche na\"{\i}ve}
\qno17
\question
Si $L({\cal A})$ n'est pas vide, soit $m$ un mot de longueur minimale. $m$ est n\'ecessairement de longueur au moins $n$, il passe  par $n+1$ \'etats au moins. Il y a donc au moins un \'etat par lequel il passe deux fois. On obtient un mot strictement plus court en supprimant toute la partie situ\'e entre ces deux passages. C'est impossible.
\question
On remplace l'ensemble des \'etats finaux par son compl\'ementaire. Un mot de $L(A)$ s'ach\`eve \`a un \'etat final, qui ne l'est plus, il n'est donc pas reconnu. Inversement un mot qui n'est pas dans $L(A)$ s'ach\`eve sur un \'etat non final, qui l'est devenu.
\question
On fait le produit cart\'esien des deux automates:$<\Sigma,Q\times Q',T",I\times I',F\times F'>$ o\`u $((p,p'),a,(q,q'))\in T"$ si et seulement si $(p,a,q)\in T$ et $(p',a,q')\in T'$.   
Pour aboutir \`a un \'etat final, il faut et il suffit que le mot soit reconnu par les deux automates.
\question
Sinon $L({\cal A})\cap \overline{L({\cal A'})}\not=\emptyset$ ou $L({\cal A}')\cap \overline{L({\cal A})}\not=\emptyset$. Dans le premier cas par exemple, d'apr\`es 18. , 19. et 20. , il existe un mot $m$ dans $L({\cal A})\cap \overline{L({\cal A'})}$ de longueur au plus $n\times n'-1$.

\question
On d\'eterminise, et on obtient le majorant $2^{n+n'}-1$.
\partietitre{Approche plus fine}
\qno22
\question
Deux automates \`a deux \'etats, l'un ne reconnaissant que le mot $a$, et l'autre tous les mots de longueur impaire.
\question
Il existe un calcul d'origine $i$, d'extremit\'e $j$ et d'\'etiquette $m=a_1\ldots a_k$ si et seulement si on a $(i_p,a_p,i_{p+1})\in T$ pour tout $p$ avec $i_1=i$ et $i_{k+1}=j$. On applique la d\'efinition de $\varphi_m$.
\question
$\varphi_m(e_1)$ vaut $e_p$ o\`u $p$ est l'extr\'emit\'e du calcul d'\'etiquette $m$ et d'origine $1$. Donc $\varphi_m(e_1).z$ vaut $1$ ou $0$ selon que le calcul est r\'eussi ou non, c'est \`a dire selon que le mot est reconnu ou non. 
\question 
$\Phi_m(E)$ vaut $(e_p;-e'_q)$, o\`u $p$ est l'extremit\'e du calcul de $\cal A$ d'\'etiquette $m$ et d'origine $1$, et $q$ l'extr\'emit\'e du calcul de ${\cal A}'$ d'\'etiquette $m$ et d'origine $1$. Donc $\Phi_m(E).Z=\varphi_m(e_1).z-\varphi'_m(e'_1).z'$  vaut $0$  si  $\varphi_m(e_1).z$ et $\varphi'_m(e'_1).z'$ prennent  la m\^eme valeur, c'est \`a dire  $m$ est \`a la fois  dans $L({\cal A})$ et $L({\cal A}')$ ou ni dans l'un ni dans l'autre. L'expression vaut $1$ si $m$ est dans $L({\cal A})$ et pas dans $L({\cal A}')$ et $-1$ si c'est le contraire .
\question
Le syst\`eme g\'en\'erateur de $V_k$ est inclus dans celui de $V_{k+1}$.
\question
C'est vrai pour $\varphi_m$, donc s\'epar\'ement pour les deux parties.
\question
On le d\'emontre pour un g\'en\'erateur de $V_k$ : soit $w=\Phi_m(E)$ avec $|m|\le k$, et on conclut par lin\'earit\'e.
En effet $\Phi_a(w)=\Phi_{ma}(E)$, et $|ma|\le k+1$.
\question
L'une des inclusions a d\'ej\`a \'et\'e faite. 

Soit $w$ un g\'en\'erateur de $V_{k+2}$. $w=\Phi_m(E)$ avec $|m|\le k+2$. Si $|w|\le k+1$, $w$ est dans $V_{k+1}$, sinon $m=\mu a$, $w'=\Phi_{\mu}(E)\in V_{k+1}$, et on applique la question 29. \`a $w'$, donc ici aussi $w\in V_{k+1}$. 

\question
D'apr\`es les questions 27. et 30., la suite des sous-espaces $V_k$ de $\R^{n+n'}$ est strictement croissante puis \'eventuellement constante. La suite des dimensions est une suite d'entiers, $V_0=\hbox{Vect}(E)$ est de dimension $1$, donc la dimension de $V_k$ est au moins  $k+1$, tant que la suite n'est pas constante. Donc la suite est constante au moins \`a partir de $k=n+n'-1$. 
\question
$\cal A$ et ${\cal A}'$ sont \'equivalents si et seulement si $\Phi_m(E).Z$ est nul pour tous les $m\in\Sigma^*$. Cela revient \`a dire que les $V_k$ sont dans l'hyperplan orthogonal de $Z$. Or $V_k\subseteq V_{n+n'-1}$ pour tout $k$. Tout revient \`a savoir si les 
$\Phi_m(E)$ sont dans l'hyperplan pour tout $m$ v\'erifiant $|m|\le n+n'-1$.

La question 23. montre qu'on ne peut pas obtenir un meilleur majorant g\'en\'eral dans le cas d'automates d\'eterministes.
\question
Pour deux automates d\'eterministes le majorant trouv\'e est $n+n'-1$. Par d\'eterminisation  on obtient le majorant $2^n+2^{n'}-1$ pour deux automates quelconques. 
  
\end{document}

