Fibonnacci et Zeckendorf

Exercice

On considère la suite de Fibonnacci définie par :
\[F(0) = 0 \text{ et } F(1) = 1\]
\[\forall n \in \mathbb{N}, F(n+2) = F(n+1) + F(n)\]

Étudions quelques algorithmes de calcul de cette suite.

$1.a)$ Écrire un algorithme récursif prenant en entrée un entier $n$ et retournant $F(n)$.

$b)$ Donner une borne inférieure et une borne supérieure de la complexité de cet algorithme.

$c)$ Écrire un algorithme itératif prenant en entrée un entier $n$ et retournant $F(n)$.

$d)$ Quelle est la complexité en temps de cet algorithme ?

$e)$ Exprimer $F(n)$ en fonction de $n$ et en déduire un algorithme calculant $F(n)$ directement. Calculer sa complexité.

$f)$ Calculer la complexité de l’algorithme récursif.

$2.$ Montrer que pour tout entier $n$, on peut trouver $k$ entiers $c_{i}$ tels que $1 \lt c_{1} \lt c_{2} \lt \cdots \lt c_{k}$ et : \[n = \sum\limits_{i=1}^{k} F(c_{i})\]

$3.a)$ Soit un ensemble fini $Z$ de $\mathbb{N} \smallsetminus {0,1}$ qui ne contient pas d’entiers consécutifs. Soit $m$ le maximum de $Z$. Prouver l’inégalité suivante : $F(m+1) \gt \sum\limits_{k \in Z} F(k)$

$b)$ Prouver l’unicité de la décomposition de tout entier comme somme de termes de la suite de Fibonnacci sans termes consécutifs. C’est le théorème de Zeckendorf.

$4.$ Montrer que le langage $\mathcal{L}$ sur l’alphabet ${0,1}$ contenant le mot vide et les mots ne possédant pas deux $1$ consécutifs mais terminant par $1$ est régulier.

Soit $u$ un mot de $\mathcal{L}$ de longueur $|u|$. Pour tout $k \leq |u|$, on pose $u(k) = 0$ si la $k$-ième lettre de $u$ est $0$ et $u(k) = 1$ sinon. Soit $n$ un entier. On dit que $u$ est la représentation de Zeckendorf de $n$ si :

\[n = \sum\limits_{k=1}^{|u|} u(k)F(k+1)\]

Cette représentation est unique.

$5.$ Quelle est la longueur de la représentation d’un entier ?

Correction

$1.$ a) On propose l’algorithme suivant:

algorithme récursif Fibonnacci

b) Soit $T(n)$ le nombre d’opérations nécessaires pour calculer $F(n)$ avec cet algorithme récursif. On a une constante $c$ telle que : \[T(0) = T(1) = c\]

\[\forall n \in \mathbb{N}, T(n+2) = T(n+1) + T(n) +c\]

On a $T(n+1) \geq T(n)$ donc pour $n\geq 2$:

\begin{align*} T(n) & \leq 2T(n-1) + c\\ & \leq 4T(n-2) + 2c + c\\ & \leq 2^{n-1}T(1) + 2^{n-2}c + \ldots + 2c + c T(n)\\ & \leq (2^{n}-1)c \end{align*}

Donc $\displaystyle \boxed{T(n) = O\left(2^{n}\right)}$. Pour la borne inférieure, on effectue un calcul similaire :

\begin{align*}
T(n) & \geq 2T(n-2) + c\\
& \geq 4T(n-4) + 2c + c\\
T(n) & \geq (2^{\left\lfloor \frac{n+2}{2}\right\rfloor}-1)c
\end{align*}

On obtient donc $\displaystyle \boxed{T(n) = \Omega\left(2^{\frac{n+2}{2}}\right)}$.

$c)$ On propose cet algorithme.

algorithme itératif Fibonnacci

$d)$ La création du tableau nous coûte $\Theta(n)$ opérations, chaque appel de boucle nous coûte $\Theta(1)$ et nous effectuons $n-2$ appels. Ainsi, la boucle correspond à $\Theta(n)$ opérations. Ainsi, notre algorithme a une complexité en temps en $\Theta(n)$.

e) Pour trouver la valeur de $F(n)$, nous commençons par résoudre l’équation caractéristique associée : $r^{2}-r-1=0$. Elle a pour solutions $\varphi$ et $\varphi’$ où $\displaystyle \varphi = \frac{1+\sqrt{5}}{2}$ et $\displaystyle\varphi’ = \frac{1-\sqrt{5}}{2}$. On a donc $\alpha$ et $\beta$ tels que :

\[\forall n \in \mathbb{N}, F(n) = \alpha\varphi^{n} + \beta\varphi’^{n}\]

Pour trouver la valeur de $\alpha$ et $\beta$, on considère les conditions initiales : $F(0) = 0$ et $F(1) = 1$.

\[\left\{\begin{matrix} \alpha + \beta = 0 \\ \alpha\frac{1+\sqrt{5}}{2} + \beta\frac{1-\sqrt{5}}{2} = 1\end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} \alpha + \beta = 0 \\ \alpha – \beta = \frac{2}{\sqrt{5}}\end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} \alpha = \frac{1}{\sqrt{5}} \\ \beta = -\frac{1}{\sqrt{5}}\end{matrix}\right. \]

Ainsi $\displaystyle F(n) = \frac{1}{\sqrt{5}}\left(\varphi^{n}-\varphi’^{n}\right)$.

On peut écrire un algorithme renvoyant directement $F(n)$ en utilisant cette formule. Pour cela, on utilise l’exponentiation rapide (voir l’exercice correspondant pour plus d’informations) qui nous donne $\varphi^{n}$ et $\varphi’^{n}$ en $\Theta(\log(n))$ multiplications.Toutefois, il est important de conserver une précision suffisante dans notre calcul.

