Sujet d'Examen ALGORITHMIQUE AVANCÉS & COMPLEXITÉ

Question de mise en confiance

Quels sont les propriétés d'un B-arbre ?

Exercice 1: Arbres et arbres de recherche (05 pts)

Considérons un arbre binaire de n nœuds. Notons f son nombre de feuilles et h sa hauteur.

Tous les arbres considérés seront supposés non vides. Répondez en vous justifiant :

1. Quelle est la hauteur minimale d'un arbre de n nœuds ? (0,5 pt)
2. Montrez que le nombre de branches vides (nombre de fils gauches et de fils droits vides) d'un arbre à n nœuds est égal à n + 1. (1 pt)
3. Montrez que le nombre de feuilles est inférieur ou égal à (n+1)/2 et qu'il y a égalité si et seulement si chaque nœud de l'arbre est soit une feuille, soit possède deux fils. (1 pt)
4. Montrez que le nombre de feuilles d'un arbre est égal au nombre de nœuds de degré deux, plus un. (1 pt)
5. Quel est le nombre maximal de feuilles d'un B-arbre de hauteur h ? (1 pt)
6. Pour un B-arbre d'ordre t de n nœuds et de hauteur h, montrez que h.

Exercice 2: Théorie des graphes et calcul parallèle (05 pts)

1. Qu'est-ce que le calcul parallèle ? (0,5 pt)
2. Présentez la classification de Flynn pour les architectures de machines parallèles. (1,5 pt)
3. Soit G = (S, A) un graphe, un sous-ensemble des sommets de G est stable s'il ne contient pas de paire de sommets adjacents. Montrez que tout sous-ensemble d'un ensemble stable est stable. (1,5 pt)
4. Dédure de l'item 3 que c'est la même chose de se donner un k-coloriage d'un graphe que de le partitionner en k sous-ensembles stables. (0,5 pt)
5. Soit G un graphe non orienté, montrez qu'au moins un des deux graphes, G ou son complémentaire, est connexe. (1 pt)

Exercice 3: Programmation dynamique et paradigme glouton (05 pts)

1. Définir un algorithme glouton et donnez la différence entre la programmation dynamique et le paradigme glouton. (1 pt)
2. Enoncez le problème d'ordonnancement d'une chaîne de multiplication de matrices (MCOP). (0,5 pt)
3. Démontrez que le problème MCOP est un problème de programmation dynamique. (2 pts)
4. Donnez la formulation de programmation dynamique de deux autres problèmes de la même classe que le problème MCOP. (1 pt)

Exercice 4: NP-complétude (05 pts)

Une clique d'un graphe non orienté est un sous-ensemble des sommets de ce graphe dont le sous graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. La taille d'tme clique est le nombre de sommets qu'elle contient. Le problème de la CLIQUE est un problème de décision pour savoir si un graphe G donné contient une Clique d'une taille k également donné

1. Quelle est la différence entre les classes de problèmes suivants : P, NP, NP-complet ? (1 pt)
2. Montrez que le problème CLIQUE appartient à NP. (1,5 pts)
3. Montrez que 3-SAT ≤_P CLIQUE. Pour ce faire, vous pouvez convertir une formule ϕ de 3-SAT en un graphe G et un entier k de sorte que ϕ la formule est satisfiable si et seulement si G a une CLIQUE de taille k. (2 pts)
4. Qu'est-ce qu'une machine de Turing ? (0,5 pt)

Exercice 1 : Arbres et Arbres de recherche … B-Arbre (05 pts)

Dans cet exercice, on notera n le nombre de nœuds d’un arbre binaire, f son nombre de feuilles et h sa hauteur. Tous les arbres considérés seront supposés non vides.

1) Hauteur minimale d'un arbre de n nœuds :

Réponse :

\( n \leq 2^{h+1} - 1 \iff n + 1 \leq 2^{h+1} \iff \log_2 (n + 1) \leq h + 1 \iff h \geq \log_2 (n + 1) - 1 \)

D’où la minoration : \( h \geq \lceil \log_2 (n+1) - 1 \rceil \).

2) Nombre de branches vides :

Réponse :

On distinguera les nœuds ayant zéro, un et deux fils. On note :

