\input exos.mac
\doublecrochets
\guillemets
%----------------------------------------------------------------------
\ex Ens ULM-Lyon-Cachan MP$^*$ 2003

\qq Soit~$A$ un alphabet fini contenant au moins deux lettres distinctes.
    Soit~$L$ le langage des palindromes sur~$A$. $L$ est-il régulier~?
    \reponse{Non, il contredit le lemme de l'étoile.}
\qq Proposer un algorithme déterministe prenant en entrée un automate
    quelconque~$\cal A$ et déterminant si~$\cal A$ reconnaît un palindrome.
    \reponse{\def\A{{\cal A}}\def\tr{\mathop{\longrightarrow}\limits}%
    Former l'automate $\A'$ ayant pour états les couples $(q,q')$ où
    $q$ et $q'$ sont des états de~$\A$ et pour transitions
    $(q,q')\tr^a(r,r')$ avec $q\tr^aq'$ et $r'\tr^ar$ dans~$\A$.
    On prend comme états initiaux de~$\A'$ les couples $(i,f)$ où $i$
    est l'état initial et $f$ un état final de~$\A$.
    Soit $u$ un mot quelconque. On a un chemin $(i,f)\tr^u(q,q')$ dans~$\A'$
    si et seulement si $i\tr^uq$ et $q'\tr^{\tilde u}f$ sont des chemins
    dans~$\A$. Ainsi, le langage $L(\A)$ contient un palindrome de longueur
    paire $u\tilde u$ si et seulement s'il existe un chemin dans~$\A'$
    de la forme $(i,f)\tr^*(q,q)$ et $L(\A)$ contient un palindrome
    de longueur impaire $ua\tilde u$ si et seulement s'il existe dans~$\A'$
    un chemin de la forme $(i,f)\tr^*(q,q')$ avec $q\tr^aq'$ dans~$\A$.}
   

%----------------------------------------------------------------------
\ex Ens Cachan MP$^*$ 2003

\qq Soit~$n\in\N^*$. On considère l'automate
    ${\cal A} = (I=\{0\}, F=\{0\}, Q = \{0,1,\dots,n-1\}, \delta)$
    où $\delta$ est définie par les triplets suivants (état,lettre,état)~:
    $$\{(i,0,i),\ i\ge 1\}\cup\{(i,0,0),\ i\ge 1\}\cup\{(i,1,i+1),\ i\le n-2\}\cup\{(n-1,1,0)\}.$$
    Montrer que l'automate déterministe obtenu par la méthode du cours
    comporte $2^n$ états.
    \reponse{Soit~$X$ un ensemble d'états accessibles construit lors de l'algorithme de
    déterminisation. Alors $X\cup\{0\}$ et l'image de~$X$ par la permutation
    circulaire $0\->1\->\dots\->n-1\->0$ seront aussi construits lors de cet
    algorithme. Et tout sous-ensemble de~$\{0,\dots,n-1\}$ peut être obtenu
    à partir de~$\vide$ par un nombre fini de ces transformations (récurrence
    sur le cardinal).
    \sv
    Remarque~: le programme officiel n'impose pas de méthode de déterminisation,
    il pourrait y avoir d'autres algorithmes que celui des sous-ensembles.
    \sv
    Remarque~: un mot~$u$ est reconnu par~$\cal A$ si et seulement s'il est
    constitué de~$0$ et de~$1$ et s'il se termine par un $0$ ou si le nombre
    d'occurences  de la lettre $1$ est nul ou au moins égal à~$n$.
    On construit facilement un automate déterministe à~$n+1$ états reconnaissant
    ce langage.\sv}

\qq On considère le langage~$L_n$ des mots sur~$A=\{a,b\}$ tels que
    la~$n$-ème lettre avant la fin soit un~$a$. Montrer que tout automate
    déterministe reconnaissant~$L_n$ comporte au moins $2^n$ états.
    \reponse{Si $u\in(a+b)^n$ alors la connaissance du résiduel
    $u^{-1}L_n = \{v\in(a+b)^*\text{ tq }uv\in L_n\}$ permet de déterminer~$u$~:
    la $k$-ème lettre de~$u$ est un~$a$ si et seulement si $ua^{n-k}\in L_n$.
    Si un automate~$\cal A$ déterministe reconnaît~$L_n$ alors $\cal A$
    a au moins autant d'états qu'il y a de mots distints dans~$(a+b)^n$, soit~$2^n$.}

%----------------------------------------------------------------------
\ex Ens ULM-Lyon-Cachan MP$^*$ 2003
On appelle {\it langage local sur un alphabet~$A$} un langage de la forme
$L = (XA^* \cap A^*Y)\setminus (A^*VA^*)$ où $X\subset A$, $Y\subset A$, $V\subset A^2$.
\qq Prouver qu'un tel langage est reconnaissable.
    \reponse{Cours.}
\qq Donner un exemple non trivial de langage reconnaissable non local.

    {\it La réponse "Aucun langage local ne contient $\varepsilon$ donc $L=A^*$ est un contre-exemple"
    a été refusée (trop facile). L'examinatrice suggère $L=(ab)^*(ac)^*$ sur l'alphabet $\{a,b,c\}$.}
    \reponse{Si $L = (XA^* \cap A^*Y)\setminus (A^*VA^*)$ alors $X=\{a\}$ (seule première lettre
    possible), $Y=\{b,c\}$ (dernières lettres possibles) et $V=\{aa,bb,cc,bc,cb\}$ (doublets exclus).
    Et \c ca ne marche pas, $acab\in(XA^* \cap A^*Y)\setminus (A^*VA^*)$.}
\qq Prouver qu'un langage local sur un alphabet à~$n$ lettres peut être reconnu
    par un atuomate déterministe complet à~$n+2$ états.
    \reponse{On prend un état initial $I$, un état rebut $R$, et un état $x$ pour
    chaque lettre de~$A$. Puis on place les transitions $x\->^yy$ pour toutes lettres
    $x,y$ telles que $xy\notin V$, les transitions $I\->^xx$ pour toutes les lettres
    de~$X$, on fait pointer les transitions manquantes vers l'état rebut.
    Les états acceptants sont ceux étiquetés par une lettre de~$Y$.}
\qq Montrer que si~$R\subset A^*$ est reconnaissable alors il existe un alphabet~$B$
    un langage $L\subset B^*$ local et une application $\app\varphi B A$ tel que $\varphi^*(L)=R$
    avec $\application {\varphi^*}{B^*}{A^*}{u=b_1\dots b_n}{\varphi^*(u) = \varphi(b_1)\dots\varphi(b_n).}$
    \reponse{Soit $\cal A$ un automate déterministe reconnaissant~$R$ et $Q$ l'ensemble
    des états de~$\cal A$. On prend $B = Q\times A\times Q$ et $\varphi(q,a,q') = a$.
    Un mot de~$B^*$ représente un chemin dans l'automate~$\cal A$ si et seulement s'il
    est de la forme~: $$u=(q_1,a_1,q_2)(q_2,a_2,q_3)\dots(q_{n-1}a_{n-1}q_n),\qquad q_i\in Q,\ a_i\in A$$
    et dans ce cas $\varphi^*(u) = a_1\dots a_n$ est le mot étiquetant ce chemin.
    Soit $L$ l'ensemble des mots~$u$ tels que $\varphi^*(u)\in R$.
    Comme $\varphi^*$ est surjective, on a $\varphi^*(L) = R$. De plus $L$ est local~:
    $X$ est l'ensemble des transitions autorisées par~$\cal A$ partant de l'état initial de~$\cal A$,
    $Y$ est l'ensemble des transitions aboutissant à un état final de~$\cal A$
    et $V$ est l'ensemble des doublets inacceptables (transitions non définies dans~$\cal A$
    ou état intermétiaire incorrect).}

%----------------------------------------------------------------------
\ex Ens ULM-Lyon-Cachan MP$^*$ 2003
Soit~$\cal G$ un graphe donné par un ensemble~$S$ de sommets et un ensemble~$E$
d'arêtes orientées.

\qq \'Ecrire un algorithme prenant en entrée le graphe~$\cal G$, un sommet~$v_0$,
    et qui renvoie la liste des sommets atteignables en partant de~$v_0$
    (on choisira une représentation des arêtes, puis le programme prendra $E$, $S$, $v_0$
    en entrée). On démontrera la terminaison et la correction de cet algorithme,
    et on calculera sa complexité.
    \reponse{On suppose que les sommets sont étiquetés par les entiers
    de~$[[0,s-1]]$ où $s=\card(S)$. On choisit de représenter~$E$ par une matrice booléenne
    $M\in \M s{\{\text{\tt true,false}\}}$ telle que $M(i,j)$ vaut {\tt true} si et seulement
    s'il existe une arête du sommet~$i$ vers le sommet~$j$. La liste résultat sera représentée
    par un vecteur~$V$ tel que $V(i)$ vaut {\tt true} si et seulement s'il existe un chemin
    dans~$\cal G$ menant de~$v_0$ à~$i$. Algorithme~:
    \sv
    {\it\obeylines V $\<- [\text{false},\dots,\text{false}]$~; $P \<-$ pile vide~; empiler $v_0$.
    Tant que $P$ est non vide~:
    \indent dépiler le sommet $i$ de~$P$ ; $V(i) \<-${\tt true}
    \indent pour $j=0\dots s-1$~: si $M(i,j)$ et non$(V(j))$ alors empiler~$j$~; finpour
    fintantque
    }\sv
    Terminaison et correction~: il y a terminaison car chaque sommet est empilé au plus une fois sur~$P$. La liste $V$
    obtenue ne contient que des sommets accessibles depuis~$v_0$ par récurrence
    sur le nombre d'itérations de la boucle {\it Tant que}. Tout sommet $i$ accessible
    depuis $v_0$ est effectivement placé dans~$V$ par récurrence sur la longueur d'un
    chemin menant de~$v_0$ à~$i$.
    \sv
    Complexité~: chaque sommet dépilé donne lieu à $\O(s)$ opérations, donc la complexité
    est $\O(sN(v_0))$ où $N(v_0)$ est le nombre de sommets accessibles depuis~$v_0$.
    Dans le pire des cas, on a une complexité $\O(s^2)$.\sv}
\qq En déduire un algorithme répondant à la question~: $\cal G$ a-t-il un cycle~?
    \reponse{Dans l'algorithme précédent, il y a un cycle passant par~$v_0$
    si et seulement si l'on dépile un sommet~$i$ tel que $M(i,v_0)$.
    En faisant varier $v_0$ on obtient un détecteur de cycle de complexité
    $\O(s^3)$.\sv}
\qq Trouver un algorithme répondant à la question précédente en $\O(\card E + \card S)$.
    On introduira une fonction $\app\sigma S\N$ telle que~:
    $\forall\ s_1,s_2\in S,\ \vct{s_1s_2}\in E \=>\sigma(s_1)<\sigma(s_2)$.
    \reponse{Une fonction~$\sigma$ telle que décrite dans l'énoncé est appelée~:
    {\it ordre topologique sur~$\cal G$}. On ordonne topologiquement
    un graphe orienté sans cycle en choisissant un sommet sans prédecesseur
    que l'on place en tête de la liste résultat~; on supprime ce sommet du graphe et on
    itère. Si à un moment on ne trouve pas de sommet sans prédecesseur alors il
    y a un cycle.
    \sv
    Mais en fait il n'y a pas besoin de faire tout \c ca~: l'algorithme donné en~{\bf 1)}
    tourne en $\O(\card E + \card S)$ si l'on représente les arrêtes par des
    {\it listes d'adjacence\/} (on note pour chaque sommet la liste de ses successeurs).
    En effet, chaque arrête du graphe est examinée au plus une fois lors de la
    recherche des sommets accessibles à partir de~$v_0$.}

%----------------------------------------------------------------------
\ex Ens Ulm-Lyon MP$^*$ 2003
Soit ${\cal G}$ un graphe connexe non orienté, $S$ l'ensemble des sommets et $A$ l'ensemble des arêtes.
Le degré $d(s)$ d'un sommet~$s$ est le nombre d'arrêtes ayant $s$ comme sommet.
Sur chaque sommet, on place $c(s)$ pions. On obtient alors une configuration $\app c S{\N.}$
\sv
{\bf Règle du jeu~:} si un sommet $s$ possède au moins $d(s)$ pions, on
distribue un pion à chacun de ses voisins, obtenant ainsi une nouvelle configuration~$c'$.
On note $c\->^sc'$ et on dit que~$s$ a été joué.
\sv
\qq Écrire un algorithme qui joue tant qu'il peut.
\qq Montrer que si une partie est infinie, alors tous les sommets sont joués
    une infinité de fois.
    \reponse{Sinon, l'ensemble $E$ des sommets joués une infinité de fois
    s'appauvrit d'au moins un pion à chaque fois qu'on joue un sommet de~$E$
    ayant un voisin hors de~$E$, et il existe un tel sommet si~$E\ne S$ car
    $\cal G$ est connexe.}
\qq Montrer que si une partie est finie, alors l'un des sommets n'est pas joué.
    \reponse{On note pour~$s\in S$, $n(s)$ le nombre de fois où $s$ a été joué.
    On suppose $n=\min\{n(s),\ s\in S\} >0$ et on considère le sommet
    $s_0\in S$ qui a atteint le premier son compte $n(s_0)$ au cours du jeu.
    Tous les voisins de~$s_0$ ont été joués au moins une fois après que $s_0$
    se soit mis à bouder, donc à la fin de la partie $s_0$ dispose d'un capital
    suffisant pour redonner un pion à chacun de ses voisins, contradiction.}
\qq Donner une condition nécessaire sur le nombre de pions pour qu'il existe
    une partie finie.
    \reponse{Le nombre total de pions, $\sum_{s\in S}c(s)$, est invariant au cours d'une partie.
    Lorsqu'on arrive à la fin d'une partie, chaque sommet a strictement moins de pions
    que son degré, d'où~: ${\dsum_{s\in S}(d(s)-c(s)) \ge \card(S)}$.}
\qq Montrer que si une partie est finie alors toutes les autres parties possibles
    à partir de la même configuration initiale sont aussi finies et aboutissent à
    la même configuration finale.
    \reponse{On démontre par récurrence sur~$n\in\N$ la proposition suivante~:
    {\it Soit $c$ une configuration et $P$ une partie commen\c cant avec~$c$
    finie de longueur~$n$. Alors toute partie~$Q$ commen\c cant avec~$c$ est
    finie et aboutit à la même configuration $c'$ que~$P$.}
    \sv
    Le cas~$n=0$ est trivial. Dans le cas où $n\ge 1$, soit $s_0$ le
    premier sommet joué au cours de~$P$ et $s_1,\dots,s_k$ les sommets joués
    au cours de~$Q$ avant $s_0$ (on doit jouer $s_0$ dans~$Q$ sinon $Q$ serait finie
    et dans la configuration finale de~$Q$ le sommet~$s_0$ aurait un capital de pions
    supérieur ou égal à~$c(s_0)\ge d(s_0)$, impossible). Au lieu de jouer
    $s_k$ puis $s_0$, on peut jouer $s_0$ puis $s_k$ car les deux sommets
    ont suffisament de pions pour cela et le compte de pions pour chaque sommet
    après ces deux coups est le même. De proche en proche, on peut ramener $s_0$
    en tête des coups joués, ce qui donne une nouvelle partie~$R$ qui aboutit
    à la même configuration que $Q$ après les~$k+1$ premiers coups. En particulier
    $R$ est finie ou infinie comme~$Q$, et le cas échéant les configurations
    finales de~$Q$ et~$R$ sont égales. Mais $R$ commence par le même premier coup
    que~$P$, donc l'hypothèse de récurrence à l'ordre $n-1$ s'applique aux
    parties $P'$, $R'$ de~$P$ et~$R$ qui suivent ce premier coup.}

%----------------------------------------------------------------------
\ex Ens Ulm-Lyon MP$^*$ 2003
Soit~$A$ un tableau de~$n$ entiers relatifs. On veut trouver le sous-tableau connexe de~$A$
dont la somme des éléments est maximale, c'est-à-dire $i\le j$ tels que $\dsum_{k=i}^jA[k]$ est maximal.
\qq Donner un algorithme simple résolvant le problème.
    \reponse{Calculer toute les sommes et retenir les indices fournissant la plus grande.}
\qq \'Evaluer sa complexité.
    \reponse{$O(n^3)$ si l'on recalcule chaque somme à partir de zéro.
    On peut faire $O(n^2)$ en calculant de proche en proche toutes les sommes
    qui commencent au même indice~$i$.}
\qq Donner un nouvel algorithme utilisant la méthode "diviser pour régner".
    \reponse{On partage le tableau en deux moitiés, on cherche récursivement
    dans chaque moitié~: la plus grande sous-somme, la plus grande sous-somme
    commen\c cant au début, la plus grande sous-somme se terminant à
    la fin et la somme totale de la moitié considérée. Ces huit informations permettent de
    déterminer en temps constant les quatre renseignements associés pour le tableau complet.}
\qq Quelle est sa complexité~?
    \reponse{linéaire.}


\answerwrite{\xe\SV}\xe\SV
\bye