$f)$ Il existe plusieurs façons de calculer la complexité en temps de notre algorithme récursif. L’idée principale est de montrer que le terme constant est négligeable pour se ramener à l’équation $T(n+2)=T(n+1)+T(n)$ qu’on vient de résoudre. Nous en proposons une schématique.

Nous pouvons tracer l’arbre binaire des appels récursifs successifs à notre fonction. Ainsi, chaque noeud correspond à un appel récursif qui nous coûte $c$, chaque feuille correspond à une exécution de notre fonction sur l’entrée $0$ ou $1$ qui coûte également $c$.

Rendered by QuickLaTeX.com

On note que si on appelle récursivement en $0$ alors on appelle également en $1$. C’est pourquoi, le nombre de feuilles étiquetées par $F(1)$ et supérieur au nombre de feuilles étiquetées par $F(0)$. De plus, $F(n)$ est égal à la somme des valeurs des feuilles qui valent au plus $1$. On a donc entre $F(n)$ et $2F(n)$ feuilles. On rappelle que le nombre de n\oe{}uds internes d’un arbre binaire est égal à son nombre de feuilles moins un. Ainsi, en comptant les feuilles, on a entre $F(n)$ et $4F(n)$ noeuds. De ce fait, la complexité de notre algorithme est comprise entre $F(n)c$ et $4F(n)c$. La question précédente nous permet donc de conclure que la complexité temporelle de l’algorithme récursif est en $\displaystyle \boxed{\Theta\left(\varphi^{n}\right)}$.

$2.$ On procède par récurrence forte sur l’ensemble des entiers naturels pour prouver la propriété $\mathcal{H}(n) = $ « Il existe $k$ entiers $c_{i}$ qui nous conviennent ». Pour $n=0$, il nous suffit de considérer la somme vide.

On suppose la propriété vraie jusqu’au rang $n\geq0$, montrons qu’elle le reste au rang $n+1$. On a $n+1 \geq F(2)$. De ce fait, on peut considérer le plus grand $m\geq2$ tels que $n+1 \geq F(m)$.

Par hypothèse, $\mathcal{H}(n+1-F(m))$ est vraie. Soit $k \in \mathbb{N}$ et $1 \lt c_1 \lt \cdots \lt c_k$ tels que $n+1-F(m) = \sum\limits_{i=1}^{k} F(c_{i})$. On note que pour tout $x \geq 2$, $F(x+1) \lt 2F(x)$. Comme $n+1 \lt F(m+1)$, on obtient $n+1-F(m) \lt F(m)$. Cela signifie donc que $c_k$ est strictement inférieur à $m$. On considère donc la suite $c_1 \lt \cdots \lt c_k \lt m$ qui convient pour $n+1$ ce qui prouve $\mathcal{H}(n+1)$ et achève la récurrence.

$3.$ a) On procède par récurrence forte sur $m$, le maximum de notre ensemble $Z$. La propriété« Tout ensemble $Z$ qui satisfait nos conditions et dont le plus grand élément est $m$ vérifie l’inégalité » est vraie au rang $m=2$ et $m=3$ car $2 \gt 1$ et $3 \gt 2$. On suppose la propriété vraie jusqu’au rang $m\geq2$. Montrons qu’elle le reste au rang $m+1$.

Soit $Z$ un ensemble fini de $\mathbb{N} \smallsetminus {0,1}$, tel que son maximum soit $m+1$ et qu’aucun nombre consécutif ne soit dans $Z$. Le deuxième plus grand élément de $Z$ est au plus $m-1$. De ce fait on a par hypothèse de récurrence et par croissance de $F$, $F(m) \gt \sum\limits_{k\in Z \smallsetminus {m+1}} F(k)$. Donc on a :

\[F(m+2) = F(m+1) + F(m) \gt \sum\limits_{k\in Z} F(k)\]

Ce qui prouve la propriété au rang $m+1$ et achève la récurrence.

$b)$ On procède par récurrence forte, similairement à $2$. On ajoute que par le lemme précédent, pour tout entier n, le plus grand $m$ telle que $F(m) \leq n$ est dans notre séquence et que si $F(m-1)$ est inférieur à $n – F(m)$ on aurait $F(m+1)$ inférieur à $n$, contredisant la définition de $m$.

$4.$ Les langages rationnels sont stables par complémentaires et le langage des mots contenant $11$ est rationnel, comme le montre l’expression $(0+1)^{*}11(0+1)^{*}$. Ainsi, le langage des mots ne contenant pas $11$ est rationnel. De plus, les langages rationnels sont stables par intersection, donc par intersection avec $(0+1)^{*}1$ le langage des mots ne contenant pas $11$ et se terminant par $1$ est rationnel. Enfin, les langages rationnels sont stables par union, donc le langages contenant le mot vide et les mots ne contenant pas $11$ mais se terminant par $1$ est rationnel.

$5.$ La longueur de la représentation de $0$ est $0$ car il s’agit du mot vide. Pour un entier strictement positif n, cette longueur correspond à $m-1$ où $m$ est le plus grand entier tel que $F(m) \lt n$. De plus $\varphi’^{n}$ est négligeable devant $\varphi^{n}$. Ainsi, la longeur de la représentation de $n$ est $\left\lfloor \log_{\varphi}\left(n\right) \right\rfloor$.

Critère de non régularité

On présente ici un critère de non régularité sur les langages. Autrement dit, on s’intéresse à une propriété sur les langages impliquant que ces derniers ne peuvent être reconnus par un automate fini. Cet exercice permet d’avoir une bonne introduction aux Exercice

Soit $\mathcal{L}$ un langage. Soit $(u_i)_{i \in \mathbb{N}}$ une suite infini de mots.