• p le nombre de nœuds ayant zéro fils ;
• q le nombre de nœuds ayant un fils ;
• r le nombre de nœuds ayant deux fils.

On a les relations suivantes :

• \(n = p + q + r\) : un nœud a soit zéro, soit un, soit deux fils.
• \(0 \times p + 1 \times q + 2 \times r = n - 1\) : tous les nœuds, la racine exceptée, ont un père.
• \(2 \times p + 1 \times q + 0 \times r = b\) : on compte les branches vides de chaque nœud.

En additionnant les deux dernières équations, on obtient :

\(2(p + q + r) = b + n - 1 \iff 2n = b + n - 1 \iff b = n + 1\).

3) Montrer que le nombre de feuilles \(f\) est inférieur ou égal à \((n + 1) / 2\) :

Réponse :

Nous avons vu que : \(2 \times p + 1 \times q + 0 \times r = b\) avec \(b = n + 1\). Or, \(p = f\), les nœuds sans fils sont exactement les feuilles ! Puisque \(q \geq 0\), nous avons \(2 \times f \leq n + 1\), ce qui établit l’inégalité recherchée. Nous avons égalité quand \(q = 0\), c’est-à-dire quand l’arbre ne contient pas de nœuds ayant un seul fils.

4) Calcul de \(p\) :

Réponse :

Nous utilisons encore les relations entre \(p\), \(q\) et \(r\) : \(p + q + r = n\) et \(q + 2r = n - 1\). En éliminant \(q\) entre ces deux équations, on obtient : \(p = r + 1\), qui est le résultat recherché.

5) Nombre maximal de feuilles d'un B-arbre de hauteur \(h\) :

Réponse :

Si \(h = 0\), c’est-à-dire si l’arbre se réduit à sa racine, \(n = 1\). Sinon, nous raisonnons par récurrence : le sous-arbre gauche (ou droit) de la racine est un arbre de hauteur \(h - 1\) et il a un nombre maximal de nœuds. Si on note \(n(h)\) le nombre maximal de nœuds d’un arbre de hauteur \(h\), alors :

\[ n(h) = \begin{cases} 1 & \text{si } h = 0 \\ 1 + 2 \times n(h - 1) & \text{sinon}. \end{cases} \]

On a donc \(n(h) = 2^{h+1} - 1\). Le nombre maximal de nœuds d’un arbre de hauteur \(h\) est donc \(2^{h+1} - 1\), et on a toujours : \(n \leq 2^{h+1} - 1\).

6) Montrons que \(h \leq \log_t \left(\frac{n+1}{2}\right)\) :

Réponse :

À la profondeur … nous avons au moins … nœuds et au moins … clefs :

D'où \(n \geq 1 + 2(t-1) \sum_{i=1}^{h} t^{i-1} = 1 + 2(t-1) \frac{t^h - 1}{t-1} = 1 + 2(t^h - 1)\). Donc :

\[ n \geq 2t^h - 1 \implies n + 1 \geq 2t^h \implies \frac{n+1}{2} \geq t^h \implies h \leq \log_t \left(\frac{n+1}{2}\right). \]

Exercice 2 : Théorie des Graphes et Calcul parallèle (05 pts)

1) Réponse : Le calcul parallèle est un mode de traitement des données dans lequel plusieurs tâches sont exécutées en même temps sur différents processeurs ou sur différents nœuds d'un système informatique.

2) Présentez la classification de Flynn pour les architectures de machines parallèles.

Réponse : 

3) Soit G=(S,A) un graphe, un sous-ensemble des sommets de G est stable s’il ne contient pas de pair de sommets adjacents. Montrer que tout sous-ensemble d’un ensemble stable est stable.

Réponse : Soient G = (S, A) un graphe, avec S l'ensemble de sommets et A l'ensemble des arêtes, et soit S' un sous-ensemble stable de S, c'est-à-dire un sous-ensemble tel que pour tout u, v dans S', il n'existe pas de (u, v) dans A. Nous allons démontrer que pour tout sous-ensemble T de S', T est également stable. Notons que T peut être défini comme T = {x dans S' | x appartient à T}. Soient u et v deux éléments de T, alors u et v sont également des éléments de S', donc (u, v) n'appartient pas à A. Par conséquent, nous pouvons démontrer que T est également stable. En utilisant la définition formelle, nous pouvons écrire cette démonstration de la manière suivante : Soit T un sous-ensemble de S', alors pour tout u, v dans T, nous avons (u, v) ∉ A, car S' est stable et u, v ∈ S'. Cela montre que la stabilité est une propriété transitive pour les sous-ensembles d'un graphe G, ce qui signifie que si un sous-ensemble est stable, alors tous ses sous-ensembles sont également stables.

