Les graphes cordaux

On s’intéresse à une famille de graphes dont les graphes d’intervalles font partis. Il s’agit des graphes cordaux. Tout comme les graphes d’intervalles, on présente un algorithme de coloration pour cette famille.

Exercice

Un graphe est dit cordal si pour tout cycle de taille supérieur ou égale à 4, il existe une corde. C’est à dire qu’il existe une arête entre deux sommets non consécutifs du cycle.

Soit un graphe $G = (S,A)$ connexe. Soit $u$ et $v$ deux sommets de $G$. On appelle séparateur minimale de $u,v$ tout sous-ensemble $V$ de $S$ tel que $u$ et $v$ ne soient pas accessibles dans le graphe induit par les sommets $S \smallsetminus V$ et tel qu’il n’existe pas de sous-ensemble strictement inclus dans $V$ qui vérifie la même propriété.

$1.$ Montrer que les sous-graphes induits d’un graphe cordal sont également des graphes cordaux.

$2.$ Montrer que si tous les séparateurs minimaux de $G$ sont des cliques alors $G$ est cordal.

$3.$ Prouver la réciproque.

Un sommet est dit simpliciale si l’ensemble de ses voisins forment une clique.

$4.$ Montrer par récurrence que tout graphe cordal à plus de deux sommets contient au moins deux sommets simpliciaux. De plus, si le graphe n’est pas complet, il possède deux sommets simpliciaux non adjacents.

On appelle ordre d’élimination parfait de $G$, un ordre sur les sommets $s_1 \lt s_2 \lt \ldots \lt s_n$ de $G$ tels que $s_i$ soit simplicial dans le sous-graphe induit de $G$ par les sommets $s_1, \ldots, s_i$.

$5.$ Montrer qu’un graphe est cordal si et seulement si il admet un ordre d’élimination parfait.

$6.$ En déduire un algorithme de coloration des graphes cordaux et prouver son optimalité.

$7.$ Conclure que les graphes cordaux sont des graphes parfaits.

Correction

$1.$ On note que tout cycle de longueur supérieur ou égale à $4$ dans un sous-graphe induit d’un graphe $G$ est également présent dans $G$. De ce fait, il admet une corde dans $G$ et donc par définition d’un sous-graphe induit, admet une corde dans le sous-graphe induit. Ainsi, tous sous-graphe induit d’un graphe cordal est un graphe cordal.

$2.$ Soit $G$ un graphe dont tous les séparateurs minimaux sont des cliques. S’ils ne possède pas de cycle de longueur supérieur ou égale à $4$, alors il est cordal. Sinon, soit $k\geq4$ et $s_1, s_2, \ldots, s_k$ un cycle de $G$. On s’intéresse à un séparateur minimal de $s_1$ et $s_3$ noté $W$. Comme $(s_1, s_2)$ et $(s_2,s_3)$ sont des arêtes de $G$ on a $s_2 \in W$. De plus, on a $i$ avec $4 \leq i \leq k$ tel que $s_i \in W$ par définition de cycle. Or par hypothèse, $W$ est une clique. Donc, $(s_2,s_i)$ est une arête de $G$.

Ainsi, tout cycle de $G$ de taille supérieur ou égale à $4$ admet une corde. Donc $G$ est cordal.

$3.$ Si $G$ est cordal. On suppose qu’il existe $W$ un séparateur minimal de $G$ qui ne soit pas une clique et qui sépare les sommets $x$ et $y$. Soit $S_1$ et $S_2$ deux composantes connexes du sous-graphes induits par $S \smallsetminus W$. On suppose que $x \in S_1$ et $y \in S_2$. Soit deux sommets $s_1$ et $s_2$ de $W$ qui ne sont pas adjacent.

On rappel que $W$ est un séparateur minimal. De ce fait, $s_1$ et $s_2$ ont tous deux une arête vers $S_1$ et une vers $S_2$. En effet, si tel n’étais pas le cas, par exemple, si $s_1$ n’avait pas d’arêtes vers $S_1,$ alors $W \smallsetminus {s_1}$ serait un séparateur plus petit de $x,y$ ce qui contredit l’hypothèse de minimalité.

On a donc un plus court chemin de $s_1$ vers $s_2$ dans $S_1$ et un plus court chemin de $s_1$ vers $s_2$ dans $S_2$. On a donc un cycle de longueur au moins $4$. Or, ce cycle ne possède pas de cordes. En effet, il n’y a pas d’arêtes entres $S_1$ et $S_2$, $s_1$ et $s_2$ sont non adjacents et s’il existait une corde à l’intérieur de $S_1$ ou $S_2$ on aurait un chemin plus court. Cela contredit donc l’hypothèse de cordalité de $G$.