$1)$ Montrer que si pour tout couple $i,j$ il existe un mot $m$ tel que $u_im$ soit dans $\mathcal{L}$ et $u_jm$ ne le soit pas, alors $\mathcal{L}$ n’est pas un langage régulier.

$2)$ En déduire que $L = {\,a^{n}b^{n} \;|\; n \in \mathbb{N}}$ n’est pas régulier.

Correction

$1)$ Notre preuve se base sur l’idée suivante : on considère un automate déterministe $A$, un de ses état $q$ et deux mots $v$ et $w$ tel que lire $v$ ou $w$ nous emmène dans l’état $q$. Pour tout mot $x$, on a $vx$ et $wx$ termine dans le même état de $A$. Autrement dit $vx$ est reconnu par $A$ si et seulement si $wx$ est reconnu par $A$.

Ainsi, soit un automate $\mathcal{A}$ qui reconnaît notre langage $\mathcal{L}$. Soit $u_i$ et $u_j$ deux mots de notre suite. Si on termine dans le même état après avoir lu $u_i$ ou $u_j$, cela signifie que pour tout mot $x$ on a $u_ix$ appartient à $\mathcal{L}$ si et seulement si $u_jx$ appartient à $\mathcal{L}$. Or on sait que ce n’est pas le cas. De ce fait, après lecture de chaque mot de $(u_n)_{n\in\mathbb{N}}$ on arrive dans un état différent de $\mathcal{A}$. Cela implique que $\mathcal{A}$ a une infinité d’état, ce qui est absurde.

Ainsi, $\mathcal{L}$ n’est pas un langage régulier.

$2)$ On s’intéresse à la suite des $(u_{i})_{i \in \mathbb{N}}$ où pour tout $i$, $u_i = a^{i}$. Pour tout $i \neq j$ on a $a^{i}b^{i}$ appartient à $L$ mais $a^{j}b^{i}$ n’appartient pas à $L$. Par notre proposition précédente, il en résulte que $L$ n’est pas régulier.

Exponentiation rapide et algorithme de Hörner

Le but de cet exercice est de calculer des puissances et d’évaluer des polynômes en utilisant le moins de multiplications possible. En effet, si on considère généralement que multiplier deux entiers est une opération élémentaire s’effectuant en $O(1)$, cette considération n’est plus possible lorsqu’on considère la multiplication d’entiers très grand, ou encore la multiplication de matrices.

Exercice

On nous donne en entrée $X$ non nul et $p$ des entiers et on cherche à calculer $X^{p}$. On con.sidère que la multiplication de deux entiers se fait en $O(1)$.

$1)$ Donner la complexité du calcul naïf de $X^{p}$.

$2)$ Si $p \gt 2$ est pair, montrer qu’il n’est pas nécessaire de calculer $X^{p-1}$.

$3)$ Donner un algorithme pour calculer $X^{p}$ en utilisant $O\left(\log(p)\right)$ produits et prouver sa correction.

On veut maintenant écrire un algorithme qui prend en entrée un polynôme $\displaystyle P(X) = \sum\limits_{k=0}^{n}X^{k}p_k$ et un réel et qui nous renvoie le polynôme évalué en ce réel.

$4)$ Proposer une façon de représenter les polynômes.

$5)$ Donner un algorithme naïf d’ évaluation. Combien utilise-t-on d’additions et de multiplications ?

$6)$ En mettant $X$ en facteur, donner un algorithme d’évaluation de polynôme.

$7)$ Donner sa complexité en nombre d’additions et de multiplications.

Correction

$1.$ Le calcul naïf de $X^{p}$ correspond à multiplier $p$ fois $X$. On effectue donc $p-1$ produits. Cela correspond alors à une complexité en $O(p)$

$2)$ Posons $p = 2k$. Si on calcul $X^k$, il nous suffit d’effectuer le calcul $X^{k} \times X^{k}$ pour obtenir $X^{2k} = X^{p}$. Il n’est donc pas nécessaire de calculer $X^{p-1}$.

$3)$ On remarque de même que si $p = 2k+1$, on a $X^{p} = X^{k} \times X^{k} \times X$. De là, on propose donc l’algorithme d’exponentiation suivant.

Algorithme exponentiation rapide

Tout d’abord, on note que $p$ est un entier positif et que l’algorithme s’arrête s’il vaut $0$. De plus, $p$ diminue strictement à chaque nouvel appel de l’algorithme. Ainsi, notre algorithme termine et $p$ est au moins divisé par $2$ à chaque étape. On a donc au plus $O\left(\log(p)\right)$ appels à ExponentiationRapide. De ce fait, ExpoentiationRapide effectue bien $O\left(\log(p)\right)$ produits.

Montrons maintenant par récurrence que notre algorithme est correcte. Soit $\mathcal{P}(n)$ la propriété « ExponentiationRapide($X,p$) calcul $X^{p}$ pour tout entier $X$ non nul et tout entier $p\leq n$. »

On a $\mathcal{P}(0)$ est vrai car pour tout entier $X$ non nul, $X^{0}=1$.

Soit $n \geq 0$. On suppose $\mathcal{P}(n)$. Montrons que $\mathcal{P}(n+1)$ est vraie.

Soit $X$ un entier non nul et $p \leq n+1$. Si $p \leq n$, par hypothèse de récurrence, ExponentiationRapide($X,p$) est bien égale à $X^{p}$. Si $p = n+1$, et que $p$ est impair, on a $k \geq 0$ tel que $p = 2k+1$. Par hypothèse de récurrence, ExponentiationRapide($X,k$) calcul $X^{k}$. De ce fait, ExponentiationRapide($X,p$) calcule bien $X^{p}$. Il en va de même si $p$ est pair.

$4)$ On peut représenter un polynome par une liste de ses coefficients. Ainsi, en indiçant notre liste à partir de $0$, on représente $P$ par une liste $L$ à $n+1$ éléments avec $L[i] = p_i$. L’avantage de ce système est qu’il n’est pas nécessaire de stocker le degré du polynôme.

