Produit efficace en binaire

Exercice

Nous cherchons ici à effectuer le produit de deux entiers $x$ et $y$ écrits en binaire sur $k$ bits, avec $k$ une puissance de $2$. On peut noter $x = x_1 x_2 \ldots x_k$ et $y = y_1 y_2 \ldots y_k$. Les bits $x_1$ et $y_1$ sont les bits de poids forts.

$1.$ Donner la complexité de l’addition de deux nombres écrits en binaire écrits sur $n$ bits.

$2.$ Donner la complexité pour multiplier un nombre écrit en binaire sur $n$ bits par une puissance de $2$ inférieure à $2^{k}$.

$3.$ Quel est la complexité du produit naïf de deux nombres en binaire sur $n$ bits dont le résultat est écrit sur $2n$ bits ?

On pose $x_G = x_1 \ldots x_{k/2}$ et $x_D = x_{k/2+1} \ldots x_k$. De même, on pose $y_G$ et $y_D$.

$4.$ Exprimer naïvement $xy$ en fonction de $x_G$, $x_D$, $y_G$, $y_D$ et des puissances de $2$.

$5.$ Quelle est la complexité de l’algorithme de diviser pour régner associé ?

$6.$ Exprimer $xy$ en fonction de $x_G$, $x_D$, $y_G$, $y_D$ et des puissances de $2$ en utilisant moins de multiplication.

$7.$ Quelle est la complexité de l’algorithme de diviser pour régner associé ?

$8.$ Comment adapter l’algorithme pour multiplier des entiers sur $k$ bits avec $k$ quelconque ?

Cet algorithme de calcul a été développé par Anatolii Karatsuba en 1960 et publié en 1962.

Correction

$1.$ Pour additionner deux entiers, il est nécessaire de regarder chaque bits. De ce fait, le problème de l’addition de deux entiers est en $\Omega(n)$. De plus l’algorithme de la retenue tourne en $O(n)$. Il en résulte que la complexité de l’addition de deux entiers de $n$ bits est $\displaystyle \boxed{\Theta\left(n\right)}$.

$2.$ Pour multiplier un entier écris sur $n$ bits par une puissance de $2$, il nous suffit de décaler les bits de notre entier. Ainsi, il nous faut encore $\boxed{\Theta\left(n\right)}$ opérations.

$3.$ L’algorithme naïf de multiplication consiste à multiplier $x$ par chaque bit de $y$ avant de sommer. Cela nécessite donc $\displaystyle \boxed{\Theta\left(n^{2}\right)}$ opérations.

$4.$ On a la formule suivante :

\[xy = x_Gy_G\cdot2^{k} + (x_Gy_D + x_Dy_G)\cdot2^{k/2} + x_Dy_D\]

$5.$ Si on calcule récursivement cette formule, on remarque qu’on effectue 4 appels sur des instances de tailles $k/2$. De plus la fusion des différents résultats nécessite deux multiplications par des puissances de $2$ et trois additions, soit un coût en $O(k)$. Ainsi, un algorithme calculant cette formule a une complexité $C(n)$ qui vérifie la récurrence :

\[C(n) = 4C\left(\frac{n}{2}\right) + O(n)\]

Le master theorem nous permet donc de conclure que notre algorithme tourne en $\boxed{\Theta\left(k^{2}\right)}$ opérations. On ne remarque donc pas d’améliorations par rapport à la méthode naïf.

$6.$ Posons $g = x_Gy_G$, $d = x_Dy_D$ et $u = (x_G+x_D)(y_G+y_D)$. On note qu’on obtient ces valeurs en trois multiplications.

De plus, on note que $u – d – g = x_Gy_D + x_Dy_G$. On a donc :

\[xy = g\cdot2^{k} + (u-g-d)\cdot2^{k/2} + d\]

$7.$ L’algorithme de diviser pour régner associé à cette formule a une complexité définie par la formule :

\[T(k) = 3T\left(\frac{k}{2}\right) + O(k)\]

Le master theorem nous donne donc $\displaystyle T(k)=O\left(n^{\log_2(3)}\right)=O\left(n^{1.6}\right)$.

$8.$ Pour des entiers de tailles $n$ quelconque, on considère $m$ tel que $2^{m} \geq n \gt 2^{m-1}$. On complète à gauche nos entiers par des zéros pour obtenir des entiers de taille $2^m$. Ensuite, on procède avec notre algorithme qui aura une complexité en $O\left(2^{ \log_2(3) \cdot m}\right)$. Or on a $2^{m} \leq 2n$, donc notre algorithme fonctionne en $O\left(2^{ \log_2(3) } \cdot n^{ \log_2(3) }\right)$, soit en $O\left(n^{ \log_2(3) }\right)$.

Le problème des 3 couleurs (3-COLOR)

Notre but ici est de montrer que le problème de coloration avec trois couleurs est NP-complet que ce soit dans le cas des graphes planaire ou non planaire. Nous souhaitons le prouver pour le cas des graphes quelconque et pour le cas des graphes planaires. Ces résultats sont dus à Garey, Johnson et Stockmeyer.

