diff options
| -rw-r--r-- | exercices-inf110.tex | 235 |
1 files changed, 235 insertions, 0 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index 10149c1..59fd82a 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -579,6 +579,241 @@ $f$ est calculée en complexité en temps p.r., donc elle est elle-même p.r. \end{corrige} +% + +\exercice\label{exercice-tableaux-fonctions-p-r}\ (${\star}{\star}$) + +On s'intéresse à des tableaux d'entiers naturels, indicés par les +entiers naturels, dont toutes les valeurs valent $0$ sauf un nombre +fini (i.e., des fonctions $\tau \colon \mathbb{N} \to \mathbb{N}$ dont +le support $\{i \in \mathbb{N} : \tau(i) \neq 0\}$ est fini). Un tel +tableau $\tau$ sera Gödel-codé comme un entier naturel sous la forme +(disons) de la liste $\dbllangle \langle i_1,\tau(i_1)\rangle, \ldots, +\langle i_k,\tau(i_k)\rangle \dblrangle$ où $i_1 < i_2 < \cdots < i_k$ +sont les indices tels que la valeur $\tau(i)$ dans le tableau à cet +indice soit $\neq 0$. + +\textbf{(1)} Sans rentrer dans énormément de détails, expliquer +pourquoi la fonction $(\tau,i) \mapsto \tau(i)$ (« lecture du tableau +$\tau$ à l'indice $i$ ») et $(\tau,i,v) \mapsto \tau'$ où $\tau'(j) = +\tau(j)$ sauf $\tau'(i) = v$ (« modification du tableau $\tau$ à +l'indice $i$ pour y mettre la valeur $v$ ») sont primitives +récursives. + +\textbf{(2)} Sans rentrer dans énormément de détails, en déduire +pourquoi, du coup, un algorithme primitif récursif peut utiliser un +tableau dans une boucle où elle lit et écrit des valeurs arbitraires +du tableau. + +\begin{corrige} +\textbf{(1)} La fonction de lecture $(\tau,i) \mapsto \tau(i)$ +consiste à parcourir tous les couples de la liste $\dbllangle \langle +i_1,\tau(i_1)\rangle, \ldots, \langle i_k,\tau(i_k)\rangle \dblrangle$ +qui représente le tableau et, pour chacune, comparer $i$ à la première +composante et, s'il y a égalité, renvoyer la seconde composante, sinon +renvoyer $0$. La boucle est bornée a priori car elle parcourt une +liste connue (dont la longueur est majorée par le numéro qui la code). +Comme le décodage des couples (et donc des listes) est primitif +récursif, tout ceci est primitif récursif. + +La fonction d'écriture $(\tau,i,v) \mapsto \tau'$ consiste à parcourir +la liste qui représente le tableau, et si on a $i = i_r$, modifier la +seconde composante du couple correspondant, tandis que si on a $i_r < +i < i_{r+1}$ (ou $i < i_0$ ou $i > i_k$) on insère un nouveau couple : +comme l'encodage et le décodage des couples (et notamment l'insertion +d'un élément dans une liste) sont primitifs récursifs, tout ceci est +primitif récursif. + +\textbf{(2)} Le tableau est codé sous forme d'entier naturel comme on +l'a dit, donc il devient une simple variable de boucle, sur laquelle +on peut effectuer des lectures et modifications par les fonctions +qu'on a expliquées (et qui sont primitives récursives). Le fait de +disposer d'une variable dans une boucle (bornée !) pour un algorithme +primitif récursif est bien permis (essentiellement par la récursion +primitive, qui permet précisément la modification d'une variable à +chaque tour de boucle). +\end{corrige} + +% + +\exercice\ (${\star}{\star}{\star}$) + +On rappelle la définition de la fonction d'Ackermann $A\colon +\mathbb{N}^3 \to \mathbb{N}$ : +\[ +\begin{aligned} +A(m,n,0) &= m+n \\ +A(m,0,1) &= 0 \\ +A(m,0,k) &= 1\text{~si~}k\geq 2 \\ +A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k) +\end{aligned} +\] +On a vu en cours que cette fonction est calculable mais non primitive +récursive. On admettra sans discussion que $A(m,n,k)$ est croissante +en chaque variable dès que $m\geq 2$ et $n\geq 2$. On pourra aussi +utiliser sans discussion les faits suivants : +\[ +\begin{aligned} +A(m,n,1) &= mn \\ +A(m,n,2) &= m^n \\ +A(0,n,k) &= ((n+1)\%2)\text{~si~}k\geq 3 \\ +A(1,n,k) &= 1\text{~si~}k\geq 2 \\ +A(m,1,k) &= m\text{~si~}k\geq 1 \\ +A(2,2,k) &= 4 \\ +\end{aligned} +\] + +On considérera aussi la \emph{fonction indicatrice du graphe} de $A$, +c'est-à-dire la fonction $B\colon \mathbb{N}^4 \to \mathbb{N}$ : +\[ +\begin{array}{ll} +B(m,n,k,v) = 1 &\text{~si~}v = A(m,n,k) \\ +B(m,n,k,v) = 0 &\text{~sinon} \\ +\end{array} +\] + +\textbf{(1)} Écrire un algorithme qui calcule $A(m,n,k)$ à partir de +$m$, $n$, $k$ et d'un \emph{majorant} $b$ de $A(m,n,k)$ selon le +principe suivant : si $m\geq 2$ et $n\geq 2$, pour chaque $\ell$ +allant de $0$ à $k$ et chaque $i$ allant de $0$ à $b$ (bien noter : +c'est $b$ et pas $n$ ici), on calcule $A(m,i,\ell)$, et on la stocke +dans la case $(i,\ell)$ d'un tableau, à condition que les valeurs déjà +calculées et contenues dans le tableau permettent de la calculer (pour +les petites valeurs $m\leq 1$ ou $n\leq 1$ on utilise les formules +données ci-dessus ; sinon, on essaye d'utiliser la formule de +récurrence en consultant le tableau). Expliquer pourquoi la valeur +$A(m,n,k)$ est bien calculée par cet algorithme. + +\textbf{(2)} Expliquer pourquoi l'algorithme qu'on a écrit en (1) est +primitif récursif (on pourra prendre connaissance des conclusions de +l'exercice \ref{exercice-tableaux-fonctions-p-r}). + +\textbf{(3)} En déduire que la fonction $B$ est primitive récursive. + +(Autrement dit, on ne peut pas calculer $A$ par un algorithme p.r., +mais on peut \emph{vérifier} sa valeur, si elle est donnée en entrée, +par un tel algorithme.) + +\begin{corrige} +\textbf{(1)} On commence par remarquer que les « petites valeurs » +$m\leq 1$ ou $n\leq 1$ de la fonction d'Ackermann, se calculent +facilement par des formules de l'énoncé. + +L'algorithme calculant $A(m,n,k)$ est alors le suivant. Si $m\leq 1$ +ou $n\leq 1$ on peut facilement calculer la valeur comme on vient de +l'expliquer, donc on se place dans le cas $m \geq 2$ et $n \geq 2$. +(Notons aussi que toute valeur de la fonction d'Ackermann pour $m\geq +1$ est non nulle, ce qui nous permet d'utiliser $0$ pour représenter +« non calculé » dans le tableau.) + +On initialise un tableau $\tau$ de deux indices, $i,\ell$, +initialement rempli de $0$, qui servira à stocker les valeurs de la +fonction d'Ackermann $A(m,i,\ell)$. Pour chaque $\ell$ allant de $0$ +à $k$ et chaque $i$ allant de $0$ à $b$, on calcule $A(m,i,\ell)$ de +la manière suivante : si $i\leq 1$ ou $\ell=0$ on utilise la formule +évoquée ci-dessus et stocke la valeur dans le tableau ; sinon, on +consulte le tableau en $(i-1,\ell)$ et, si cette valeur $u$ est +définie (c'est-à-dire non nulle), on consulte le tableau en +$(u,\ell-1)$ et, si cette valeur $w$ est définie, on la stocke dans le +tableau en $(i,\ell)$. + +Autrement dit : +\begin{itemize} +\item si $m\leq 1$ ou $n\leq 1$, calculer facilement $A(m,n,k)$ et + renvoyer sa valeur ; sinon : +\item initialiser un tableau $\tau$ (d'indices $i$ allant de $0$ à $b$ + et $\ell$ allant de $0$ à $k$, et initialement rempli de $0$), +\item pour $\ell$ allant de $0$ à $k$, +\begin{itemize} +\item pour $i$ allant de $0$ à $b$, +\begin{itemize} +\item si $i\leq 1$ ou $\ell=0$, calculer facilement $w := A(m,i,\ell)$ + et stocker $\tau(i,\ell) \leftarrow w$, +\item sinon, consulter $u := \tau(i-1,\ell)$, +\item si $u \neq 0$, consulter $w := \tau(u,\ell-1)$, +\item si $w \neq 0$, stocker $\tau(i,\ell) \leftarrow w$. +\end{itemize} +\end{itemize} +\item finalement : renvoyer $\tau(k,n)$ si elle est $>0$, sinon + « échec ». +\end{itemize} + +En Python, avec de petites variations : + +{\tt +\noindent +def ackermann\_small(m,n,k):\\ +\strut\quad \# Returns A(m,n,k) value if m<=1 or n<=1 or k<=2\\ +\strut\quad if k==0: return m+n\\ +\strut\quad if k==1: return m*n\\ +\strut\quad if k==2: return m**n\\ +\strut\quad if n==0: return 1\\ +\strut\quad if n==1: return m\\ +\strut\quad if m==0: return (n+1)\%2\\ +\strut\quad if m==1: return 1\\ +\\ +def ackermann\_bounded(m,n,k,b):\\ +\strut\quad \# Returns A(m,n,k) (at least) if its value is <=b\\ +\strut\quad if m<=1 or n<=1: return ackermann\_small(m,n,k)\\ +\strut\quad tab = \{\}\\ +\strut\quad for l in range(k+1):\\ +\strut\quad \strut\quad for i in range(b+1):\\ +\strut\quad \strut\quad \strut\quad if l==0 or i<=1:\\ +\strut\quad \strut\quad \strut\quad \strut\quad w = ackermann\_small(m,i,l)\\ +\strut\quad \strut\quad \strut\quad \strut\quad tab[(i,l)] = w\\ +\strut\quad \strut\quad \strut\quad else:\\ +\strut\quad \strut\quad \strut\quad \strut\quad if (i-1,l) in tab:\\ +\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad u = tab[(i-1,l)]\\ +\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad if (u,l-1) in tab:\\ +\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad w = tab[(u,l-1)]\\ +\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad tab[(i,l)] = w\\ +\strut\quad if (n,k) in tab:\\ +\strut\quad \strut\quad return tab[(n,k)] +} + +L'algorithme repose sur la formule $A(m,i,\ell) = +A(m,A(m,i-1,\ell),\ell-1)$ (qui est une simple réécriture de la +troisième ligne de la définition), où on a appelé $u = A(m,i-1,\ell)$ +et $w = A(m,u,\ell-1)$ : cete formule montre que si les valeurs +$(i-1,\ell)$ et $(u,\ell-1)$ sont trouvées dans le tableau, la valeur +$A(m,i,\ell)$ sera correctement calculée. + +Or on montre par récurrence sur $\ell$ et $i$ que toutes les valeurs +pour lesquelles $A(m,i,\ell) \leq b$ (ou bien $i\leq 1$ ou $\ell=0$) +seront effectivement calculées par l'algorithme : en effet, si +$A(m,i,\ell) \leq b$, alors par la croissance en la deuxième variable +de la fonction d'Ackermann, $u := A(m,i-1,\ell)$ est lui-même $\leq b$ +(ou alors $i=1$), donc aura été correctement calculé avant +$A(m,i,\ell)$, et $A(m,u,\ell-1)$ aura été calculé et stocké dans le +tableau puisque la boucle sur $\ell$ est extérieure à celle sur $i$ et +que la valeur $u$ est dans les bornes de la boucle sur $i$. + +En particulier, si $b$ est un majorant de la valeur $A(m,n,k)$ qu'on +cherchait, alors l'algorithme renvoie $A(m,n,k)$. + +\textbf{(2)} L'algorithme qu'on a décrit ci-dessus ne fait aucun appel +récursif et n'utilise que des boucles bornées (deux boucles +imbriquées). L'utilisation d'un tableau est justifiée par +l'exercice \ref{exercice-tableaux-fonctions-p-r}. On a donc bien +défini une fonction primitive récursive. + +\textbf{(3)} L'algorithme qu'on a décrit calcule de façon primitive +récursive en $m,n,k,b$ la valeur $A(m,n,k)$ si tant est que celle-ci +est $\leq b$. En particulier, pour calculer $B(m,n,k,v)$ il suffit +d'appliquer cet algorithme à $m,n,k,v$ (c'est-à-dire avec $v$ lui-même +comme borne) et, s'il renvoie une valeur $w$, tester si $v=w$ : si +c'est le cas on renvoie « oui » (enfin, $1$), sinon, ou si +l'algorithme n'a pas réussi à caluler $A(m,n,k)$ on renvoie « non » +(enfin, $0$). La fonction $B$ est donc primitive récursive. + +(On dit parfois abusivement que la fonction d'Ackermann a un graphe +primitif récursif pour dire que la fonction indicatrice de son graphe +est primitive récursive. On comparera à +l'exercice \ref{exercice-graphe-calculable} d'après lequel une +fonction dont la fonction indicatrice du graphe est calculable, i.e., +générale récursive, est elle-même calculable, i.e., générale +récursive.) +\end{corrige} % |