Catégorie : Exercices

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 à […]

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 […]

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, […]

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 […]

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 […]

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 […]

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 […]

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 […]