De ce fait, on a montré que si $G$ est un graphe cordal, alors ses séparateurs minimaux sont des cliques.

$4.$ On note que tous les sommets d’un graphe complet sont simpliciaux.

Soit $\mathcal{P}(n)$ la proposition : « Un graphe cordal non complet à $k$ sommets, où $2\leq k \leq n$, possède deux sommets simpliciaux non adjacents »

Dans le cas d’un graphe à deux sommets, s’il n’est pas une clique, alors le graphe n’a pas d’arêtes. De ce fait, les deux sommets n’ont pas de voisins et sont bien simpliciaux.

Soit $n \geq 2$. On suppose $\mathcal{P}(n)$ vrai et on cherche à prouver $\mathcal{P}(n+1)$.

Soit $G$ un graphe chordal non complet à plus de $2$ sommets. Si $G$ à moins de $n$ sommets, par $\mathcal{P}(n)$ il possède deux sommets simpliciaux non adjacents. Supposons maintenant que $G$ a $n+1$ sommets. Il nous faut juste prouver que $G$ possède deux sommets simpliciaux non adjacents. Soit $W$ un séparateur minimal de $G$ et $S_1$ et $S_2$ deux composantes connexes du sous-graphe induit par $S \smallsetminus W$. On s’intéresse maintenant au sous-graphe induit par $S_1 \cup W$. Si il est complet, alors on considère $x \in S_1$ qui est donc simplicial dans $G$. Sinon, par $\mathcal{P}(n)$, on a deux sommets simpliciaux non adjacents. Or, on rappelle que $W$ est une clique. De ce fait, il existe $x \in S_1$ simplicial dans le sous-graphe induit par $S_1 \cup W$, et donc par définition de $S_1$, simplicial dans $G$. On trouve de même $y \in S_2$ simplicial dans $G$.

On a donc bien trouvé deux sommets simplicial non adjacent, ce qui prouve $\mathcal{P}(n+1)$ et achève la récurrence.

$5.$ Montrons que si un graphe possède un ordre parfait d’élimination alors il est cordal. Soit $G$ un graphe qui possède un ordre parfait d’élimination. Si $G$ n’a pas de cycle de taille supérieur à $4$ alors il est cordal. Sinon, soit $k \geq 4$ et $s_1, \ldots, s_k, s_1$ un cycle de $G$. Sans pertes de généralités, on peut supposer que $s_1$ est le plus grand dans l’ordre d’élimination. Cela implique donc que $s_k$ et $s_2$ sont adjacents. De ce fait, $G$ possède un corde. Il en résulte que $G$ est cordal.

Prouvons maintenant la réciproque et supposons que $G$ est cordal. On sait que tout graphe cordal possède au moins un sommet simplical. De plus, le sous-graphe induit d’un graphe cordal est un graphe cordal. Il en résulte qu’on peut construire un ordre parfait d’élimination de façon décroissante en sélectionnant un sommet simplicial puis en le supprimant avant de recommencer.

Ainsi on a donc qu’un graphe est cordal si et seulement si il possède un ordre parfait d’élimination.

$6.$ On note qu’on a un algorithme qui nous permet de construire l’ordre parfait d’élimination d’un graphe cordal. On visite chaque sommet selon l’ordre d’élimination parfait et on lui assigne première couleur qui n’est pas utilisé pour colorier un de ses voisins déjà visité. Chaque sommet visité fait partie d’une clique de la taille de ses voisins déjà coloré plus un. De ce fait, la couleur attribuée est toujours plus petite ou égale à la taille de la plus grande clique du graphe.

Or la taille de la plus grande clique du graphe est une borne minimal au nombre chromatique. Ainsi, on ne peut utiliser moins de couleurs. Il en résulte que notre coloration est optimale.

$7.$ De la question précédente on en déduit que le nombre chromatique d’un graphe cordal est égale à la taille de sa plus grande clique. De plus, comme le sous-graphe induit d’un graphe cordal est également un graphe cordal, cela reste vrai pour tous ses sous-graphes induits. Il en résulte donc que les graphes cordales sont des graphes parfaits.

Exercices en liens

Les graphes d’intervalles

On sait que le problème de coloration des graphes est difficile. Cependant, il existe certaines familles de graphes pour lequel le problème de coloration est polynomial. C’est le cas pour les graphes d’intervalles que nous étudions ici.

Exercice