Dans un autre exercice, on s’intéresse à une approximation du problème des 3 couleurs.

Exercice

On appelle coloration d’un graphe une fonction des sommets du graphe vers les entiers tels que deux sommets adjacents ne sont pas assignés le même entier. Le problème des 3 couleurs noté 3-COL prend en entré un graphe et répond vrai si et seulement si il existe une coloration du graphe utilisant moins de trois couleurs. Autrement dit, telle qu’il existe un fonction de coloration dont l’image est incluse dans ${1,2,3}$.

$1.$ Montrer que 3-COL est un problème dans NP.

Pour montrer que le problème est NP-difficile, on cherche à effectuer une réduction à partir de 3-SAT. Pour ce faire, une considère une formule $\varphi$ sous forme normale conjonctive dont toutes les clauses ont exactement trois littéraux. On note : $\varphi = \bigwedge\limits_{i=1}^{n}C_i$ et $C_i = (x_{1}^{i},x_{2}^{i},x_{3}^{i})$.

On veut maintenant construire un graphe qui est 3 coloriable si et seulement si $\varphi$ est satisfiable. Pour commencer on ajoute pour chaque variable et chaque négation de variable un sommet. Notre but est que pour chaque couple de variable et sa négation la couleur d’un des deux sommets corresponde à la valuation Vrai et la couleur d’un autre sommet corresponde à la valuation Faux.

$2.$ On souhaite que la fonction de coloration de notre graphe, si elle existe, soit une fonction de distribution de valeur de vérité. Donner une façon de s’en assurer.

Intéressons nous au gadget suivant :

Rendered by QuickLaTeX.com

$3.$ Que peut-on dire de la couleur du sommet $e$ en fonction des couleurs de $a$ et $b$ lorsqu’on se limite à $3$ couleurs ?

$4.$ En déduire un gadget tel qu’un sommet donné puisse être à la couleur de Vrai si et seulement si une clause et satisfaite. Donc si et seulement si une des variables de la clause soit coloré par la couleur associé à Vrai.

$5.$ Terminer la réduction.

$6.$ Montrer maintenant que pour tout $k$, $k$-COL est NP-complet.

Intéressons nous maintenant au cas planaire. On dit qu’un graphe est planaire si dans une de ses représentations graphique dans le plan, aucune arête ne se croise. Le théorème des quatre couleurs nous dit que tout graphe de ce type est 4-coloriable. Cependant, savoir si un tel graphe est 3-coloriable est NP-complet. Ce problème est appelé PLANAR-3-COL.

$7.$ Montrer que PLANAR-3-COL est dans NP.

On considère le gadget suivant :

Rendered by QuickLaTeX.com

$8.$ Montrer que pour tout 3-coloration $c$ correcte de ce gadget, on a nécessairement $c(a)=c(m)$ et $c(e)=c(i)$.

$9.$ Montrer que dans un graphe quelconque, on peut remplacer chacune de ses intersections par ce gadget et s’assurer que non seulement le nouveau graphe obtenue est planaire mais en plus il est 3-coloriable si et seulement si le graphe initial l’est.

$10.$ Conclure

$11.$ Expliquer en quelques mots pourquoi on ne peut pas adapter cette démonstration pour montrer que PLANAR-4-COL est NP-complet ?

Correction

$1.$ Si on dispose d’une $3$ coloration d’un graphe, un simple parcours du graphe nous permet de vérifier si elle est correcte. De ce fait on a un certificat de taille polynomiale en la taille de notre graphe qui permet de vérifier qu’un graphe est $3$-coloriable. On en déduit que 3-COL est dans NP.

$2.$ On crée trois sommets nommés $V$, $F$ et $A$ reliés entre eux. De plus, pour chaque variable $v_i$ de notre graphe on crée deux sommets nommés $v_i$ et $\bar{v_i}$. On ajoute alors les arêtes $(v_i,\bar{v_i}), (v_i,A), (A,\bar{v_i})$. Ainsi, chaque variable est soit de la même couleur que $V$ et sa négation de la couleur de $F$ soit l’inverse.

Rendered by QuickLaTeX.com

$3.$ Pour une coloration valide $c$, si $c(a) = c(b)$ alors $c(a) = c(e)$. De ce fait, si les couleurs de $a$ et $b$ sont soit celle de $V$ soit celle de $F$, alors $c(e)$ ne peut être égale à $c(V)$ que si $c(a) = c(V)$ ou $c(b) = c(V)$.

$4.$ On vient de construire un gadget permettant de calculer, $a \vee b$. Il nous suffit donc de le répéter. Ainsi si une clause $C$ s’écrit $(x_1 \vee x_2 \vee x_3)$ on peut considérer le gadget suivant :

Rendered by QuickLaTeX.com

Pour toute 3-coloration $c$ tel que $c(x_1)$, $c(x_2)$, $c(x_3)$ sont dans ${c(V),c(F)}$, on a $c(i) = c(V)$ seulement si il existe $1 \leq k \leq 3$ tel que $c(x_k) = c(V)$. En effet, si $c(i) = c(V)$ et $c(h) = c(F)$ alors $c(x_3) = c(V)$. Si $c(g) = c(F)$ alors $c(e) \neq c(F)$ et soit $c(x_1)$ soit $c(x_2)$ égale à $c(V)$.

