Théorie de la compléxité
Introduction
La théorie de la complexité est une branche de l'informatique théorique qui étudie les ressources nécessaires pour résoudre des problèmes informatiques, telles que le temps et l'espace. Elle permet de classifier les problèmes en fonction de leur difficulté et d'analyser la faisabilité des algorithmes qui les résolvent.
Concepts Clés
- Complexité Temporelle : Le temps nécessaire pour exécuter un algorithme en fonction de la taille de l'entrée.
- Complexité Spatiale : L'espace mémoire nécessaire pour exécuter un algorithme en fonction de la taille de l'entrée.
Classes de Complexité
Les classes de complexité sont des catégories qui regroupent des problèmes en fonction des ressources nécessaires pour les résoudre.
Classe P
Définition : La classe P (Polynomial Time) contient les problèmes qui peuvent être résolus par un algorithme déterministe en temps polynomial.
Exemple de Vulgarisation
Histoire : Imagine que tu es un bibliothécaire et que tu dois vérifier si un livre spécifique est dans une étagère triée. Utiliser une recherche binaire (qui divise l'étagère en deux à chaque étape) permet de trouver le livre en un nombre de comparaisons proportionnel au logarithme de la taille de l'étagère.
Exemple en
JavaScript : Recherche Binaire
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // Élément trouvé
} else if (arr[mid] < target) {
left = mid + 1; // Rechercher dans la moitié droite
} else {
right = mid - 1; // Rechercher dans la moitié gauche
}
}
return -1; // Élément non trouvé
}
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 7;
console.log(binarySearch(arr, target)); // Output: 3
Classe NP
Définition : La classe NP (Non-deterministic Polynomial Time) contient les problèmes pour lesquels une solution proposée peut être vérifiée en temps polynomial par un algorithme déterministe.
Exemple de Vulgarisation
Histoire : Imagine que tu es un professeur qui doit vérifier si un étudiant a résolu un puzzle correctement. Vérifier la solution est beaucoup plus rapide que de trouver la solution toi-même.
Exemple en JavaScript : Problème de la Clique
Vérifier si un sous-ensemble de sommets dans un graphe forme une clique.
function isClique(graph, vertices) {
for (let i = 0; i < vertices.length; i++) {
for (let j = i + 1; j < vertices.length; j++) {
if (!graph[vertices[i]].includes(vertices[j])) {
return false;
}
}
}
return true;
}
const graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
};
const vertices = [0, 1, 2];
console.log(isClique(graph, vertices)); // Output: true
Classe NP-Complet
Définition : Les problèmes NP-complets sont les problèmes les plus difficiles de la classe NP. Un problème est NP-complet s'il est dans NP et que tout autre problème dans NP peut être réduit à ce problème en temps polynomial.
Exemple de Vulgarisation
Histoire : Imagine que résoudre un puzzle particulier permettrait de résoudre tous les autres puzzles de la même difficulté. Ce puzzle est considéré comme le plus difficile de son genre.
Exemple en JavaScript : Problème du Sac à Dos
Bien que nous ne résolvions pas le problème en entier, nous pouvons formuler une partie du problème du sac à dos pour illustrer la complexité.
function knapsack(values, weights, capacity) {
const n = values.length;
const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
const values = [60, 100, 120];
const weights = [10, 20, 30];
const capacity = 50;
console.log(knapsack(values, weights, capacity)); // Output: 220
Classe NP-Difficile
Définition : Les problèmes NP-difficiles sont au moins aussi difficiles que les problèmes NP-complets. Ils ne doivent pas nécessairement être dans NP (c'est-à-dire que leurs solutions ne doivent pas nécessairement être vérifiables en temps polynomial).
Exemple de Vulgarisation
Histoire : Imagine que tu as un puzzle si complexe que même vérifier si une solution est correcte prend autant de temps que de résoudre le puzzle lui-même.
Réductions de Problèmes
La réduction de problèmes consiste à transformer un problème en un autre problème de manière à ce que la solution au deuxième problème permette de résoudre le premier.
Exemple : Réduction du Problème du Voyageur de Commerce (TSP) à un Problème de Circuit Hamiltonien
Histoire : Si tu peux trouver un chemin qui visite chaque ville exactement une fois (circuit Hamiltonien), tu peux résoudre le problème de trouver le chemin le plus court (TSP).
Introduction
Le problème du Voyageur de Commerce (TSP) et le problème du Circuit Hamiltonien sont deux problèmes classiques en informatique théorique. Le TSP consiste à trouver le chemin le plus court passant par chaque ville exactement une fois et revenant à la ville de départ. Le problème du Circuit Hamiltonien consiste à trouver un chemin qui visite chaque sommet d'un graphe exactement une fois.
La réduction consiste à montrer comment une solution au problème du Circuit Hamiltonien peut être utilisée pour résoudre le TSP.
Concepts Clés
- TSP (Voyageur de Commerce) : Trouver le chemin le plus court passant par chaque ville exactement une fois et revenant à la ville de départ.
- Circuit Hamiltonien : Trouver un chemin dans un graphe qui visite chaque sommet exactement une fois.
Étapes de la Réduction
- Convertir le problème TSP en un problème de Circuit Hamiltonien.
- Résoudre le problème de Circuit Hamiltonien.
- Utiliser la solution du Circuit Hamiltonien pour résoudre le TSP.
Exemple
Étape 1 : Conversion en un Problème de Circuit Hamiltonien
Supposons que nous avons un graphe complet où chaque ville est un sommet, et chaque arête a un poids correspondant à la distance entre deux villes.
Étape 2 : Résolution du Problème de Circuit Hamiltonien
Trouvons un circuit Hamiltonien dans le graphe. Cela signifie trouver un chemin qui visite chaque sommet exactement une fois.
Étape 3 : Utilisation de la Solution
Une fois que nous avons trouvé le circuit Hamiltonien, ce chemin est une solution pour le TSP, car il visite chaque ville exactement une fois.
Implémentation en JavaScript
Nous allons illustrer cela par un exemple simple.
Graphique d'Exemple
const graph = {
A: { B: 10, C: 15, D: 20 },
B: { A: 10, C: 35, D: 25 },
C: { A: 15, B: 35, D: 30 },
D: { A: 20, B: 25, C: 30 }
};
// Fonction pour vérifier si un chemin est un circuit Hamiltonien
function isHamiltonianPath(graph, path) {
const n = Object.keys(graph).length;
const visited = new Set(path);
// Vérifier si le chemin visite chaque sommet exactement une fois
if (visited.size !== n) {
return false;
}
// Vérifier si chaque sommet est connecté au suivant dans le chemin
for (let i = 0; i < path.length - 1; i++) {
if (!graph[path[i]][path[i + 1]]) {
return false;
}
}
return true;
}
// Exemple de chemin pour vérifier
const path = ['A', 'B', 'D', 'C'];
console.log(isHamiltonianPath(graph, path)); // Output: true (si c'est un chemin hamiltonien)
Fonction TSP
function tspNearestNeighbor(graph, start) {
const n = Object.keys(graph).length;
const visited = new Set();
const path = [start];
let totalDistance = 0;
let current = start;
while (visited.size < n) {
visited.add(current);
let nearest = null;
let minDistance = Infinity;
for (let neighbor in graph[current]) {
if (!visited.has(neighbor) && graph[current][neighbor] < minDistance) {
minDistance = graph[current][neighbor];
nearest = neighbor;
}
}
if (nearest === null) break;
path.push(nearest);
totalDistance += minDistance;
current = nearest;
}
// Retourner à la ville de départ
totalDistance += graph[current][start];
path.push(start);
return { path, totalDistance };
}
// Résoudre le problème TSP
const tspResult = tspNearestNeighbor(graph, 'A');
console.log(`Chemin TSP : ${tspResult.path}`);
console.log(`Distance Totale : ${tspResult.totalDistance}`);
Explication du Code
- Vérification du Circuit Hamiltonien : La fonction
isHamiltonianPathvérifie si un chemin donné visite chaque sommet exactement une fois et si chaque sommet est connecté au suivant. - Solution du TSP par l'Heuristique du Plus Proche Voisin : La fonction
tspNearestNeighborutilise l'heuristique du plus proche voisin pour trouver un chemin approximatif pour le TSP. Elle commence par une ville de départ, visite la ville la plus proche non visitée, et continue jusqu'à ce que toutes les villes soient visitées, puis retourne à la ville de départ.
La réduction du problème du Voyageur de Commerce (TSP) au problème du Circuit Hamiltonien montre comment une solution pour le Circuit Hamiltonien peut être utilisée pour résoudre le TSP. Cette approche illustre le concept de réduction de problèmes en théorie de la complexité, où résoudre un problème peut aider à résoudre un autre problème. Les exemples en JavaScript montrent comment vérifier un circuit Hamiltonien et comment utiliser une heuristique pour trouver une solution approximative au TSP.
Conclusion
La théorie de la complexité est essentielle pour comprendre la faisabilité des algorithmes et pour classifier les problèmes en fonction de leur difficulté. Les classes de complexité telles que P, NP, NP-complet et NP-difficile aident à déterminer si des solutions efficaces peuvent être trouvées pour différents problèmes et comment ces problèmes sont interconnectés. Les réductions de problèmes montrent comment la résolution d'un problème peut aider à résoudre d'autres problèmes, soulignant l'importance des problèmes NP-complets dans l'informatique théorique et appliquée.