$5)$ On propose l’algorithme d’évaluation de polynôme suivant.

Algorithme évaluation polynôme naïf.

L’invariant de boucle a considéré pour prouver la correction de notre algorithme est qu’après chaque boucle, Total égale $\displaystyle \sum\limits_{i=0}^{k} x^{i}p_i$.

On utilise donc $n-1$ multiplications pour calculer les puissances de $X$ et $n$ pour calculer les $x^{i}p_i$ avec $i \geq 1$. Ce qui fait alors $2n-1$ multiplications. Pour l’addition, on en effectue une par passage dans la boucle, donc $n$.

$6)$ On remarque la chose suivante :

\begin{align*} P(X) & = p_0 + Xp_{1} + \ldots + X^{n-1}p_{n-1} + X^{n}p_n\\ & = p_0 + X\left(p_{1} + \ldots + X^{n-2}p_{n-1} + X^{n-1}p_n\right)\\ P(X) & = p_0 + X\left(p_1 + X\left(\ldots + X\left(p_n-1 + Xp_n\right)\ldots\right)\right) \end{align*}

Pour $ i \leq n$, on définit les polynômes $P_i$ tel que $\displaystyle P_i(X) = \sum\limits_{k=i}^{n} X^{k-1}p_k$. On a alors, $P(X) = P_0(X)$. Et pour tout $i \lt n $, $P_i(X) = p_i + XP_{i+1}(X)$.

On peut donc proposer l’algorithme de Hörner d’évaluation des polynômes.

Algorithme d'Hörner d'évaluation des polynômes.

Pour prouver sa correction, on considère l’invariant de boucle suivant : à chaque sortie de boucle, Total a pour valeur $P_k(x)$. Lorsqu’on entre dans la boucle pour la première fois, Total vaut $P_n(x)$. Notre définition des $P_i$ nous assure que l’invariant de boucle reste vérifié après la boucle suivante. Ainsi, à la fin de la dernière boucle, Total vaut $P_0(x) = P(x)$.

$7)$ Notre algorithme utilise cette fois une addition et une multiplication par passage de boucles, soit $n-1$ additions et $n-1$ multiplications.

Le drapeau hollandais

Le problème du drapeau hollandais, proposé par Dijkstra, consiste à trier un tableau contenant des boules de couleurs bleues, blanches et rouges de façon à retrouver le drapeau hollandais.

Exercice

On dispose d’un tableau de taille $n$ contenant soit des boules bleues, soit des boules blanches. Nous représentons les boules bleues par l’entier $0$ et les boules blanches par $1$. Les seules opérations autorisés sont la lecture d’une case du tableau et l’échange de deux cases.

$1)$ Proposer un algorithme de tri sur place du tableau effectuant au plus $n$ lecture de cases.

$2)$ Combien d’échange au maximum l’algorithme effectue-t-il ?

Le problème du drapeau Hollandais, fonctionne sur le même principe excepté qu’on ajoute cette fois-ci des boules rouges représentées par $2$. Notre but est de trier notre tableau en bleu-blanc-rouge en effectuant le moins de lecture de cases possible.

$3)$ Proposer un algorithme de tri sur place du tableau effectuant au plus $n$ lecture de cases.

$4)$ Combien d’échange au maximum l’algorithme effectue-t-il ?

Correction

$1)$ On propose l’algorithme suivant.

La quantité $y-x$ est entière et décroît de 1 à chaque itération. De plus, on sort de la boucle si $y-x \lt 0$. Ainsi, l’algorithme termine après $n$ itérations de boucles. Or chacune n’effectue qu’une unique lecture. On effectue donc exactement $n$ lectures mémoires.

Prouvons la correction de cet algorithme. Pour ce faire, nous exhibons un invariant de boucle $\mathcal{I}$ en définissant $\mathcal{I}(i) = $ « À la fin de l’itération $i$, les boules de $1$ à $x$ sont toutes bleues et les boules de $y+1$ à $n$ sont toutes blanches » . Avant d’entrer dans la boucle, $x(i)=1$ et $y(i)=n$ donc la propriété est vérifiée.

On suppose que l’invariant est vérifié à l’étape $i$. À l’étape $i+1$ si $T[x(i)]$ est bleue et $x(i+1)=x(i)+1$. Les boules de $0$ à $x(i+1)-1$ sont bleues et comme $y$ n’est pas modifié, on a encore que les boules de $y(i+1)+1$ à $n-1$ sont toutes blanches. Si $T[x(i)]$ est blanche, on montre de même que l’invariant est conservé.

Enfin, à la sortie de la boucle après l’itération $n$, on a $y(n) \lt x(n)$. Ainsi, notre algorithme renvoie bien un tableau trié.

$2)$ Dans chaque itération, on effectue au plus un échange. On effectue donc au plus $n$ échanges. De plus, ce nombre est atteint dans le cas du tableau ne contenant que des boules blanches.

$3)$ On considère l’algorithme suivant.

On effectue exactement $n$ passages dans la boucle. On effectue donc bien exactement $n$ lectures de cases.

La preuve de la correction et de la terminaison est similaire à l’algorithme du cas deux couleurs. L’invariant à considérer est $\mathcal{I}(i) = $ « À la fin de l’itération $i$, les boules de $1$ à $x$ sont toutes bleues, les boules de $y+1$ à $z$ sont toutes blanches et les boules de $z+1$ à $n$ sont toutes rouges. »

$4)$ Dans le pire des cas, on effectue deux échanges par itération. On effectue donc au plus $2n$ échanges. Ce pire cas est atteint dans le cas du tableau ne contenant que des boules rouges.

Stabilité des langages rationnels