De plus si on a $1 \leq k \leq 3$ tel que $c(x_k) = c(V)$ alors on a une coloration telle que $c(i) = c(V)$.

$5.$ Pour chaque clause $C_k$ on construit le gadget précédent. Pour les $x_i$ on utilise évidemment les sommets de variables déjà créés. Sinon, on associe à chacun les sommets $c_k$, $d_k$, $e_k$, $g_k$, $h_k$, $i_k$. Enfin, il nous suffit de rajouter pour tous $k$ les arêtes $(i_k,A)$ et $(i_k,F)$.

Ainsi, supposons que $\varphi$ soit satisfiable. On considère la coloration suivante : on associe à $F$ la couleur $0$, à $V$ la couleur $1$ et à $A$ la couleur $2$. On considère la distribution de valeur qui satisfait $\varphi$. Pour chaque variable $x_i$ on lui associe $1$ si elle est à vrai et $0$ sinon. Ensuite, comme cette distribution assure que pour chaque clause au moins une des variables soit de couleur $1$ on s’assure qu’on peut colorier chaque gadget de telle sorte à ce que tous les $i_k$ soient de couleur $1$. Ainsi deux sommets reliés sont de couleurs différentes et on a bien une 3-coloration de notre graphe.

Réciproquement, si notre graphe est 3-coloriable, cela signifie que tous les $i_k$ sont de la même couleur que $V$. De plus, comme les couleurs des $x_j$ sont dans ${c(V),\:c(F)}$, car voisins de $A$, on a prouvé qu’un des trois sommets initiaux de chaque gadget est de la même couleur que $c(V)$. De ce fait, si on met à vrai tous les littéraux de la même couleur que $V$ et les autres à faux, on s’assure qu’au moins un littéral par clause soit à vrai et que donc notre formule soit bien satisfaite.

Ainsi, on a construis un graphe de taille polynomiale en la taille de notre formule qui est $3$ coloriable si et seulement si $\varphi$ est satisfiable. On a donc bien montré que 3-COL est NP-complet.

$6.$ Pour montrer que pour tout $k \geq 4$, $k$-COL est NP-complet, on effectue une réduction à partir de $3$-COL. On considère un graphe $G$. On ajoute $k-3$ sommets tous reliés entre eux et reliés à tous les autres sommets de $G$ Le nouveau graphe obtenue est $k$ coloriable si et seulement si $G$ est 3 coloriable. Notons que notre réduction est bien polynomiale car $k$ n’est pas un paramètre du problème.

$7.$ Comme pour $3$-COL, il nous suffit de considérer comme certificat une coloration correcte du graphe.

$8.$ On considère une coloration correcte $c$ de notre gadget. On commence par appeler $1$ la couleur de $g$ et $2$ la couleur du sommet $c$. En effet, comme $g$ et $c$ sont liés par une arête, on sait qu’ils sont de couleurs différentes. Ainsi, on a nécessairement $c(f) = 3$, $c(h) = 3$ et $c(k) = 2$. Il nous reste alors deux choix pour colorier $b$. Soit $c(b) = 1$, soit $c(b) = 3$. Dans les deux cas, la coloration des derniers sommets est forcée et nous nous retrouvons dans une de ces deux configurations :

Rendered by QuickLaTeX.com

On a donc bien toujours $c(a)=c(m)$ et $c(e)=c(i)$.

$9.$ On considère les sommets $u,v,u’,v’$ et la situation suivante :

Rendered by QuickLaTeX.com

On remplace cette occurence par :

Rendered by QuickLaTeX.com

Il nous suffit alors de remplacer toutes les intersections en commençant par l’intersection la plus en haut à gauche. De ce fait, le graphe ainsi construit est planaire et est $3$ coloriable si et seulement si le graphe initial l’est.

$10.$ Il nous reste à montrer que notre transformation est bien de taille polynomiale. On note que cette transformation fonctionne pour toute représentation de notre graphe initial tel qu’aucune arête ne passe par un autre sommet. On considère uniquement des arêtes représenté par un segment du plan. Ainsi, tout couple d’arête ne se croise qu’au plus une fois. On ajoute donc $\displaystyle O\left(n^{2}\right)$ de sommets et d’arêtes.

Il en résulte donc qu’on a obtenu une réduction polynomiale de $3$-COL à PLANAR-$3$-COL qui est dans NP. Ainsi, PLANAR-$3$-COL est NP-complet.

$11.$ Le gadget qu’on a construit repose sur le fait qu’on colorie avec au plus $3$ couleurs. Ainsi, si on voulait pouvoir adapter cette démonstration il nous faudrait trouver un autre gadget jouant le même rôle pour un nombre plus élevés de couleurs. Cependant, on note que tout graphe planaire est $4$ coloriable donc on sait qu’un tel gadget n’existe pas car il existe des graphes non planaires qui ne sont pas $4$ coloriables.

Exercices en lien

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.