On considère un ensemble d’intervalle fermé $\left(I_k\right)_{k \leq n}$. On appelle graphe d’intervalles associé, noté $G=(A,S)$, le graphe de $n$ sommets où chaque sommets représente un intervalle, et deux sommets $u$ et $v$ sont connectés par une arête si et seulement si $I_u \cap I_v \neq \emptyset$.

$1.$ On considère une clique de $G$. Que peut-on dire de l’intersection des intervalles associés ?

$2.$ Donner un algorithme de coloration d’un graphe d’intervalle et prouver son optimalité.

On dit que $\mathcal{H}$ est un sous-graphe induit d’un graphe $\mathcal{G}$, si l’ensemble des sommets de $\mathcal{H}$ est un sous-ensemble de l’ensemble des sommets de $\mathcal{G}$ et que $x$ et $y$ sont liés par une arête dans $\mathcal{H}$ si et seulement si ils sont liés par une arête dans $\mathcal{G}$.

On dit qu’un graphe est un graphe parfait si le nombre chromatique de chacun de ses sous-graphes induit, est égale à la taille de la plus grande clique du sous-graphe.

$3.$ Prouver que les graphes d’intervalles sont des graphes parfaits.

Correction

$1.$ L’intersection des intervalles associés à une clique de $G$ est non vide. En effet, soit $J_1, \ldots, J_k$ une clique de $G$. Si $\displaystyle \bigcap\limits_{i\leq k} J_i = \emptyset$ alors on a $l \geq 2$ tel que $\mathcal{J} = \displaystyle \bigcap\limits_{i \lt l} J_i \neq \emptyset$ et $\displaystyle \mathcal{J} \cup J_l = \emptyset$. Autrement dit, soit l’intervalle $J_l$ termine avant que $\mathcal{J}$ commence, soit l’inverse. Par symétrie, supposons que $J_l$ se termine en premier et notons $f$ sa date de fin. Notons $d$ la date de début de $\mathcal{J}$. On a $i \lt l$ tel que $i$ commence après $d$. En effet, s’ils commençaient tous strictement avant, la date de début de $\mathcal{J}$ seraient antérieur à $d$ ce qui est absurde. De ce fait, $J_l \cup J_i = \emptyset$ ce qui contredit l’hypothèse qu’ils soient dans la même clique.

De ce fait, l’intersection des intervalles associés à une clique de $G$ est non vide. Réciproquement, si l’intersection d’un ensemble d’intervalles de $G$ est non vide, alors ils forment une clique.

$2.$ On propose l’algorithme suivant : on trie les intervalles par dates de début, puis pour tous les intervalles on lui assigne la plus petite couleur non-utilisée par un intervalle visité précédemment et qui le chevauche.

On s’assure donc que deux intervalles voisins n’ont pas la même couleur. Il s’agit donc bien d’un algorithme de coloration. Montrons maintenat qu’il est optimal.

Pour montrer que notre algorithme précédent utilise le moins de couleurs possible, il suffit de remarquer que si on assigne la couleur $c$ à un sommet alors ce sommet fait partie d’une clique de taille au moins $c$.

En effet, le nombre chromatique d’un graphe est toujours supérieur à la taille de sa plus grande clique. Si on montre que la plus grande couleur utilisée est de la taille de la plus grande clique, on aura montré qu’on ne peut utiliser moins de couleurs.

Lorsqu’on assigne une couleur $c \geq 2$ à un intervalle $\mathcal{I} = [\,d\,;\,f\,]$, cela signifie que $c-1$ intervalles $J_1, \ldots, J_{c-1}$ ayant commencé avant $\mathcal{I}$ se terminent après $d$. Donc on a :

\[\{d\} \subset \left(\bigcup\limits_{i \leq c-1} J_i\right) \cup \mathcal{I} \]

Ainsi, $\mathcal{I}$ appartient à une clique de taille au moins $c$. Donc, notre algorithme de coloration est bien optimale.

$3.$ On a montré à la question précédente que le nombre chromatique d’un graphe d’intervalle est égale à la taille de sa plus grande clique. De plus, on note que le sous-graphe d’un graphe d’intervalle est toujours un graphe d’intervalle. Il en résulte que les graphes d’intervalles sont des graphes parfaits.

Exercices en lien

Le problème de la couverture par sommet

Exercice

Une couverture par sommet d’un graphe $G=(S,A)$ non orienté est un sous ensemble $W \subseteq S$ tel que pour chaque arrête $(u,v) \in A$ on a $u \in W$ ou $v \in W$. Le problème de décision de la couverture par sommet, appelé en anglais vertex cover et désigné par la suite par VC, est le suivant :