Le but de cet exercice est de présenter plusieurs opérations stables sur les langages rationnels. On suppose connu l’équivalence entre les langages rationnels et les langages reconnaissables par automate fini.

Exercice

Soit $\mathcal{L}_1$ et $\mathcal{L}_2$ deux langages rationnels sur l’alphabet $\Sigma$. Montrer que les langages suivants sont rationnels.

$1)$ $\overline{\mathcal{L}_1} = {\;w \in \Sigma^{*}\;|\;w \notin \mathcal{L}_1\;}$ le complémentaire de $\mathcal{L}_1$.

$2)$ $\mathcal{L}_1 \cap \mathcal{L}_2$ l’intersection de $\mathcal{L}_1$ et $\mathcal{L}_2$.

$3)$ $\mathcal{L}_1 \setminus \mathcal{L}_2$ la différence ensembliste de $\mathcal{L}_1$ et $\mathcal{L}_2$.

$4)$ $Mir(\mathcal{L}_1) = \{\;\bar{w} = w_1 w_2 \ldots w_n \in \Sigma^{*}\;|\;w_i \in \Sigma,\;w = w_n \ldots w_2 w_1 \in \mathcal{L}_1\;\}$ le langage miroir de $\mathcal{L}_1$.

$5)$ $Pre(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists v \in \Sigma^{*}, \; wv \in \mathcal{L}_1\;\}$, le langage des préfixes de $\mathcal{L}_1$.

$6)$ $Suf(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists u \in \Sigma^{*}, \; uw \in \mathcal{L}_1\;\}$, le langage des suffixes de $\mathcal{L}_1$.

$7)$ $Fac(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists u,v \in \Sigma^{*} \; uwv \in \mathcal{L}_1\;\}$, le langage des facteurs de $\mathcal{L}_1$.

$8)$ $\mathcal{L}_1\#\mathcal{L}_2$ : le produit mélangé de $\mathcal{L}_1$ et $\mathcal{L}_2$. Les mots mélangé sont les $u_1v_1 \ldots u_kv_k$ avec les $u_i, v_i \in \Sigma^{*}$, avec $u=u_1u_2\ldots u_k \in \mathcal{L}_1$ et $v=v_1v_2\ldots v_k \in \mathcal{L}_2$.

$9)$ $\sqrt{\mathcal{L}_1} = \{\;w \in \Sigma^{*}\;|\; ww \in \mathcal{L}_1\;\}$, la racine carré de $\mathcal{L}_1$.

$10)$ $\frac{\mathcal{L}_1}{2} = \{\;w \in \Sigma^{*}\;|\;\exists u \in \Sigma^{*},\;|w|=|u|,\; wu \in \mathcal{L}_1,\;\}$, la moitié de $\mathcal{L}_1$.

Correction

Dans toute la suite, on notera $\mathcal{A}_1 = \left(\Sigma,\; Q,\; q_0,\; F,\; \delta\right)$ et $\mathcal{A}_2 = \left(\Sigma,\; Q’,\; q’_0,\; F’,\; \delta’\right)$ deux automates déterministe complet reconnaissant respectivement $\mathcal{L}_1$ et $\mathcal{L}_2$.

$1)$ Un mot $w$ appartient à $\mathcal{L}_1$ si et seulement si on atteint un état de $F$ dans $\mathcal{A}_1$ lorsqu’on lit $w$. De ce fait, un mot n’est pas dans $\mathcal{L}_1$ si et seulement si on atteint un état de $Q \setminus F$ dans $\mathcal{A}_1$ lorsqu’on lit $w$. Il en résulte donc que le complémentaire de $\mathcal{L}_1$ est reconnu par l’automate : \[\overline{\mathcal{A}}_1 = \left(\Sigma,\; Q,\; q_0,\; Q \setminus F,\; \delta\right)\] De ce fait, les langages rationnels sont stables par complémentaire.

$2)$ Pour deux ensembles $A$ et $B$ on rappel qu’on a la formule suivante : \[A \cap B = \overline{\overline{A} \cup \overline{B}}\] On a donc : \[\mathcal{L}_1 \cap \mathcal{L}_2 = \overline{\overline{\mathcal{L}_1} \cup \overline{\mathcal{L}_2}}\] Les langages rationnels étant stables par union et complémentaire, il en résulte qu’ils sont stables par intersection et $\mathcal{L}_1 \cap \mathcal{L}_2$ est rationnel.

$3)$ On rappel que pour deux ensembles $A$ et $B$ on a : \[A \setminus B = A \cap \overline{B}\] On a donc que les langages rationnels sont stables par différence ensemblistes.

$4)$ On considère $\delta^{-1}$ la fonction qui à $(q,a) \in Q \times \Sigma$ associe l’ensemble, éventuellement vide, des états $q’$ de $Q$ tels que $\delta(q,a) = q’$. On veut montrer que $Mir(\mathcal{L}_1)$ est reconnu par l’automate non déterministe suivant : \[Mir(\mathcal{A}_1) = \left(\Sigma,\; Q,\; F,\; \{q_0\},\; \delta^{-1}\right)\] En effet, si $w \in Mir(\mathcal{L}_1)$ alors $\bar{w} \in \mathcal{L}_1$. De ce fait, on considère la suite d’états de $q_0$ à $q’ \in F$ par lequel passe $\mathcal{A}_1$ en lisant $\bar{w}$. On note qu’un chemin dans $Mir(\mathcal{A}_1)$ en lisant $w$ est le chemin inverse de $q’$ à $q_0$. Donc on a bien $Mir(\mathcal{A}_1)$ qui reconnaît $w$. Réciproquement, si $w$ est reconnu par $Mir(\mathcal{A}_1)$ alors par définition de $\delta^{-1}$, on a un chemin de $q_0$ à un élément de $F$ dans $\mathcal{A}_1$ qui reconnait $\bar{w}$ et $w$ appartient à $Mir(\mathcal{L}_1)$. Ainsi, les langages rationnels sont stables par miroir.

