Question de mise en confiance
Indécidabilité d'un problème ≡ il n'existe pas d'algorithme résolvant ce problème de manière générale ≡ il n'existe pas de machine de Turing qui prend en entrée les données (Pb) et qui s'arrête toujours en donnant une solution.
Exemple : Le problème de l'arrêt pour les machines de Turing est indécidable. Un Pb accepté par une machine de Turing est dit Turing-acceptable ou récursivement énumérable. Si la machine de Turing s'arrête sur toutes les entrées possibles (c-à-d pour tous les informations i, i ∈ P ou i ∉ P), alors il est dit Turing-décidable ou récursif.
Exercice 1 : Algorithmes de Graphes et Complexité
1. Montrons :
...
2. Polynôme :
...
3. Pour montrer que Cij est un plus court chemin de Xi à Xj, nous allons utiliser un argument de parcourement par l'absurde (preuve par l'absurde) en supposant le contraire, c'est-à-dire que Cij n'est pas un plus court chemin de Xi à Xj. Supposons que Cij ne soit pas le plus court chemin de Xi à Xj, alors il existe un autre chemin P de Xi à Xj tel que la somme des poids des arêtes de P soit inférieure à la somme des poids des arêtes de Cij. Maintenant, Cij est un sous-chemin de C, et nous savons que C est un plus court chemin de X1 à XK. Donc, la somme des poids des arêtes de C est minimale parmi tous les chemins de X1 à XK.
Maintenant, nous pouvons diviser C en deux parties : C1, qui va de X1 à Xi, et C2, qui va de Xj à XK. Donc, C = C1 + Cij + C2. Maintenant, P peut être vu comme un chemin de Xi à Xj suivi de C2. La somme des poids des arêtes de P est donc égale à la somme des poids des arêtes de Cij (car P est supposé être plus court que Cij) plus la somme des poids des arêtes de C2. Mais comme C est un plus court chemin de X1 à XK, la somme des poids des arêtes de C2 doit être minimale. Donc, la somme des poids des arêtes de P doit être plus grande que la somme des poids des arêtes de Cij, ce qui contredit notre hypothèse initiale. Par conséquent, Cij doit être un plus court chemin de Xi à Xj.
4. En déduisant de la question 3, nous comprenons que le concept de plus court chemin entre deux nœuds dans un graphe est basé sur l'optimalité locale (optimum local). C'est-à-dire que si un chemin est le plus court entre deux nœuds consécutifs, alors ce chemin fait partie intégrante du plus court chemin entre les nœuds d'origine et de destination.
Dans un graphe acyclique, l'absence de cycles garantit que le chemin le plus court entre deux nœuds est déterminé uniquement par les chemins précédents et ne nécessite pas de réexamen constant des mêmes nœuds. En d'autres termes, il existe un chevauchement entre les sous-problèmes de recherche de plus court chemin pour différentes paires de nœuds.
La programmation dynamique consiste à résoudre des problèmes en décomposant le problème global en sous-problèmes plus petits et en stockant les résultats intermédiaires (dans ce cas, les distances les plus courtes entre les nœuds) pour éviter de recalculer les mêmes valeurs. Dans le contexte de la recherche du plus court chemin dans un graphe acyclique, cette méthode est applicable, car le problème présente une structure de sous-problèmes imbriqués qui permet d'optimiser le calcul des distances les plus courtes.
5.
6.
7. Fonction en C :
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_NŒUDS 100
struct Noeud {
int données;
struct Noeud* suivant;
};
struct Graphe {
struct Noeud* listeAdjacence[MAX_NŒUDS];
int nœuds;
};
struct Graphe* créerGraphe(int nœuds) {
struct Graphe* graphe = (struct Graphe*)malloc(sizeof(struct Graphe));
graphe->nœuds = nœuds;
for (int i = 0; i < nœuds; i++) {
graphe->listeAdjacence[i] = NULL;
}
return graphe;
}
void ajouterArête(struct Graphe* graphe, int src, int dest) {
struct Noeud* nouveauNoeud = (struct Noeud*)malloc(sizeof(struct Noeud));
nouveauNoeud->données = dest;
nouveauNoeud->suivant = graphe->listeAdjacence[src];
graphe->listeAdjacence[src] = nouveauNoeud;
}
bool aCycleBFS(struct Graphe* graphe) {
bool visité[MAX_NŒUDS];
bool dansLaFile[MAX_NŒUDS];
int file[MAX_NŒUDS];
int début = 0, fin = 0;
memset(visités, false, sizeof(visités));
memset(dansLaFile, false, sizeof(dansLaFile));
for (int i = 0; i < graphe->nœuds; i++) {
if (!visités[i]) {
file[fin++] = i;
visités[i] = true;
dansLaFile[i] = true;
while (début != fin) {
int courant = file[début++];
dansLaFile[courant] = false;
struct Noeud* temp = graphe->listeAdjacence[courant];
while (temp) {
int voisin = temp->données;
if (!visités[voisin]) {
file[fin++] = voisin;
visités[voisin] = true;
dansLaFile[voisin] = true;
} else if (dansLaFile[voisin]) {
return true;
}
temp = temp->suivant;
}
}
}
}
return false;
}
8. Montrons :
L’algorithme de Kruskal peut s’exécuter en O(A log S), en utilisant des tas binaires ordinaires. Le temps d’exécution de l’algorithme de Kruskal sur un graphe G = (S, A) dépend de l’implémentation de la structure d’ensembles disjoints. L’initialisation de l’ensemble E en ligne 1 requiert un temps O(1), et le temps pris par le tri des arcs en ligne 4 est O(A log A). (Nous tiendrons compte du coût des |S| opérations CRÉER-ENSEMBLE de la boucle pour des lignes 1–3.) La boucle pour des lignes 5–8 fait O(A) opérations TROUVER-ENSEMBLE et UNION sur la forêt d’ensembles disjoints. Avec les |S| opérations CRÉER-ENSEMBLE, cela fait un total de O((S + A) a(S)) temps, où a est la fonction à très lente croissance. Comme G est censé être connexe, on a |A| ≥ |S| - 1, et donc les opérations d’ensembles disjoints prennent un temps O(A α(S)). En outre, comme α(|S|) = O(log S) = O(log A), le temps d’exécution total de l’algorithme de Kruskal est O(A log A). On observe que |A| < |S|^2, on a log|A| = O(log S), et l’on peut donc reformuler le temps d’exécution de l’algorithme de Kruskal comme étant O(A log S).
Algorithme Kruskal :
Algorithme Kruskal (w, E)
1 E <- Ø
2 pour chaque sommet v ∈ S[G]
3 faire CRÉER-ENSEMBLE(v)
4 trier les arêtes de A par ordre croissant de poids w
5 pour chaque arête (u, v) ∈ A prise par ordre de poids croissant
6 faire si TROUVER-ENSEMBLE(u) ≠ TROUVER-ENSEMBLE(v)
7 alors E <- E ∪ {(u, v)}
8 UNION(u, v)
9 retourner E
8. Les problèmes de la 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.
Formulation de 2 problèmes NP-Complet :
1. Problème DE LA Chaîne Hamiltonienne :
Données : un graphe non-orienté G, deux sommets u et v distincts de G.
Question : G contient-il une chaîne hamiltonienne entre u et v ?
2. Problème du Voyageur de Commerce :
Données : Un graphe complet G muni d’une fonction de coût positif sur les arêtes, et un entier k.
Question : Existe-t-il un circuit passant au moins une fois par chaque ville et dont la somme des coûts des arêtes est au plus k ?
Exercice 2 : Arbres et Arbres de recherche
1. Le nombre maximal de nœuds dans un arbre binaire de hauteur h :
Le nombre maximal de nœuds dans un arbre binaire de hauteur h peut être calculé en considérant que chaque niveau de l'arbre double le nombre de nœuds par rapport au niveau précédent. Au niveau 0, il y a 1 nœud (la racine). Au niveau 1, il peut y avoir au plus 2 nœuds, et ainsi de suite. Donc, le nombre maximal de nœuds dans un arbre binaire de hauteur h est 2h - 1. Cette formule est basée sur le fait qu'un arbre binaire de hauteur h a h niveaux, et chaque niveau peut avoir au plus 2h nœuds. La soustraction de 1 est nécessaire car la racine est comptée comme un nœud initial, et le nombre total de nœuds est toujours un de moins que 2h.
Source : Pandacodeur.com
2. Un arbre binaire complet de hauteur h :
Un arbre binaire complet de hauteur h possède au plus 1 + 2 + … + 2h = 2h+1 - 1 nœuds internes. Autrement dit, un arbre ayant n nœuds internes est de hauteur au moins égale à log(n + 1) - 1. La hauteur minimale d'un arbre à n nœuds internes est atteinte lorsque l'arbre est parfaitement équilibré et que les feuilles sont toutes sur un ou deux niveaux. log(n + 1) - 1 ≤ h.
3. Pour trier un ensemble de n entiers à l'aide d'un arbre binaire de recherche :
Vous pouvez effectuer l'insertion des entiers un par un dans l'arbre. L'insertion se fait en suivant la propriété de l'arbre binaire de recherche, en plaçant chaque entier à sa position appropriée dans l'arbre en fonction de sa valeur. Une fois que tous les entiers sont insérés, vous pouvez effectuer un parcours infixe de l'arbre pour récupérer les clés dans l'ordre trié.
La complexité de cet algorithme dépend de la forme de l'arbre binaire de recherche résultant. Dans le meilleur des cas, si l'arbre est équilibré, la hauteur de l'arbre sera d'environ log2(n), ce qui donne une complexité moyenne de O(n log n) pour l'insertion des n entiers et un parcours infixe. Cependant, dans le pire des cas, si l'arbre est déséquilibré et ressemble à une liste chaînée, la hauteur de l'arbre sera n, ce qui donnera une complexité de O(n2).
Donc, la complexité de l'algorithme de tri à l'aide d'un arbre binaire de recherche peut varier considérablement en fonction de la forme de l'arbre, mais en moyenne, elle est de l'ordre de O(n log n) si l'arbre est équilibré.
(a) Preuve par induction sur la hauteur :
On peut prouver cette proposition par induction sur la hauteur de x. Si la hauteur de x est 0, x est une feuille et le sous-arbre enraciné à x contient 0 nœud interne, c’est-à-dire 2Hn(x) - 1 = 20 - 1. Soit x un nœud de hauteur h(x) > 0. Ce nœud a deux fils, g et d. Dans ce cas, Hn(g) ≥ Hn(x) - 1 et Hn(d) ≥ Hn(x) - 1. De plus, la hauteur de g et de d est inférieure à la hauteur de x, donc, en appliquant l’hypothèse d’induction à g et d, les sous-arbres enracinés à g et d possèdent chacun au moins 2Hn(g) - 1 ≥ 2Hn(x) - 1 - 1 et 2Hn(d) - 1 ≥ 2Hn(x) - 1 - 1 nœuds internes. Il s’ensuit que le sous-arbre enraciné à x possède au moins :
2(2Hn(x) - 1 - 1) + 1 = 2Hn(x) - 1 nœuds internes.
(b) Hauteur de l’arbre :
Soit h la hauteur de l’arbre. D’après la propriété 3 (Si un nœud est rouge, alors ses deux fils sont noirs), au moins la moitié des nœuds d’un chemin simple reliant la racine de l’arbre à une feuille doivent être noirs (preuve facile par l’absurde). En conséquence, la hauteur noire de la racine vaut au moins h/2, donc n ≥ 2h/2 - 1, d’où h ≤ 2 log(n + 1).
Montrons que h ≤ logt((n + 1)/2)
\( h \leq \log_t \left(\frac{n+1}{2}\right) \)
Réponse :
A la profondeur \( k \), on a au moins \( 2^{tk} - 1 \) nœuds
Et au moins \( 2^{tk} - 1 \) clés
\[ \begin{array}{|c|c|c|} \hline \text{Profondeur} & \text{Nombre minimum de nœuds} & \text{Nombre minimum de clés} \\ \hline 0 & 1 & 1 \\ 1 & 2t^0 = 2 & 2t^0(t - 1) = 2(t - 1) \\ 2 & 2t^1 = 2t & 2t^1(t - 1) = 2t(t - 1) \\ 3 & 2t^2 = 2t^2 & 2t^2(t - 1) \\ \vdots & \vdots & \vdots \\ h & 2t^h - 1 & 2t^h(t - 1) \\ \hline \end{array} \]
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) = 1 + 2t^h - 2 = 2t^h - 1 \] \[ n \geq 2t^h - 1 \] \[ n + 1 \geq 2t^h \] \[ \frac{n + 1}{2} \geq t^h \] \[ h \leq \log_t \left(\frac{n + 1}{2}\right) \]
4. Arbres rouges et noirs :
Les arbres rouges et noirs garantissent que l'arbre reste équilibré en suivant des règles strictes lors de l'insertion ou de la suppression de nœuds. Ces règles garantissent que la hauteur de l'arbre est limitée à O(log n), où n est le nombre de nœuds dans l'arbre. Pour trier un ensemble de n entiers à l'aide d'un arbre rouge-noir, vous insérerez chaque entier dans l'arbre en respectant les règles de l'arbre rouge-noir, ce qui garantira que l'arbre reste équilibré. Une fois tous les entiers insérés, vous effectuerez un parcours infixe de l'arbre pour récupérer les clés dans l'ordre trié. La complexité de cet algorithme sera en moyenne O(n log n), car l'arbre rouge-noir maintient un équilibre relatif. Cela signifie que, même dans le pire des cas, la hauteur de l'arbre restera proportionnelle à log n. La complexité est donc de O(n log n).
5. B-arbres :
Un B-arbre est un arbre T possédant les propriétés suivantes :
- 1) Toute feuille a la même profondeur, qui est la hauteur h de l'arbre.
- 2) Chaque nœud x contient les champs ci-dessous :
- n[x], le nombre de clés conservées actuellement par le nœud x,
- les n[x] clés elles-mêmes, stockées par ordre non décroissant : clé1[x] ≤ clé2[x] ≤ … ≤ clé_n[x],
- feuille[x], une valeur booléenne qui vaut VRAI si x est une feuille et FAUX si x est un nœud interne.
- 3) Chaque nœud interne x contient également n[x] + 1 pointeurs c1[x], c2[x], ..., c_n[x] + 1[x] vers ses enfants. Les feuilles n’ont pas d'enfants, et leurs pointeurs ne sont donc pas définis.
- 4) Les clés clé_i[x] déterminent les intervalles de clés stockés dans chaque sous-arbre : si k_i est une clé stockée dans le sous-arbre de racine c[x], alors clé1 ≤ clé_i[x] ≤ clé2 ≤ … ≤ clé_n[x] ≤ k_(n[x] + 1).
- 5) Il existe un majorant et un minorant pour le nombre de clés pouvant être contenues par un nœud. Ces bornes peuvent être exprimées en fonction d’un entier fixé t ≥ 2, appelé le degré minimal du B-arbre :
- Tout nœud autre que la racine doit contenir au moins t - 1 clés. Tout nœud interne autre que la racine possède donc au moins t enfants. Si l’arbre n’est pas vide, la racine doit posséder au moins une clé.
- Tout nœud peut contenir au plus 2t - 1 clés. Un nœud interne peut donc posséder au plus 2t enfants. On dit qu’un nœud est complet s’il contient exactement 2t - 1 clés.