diff options
| -rw-r--r-- | controle-20180206.tex | 63 |
1 files changed, 60 insertions, 3 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex index c4aadc5..e384481 100644 --- a/controle-20180206.tex +++ b/controle-20180206.tex @@ -24,9 +24,9 @@ \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\thingy{% -\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% -\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}} \renewcommand{\qedsymbol}{\smiley} % \DeclareUnicodeCharacter{00A0}{~} @@ -110,7 +110,7 @@ Durée : 1h30 Barème \emph{indicatif} : 7 points par exercice \ifcorrige -Ce corrigé comporte 9 pages (page de garde incluse) +Ce corrigé comporte 10 pages (page de garde incluse) \else Cet énoncé comporte 4 pages (page de garde incluse) \fi @@ -506,6 +506,18 @@ s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$ que $@$ s'associe à droite. \end{corrige} +\begin{commentaire} +Beaucoup de copies affirment, par exemple, que l'opération $\#$ est +prioritaire sur $@$ parce que $\#$ est plus haut dans l'arbre ou se +rencontre en premier dans l'analyse : en réalité, l'opération +prioritaire est celle qui se calcule en premier, c'est-à-dire de la +façon la plus \emph{profonde} (on a précisé que $\boxtimes$ est +prioritaire sur $\boxplus$ lorsque « $u\boxtimes v\boxplus w$ » se +comprend comme « $(u\boxtimes v)\boxplus w$ » : c'est bien $\boxtimes$ +qui est imbriqué le plus profondément dans les parenthèses, et la +comparaison avec l'arbre (e) aurait dû lever tout doute). +\end{commentaire} + \smallskip (La question (3) est indépendante de (1) et (2). Par ailleurs, on @@ -570,6 +582,27 @@ rationnel ?\quad (c) Le langage $L$ est-il rationnel ? pas rationnel. \end{corrige} +\begin{commentaire} +Dans la question (a), beaucoup de copies montrent correctement une +seule implication (que tout mot de la forme « ${(}^i\, x\, {)}^j$ » +appartient à $L\cap M$, ou bien que tout mot de $L\cap M$ a cette +forme), mais oublient qu'il est essentiel de traiter les deux. + +Pour ce qui est de la question (b), certains se sont rendu la vie +inutilement compliquée en prenant certes un mot de la forme $a^i x +b^i$ mais en ne choisissant pas $i=k$ (ou au moins $i\geq k$), ce qui +oblige à des discussions de cas qui n'avaient pas lieu d'être. On +rappelle donc que lorsqu'on applique le lemme de pompage, on choisit +le mot $t$ auquel on va appliquer la propriété (la seule contrainte +étant de devoir prendre $|t|\geq k$). + +La question (c) a été étonnamment peu traitée eu égard à sa +simplicité. Beaucoup ne montrent pas, ne pensent pas à montrer, ou ne +savent pas montrer, que $M$ est rationnel (ce qui devrait pourtant +sauter aux yeux...). Certains arrivent à des conclusions fantaisistes +comme « $L$ est rationnel ». +\end{commentaire} + % % @@ -660,6 +693,18 @@ l'entrée $x$, on ne termine pas non plus). Ceci montre que $L$ est semi-décidable. Le même raisonnement s'appliquer pour $M$. \end{corrige} +\begin{commentaire} +Certains pensent pouvoir déduire la semi-décidabilité de $L$ et $M$ de +celle du problème de l'arrêt : la situation est effectivement proche, +mais à moins d'une explication précise sur le fait qu'on peut calculer +la valeur $\varphi_e(x)$ une fois qu'on s'est assuré qu'elle est bien +définie, ce n'est pas légitime ; d'ailleurs, la semi-décidabilité du +problème de l'arrêt est quelque chose de tellement simple (une fois +acquise l'existence d'une machine universelle) qu'on ne devrait jamais +l'invoquer, car il sera essentiellement toujours plus simple de dire +« il suffit de lancer l'exécution du programme... ». +\end{commentaire} + (5) En imitant la démonstration du théorème de Turing sur l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours @@ -685,6 +730,12 @@ $2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une contradiction. \end{corrige} +\begin{commentaire} +Il n'y a eu à peu près qu'une réponse correcte à cette question. +Quelques points partiels ont été attribués à ceux qui tentaient au +moins de dire quelque chose et qui avaient un semblant d'idée. +\end{commentaire} + (6) Conclure. \begin{corrige} @@ -695,6 +746,12 @@ disjoints et semi-décidables. On a donc bien montré l'existence de langages semi-décidables disjoints et calculablement inséparables. \end{corrige} +\begin{commentaire} +Bien qu'elle fût essentiellement triviale (il suffisait de redire les +résultats des questions précédentes), cette question n'a quasiment pas +été traitée. +\end{commentaire} + \smallskip {\footnotesize (Remarque culturelle :\quad La construction de langages |