$5)$ Soit $T$ l’ensemble des états $q$ de $\mathcal{A}_1$ tel qu’il existe un chemin de $q$ vers un état de $F$. Soit $v_q$ le mot formé par ce chemin. On considère un mot $w$ tel que $\mathcal{A}_1$ arrive dans un état $q$ de $T$ lorsqu’il le lit. On note alors que si on lit $wv_q$ on arrive dans un état de $F$. Il en résulte que $wv_q \in \mathcal{L}_1$ Donc $w \in Pre(\mathcal{L}_1)$. De plus, si $w$ est un mot préfixe de $\mathcal{L}_1$ alors il existe $v$ tel que $wv \in \mathcal{L}_1$. Donc, si $\mathcal{A}_1$ arrive dans un état $q$ en lisant $w$ alors $q \in T$. Il en résulte que $Pre(\mathcal{L}_1)$ est reconnu par l’automate suivant : \[Pre(\mathcal{A}_1) = \left(\Sigma,\; Q,\; q_0,\; T,\; \delta\right)\] Donc le langage des préfixes d’un langage rationnel est un langage rationnel.

$6)$ On note que le langage des suffixes de $\mathcal{L}_1$ est le miroir du langage des préfixes de $Mir(\mathcal{L}_1)$. Il en résulte donc que le langage des suffixes d’un langage rationnel est un langage rationnel.

$7)$ On remarque que les facteurs d’un mot correspond à l’ensemble des préfixes de ses suffixes. On a donc : \[Fac\left(\mathcal{L}_1\right) = Pre\left(Suf\left(\mathcal{L}_1\right)\right)\] Il en résulte que le langage des facteurs d’un langage rationnel est un langage rationnel.

$8)$ On pose $\Delta$ une fonction de $\left(Q \times Q’\right) \times \Sigma$ dans $\mathcal{P}\left(Q \times Q’\right)$ l’ensemble des parties de $Q \times Q’$ et définie par : \[\Delta((q,q’),a) = \left\{\;(r,q’)\;|\;\delta(q,a) = r\;\right\} \bigcup \left\{\;(q,r’)\;|\;\delta'(q’,a) = r’\;\right\} \] On a $\mathcal{L}_1\#\mathcal{L}_2$ est reconnu par l’automate non déterministe suivant : \[\mathcal{A}_{\#} = \left(\Sigma,\;Q \times Q’,\;\{(q_0,q’_0)\},\;F \times F’,\; \Delta \right) \] Ainsi, les langages rationnels sont stables par mélange de mots.

$9)$ Le principe de l’automate qu’on va construire ici est de simuler la lecture de notre mot d’entrée en partant de tous les états à la fois. Ainsi, une fois qu’on aura terminer de lire notre mot, on pourra directement le lire une seconde foi. L’ensemble d’états qui nous intéresse est donc $Q^{n}$ où $n$ est le nombre d’états de l’automate. Notre état initial est $(q_0,q_1, \ldots, q_{n-1})$ où les $q_i$ sont les états de $Q$ numérotés de $0$, l’état initial, à $n$. Notre fonction d’état $\delta_n$ est donnée par : \[\delta_n((p_0,\ldots,p_{n-1}),a) = (\delta(p_0,a), \ldots, \delta(p_{n-1},a))\] L’ensemble des états finaux $F_{\sqrt{\;}}$ est l’ensemble des $(p_1, \ldots, p_n)$ tel que $p_1 = q_i$ et $p_{i} \in F$. Autrement dit on regarde dans quel état on se trouve après avoir lu $w$ et on en déduit où on termine après avoir lu $ww$. Ainsi l’automate $\mathcal{A}_{\sqrt{\;}}$ suivant reconnaît bien $\displaystyle \sqrt{\mathcal{L}_1}$ : \[\mathcal{A}_{\sqrt{\;}} = \left(\Sigma,\;Q^{n},\;(q_0,q_1,\ldots,q_{n-1}),\;F_{\sqrt{\;}},\;\delta_n \right)\] Les langages rationnels sont stables par racine carrée.

$10)$ On procède de même que pour la racine carrée excepté qu’on utilise un automate non déterministe. Cette fois-ci, on s’intéresse à tous les états accessible à partir de chaque état. Notre automate a pour ensemble d’état $Q^{n+1}$. Notre fonction d’état $\delta_{n+1}$ est donnée par : \[\delta_{n+1}((p,p_0,\ldots,p_{n-1}),a) = \{\;(\delta(p,a),\delta(p_0,x_1), \ldots, \delta(p_{n-1},x_n)\;|\;\exists x_1,\ldots,x_n \in \Sigma\;\}\] L’ensemble d’états finaux est l’ensemble des $(p,p_1,\ldots,p_n)$ tel que $p=p_i$ et $p_i \in F$. Enfin, l’ensemble d’états initiaux est $\{(q_0,q_0,q_1,\ldots,q_n)\}$. Ainsi, les langages rationnels sont stables par moitié.

La fonction d’Ackermann

Ici on s’attaque à un des exercices les plus classiques en matière de terminaison d’algorithme. On présente une fonction récursive et le but est de montrer qu’un algorithme calculant cette fonction termine.

Exercice

La fonction d’Ackermann est une fonction de $\mathbb{N}^{2}$ dans $\mathbb{N}$ et est définie par : \[A(m,\:n) = \begin{cases} n+1& \text{ si }m=0\\ A(m-1,\:1) & \text{ si }m\gt 0 \text{ et }n=0\\ A(m-1, A(m,\:n-1)) & \text{ si }m\gt 0 \text{ et }n\gt 0 \end{cases}\]

$1)$ Munir $\mathbb{N}^{2}$ d’un ordre bien fondée.