Entrée : Un graphe $G = (S,A)$ et un entier $k$.

Sortie : Existe-t-il une couverture par somme de $G$ de taille $k$ ?

Ce problème fait partie des 21 problèmes NP-complet de Karp qui ont été prouvé NP-complet par Richard Karp en 1972.

$1.$ Montrer que VC est dans NP.

On effectue une réduction à partir de Clique : le problème de l’existence d’une clique de taille $l$ dans un graphe $G$. Considérons une instance $\displaystyle \left(G=\left(S,A\right),\;l\right)$ de clique.

$2.$ Montrer que $G$ a une clique de taille $l$ si et seulement si $\bar{G}$, le complémentaire de $G$, a une couverture par sommet de taille $|S| – l$.

$3.$ Conclure.

À présent que nous avons montré que VC est NP-complet, on note que $k$ est un paramètre du problème. On peut donc se demander ce qui se passe si $k$ est fixé.

$4.$ Montrer que pour tout $k$ entier, le problème $k$-VC qui prend en entrée un graphe $G$ représentée sous forme de matrice d’adjacence et vérifie s’il existe une couverture par sommet de taille exactement $k$ se résout en temps cubique en le nombre de sommets.

Correction

$1.$ On donne comme certificat une liste de $k$ sommets et on vérifie en temps polynomiale en la taille du graphe qu’ils constituent bien d’une couverture par sommet. De ce fait, VC appartient à NP.

$2.$ Supposons que $G$ a une clique de taille $l$ et soit $C$ l’ensemble des sommets de cette clique. On note que pour toute arrête $(x,y)$ dans $\bar{G}$ on ne peut avoir $x \in C$ et $y \in C$, car cela contredirait le fait que $C$ soit une clique dans $G$. Ainsi $S \smallsetminus C$ est une couverture par sommet de $\bar{G}$ et il en résulte donc que $\bar{G}$ admet une couverture par sommet de taille $|S|-l$.

Réciproquement, si $\bar{G}$ possède une couverture par sommet de taille $|S|-l$, on note $V$ cette couverture. Par définition, il n’y a aucune arrête entre les éléments de $S \smallsetminus V$. De ce fait, $S \smallsetminus V$ constitue une clique dans le complémentaire de $\bar{G}$. On a donc bien exhibé une clique de taille $l$ dans $G$.

$3.$ On peut transformer tout problème de Clique en un problème de VC en temps polynomiale. Or Clique est un problème NP-complet. Il en résulte que VC est NP-difficile. Or VC est dans NP, donc VC est un problème NP-complet.

$4.$ Notons que pour toute arrête $(s,t)$ de $G$ et toute couverture par sommet $V$ de $G$, on a au moins $s$ ou $t$ dans $V$. Autrement dit, pour tout sommet $s$, soit $s \in V$ soit tous ses voisins font partie de $V$. Cela nous donne donc l’algorithme récursif suivant.

algrorithme recursif pour résoudre vertex cover

Dans le pire des cas, notre algorithme tourne en $O\left(2^{k}n^{3}\right)$ étapes. Il est important de noter que $k$ ne fait pas partie de l’instance du problème $k$-VC. Ainsi, le facteur $2^{k}$ ne varie pas suivant la taille de $G$ et n’est donc qu’une constante. Ainsi, kVertexCover fonctionne en temps $O\left(n^{3}\right)$.

Exercice en lien

Sudoku #3

Sudoku haché #2

English version here

Un nouveau sudoku haché ! Les règles sont sous la grille ! Amusez-vous bien.

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 des doubles flèches est divisible par le carré du nombre le plus proche de la double flèche.

Bonne chance !

Et si vous aimez ce type de sudoku, un autre sudoku haché est présent ici !

Distance d’édition

Étant donné deux textes, il est parfois utile de savoir à quel point ils sont semblables ou différents. Un des outils utilisé pour répondre à ce problème est la distance de Levenshtein ou distance d’édition. Elle est notamment utilisé dans les correcteurs orthographiques.

Exercice

À partir d’un mot donné, on définit les opérations élémentaires comme l’ensemble d’actions suivants :

  • Suppression d’une lettre
  • Insertion d’une lettre
  • Substitution d’une lettre par une autre.

On définit alors la distance d’édition $d$ entre deux mots comme le nombre d’opérations élémentaires nécessaires pour passer d’un mot à l’autre.

Pour $x$ un mot, on note $x_k$ la $k$-ème lettre de $x$. De plus on note $x^i$ le préfixes de $x$ composés de ses $i$ premières lettres. Ainsi on a $x^{0} = \epsilon$.

