summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-03 16:38:11 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-03-03 16:38:11 (GMT)
commit582b317811b947b1f715ca411263f2b9c14a537c (patch)
tree808a99c3e128959362a856e1efcc3fbc54424ed6
parent3a16ca949de222d612c899b6c692de727e96ec7f (diff)
downloadinf105-582b317811b947b1f715ca411263f2b9c14a537c.zip
inf105-582b317811b947b1f715ca411263f2b9c14a537c.tar.gz
inf105-582b317811b947b1f715ca411263f2b9c14a537c.tar.bz2
Add various comments on exam.
-rw-r--r--controle-20170207.tex87
1 files changed, 84 insertions, 3 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex
index 0a77b4e..2d09bc0 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -52,6 +52,11 @@
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
@@ -110,7 +115,7 @@ Durée : 1h30
Barème \emph{indicatif} : 8 points par exercices
\ifcorrige
-Ce corrigé comporte 10 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
@@ -426,6 +431,33 @@ pouvait utiliser directement ce raisonnement pour produire
l'expression.)
\end{corrige}
+\begin{commentaire}
+(0) De nombreuses copies parlent d'« automate déterministe à
+ transitions spontanées ». Cette notion n'existe tout simplement
+ pas et n'a pas de sens.
+
+(1b) De nombreuses erreurs dans la manipulation des automates, qui
+ auraient pu être attrapées par l'utilisation ce ces mots-tests ne
+ l'ont pas été, et c'est dommage (ces erreurs ont été comptées plus
+ sévèrement).
+
+(3) La consigne sur la présentation de l'automate a été presque
+ universellement ignorée (pourquoi ?).
+
+(5) De nombreuses copies essaient de construire un automate
+ reconnaissant $\overline{L}$ autrement qu'en échangeant états finaux
+ et non-finaux dans un automate \underline{déterministe complet}.
+
+(6) Beaucoup de gens croient à tort que la négation de « contenir
+ unique $a$ ou bien contenir un unique $b$ » est « être le mot vide
+ ou bien contenir au moins deux $a$ ou bien au moins deux $b$ » :
+ le mot $aab$ de la question (1b) aurait dû permettre d'éviter cette
+ erreur. À l'inverse, certains croient que cette négation est « être
+ le mot vide ou bien contenir au moins deux $a$ \emph{et} au moins
+ deux $b$ » : le mot $aa$ aurait dû permettre d'éviter cette
+ erreur.
+\end{commentaire}
+
%
%
@@ -542,7 +574,7 @@ ne termine pas sur $x$, alors $L_T = \Sigma^*$. L'utilisation de
$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine
sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.
-Variante de la même idée : on appelle « trace d'exécution » de $S$ sur
+\textit{Variante de la même idée :} on appelle « trace d'exécution » de $S$ sur
$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
courant et le contenu du ruban à chaque étape), du début à l'arrêt.
@@ -559,6 +591,13 @@ algorithmiquement si $S$ termine sur $x$, ce qui contredit
l'indécidabilité du problème de l'arrêt.
\end{corrige}
+\begin{commentaire}
+Cet exercice a été très peu traité, ce qui est dommage car la
+question (1) consistait essentiellement à dire « oui : on a vu dans le
+ cours tous les algorithmes nécessaires ».
+\end{commentaire}
+
+
%
%
@@ -664,7 +703,22 @@ L(T)^*$ où « $*$ » est l'étoile de Kleene. (Si on veut, la règle $S
préservée par toute dérivation immédiate pour $G$ puisqu'elle est
préservée en remplaçant $S$ par $TS$ ou par le mot vide et en
remplaçant $T$ par $aSbSc$. Elle est donc vérifiée pour tout mot de
-$L(S)$ (et en particulier, pour tout mot de $L(T)$).
+$L(S)$ (et en particulier, pour tout mot de $L(T)$), ce qu'il fallait
+démontrer.
+
+\textit{Autre possibilité :} il suffit de montrer $|w|_a = |w|_b =
+|w|_c$ pour tout mot $w\in L(S)$ (puisque $L(T) \subseteq L(S)$) : on
+va procéder par récurrence sur la longueur $|w|$. D'après (1), on
+peut écrire $w = u_1\cdots u_k$ avec $u_i\in L(T)$ : si $k>1$, alors
+chaque $u_i$ est de longueur strictement plus petite, donc l'hypothèse
+de récurrence assure que la propriété est vraie pour eux, donc elle
+l'est pour $w$ car $|w|_x = \sum_{i=1}^k |u_i|_x$ pour chaque
+$x\in\{a,b,c\}$. Reste le cas $k=1$, c'est-à-dire, $w\in L(T)$ : mais
+on a alors (toujours d'après (1)) $w = avbv'c$ avec $v,v'\in L(S)$ qui
+sont de longueur strictement plus petite que $w$, donc l'hypothèse de
+récurrence assure que la propriétée st vraie pour $v$ et $v'$, et
+comme $|w|_x = 1 + |v|_x + |v'|_x$ pour chaque $x\in\{a,b,c\}$, on a
+la propriété voulue pour $w$.
\smallbreak
@@ -729,6 +783,33 @@ conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le
$a$ initial et le $c$ final.
\end{corrige}
+\begin{commentaire}
+(3) Les deux démonstrations proposées dans le corrigé ci-dessus ont
+ effectivement été trouvées (rédigées de façon généralement
+ incorrecte, mais on n'a pas sanctionné trop sévèrement les
+ imprécisions).
+
+(4) Malgré la note \ref{prefix-note} en bas de page, la plupart des
+ copies pensent qu'un préfixe de $au_1\cdots u_k bu'_1\cdots u'\ell
+ c$ est de la forme $au_1\cdots u_i$ ou bien $au_1\cdots u_k
+ bu'_1\cdots u'_i$, et oublient que le dernier facteur peut lui-même
+ être coupé (c'était bien ça le sens de la note). Cette erreur n'a
+ pas été sanctionnée trop sévèrement.
+
+(5) Cette question comportait deux sous-questions. La première (si
+ $u\in L(T)$ et $v$ préfixe de $u$ différent de $u$ alors $v\not\in
+ L(T)$) a été correctement traitée à ceci près que beaucoup oublient
+ le cas $v=\varepsilon$ qui n'était pas couvert par la question (4) ;
+ la seconde (concernant les préfixes de $uz$) a été souvent oubliée,
+ et certains oublient de considérer le cas d'un préfixe de
+ longueur $>|u|$.
+
+En outre, pour l'application à la question (6), certains parlent de
+« unique préfixe de $w$ » pour « unique préfixe de $w$ qui appartienne
+ à $L(T)$ ». Il n'est pas clair s'il s'agit d'une confusion ou d'un
+oubli.
+\end{commentaire}
+
%