$2)$ En déduire que la fonction d’Ackermann est bien définie.

Correction

$1.$ Considérons l’ordre lexicographique $\lt_{lex}$ définie par :
\[(x,y) \lt_{lex} (x’,y’) \Leftrightarrow x\lt x’ \text{ ou } ( x=x’ \text{ et } y\lt y’ )\]

Prouvons que cet ordre est bien fondée. Nous proposons deux méthodes utilisant les deux définitions équivalentes de l’ordre bien fondée.

Première méthode : montrons qu’il n’existe pas de suite infinie strictement décroissante Par l’absurde, supposons qu’une telle suite existe. Appelons-là $\displaystyle (u_n)_{n\in\mathbb{N}}$. Soit $u_0 = (x,y)$. On note que les éléments de $(u_n)$ sont de la forme $(k,k’)$ avec $0 \leq k \leq x$. Notre suite étant infinie et le nombre de possibilité pour le premier élément étant finie, on a $K \in \mathbb{N}$ tel qu’on ait une infinité d’élément de $(u_n)_{n\in\mathbb{N}}$ de la forme $(K,k’)$. Ainsi, on a $\varphi$ une extractrice de $\mathbb{N}$ telle que la suite $(u_{\varphi(n)})$ soit strictement décroissante et n’ait que des valeurs de la forme $(K,k’)$. On pose $u_{\varphi(0)} = (K,K’)$. Or, nous n’avons que $K’+1$ éléments distincts compris entre $(K,K’)$ et $(K,0)$, ce qui contredit l’hypothèse de stricte décroissance. Ainsi, $\lt_{lex}$ définit bien un ordre bien fondé sur $\mathbb{N}^{2}$.

Deuxième méthode : montrons que pour tout sous ensemble de $\mathbb{N}^{2}$, il existe un élément strictement minimal au sens de l’ordre $\leq_{lex}$. Pour cela, il suffit de considérer un ensemble de $\mathbb{N}^{2}$ et de considérer le sous-ensemble constitué des éléments dont le premier élément du $2$-uplet est minimale. Puis, on prend le plus petit élément dans cet ensemble par rapport à la seconde composante, ce qui est possible dans les deux cas car $(\mathbb{N},\lt )$ est bien fondée. On a bien exhibé un plus petit élément, donc $(\mathbb{N}^{2},\lt_{lex})$ est bien fondé.

$2)$ Prouvons à présent que la fonction d’Ackermann est bien définie. On peut considérer notre définition comme un algorithme récursif et la question est alors de savoir si notre programme termine. Pour le prouver, on procède par induction sur l’entrée.

Tout d’abord, si $m=0$, $A(m,n)$ termine en une étape.

Soit $(m,n) \in \mathbb{N}^{*}\times\mathbb{N}$. On suppose que la fonction d’Ackermann termine sur tout $(k,l)\lt_{lex}(m,n)$. Montrons qu’elle termine sur l’entrée $(m,n)$. Si $n=0$, Ackermann termine sur $(m-1,1)$ donc termine sur $(m,n)$. Sinon, par hypothèse d’induction, $A(m,n-1)$ existe et le calcul termine. De plus $(m-1,A(m,n-1))\lt_{lex}(m,n)$. Ainsi, toujours par hypothèse d’induction, notre fonction termine sur l’entrée $(m-1,A(m,n-1))$ et donc termine sur $(m,n)$. Cela prouve donc le cas $(m,n)$ et achève la récurrence.

Nous avons donc prouvé que la fonction d’Ackermann est bien définie.

La fonction 91 de McCarthy

Exercice

On définit la fonction récursive suivante due à McCarthy. Elle prend en entrée un entier $n$ et est définie par : \[f(n) = \begin{cases} n – 10 & \text{ si } n \gt 100 \\ f(f(n+11)) & \text{ sinon} \end{cases}\]

On considère l’algorithme qui calcule $f(n)$ en partant de la formule de récurrence. Montrer que cet algorithme termine et donner une valeur explicite de $f(n)$ pour tout entier $n$.

Correction

Nous savons que notre algorithme termine pour tout entrée supérieur à $101$, mais nous ignorons comment il se comporte pour des entrées plus petites. On doit donc effectuer une récurrence décroissante.

Montrons par induction que f l’algorithme calculant la fonction de McCarthy termine sur toute entrée entière $n$ et renvoie $n – 10$ si $n$ est supérieur ou égale à $101$ et renvoie $91$ sinon.

On initialise notre induction pour les cas de bases $n\gt100$. Dans ce cas, la fonction de McCarthy termine bien et renvoie ce que l’on souhaite.

On suppose maintenant la propriété vraie pour tout $n \gt k$ avec $ 0 \leq k\leq100$. Montrons qu’elle le reste au rang $k$.

Si $100\geq k\geq90$ : alors $f(k) = f(f(k+11))$. Or ici, $k+11 \gt 100$ et $f(k+11)$ termine et renvoie $k+1$. Donc $f(f(k+11)) = f(k+1)$. Par hypothèse d’induction, la fonction termine sur l’entrée $k+1$. De plus, si $k=100$ alors $f(k+1)=f(101)=91$ et si $k<100$, alors $f(k)=f(k+1)=91$. Donc la fonction de McCarthy termine sur l'entrée $k$ et renvoie $91$.

Si $90 \gt k$ : On a $f(k)=f(f(k+11))$. Or, par hypothèse d’induction, $f$ termine sur l’entrée $k+11$ et renvoie $91$. Donc $f(k)=f(91)$ qui termine et vaut $91$.

Cela achève notre induction et nous permet donc de conclure que l’algorithme calculant la fonction de McCarthy termine sur toute entrée entière $k$ et est définie par :