$1.$ Montrer que $d$ définit bien une distance.

$2.$ Quelle est la valeur de $d(x^i,y^0)$ ?

$3.$ Exprimer $d(x^i,y^j)$ en fonction de mots plus petits.

$4.$ Donner un algorithme pour calculer $d(x,y)$.

$5.$ Quel est sa complexité ?

Correction

$1.$ On rappel qu’une distance est un fonction $f$ positive à deux paramètres qui vérifie les propriétés de séparation (annulation de $f(x,y)$ si et seulement si $x = y$), de symétrie et l’inégalité triangulaire. La fonction $d(x,y)$ est une fonction positive qui ne s’annule que s’il n’y a pas d’opérations élémentaires à effectuer pour passer de $x$ à $y$, donc si $x=y$. Elle est également symétrique. En effet si on peut aller de $u$ à $v$ en une opération élémentaire, alors on peut aller de $v$ à $u$ également en une opération. Il nous reste à montrer que $d$ satisfait bien l’inégalité triangulaire. Si on avait $z$ tel que $d(x,z)+d(z,y)$ soit supérieur strictement à $d(x,z)$ cela signifierait qu’en considérant le chemin minimal pour aller de $x$ à $z$ puis de $z$ à $y$, on aurait un chemin de $x$ à $y$ de taille plus courte que $d(x,y)$ ce qui contredirait notre définition.

Ainsi $d$ définit bien une distance.

$2.$ On désigne la taille d’un mot $x$ par $|x|$. Commençons par noter que $d(x,y) \geq ||x|-|y||$. En effet, une opération élémentaire ne modifie la taille d’un mot que d’au plus une lettre. Ainsi, comme $y^0 = \epsilon$ on a $|y^0|=0$. On note donc que $d(x^i,y^0) \geq |x^i|$. Or le chemin qui consiste à ajouter une à une les lettres de $x_i$ prend $|x_i|$ étapes. On a donc :

\[d(x^i,y^0) = i\]

$3.$ Commençons par remarquer qu’il existe un chemin de taille minimal de $x$ à $y$ où chaque lettre n’est modifié qu’au plus une fois et que les modifications peuvent être effectuées dans l’ordre que l’on souhaite. En effet, si une solution nous incite à effectuer une opération sur une lettre à laquelle on a déjà touché, on aurait pu effectuer l’opération la première fois. De ce fait, les lettres sont indépendantes et peuvent être modifiées dans n’importe quel ordre.

Soit $i,j \geq 1$. On s’intéresse aux deux dernières lettres de $x^i$ et $y^j$. On note qu’une solution optimale ne permet pas de supprimer $x_i$ et d’ajouter $y_i$. En effet, si une telle solution existait, on remarque qu’en substituant $x_i$ en $y_i$ on gagne une étape. Il ne reste donc que trois possibilités. Soit on a modifié $x_i$ en $y_i$, ce qui a un coût de $0$ dans le cas où $x_i=y_i$, soit on a supprimé $x_i$ et dans ce cas là, il nous reste à transformer $x^{i-1}$ en $y^{j}$ ce qui a un coût de $d(i-1,j)$. Enfin, soit on a supprimé $y_j$ et il nous faut modifier $x^{i}$ en $y^{j-1}$. Notre but est de prendre la solution la moins coûteuse, ce qui nous permet donc d’obtenir la formule suivant.

\begin{align*} \forall\;0 \leq i \leq |x|,\quad d(x^i,y^0) = &\; i \\ \forall\;0 \leq j \leq |y|,\quad d(x^0,y^j) = &\; j \end{align*}

\[\forall\;1 \leq i \leq |x|,\quad 1 \leq j \leq |y|,\]

\[d(x^i,y^j) = \min(d(x^{i-1},y^{j-1}) + \delta_{i,j},\; d(x^{i-1},y^{j}) + 1,\; d(x^{i},y^{j-1}) + 1)\]

où $\delta_{i,j}$ vaut $1$ si $x_i \neq y_j$ et $0$ sinon.

On remarque que lors d’un calcul récursif de $d(x,y)$ on recalcule souvent les mêmes objets. En réalité si on écrit une fonction récursive, le temps de calcul est exponentiel. C’est pourquoi, il est plus efficace de stocker les valeurs dans un tableau pour proposer l’algorithme de programmation dynamique suivant.

Algorithme distance edition

$5.$ L’initialisation a un coût en $O(|x|+|y|)$. Le calcul des éléments du tableau est en $O(1)$ par case. Ainsi notre algorithme tourne en $\displaystyle \boxed{O\left(|x||y|\right)}$.

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.