4) Réponse : D’après la question (3) , Un k-coloriage de G est une partition de π de S en K ensemble stable S1, S2, S3, …, SK appelés les couleurs du coloriage. Alors, un graphe est donc K-coloriable si son nombre chromatique X(G)= min{π | π est un coloriage} ≤ k.

5) Soit G un graphe non orienté, montrez qu’au moins un des deux graphes, G ou son complémentaire, est connexe.

Réponse :

Proposition 1 : (Il faut noter que je décompose la solution ici en 2 donc c’est à vous de choisir ce qui vous convient le mieux) Soit G = (S, A) un graphe non orienté, avec S l'ensemble de sommets et A l'ensemble des arêtes. Le complémentaire de G, noté G', est un graphe (S, A') tel que A' = {(u, v) | (u, v) n'appartient pas à A et u, v dans S}. Nous allons démontrer que, pour un graphe non orienté G, soit G est connexe, soit son complémentaire G' est connexe. Supposons que G n'est pas connexe, c'est-à-dire qu'il existe un sous-ensemble S' de sommets tels que pour tout u dans S', il n'existe pas de chemin de u à un autre sommet v dans S \ S'. Alors, pour tout (u, v) avec u dans S' et v dans S \ S', (u, v) appartient à A', car (u, v) n'appartient pas à A. Par conséquent, tous les sommets de S' sont connectés entre eux par des arêtes dans A', ce qui signifie que G' est connexe. En utilisant la définition formelle, nous pouvons écrire cette démonstration de la manière suivante : Soit G = (S, A) un graphe non orienté. Soit G' = (S, A') son complémentaire. Alors, soit G est connexe, soit G' est connexe. Supposons que G n'est pas connexe, c'est-à-dire qu'il existe un sous-ensemble S' de sommets tels que pour tout u dans S', il n'existe pas de chemin de u à un autre sommet v dans S \ S'. Alors, pour tout (u, v) avec u dans S' et v dans S \ S', (u, v) appartient à A', ce qui signifie que G' est connexe.

Proposition 2 : (Il faut noter que je décompose la solution ici en 2 donc cet à vous de choisir ce qui vous convient le mieux) Une autre façon de démontrer que, pour un graphe non orienté G, soit G est connexe, soit son complémentaire G' est connexe, est d'utiliser la contrapositive. Supposons que ni G ni son complémentaire G' ne sont connexes. Alors, il existe des sous-ensembles disjoints S1 et S2 de sommets tels que pour tout u dans S1 et v dans S2, il n'existe pas de chemin entre u et v dans G ni dans G'. Cependant, cela signifie que toutes les paires de sommets u dans S1 et v dans S2 sont adjacentes dans G, ce qui est contraire à notre hypothèse selon laquelle ni G ni G' ne sont connexes. Par conséquent, nous pouvons en déduire que soit G est connexe, soit son complémentaire G' est connexe. En utilisant la définition formelle, nous pouvons écrire cette démonstration de la manière suivante : Soit G = (S, A) un graphe non orienté. Soit G' = (S, A') son complémentaire. Alors, soit G est connexe, soit G' est connexe. Supposons que ni G ni G' ne sont connexes. Alors, il existe des sous-ensembles disjoints S1 et S2 de sommets tels que pour tout u dans S1 et v dans S2, il n'existe pas de chemin entre u et v dans G ni dans G'. Cependant, cela signifie que toutes les paires de sommets u dans S1 et v dans S2 sont adjacentes dans G, ce qui est contraire à notre hypothèse selon laquelle ni G ni G' ne sont connexes. Par conséquent, nous pouvons en déduire que soit G est connexe, soit son complémentaire G' est connexe.

Exercice 3 : Programmation dynamique et paradigme glouton (05 pts)

Question 1

Définir algorithme glouton et donnez la différence entre la programmation dynamique et le paradigme glouton.

Réponse :

Définition : L'algorithme glouton est une méthode d'optimisation qui peut être considérée comme une stratégie de choix optimiste qui suppose que les choix locaux optimaux à chaque étape seront combinés de manière optimale pour donner une solution optimale globale.

Différence : Tout d’abord, il faut noter que l'algorithme glouton et la programmation dynamique sont deux approches différentes pour résoudre des problèmes d'optimisation. La différence fondamentale entre les deux approches est la façon dont elles abordent le choix des décisions à chaque étape du processus de résolution. Dans l'algorithme glouton, les décisions sont prises en fonction de la valeur locale immédiate de chaque option, sans tenir compte des conséquences futures potentielles. Cette approche est basée sur une stratégie de choix optimiste qui suppose que les décisions prises à chaque étape seront optimalement combinées pour donner une solution optimale globale. Cependant, cette approche peut souvent aboutir à des solutions sub-optimales, car les décisions prises à chaque étape ne tiennent pas compte de la façon dont elles peuvent affecter les décisions futures.

La programmation dynamique, d'un autre côté, aborde le choix des décisions de manière plus réfléchie. Au lieu de prendre des décisions en fonction de la valeur immédiate de chaque option, la programmation dynamique considère les conséquences futures potentielles de chaque décision en divisant le problème en sous-problèmes plus petits et en mémorisant les solutions intermédiaires pour éviter les redondances de calcul. Cette approche est souvent utilisée pour résoudre des problèmes qui peuvent être décomposés en sous-problèmes récurrents, où certaines parties du problème peuvent être réutilisées pour trouver la solution optimale globale.

En conclusion, la différence entre l'algorithme glouton (optimum local) et la programmation dynamique (plusieurs solutions optimales) réside dans leur manière de gérer les décisions à chaque étape du processus de résolution.

Question 2

Énoncer le problème d’ordonnancement d’une chaîne de multiplication de matrices (MCOP).

Réponse : Le problème d'ordonnancement de chaîne de multiplication de matrices consiste à déterminer l'ordre optimal dans lequel les matrices d'une chaîne doivent être multipliées pour minimiser le nombre total de multiplications scalaires effectuées. (En gros, le nombre de parenthèses possibles d’une expression à n termes est exponentiel en n.)

Exercice 4 : NP Complétude (05 pts)

1) Quelle est la différence entre les classes de problèmes suivant : P, NP, NP Complet ?

Réponse : La classe P, NP et NP-complet sont des classes de complexité algorithmique qui décrivent la difficulté des problèmes informatiques.

• Classe P (Polynomial time solvable problems) : Les problèmes de la classe P sont ceux pour lesquels une solution peut être trouvée en un temps polynomial par rapport à la taille de l'entrée. Autrement dit, le temps de traitement pour résoudre un problème de la classe P augmente de manière modérée avec la croissance de la taille de l'entrée.
• Classe NP (Nondeterministic Polynomial time solvable problems) : Les problèmes de la classe NP sont ceux pour lesquels il est facile de vérifier une solution, mais difficile de trouver la solution en un temps polynomial. En d'autres termes, il existe une solution qui peut être vérifiée rapidement pour les problèmes de la classe NP, mais il n'y a pas de garantie que cette solution puisse être trouvée en un temps polynomial.
• Classe NP-complet : Les problèmes de la classe NP-complet sont des problèmes NP qui ne peuvent être résolus en un temps polynomial, mais pour lesquels tout autre problème NP peut être réduit à eux. Cela signifie que si une solution efficiente (en un temps polynomial) était trouvée pour un problème NP-complet, alors des solutions efficientes pourraient également être trouvées pour tous les autres problèmes NP.

En résumé, la classe P décrit les problèmes qui peuvent être résolus en un temps polynomial, la classe NP décrit les problèmes qui peuvent être vérifiés rapidement, mais pour lesquels la résolution peut prendre plus de temps, et la classe NP-complet décrit les problèmes NP les plus difficiles qui peuvent servir de référence pour évaluer la difficulté de tous les autres problèmes NP.

Approche par un tableau

Une comparaison entre les classes de problèmes P, NP et NP-complets :

(Source : PandaCodeur.com)