\[f(k) =\begin{cases} n – 10 & \text{ si } n \gt 100 \\ 91 & \text{ sinon} \end{cases}\]

Coloration de Wigderson

Exercice

Le but de cet exercice est de colorer un graphe que l’on sait $3$-coloriable en utilisant le moins de couleurs possible.

$1)$ Soit un graphe $G$ quelconque de degré maximal $\Delta$. Donner une borne sur le nombre chromatique de $G$.

Soit $G$ un graphe $3$-coloriable. Pour $u$ un sommet de $G$, on note $N(u)$ l’ensemble des voisins de $u$.

$2)$ Montrer qu’on peut colorier avec $3$ couleurs en temps polynomial le sous-graphe induit par $\{u\} \bigcup N(u)$.

$3)$ En déduire un algorithme qui tourne en temps polynomial pour colorier un graphe $3$-coloriable de $n$ sommets avec $3\sqrt{n}$ couleurs.

Correction

$1.$ On propose l’algorithme suivant : on colorie chaque sommet un par un en lui attribuant la plus petite couleur non attribué à un de ses voisins. De ce fait, chaque sommet a une couleur inférieur ou égale au nombre de ses voisins plus un. Ainsi, pour un graphe $G$ de degré maximal $\Delta$, son nombre chromatique est borné par $\Delta + 1$.

On note que dans le cas du graphe complet, cette borne est atteinte. Il s’agit donc de la meilleure borne possible.

$2.$ On attribue à $u$ la couleur $1$. De plus, comme $G$ est $3$-coloriable, cela signifie que l’ensemble de ses voisins forme un graphe bipartie. Or $2$-colorier un graphe bipartie est faisable par un simple parcours. On a donc colorié notre sous-graphe avec trois couleurs en un temps polynomial.

$3.$ Soit $n$ le nombre de sommets de notre graphe. On propose l’algorithme récursif suivant : on cherche le sommet $s$ de degré maximal. Si ce degré est strictement inférieur à $\sqrt{n}$ on peut colorier le graphe avec $\sqrt{n}$ couleurs. Sinon, on considère ses voisins qui forment donc un graphe bipartie. On les colorie avec $2$ couleurs qu’on ne réutilisera plus. On supprime les sommets coloriés du graphe et on recommence. On effectue au plus $\sqrt{n}$ passage dans la boucle. Dans chaque passage, on utilise $2$ nouvelles couleurs, soit $2\sqrt{n}$ au total. Enfin, on passe au plus une fois dans le cas où on colorie utilisant $\sqrt{n}$ couleurs.

Notre algorithme permet donc bien de colorier un graphe $3$-coloriable avec $3\sqrt{n}$ couleurs.

Cette approximation a été proposée par Wigderson. Khanna, Linial et Saffra ont montré en 1993 que le problème de colorier un graphe qu’on sait $3$-coloriable avec $4$ couleurs est NP-difficile.

Sudoku #2

Sudoku haché

Résoudre en ligne !

Les règles habituelles du sudoku s’appliquent. Le long des flèches, la somme des entiers est divisible par le nombre le plus proche de la flèche. De plus, le long d’une flèche, tous les nombres sont différents. Enfin, la somme des cellules le long de la triple flèche est divisible par le cube du nombre le plus proche de la triple flèche.

Bonne chance !

Mot croisé cryptique #2

Horizontal

1 : Beaucoup de centaures décapités $(4)$ — Drogue d’une pauvre à moitié enceinte $(5)$

2 : Arrêté, ce con donnera un cocktail $(10)$

3 : Un bouleversement austère $(2)$ — Possède un peu d’ail $(2)$ — Note pour s’arrêter au bon endroit $(2)$

4 : Maladie de la roue d’un moine dans tous ses états $(9)$

5 : Endort des équidés, une boisson que tu tises mal $(12)$

6 : Trouée après le soutien $(5)$ — Tes changements au tennis $(3)$

7 : Moche bout de faim, plat sur la table $(10)$

8 : Menuisier que tu bénis pendant l’été $(8)$ — Eau d’une autre lettre $(3)$

9 : Démangeaison qui recuirait la salade $(9)$ — Période du mi-dimanche $(2)$

10 : Début de descente du prix d’une lettre $(2)$ — L’intelligence de vider quoi $(2)$ — Nous sommes au centre d’un cercle $(2)$ — Tissu remontant l’Égypte $(3)$

11 : Réservé le milieu d’une alouette $(4)$ — Neurone éventré en son sein $(4)$

12 : Frappa caché dans une classe nationale $(6)$ — Organe avec presque rien $(4)$

Vertical

A : Imbécile, gâteux complexé et perturbé, infectieux $(10)$

B : Milieux de nombres puérils en orée $(8)$

C : On renverse un drame lyrique $(2)$ — Autorise un remous trempé $(6)$ — On sécurise au début un imprévu $(2)$

D : Danse d’argentins qui coupe une querelle modifié $(12)$

E : Médecin dont l’identité modifié incorpore ses collègues innomés $(11)$

F : Exclamation à la limite horrible $(2)$ — Bruit sceptique au milieu du brouhaha $(2)$ — Douane très sévèrement arriéré et débutante $(3)$

G : Le menu ornait étrangement la liste $(11)$

H : Route nationale un peu radioactive $(2)$ — Osciller au bout dans le corps $(2)$ — Flouer, enrober un ordre asséché $(6)$

I : Pivot de ruban nippon interdit $(5)$ — En bouscule pas $(2)$

J : Ne retourne qu’à l’intérieur $(2)$ — Rivière au remous tissé $(5)$ — Pièces proche d’une île $(3)$

K : Décréter l’amoindrissement d’une coupe $(5)$ — Détesté à l’ouest d’une île des Caraïbes $(3)$

L : Personnage devançant Edd $(3)$ — Présent en étrange entrée avec aversion $(7)$

Solution ici !