Section VI — Algorithmique, complexité et structures de données

Données : - Boucle externe : i prend les valeurs 2^p pour p = 0, 1, ..., m, avec m = floor(log2(n)). - Boucle interne : j parcourt 1 à i, soit i itérations. - Coût par itération : O(1). Raisonnement chiffré : Le nombre total d'exécutions du corps de la boucle est : T(n) = Σ(p=0 à m) 2^p Il s'agit d'une somme géométrique de raison 2. T(n) = (2^(m+1) - 1) / (2 - 1) = 2^(m+1) - 1. Par définition de m = floor(log2(n)), on a : 2^m <= n < 2^(m+1) En multipliant l'inégalité par 2 : 2^(m+1) <= 2n Et comme 2^(m+1) > n, on obtient : n < 2^(m+1) <= 2n En substituant dans l'expression de T(n) : n - 1 < T(n) <= 2n - 1 Résultat final : T(n) est majoré par 2n - 1 et minoré par n - 1 pour tout n >= 1. Par définition de la notation Theta, la complexité temporelle exacte est : Θ(n) Hypothèses : - Le corps des boucles s'exécute en temps constant O(1). - n est un entier strictement positif. - La suite i = 1, 2, 4, ... correspond strictement aux puissances de 2 (2^p). - Aucune opération supplémentaire de complexité non linéaire n'intervient dans les boucles.

Données du problème Réurrence : \(T(n) = 2T(n/2) + n \log n\) Forme générale : \(T(n) = aT(n/b) + f(n)\) avec \(a = 2\), \(b = 2\), \(f(n) = n \log n\). Analyse comparative Exposant critique : \(\log_b a = \log_2 2 = 1\), donc \(n^{\log_b a} = n^1 = n\). Comparaison de \(f(n)\) avec \(n^{\log_b a}\) : \(f(n) = n \log n\) croît plus rapidement que \(n\), mais pas de manière polynomiale (il n'existe aucun \(\epsilon > 0\) tel que \(n \log n = \Omega(n^{1+\epsilon})\)). Le théorème master standard ne couvre pas directement ce cas. On utilise la méthode de l'arbre de récursion. Calcul détaillé par arbre de récursion Profondeur de l'arbre : \(h = \log_2 n\) (on suppose \(n\) puissance de 2 pour la simplicité, résultat identique asymptotiquement). Niveau \(i\) (avec \(0 \le i < h\)) : - Nombre de nœuds : \(2^i\) - Taille de chaque sous-problème : \(n/2^i\) - Coût par nœud : \(f(n/2^i) = (n/2^i) \log(n/2^i)\) - Coût total du niveau \(i\) : \(2^i \times (n/2^i) \log(n/2^i) = n (\log_2 n - i)\) Somme des coûts internes (niveaux \(0\) à \(h-1\)) : \(S = \sum_{i=0}^{h-1} n (\log_2 n - i) = n \sum_{i=0}^{h-1} (h - i)\) La somme arithmétique vaut \(\sum_{k=1}^{h} k = \frac{h(h+1)}{2}\). Donc \(S = n \cdot \frac{h(h+1)}{2} = \frac{n}{2} h^2 + \frac{n}{2} h\). En remplaçant \(h = \log_2 n\) : \(S = \frac{n}{2} \log_2^2 n + \frac{n}{2} \log_2 n\). Coût des feuilles (niveau \(h\)) : Nombre de feuilles : \(2^h = n\). Coût total des feuilles : \(n \cdot T(1)\). Hypothèse standard : \(T(1) = \Theta(1)\), donc coût des feuilles = \(\Theta(n)\). Total exact \(T(n) = S + n T(1) = \frac{n}{2} \log_2^2 n + \frac{n}{2} \log_2 n + \Theta(n)\). Résultat asymptotique Le terme dominant est \(\frac{n}{2} \log_2^2 n\). La base du logarithme ne change pas la classe asymptotique. \(T(n) = \Theta(n \log^2 n)\). Hypothèses - \(T(1) = \Theta(1)\) - \(n\) est suffisamment grand pour que les termes de plus haut degré dominent - La récurrence est bien définie pour tout \(n\) (extension standard aux entiers non puissances de 2 via \(\lfloor n/2 \rfloor\) ou \(\lceil n/2 \rceil\) sans modifier la complexité)

Comparaison des mécanismes : Le parcours en largeur (BFS) explore le graphe niveau par niveau, en visitant d'abord tous les voisins directs du nœud de départ (distance 1), puis les voisins de ces voisins (distance 2), et ainsi de suite. Il utilise une file d'attente pour gérer l'ordre de visite. Le parcours en profondeur (DFS) explore une branche du graphe aussi loin que possible avant de revenir en arrière (backtracking) pour explorer une autre branche. Il utilise une pile d'attente ou la récursivité pour gérer l'ordre de visite. Garantie d'optimalité : Le BFS garantit l'optimalité pour trouver un plus court chemin dans un graphe non pondéré. Explication de l'optimalité du BFS : Dans un graphe non pondéré, le coût d'un chemin est égal au nombre d'arêtes qu'il contient. Le BFS garantit la découverte du plus court chemin car il explore les sommets par ordre de distance croissante (monotonie de la distance). Le premier nœud cible rencontré par l'algorithme l'est nécessairement via le chemin comportant le minimum d'arêtes. Dès que le nœud cible est atteint, l'algorithme peut s'arrêter en étant certain qu'aucun chemin plus court n'existe. Pourquoi le DFS ne garantit pas l'optimalité : Le DFS ne garantit pas l'optimalité car il peut emprunter une branche très longue ou mener à une impasse avant de découvrir un chemin plus court existant ailleurs dans le graphe. Il est possible que le DFS rencontre le nœud cible après avoir traversé une multitude d'arêtes, alors qu'un chemin beaucoup plus court (avec moins d'arêtes) relie directement le départ à l'arrivée, sans que le DFS ne l'ait encore exploré.

Hypothèses raisonnables - Les éléments du tableau sont hashables ou appartiennent à un domaine de valeurs entières bornées. - On accepte une complexité en temps moyenne O(n) grâce à une table de hachage, ou on impose une plage de valeurs entières contiguës pour garantir un pire cas strict O(n). Algorithme (approche par table de hachage) 1. Initialiser un ensemble vide nommé `vus`. 2. Parcourir le tableau `T` élément par élément avec la variable `val` : a. Calculer le complémentaire `cible - val`. b. Si `cible - val` appartient à `vus`, retourner Vrai. Deux indices distincts existent, leur somme vaut la cible. c. Sinon, ajouter `val` à `vus`. 3. Si la boucle termine sans retour, retourner Faux. Analyse de complexité - Temps : O(n) en moyenne. Chaque élément est traité une seule fois, les opérations d'insertion et de recherche dans un ensemble de hachage coûtent O(1) en moyenne. - Espace : O(n) au pire. L'ensemble `vus` peut contenir tous les éléments du tableau. - Pire cas théorique avec hachage : O(n^2) en cas de collisions massives, mais ce scénario est évité par une fonction de hachage robuste et une réhashing dynamique. Pour un pire cas strict O(n), on utilise une table de hachage directe (tableau booléen) si les valeurs sont des entiers dans un intervalle [min, max] de taille M, avec un coût en espace O(M). Implémentation et vérification ```python def detecte_somme(T, cible): vus = set() for val in T: if (cible - val) in vus: return True vus.add(val) return False # Vérification fonctionnelle print(detecte_somme([2, 7, 11, 15], 9)) print(detecte_somme([3, 2, 4], 6)) print(detecte_somme([3, 3], 6)) print(detecte_somme([1, 2, 3], 10)) ``` Sortie de la vérification : True True True False Conclusion L'algorithme parcourt le tableau une seule fois. Il stocke les valeurs déjà rencontrées dans un ensemble de hachage. Pour chaque élément, il vérifie en temps constant si le complémentaire nécessaire à la cible a déjà été vu. La complexité temporelle est O(n) en moyenne, la complexité spatiale est O(n). L'approche est optimale pour le problème général sans tri préalable.

La complexité temporelle dans le pire cas du tri fusion est O(n log n). Justification de la récurrence : Le tri fusion repose sur une stratégie diviser pour régner. Pour trier une structure de n éléments, l'algorithme suit exactement 3 étapes : 1. Division : la structure est découpée en 2 sous-structures de taille n / 2. Ce découpage s'effectue en temps constant, noté O(1). 2. Résolution récursive : chaque sous-structure est triée de manière indépendante. Cela engendre 2 appels récursifs, chacun traitant un problème de taille n / 2, soit 2 T(n / 2). 3. Combinaison (fusion) : les 2 sous-structures triées sont combinées en une seule structure triée. La fusion nécessite de parcourir et de recomparer chaque élément une fois, ce qui requiert un temps linéaire proportionnel à n, noté cn, où c est une constante. En regroupant ces étapes, on obtient la relation de récurrence suivante : T(n) = 2 T(n / 2) + cn, avec T(1) = d (constante). Résolution de la récurrence : On utilise la méthode de l'arbre de récursion. - Profondeur de l'arbre : à chaque appel récursif, la taille du problème est divisée par 2. On atteint la taille de base 1 après log2(n) niveaux. - Coût par niveau : au niveau k (de 0 à log2(n)), il existe 2^k sous-problèmes, chacun de taille n / 2^k. Le coût de fusion à ce niveau est 2^k * c * (n / 2^k) = cn. Le coût total est donc constant à chaque niveau. - Coût total : il y a log2(n) + 1 niveaux. Le coût global vaut (log2(n) + 1) * cn = cn log2(n) + cn. En complexité asymptotique, on néglige les termes de moindre ordre et les constantes multiplicatives, ce qui donne T(n) = O(n log n). Vérification avec le théorème maître : La récurrence est de la forme T(n) = a T(n / b) + f(n) avec a = 2, b = 2, f(n) = cn. On calcule n^(log_b(a)) = n^(log2(2)) = n^1 = n. Comme f(n) = Θ(n), on se situe dans le cas 2 du théorème maître, qui stipule que T(n) = Θ(n log n). Le résultat est confirmé. Conclusion : la complexité dans le pire cas est strictement O(n log n).

Explication du mécanisme d'échec L'algorithme de Dijkstra repose sur une stratégie gloutonne qui suppose qu'une fois un sommet extrait de la file de priorité, sa distance minimale depuis la source est définitive. Cette propriété est garantie uniquement lorsque tous les poids d'arêtes sont supérieurs ou égaux à 0. Avec des poids négatifs, il devient possible qu'un chemin plus court vers un sommet déjà extrait existe via un autre sommet qui sera traité plus tard. Comme Dijkstra ne revisite jamais les sommets marqués comme définitifs, il ignore les mises à jour potentielles apportées par les arêtes à poids négatif, ce qui conduit à des distances finales incorrectes. Contre-exemple vérifiable Sommets : A, B, C Arêtes et poids : - A -> B : 2 - A -> C : 3 - C -> B : -2 Source : A Trace pas à pas de Dijkstra 1. Initialisation : d[A] = 0, d[B] = infini, d[C] = infini. File de priorité : [(A, 0)]. 2. Extraction de A. Relaxation des voisins : d[B] = 2, d[C] = 3. File de priorité : [(B, 2), (C, 3)]. 3. Extraction de B (distance minimale 2). Le sommet B est marqué comme définitif. 4. Extraction de C (distance 3). Relaxation de l'arête C -> B : nouvelle distance = 3 + (-2) = 1. Comme B est déjà définitif, l'algorithme ne met pas à jour sa valeur et conserve d[B] = 2. 5. Fin de l'exécution. Résultat renvoyé : d[B] = 2. Comparaison avec la réalité Le chemin optimal réel est A -> C -> B, dont le coût total est 3 + (-2) = 1. L'algorithme renvoie 2, soit une valeur surestimée. L'échec provient du fait que B a été figé prématurément avant que l'arête à poids négatif (C -> B) ne soit prise en compte. Conclusion Dijkstra ne peut pas gérer les poids négatifs car son hypothèse de finalisation gloutonne est violée. Pour des graphes avec des poids négatifs, il faut utiliser l'algorithme de Bellman-Ford ou de SPFA, qui autorisent la revisite des sommets et détectent les cycles négatifs.

Données du graphe orienté pondéré : - A → B : 4 - A → C : 1 - C → B : 2 - B → D : 1 - C → D : 5 Raisonnement (algorithme de Dijkstra) : Initialisation : d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞ 1. Extraction de A (d=0) : - d(B) = min(∞, 0+4) = 4 - d(C) = min(∞, 0+1) = 1 2. Extraction de C (d=1) : - d(B) = min(4, 1+2) = 3 - d(D) = min(∞, 1+5) = 6 3. Extraction de B (d=3) : - d(D) = min(6, 3+1) = 4 4. Extraction de D (d=4) : aucun arc sortant. Code de vérification et sortie : ```python import heapq graphe = {'A': [('B', 4), ('C', 1)], 'B': [('D', 1)], 'C': [('B', 2), ('D', 5)], 'D': []} def dijkstra(g, s): dist = {n: float('inf') for n in g} dist[s] = 0 pq = [(0, s)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, w in g[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w heapq.heappush(pq, (dist[v], v)) return dist print(dijkstra(graphe, 'A')) ``` Sortie : `{'A': 0, 'B': 3, 'C': 1, 'D': 4}` Résultats finaux des distances minimales depuis A : - Distance A → A : 0 - Distance A → B : 3 - Distance A → C : 1 - Distance A → D : 4

Algorithme de détection de cycle dans un graphe orienté Méthode recommandée : Recherche en profondeur (DFS) avec codage des états des sommets. Principe Chaque sommet est dans l'un des trois états suivants : - 0 (blanc) : non visité - 1 (gris) : en cours de visite, présent dans la pile d'appels récursifs (chemin actuel) - 2 (noir) : visite terminée, tous les descendants ont été explorés Un cycle est détecté si, lors du parcours DFS, on rencontre un sommet déjà dans l'état gris. Cela signifie qu'un chemin revient vers un ancêtre dans l'arbre de parcours, formant ainsi un cycle. Pseudocode Fonction DetectCycle(graphe) : n = nombre de sommets etats = tableau de taille n initialise a 0 Pour chaque sommet i de 0 a n-1 : Si etats[i] == 0 : Si DFS_VerifieCycle(i, graphe, etats) == Vrai : Retourner Vrai Retourner Faux Fonction DFS_VerifieCycle(u, graphe, etats) : etats[u] = 1 // Marquer comme en cours de visite Pour chaque voisin v de u dans graphe : Si etats[v] == 1 : Retourner Vrai // Cycle detecte Si etats[v] == 0 : Si DFS_VerifieCycle(v, graphe, etats) == Vrai : Retourner Vrai etats[u] = 2 // Marquer comme termine Retourner Faux Analyse de complexité Données : V sommets, E arcs, graphe représenté par des listes d'adjacence. Raisonnement : - Chaque sommet est initialisé une fois, puis visité exactement une fois. Cela représente un coût linéaire en V. - Chaque arc est examiné exactement une fois lors de l'itération sur les voisins. Cela représente un coût linéaire en E. - La pile d'appels récursifs ne dépasse jamais la hauteur du plus long chemin simple, donc au maximum V appels empilés simultanément dans le pire des cas. Résultat : - Complexité temporelle : O(V + E) - Complexité spatiale : O(V) (tableau des états + pile d'appels) Vérification de la logique - Si le graphe est acyclique, aucun sommet ne peut être revisité dans l'état gris. L'algorithme parcourt l'ensemble du graphe et retourne Faux. - Si un cycle existe, le DFS pénètre dans une boucle de dépendances. Le premier sommet du cycle revisité est nécessairement dans l'état gris, ce qui déclenche la détection. La propriété est exacte et couvre tous les cas (cycles simples, multiples, ou sous-graphes isolés). Alternative : Le tri topologique de Kahn (algorithme BFS basé sur les degrés entrants). Il détecte un cycle si le nombre de sommets traités est inférieur à V. Complexité identique : O(V + E) en temps, O(V) en espace.

**Complexité moyenne de la recherche** : O(1 + α) **Complexité pire cas de la recherche** : O(n) **Détail des bornes** - Temps moyen : E[T] = c_hachage + c_parcours × (1 + α) = O(1 + α) - α = n / N, où n est le nombre d'éléments insérés et N le nombre de cases (buckets) du tableau. - Si α reste constant (redimensionnement dynamique maintenu), la complexité moyenne est O(1). - Temps pire : toutes les clés peuvent converger vers une même case. La chaîne associée contient n éléments. Le parcours séquentiel d'une liste chainée simple nécessite O(n) opérations. (Si les chaînes sont remplacées par des arbres équilibrés, le pire cas passe à O(log n), mais ce n'est plus l'implémentation standard par chaînage séparé.) **Hypothèses nécessaires** 1. Hypothèse de hachage uniforme simple : chaque clé est indépendante et uniformément répartie sur les N cases. P(case_i) = 1 / N pour tout i. 2. La fonction de hachage s'exécute en temps O(1) et ne dépend pas de la distribution des clés. 3. α est borné supérieurement par une constante (sinon O(1 + α) devient linéaire en n). 4. Les chaînes sont implémentées par des listes linéaires simples. Le parcours s'effectue séquentiellement sans optimisation structurelle. 5. L'élément recherché n'est pas systématiquement le dernier d'une chaîne (l'attente de la position dans la chaîne est (1 + α) / 2 en moyenne, ce qui conserve la borne O(1 + α)). 6. L'implémentation ne réalise pas de rééquilibrage dynamique des chaînes ni de hachage adaptatif. **Vérification de cohérence** - Si n = 0, α = 0, temps moyen = O(1) (recherche échoue immédiatement). - Si N = 1, α = n, temps moyen = O(n), cohérent avec le pire cas. - La borne O(1 + α) provient de la somme du temps de hachage (constant) et du temps moyen de parcours de chaîne (α éléments en moyenne). Aucune contradiction.

Voici la comparaison structurée des trois approches pour trouver l'élément de rang k dans un tableau non trié de taille n. 1. Tri complet Principe : Trier le tableau par ordre croissant, puis accéder à l'indice k-1. Complexité temporelle : O(n log n) dans tous les cas pour les tris optimaux par comparaison. Complexité spatiale : O(1) à O(n) selon l'algorithme (tri fusion en O(n), tri rapide en O(log n) pour la pile, tri par tas en O(1)). Avantages : Implémentation triviale, pré-trie le tableau pour des requêtes ultérieures, stable si nécessaire. Inconvénients : Surcoût systématique si k est petit ou proche de 1/n, car tout le tableau est trié pour un seul accès. 2. Tas (file de priorité) Principe : Maintenir un tas max contenant les k plus petits éléments rencontrés. Parcourir le tableau, insérer chaque élément et extraire le maximum si la taille dépasse k. Complexité temporelle : O(n log k). La construction initiale est ignorée au profit de l'insertion progressive. Complexité spatiale : O(k). Avantages : Adaptable aux flux de données (streaming), efficace si k << n, pas de modification du tableau d'origine. Inconvénients : Surcoût constant lié aux échanges de tas, moins performant que Quickselect pour k proche de n/2. 3. Sélection linéaire (Quickselect / Algorithme de Hoare) Principe : Partitionner le tableau comme le tri rapide autour d'un pivot, mais ne récursiver que sur le sous-tableau contenant l'indice k-1. Complexité temporelle moyenne : O(n). Complexité temporelle pire cas : O(n^2) (cas où le pivot est toujours le minimum ou le maximum). L'algorithme BFPRT (Median of Medians) garantit O(n) dans le pire cas, mais avec une constante multiplicative élevée. Complexité spatiale : O(1) ou O(log n) pour la pile de récursion (tri in-place). Avantages : Optimal en complexité asymptotique moyenne, faible surcoût mémoire, très rapide en pratique. Inconvénients : Pire cas théorique, algorithme non stable, BFPRT lourd en pratique. Tableau comparatif | Méthode | Complexité temporelle (moyenne) | Complexité temporelle (pire cas) | Complexité spatiale | Cas d'usage optimal | |---|---|---|---|---| | Tri complet | O(n log n) | O(n log n) | O(1) à O(n) | k proche de n/2, besoin du tableau trié ultérieurement | | Tas (max-heap taille k) | O(n log k) | O(n log k) | O(k) | Flux de données, k très petit (k << n) | | Sélection linéaire (Quickselect) | O(n) | O(n^2) | O(1) ou O(log n) | k quelconque, tableau en mémoire, besoin de rapidité | | Sélection linéaire (BFPRT) | O(n) | O(n) | O(1) ou O(log n) | Garanties temps réel strictes, k quelconque | Démonstration des complexités (calcul étape par étape) Données : Tableau de taille n, rang k. Quickselect (moyen) : T(n) = n + T(n/2) (la partition coûte n comparaisons, la récursion porte sur la moitié en moyenne) Déploiement : T(n) = n + n/2 + n/4 + n/8 + ... + 1 Somme géométrique : T(n) = n(1 + 1/2 + 1/4 + ...) < 2n Résultat : T(n) = O(n) Tas (max-heap taille k) : Chaque élément du tableau est traité une fois. Coût par élément : O(log k) (insertion ou extraction-max) Nombre d'opérations : n × O(log k) Résultat : T(n) = O(n log k) Comparaison directe - Asymptotique : Quickselect O(n) domine le tri O(n log n) et le tas O(n log k) lorsque k > 2. - Mémoire : Quickselect O(1) est optimal si k est grand. Le tas O(k) est justifié uniquement si k est très petit ou si le tableau est un flux infini. - Pratique : Quickselect est l'algorithme standard (std::nth_element en C++, np.partition en Python). Le tas est privilégié pour les requêtes top-k en streaming. Le tri complet n'est retenu que si le tableau doit être réutilisé trié. Hypothèses - L'ordre des éléments égaux n'est pas préservé (algorithmes non stables). - L'accès aléatoire au tableau est O(1). - Pour k=1 ou k=n, un parcours linéaire O(n) simple suffit, sans structure de données.

Données : - Somme étudiée : S_n = somme_{k=1}^n log(k) - Objectif : déterminer l'ordre asymptotique lorsque n tend vers l'infini. Raisonnement : 1. Identification de la somme : log(a) + log(b) = log(a x b), donc S_n = log(1 x 2 x ... x n) = log(n!). 2. Utilisation de la formule de Stirling (valable pour le logarithme naturel ou décimal, le facteur multiplicatif de base ne change pas l'ordre asymptotique) : log(n!) = n*log(n) - n + O(log(n)). 3. Extraction du terme dominant : Quand n -> infty, le terme n*log(n) lisse les termes -n et O(log(n)). On calcule le rapport avec le candidat n*log(n) : log(n!) / (n*log(n)) = [n*log(n) - n + O(log(n))] / (n*log(n)) = 1 - 1/log(n) + O(log(n)/(n*log(n))) = 1 - 1/log(n) + O(1/n). La limite de ce rapport quand n -> infty est bien 1, car 1/log(n) -> 0 et 1/n -> 0. 4. Conclusion théorique : S_n ~ n*log(n). L'ordre asymptotique est n*log(n). Vérification numérique (laboratoire Python) : J'exécute un calcul numérique pour confirmer que le rapport tend vers 1. Code exécuté : ```python import math for n in [10**3, 10**4, 10**5, 10**6]: s = sum(math.log(k) for k in range(1, n+1)) ratio = s / (n * math.log(n)) print(f"n={n}, ratio={ratio}") ``` Sortie du laboratoire : n=1000, ratio=0.9986326013778143 n=10000, ratio=0.9995727180505394 n=100000, ratio=0.9998351095686573 n=1000000, ratio=0.9999331731686935 Le rapport converge effectivement vers 1, validant l'analyse asymptotique. Résultat final : L'ordre asymptotique de la somme est n*log(n). Plus précisément : somme_{k=1}^n log(k) = n*log(n) - n + O(log(n)). Hypothèse : n tend vers l'infini, log désigne un logarithme de base fixe (>1). Le résultat est indépendant de la base à un facteur multiplicatif constant près.

Définitions NP (Polynomial Nondeterministic) : classe des problèmes de décision pour lesquels toute réponse affirmative dispose d’un certificat de taille polynomiale vérifiable en temps polynomial par une machine de Turing déterministe. NP-difficile (NP-hard) : classe des problèmes (pas nécessairement de décision, pas nécessairement décidables) tels que tout problème de NP peut être réduit à eux par une réduction polynomiale. Un problème est NP-difficile si sa résolution impliquerait, par transformation polynomiale, la résolution de n’importe quel problème de NP. NP-complet : classe des problèmes de décision qui sont simultanément dans NP et NP-difficile. Ce sont les problèmes les plus difficiles de NP au sens des réductions polynomiales. Relations structurelles (valables sans hypothèse sur P et NP) - P est inclus dans NP. - NP-complet est inclus dans NP. - NP-complet est inclus dans NP-difficile. - NP-complet est exactement l’intersection de NP et NP-difficile. - NP-difficile n’est pas inclus dans NP en général. Il contient des problèmes hors NP, y compris des problèmes indécidables comme le problème de l’arrêt. - NP se décompose en deux parties disjointes : les problèmes NP-complets et les problèmes de NP qui ne sont pas NP-difficiles (les problèmes NP-intermédiaires, s’ils existent). Implications selon la relation entre P et NP - Si P = NP, alors NP = P. Tous les problèmes NP-complets appartiendraient à P. La vérification polynomiale coïnciderait avec la résolution polynomiale. Les problèmes NP-difficile resteraient au moins aussi difficiles, mais incluraient toujours des problèmes hors de NP. - Si P ≠ NP, alors aucun problème NP-complet n’appartiendrait à P. La classe NP contiendrait strictement des problèmes non résolubles en temps polynomial déterministe. Le théorème de Ladner garantit alors l’existence de problèmes NP-intermédiaires. - Dans les deux cas, les définitions de NP, NP-difficile et NP-complet et la relation NP-complet = NP ∩ NP-difficile demeurent inchangées. Précisions méthodologiques - La réduction polynomiale est transitive. Si un problème A se réduit à un problème B en temps polynomial et B est NP-difficile, alors A est au moins aussi difficile que B. - Le théorème de Cook-Levin établit que la satisfiabilité booléenne (SAT) est NP-complet. C’est le premier problème démontré dans cette classe. - La classification concerne la complexité théorique asymptotique. Elle ne prédit pas les performances empiriques sur des instances de taille réelle. - Les problèmes d’optimisation ne sont pas directement dans NP, car NP ne concerne que les problèmes de décision. On les qualifie de NP-difficiles ou NP-complets via leur version décisionnelle correspondante.

La recherche binaire réduit itérativement l'espace de recherche en divisant un intervalle `[low, high]` par deux. Un invariant de boucle est indispensable car il constitue la seule garantie formelle que la stratégie de division successive n'exclut jamais la valeur cible, que la boucle se termine bien et que le résultat retourné est correct. Sans invariant, on ne peut pas prouver la correction partielle (l'algorithme retourne l'index exact si l'élément existe) ni la terminaison (les bornes évoluent strictement vers un intervalle vide ou un élément trouvé). L'invariant relie l'état initial, les transformations de `low` et `high`, et le résultat final, et il est le seul moyen de justifier rigoureusement les mises à jour des bornes. Invariant correct : Soit `A` un tableau trié de taille `n`, et `x` la valeur recherchée. Durant toute itération de la boucle, l'invariant suivant est vérifié : « Si `x` appartient à `A`, alors `x ∈ A[low..high]`. » Formulation équivalente et plus précise pour les bornes : « ∀ `i < low`, `A[i] < x` » et « ∀ `j > high`, `A[j] > x`. » Vérification formelle de l'invariant : 1. Initialisation : avant la première itération, `low = 0` et `high = n - 1`. L'intervalle `A[0..n-1]` correspond au tableau entier. L'assertion « Si `x ∈ A`, alors `x ∈ A[0..n-1]` » est trivialement vraie. 2. Conservation : supposons l'invariant vrai en début d'itération. On calcule `mid = floor((low + high) / 2)`. - Si `A[mid] == x`, l'algorithme retourne `mid`. L'objectif est atteint, l'invariant n'est plus requis. - Si `A[mid] < x`, on pose `low = mid + 1`. Comme `A` est trié, tous les indices `≤ mid` vérifient `A[k] ≤ A[mid] < x`, donc `x` ne peut se trouver qu'au-dessus de `mid`. L'intervalle réduit `[mid+1, high]` conserve la propriété « Si `x ∈ A`, alors `x ∈ A[low..high] ». - Si `A[mid] > x`, on pose `high = mid - 1`. Tous les indices `≥ mid` vérifient `A[k] ≥ A[mid] > x`, donc `x` ne peut se trouver qu'en dessous de `mid`. L'intervalle réduit `[low, mid-1]` conserve également l'invariant. 3. Terminaison et correction : la boucle se termine quand `low > high`. À ce stade, l'invariant stipule « Si `x ∈ A`, alors `x ∈ A[low..high] ». Or l'intervalle `[low, high]` est vide, donc la prémisse « `x ∈ A` » est fausse. Le retour d'une valeur indiquant l'absence (par exemple `-1` ou `null`) est donc correct. Si l'algorithme sort via `A[mid] == x`, il retourne un index valide, ce qui est également correct. Sans cet invariant, toute modification des bornes (par exemple `low = mid` au lieu de `mid + 1`, ou `high = mid` au lieu de `mid - 1`) brise la conservation ou empêche la terminaison, ce qui illustre pourquoi l'invariant n'est pas un détail de documentation mais la condition nécessaire et suffisante de la correction de l'algorithme.

Voici l'algorithme de programmation dynamique pour le problème du sac à dos 0/1, suivi de l'analyse rigoureuse de sa complexité pseudo-polynomiale. Algorithme dynamique Entrées : n articles, un tableau de poids w[1..n], un tableau de valeurs v[1..n], une capacité maximale W. Sortie : la valeur maximale achievable sans dépasser la capacité W. Initialisation : créer une table dp de dimensions (n+1) x (W+1), initialisée à 0. dp[i][c] représente la valeur maximale obtenue en utilisant un sous-ensemble des i premiers articles avec une capacité de c. Récurrence : pour chaque article i de 1 à n, et pour chaque capacité c de 0 à W : Si w[i] > c, l'article i ne peut pas être placé dans le sac de capacité c. On hérite de la meilleure valeur sans cet article : dp[i][c] = dp[i-1][c] Sinon, on choisit le maximum entre ne pas prendre l'article i, ou le prendre en ajoutant sa valeur à la meilleure solution restante : dp[i][c] = max(dp[i-1][c], v[i] + dp[i-1][c - w[i]]) Résultat : dp[n][W] contient la valeur optimale. Pour reconstruire la solution, on peut effectuer un parcours à rebours à partir de dp[n][W]. Complexité temporelle La table comporte (n+1) * (W+1) cellules. Chaque cellule est calculée en temps constant O(1). La complexité temporelle totale est donc O(n * W). Complexité spatiale L'algorithme standard utilise une table à deux dimensions, nécessitant O(n * W) espaces mémoire. Une optimisation courante permet de réduire l'espace à O(W) en n'utilisant qu'un tableau unidimensionnel mis à jour sur place, mais cela nécessite de parcourir les capacités en ordre décroissant pour éviter de réutiliser le même article. Caractère pseudo-polynomial La complexité O(n * W) est dite pseudo-polynomiale car elle est polynomiale par rapport à la valeur numérique de W, mais non polynomiale par rapport à la taille de l'encodage de W. Un entier W nécessite environ log2(W) bits pour être représenté. Si l'on note L la taille totale de l'entrée en bits (proportionnelle à n + log(W)), le temps d'exécution devient proportionnel à n * 2^L, ce qui est exponentiel par rapport à la taille de l'entrée. L'algorithme reste donc efficace uniquement lorsque W est de l'ordre de grandeur des autres paramètres, mais devient impraticable pour des capacités très grandes. Le problème du sac à dos 0/1 est NP-complet, ce qui signifie qu'il n'existe pas d'algorithme polynomial vrai en temps, à moins que P = NP. Vérification et limites La récurrence repose sur le principe d'optimalité de Bellman : une sous-solution optimale d'un sous-problème de capacité c avec i articles doit nécessairement contenir une sous-solution optimale pour la capacité c ou c-w[i] avec i-1 articles. Tout écart par rapport à cette structure conduirait à une solution sous-optimale. La méthode garantit une solution exacte, contrairement aux approches heuristiques ou gloutonnes qui ne fournissent qu'une approximation.

Données : graphe simple non orienté à \(n\) sommets. Raisonnement chiffré : - Un graphe simple interdit les boucles (arêtes reliant un sommet à lui-même) et les arêtes multiples entre deux sommets. - Chaque arête correspond à une paire unique de sommets distincts. - Le nombre maximal de paires possibles parmi \(n\) sommets est le coefficient binomial \(\binom{n}{2}\). - Développement : \(\binom{n}{2} = \frac{n \times (n-1)}{2}\). - Vérification par substitution : pour \(n=4\), \(\frac{4 \times 3}{2} = 6\). Le graphe complet \(K_4\) possède exactement 6 arêtes, ce qui confirme le calcul. Résultat final mis en évidence : \(\frac{n(n-1)}{2}\) arêtes. Hypothèses éventuelles : La formule s'applique pour tout entier \(n \ge 0\). Pour \(n=0\) ou \(n=1\), le résultat donne 0, ce qui est cohérent. Le graphe qui atteint ce maximum est le graphe complet noté \(K_n\).

**Définition du problème** Dans un graphe orienté G=(V,E), une composante fortement connexe (SCC) est un sous-ensemble maximal de sommets tel que pour tout couple (u,v) de ce sous-ensemble, il existe un chemin de u vers v et un chemin de v vers u. L'objectif est de partitionner V en SCC disjointes en O(|V|+|E|). **Algorithme de Tarjan (parcours DFS unique)** Cet algorithme détecte les SCC en temps linéaire grâce à un seul parcours DFS profond, en exploitant les notions de temps de découverte et de valeur low-link. **Structures de données nécessaires** - `disc[u]` : heure de découverte du sommet u lors du DFS (initialisé à -1 ou 0). - `low[u]` : plus petit `disc` atteignable depuis u en suivant uniquement des arêtes de l'arbre DFS et au plus une back-edge. - `pile` : pile LIFO contenant les sommets visités et appartenant encore au SCC courant. - `onStack[u]` : booléen indiquant si u est actuellement dans la pile. - `temps` : compteur global incrémenté à chaque découverte. **Déroulement de l'algorithme** 1. Initialiser tous les `disc` à -1, `low` à -1, `onStack` à false, `pile` vide, `temps` à 0. 2. Pour chaque sommet s de V non visité : appeler `DFS(s)`. Définition de `DFS(u)` : - `disc[u] = low[u] = ++temps` - Empiler u, positionner `onStack[u] = true` - Pour chaque voisin v de u (arête u→v) : - Si `disc[v] == -1` (v non visité) : - `DFS(v)` - `low[u] = min(low[u], low[v])` - Sinon si `onStack[v] == true` (v déjà visité et dans le même SCC potentiel) : - `low[u] = min(low[u], disc[v])` - Si `low[u] == disc[u]` : - u est la racine d'un SCC. - Dépiler successivement les sommets jusqu'à u inclus (en retirant aussi `onStack` de chacun). - Les sommets dépilés forment un SCC complet. **Justification de la complexité linéaire O(|V|+|E|)** - Chaque sommet est visité exactement une fois par le DFS initial : coût O(|V|). - Chaque arête est examinée exactement une fois lors de l'itération sur les voisins : coût O(|E|). - Les opérations de pile (empiler, dépiler) sont en O(1). Chaque sommet est empilé une fois et déposé dans une SCC une fois au maximum : coût O(|V|). - La comparaison `low[u] == disc[u]` et la mise à jour des valeurs sont en O(1). - Total : O(|V|+|E|) en temps et O(|V|) en espace mémoire. **Alternative : algorithme de Kosaraju** Fonctionne en deux passes DFS : 1. Premier DFS sur G pour calculer les temps de fin (post-ordre) de chaque sommet. 2. Construire le graphe transposé G^R (toutes les arêtes inversées). 3. Deuxième DFS sur G^R en traitant les sommets par ordre décroissant de temps de fin du premier DFS. Chaque appel DFS non visité sur G^R révèle exactement une SCC. Complexité identique O(|V|+|E|), mais nécessite la construction explicite de G^R et deux parcours complets. **Points de vigilance techniques** - La condition `low[u] == disc[u]` garantit que u est le premier sommet d'une SCC découvert dans la branche DFS courante ; aucun descendant ne peut atteindre un ancêtre hors de ce bloc sans quitter la pile. - L'utilisation de `disc[v]` et non `low[v]` pour les back-edges est cruciale dans Tarjan pour éviter la propagation prématurée de valeurs low-link entre SCC distincts. - Sur les très grands graphes, une implémentation itérative du DFS (avec pile explicite) est recommandée pour éviter le débordement de la pile d'appel système.

Algorithme : Recherche de cycle de Floyd (Tortue et Lièvre) Pseudocode : fonction detecteCycle(entete): si entete est nul ou entete.suivant est nul: retourner faux lent = entete rapide = entete tant que rapide est non nul et rapide.suivant est non nul: lent = lent.suivant rapide = rapide.suivant.suivant si lent == rapide: retourner vrai retourner faux Complexité espace : O(1) L'algorithme n'utilise que deux variables de référence (lent et rapide). Aucune structure auxiliaire (table de hachage, pile, tableau de marqueurs) n'est allouée. La mémoire supplémentaire reste strictement constante, indépendante de la taille n de la liste. Complexité temps : O(n) Si la liste contient un cycle de longueur c et une partie linéaire de longueur k, le pointeur lent avance de 1 pas par itération et le pointeur rapide de 2 pas. Après au plus k + c itérations, les deux pointeurs se retrouvent dans le cycle. À partir de là, la distance relative diminue de 1 à chaque itération, donc la rencontre intervient au plus c itérations plus tard. Le nombre total d'accès nœud est borné par 2(k + c) ≤ 2n. Justification de la correction : - Absence de cycle : le pointeur rapide atteint un nœud terminal (nul) et la boucle se termine par un retour faux. - Présence de cycle : une fois les deux pointeurs dans le cycle, ils se comportent comme deux coureurs sur une piste circulaire de longueur c. Leur vitesse relative est de 1 pas/itération. Le pointeur rapide rattrape donc inévitablement le lent en au plus c itérations, déclenchant la condition lent == rapide et un retour vrai.

Données : - Algorithme : tri par insertion - Taille du tableau : n éléments (indexés de 0 à n-1) - Pire cas : tableau trié en ordre strictement décroissant Raisonnement chiffré : L'algorithme parcourt le tableau de l'indice 1 à n-1. Pour chaque indice i, l'élément à insérer est comparé successivement aux éléments situés à sa gauche (indices i-1, i-2, ..., 0). Dans le pire cas, il faut le comparer à tous les éléments précédents, soit exactement i comparaisons. Le nombre total de comparaisons C(n) est la somme des comparaisons pour chaque étape : C(n) = 1 + 2 + 3 + ... + (n-1) C(n) = somme(i pour i allant de 1 à n-1) C(n) = (n-1) * n / 2 C(n) = (n^2 - n) / 2 Pour isoler le terme principal, on examine le comportement asymptotique : C(n) ~ n^2 / 2 quand n -> infini Code de vérification : ```python from sympy import symbols, summation, limit n = symbols('n') i = symbols('i', integer=True, positive=True) C = summation(i, (i, 1, n-1)) print("Somme exacte :", C) print("Ratio par n^2/2 :", C / (n**2/2)) print("Limite asymptotique :", limit(C / (n**2/2), n, float('inf'))) ``` Sortie : Somme exacte : n*(n - 1)/2 Ratio par n^2/2 : 1 - 1/n Limite asymptotique : 1.0 Résultat final : Nombre exact de comparaisons dans le pire cas : (n^2 - n) / 2 Terme principal : n^2 / 2 Hypothèses : - L'indice de départ de la boucle externe est 1 (le premier élément est considéré comme trié). - Chaque itération de la boucle interne effectue exactement une comparaison avant de décaler ou de s'arrêter. - La complexité asymptotique est notée O(n^2 / 2), équivalente à O(n^2). - L'analyse suppose un tableau en mémoire contiguë sans optimisations spécifiques (comme l'arrêt anticipé ou les sentinelles).

Cette affirmation est fausse. Dans un arbre binaire de recherche (ABR), la recherche d'une clé se fait en comparant progressivement la valeur cible avec les nœuds parcourus depuis la racine. Le nombre d'opérations de comparaison est au maximum égal à la hauteur de l'arbre. Un ABR équilibré (AVL, rouge-noir, etc.) est précisément conçu pour limiter cette hauteur. Pour n éléments, la hauteur h vérifie h ≤ c × log₂(n), où c est une constante proche de 1 (par exemple c ≈ 1,44 pour les arbres AVL, c = 2 pour les arbres rouge-noir). La complexité temporelle d'une recherche dans le pire des cas est donc O(log n). La complexité O(1) impliquerait un temps de recherche constant, strictement indépendant de n. Or, la théorie de la complexité des algorithmes de recherche par comparaison établit une borne inférieure de Ω(log n) comparaisons dans le pire des cas pour localiser un élément parmi n. Un ABR équilibré atteint cette borne optimale, mais ne peut pas la descendre jusqu'à O(1). En conséquence, un ABR équilibré garantit une recherche en O(log n) dans le pire des cas, et non en O(1). L'affirmation est réfutée.

La structure de données optimale pour ce jeu d'opérations est le **tas binaire minimum** (Min-Heap), généralement exposé au développeur sous l'abstraction de **pile de priorité minimum**. **Complexités temporelles moyennes :** - Lecture du minimum : O(1) - Insertion : O(log n) - Suppression du minimum : O(log n) **Complexité spatiale :** O(n) pour le stockage des éléments. **Principe de fonctionnement :** Le tas est représenté par un tableau continu (liste dynamique) sans pointeurs. Il respecte la propriété d'ordre partiel : la valeur à la racine est inférieure ou égale à celle de chacun de ses enfants. - L'insertion ajoute l'élément à la fin du tableau, puis effectue une remontée (bubble up) en comparant avec le parent jusqu'à restauration de la propriété. - La suppression du minimum remplace la racine par le dernier élément du tableau, réduit la taille, puis effectue une descente (sift down) en échangeant avec l'enfant de valeur minimale jusqu'à restauration de la propriété. - La lecture se fait directement sur la racine. **Comparaison avec d'autres approches :** | Structure | Lecture min | Insertion | Suppression min | Mémoire | |-----------|-------------|-----------|-----------------|---------| | Tableau non trié | O(n) | O(1) | O(n) | O(n) | | Tableau trié | O(1) | O(n) | O(n) | O(n) | | Tas binaire min | O(1) | O(log n) | O(log n) | O(n) | | Arbre équilibré (AVL/Red-Black) | O(log n) | O(log n) | O(log n) | O(n) + pointeurs | Le tas minimum est le choix standard car il offre la complexité asymptotique optimale pour ces trois opérations, une localisation mémoire excellente (tableau contigu, cache-friendly), et un surcoût constant bien inférieur à celui des arbres équilibrés. **Implémentations courantes :** `heapq` (Python), `std::priority_queue` avec `std::greater` (C++), `PriorityQueue` avec comparateur inverse (Java), `std::priority_queue` avec `std::greater` (C++).

**Algorithme** (entrée `a >= b >= 0`) : 1. Tant que `b != 0` : `a, b <- b, a mod b` 2. Retourner `a` **Preuve de correction** 1. Terminaison À chaque itération, on pose `a = bq + r` avec `0 <= r < b`. Le nouveau `b` vaut `r`. La suite des deuxièmes paramètres `(b_0, b_1, ...)` vérifie `0 <= b_{i+1} < b_i`. Il s’agit d’une suite strictement décroissante d’entiers naturels, minorée par 0. Elle atteint donc nécessairement 0 en un nombre fini d’étapes. 2. Invariant de PGCD On démontre que `pgcd(a, b) = pgcd(b, r)` où `r = a mod b`. Soit `D(a, b)` l’ensemble des diviseurs communs à `a` et `b`. - Si `d ∈ D(a, b)`, alors `d | a` et `d | b`. Par linéarité, `d | (a - bq) = r`. Donc `d ∈ D(b, r)`. - Si `d ∈ D(b, r)`, alors `d | b` et `d | r`. Par linéarité, `d | (bq + r) = a`. Donc `d ∈ D(a, b)`. Les ensembles sont identiques : `D(a, b) = D(b, r)`. Le plus grand élément de ces ensembles est le même, d’où `pgcd(a, b) = pgcd(b, r)` à chaque itération. 3. Correctitude au retour L’invariant `pgcd(a, b)` reste constant sur toute l’exécution. À l’arrêt, `b = 0`, donc le programme retourne `pgcd(a, 0)`. Par définition, `pgcd(a, 0) = a`. La valeur retournée est donc le pgcd des entrées initiales. Conclusion : l’algorithme termine en un nombre fini d’étapes et retourne exactement `pgcd(a, b)`.

**Définitions** Complexité amortie : elle évalue le coût moyen par opération sur une séquence quelconque d'opérations, même dans le pire des cas. Le coût ponctuellement élevé d'une opération est réparti sur l'ensemble de la séquence. Aucune hypothèse probabiliste n'est requise. L'analyse borne le coût total pour N opérations, puis divise par N. Complexité moyenne : elle évalue le coût attendu d'une exécution pour une entrée de taille n, en moyennant sur toutes les entrées possibles pondérées par leur probabilité d'apparition. Elle dépend explicitement de la distribution de probabilité des données d'entrée. **Différences fondamentales** Champ d'analyse : amortie porte sur une séquence d'opérations sur une structure de données ; moyenne porte sur une exécution unique tirée aléatoirement. Hypothèses : amortie suppose aucune distribution, elle garantit une borne sur le pire séquence ; moyenne impose une loi de probabilité sur les entrées, et le résultat varie selon cette loi. Interprétation : amortie certifie qu'aucune suite d'opérations ne dépassera une charge globale fixée ; moyenne prédit l'espérance mathématique sur un tirage aléatoire. **Exemple concret** Structure : tableau dynamique avec redimensionnement. Complexité amortie : insérer N éléments. Un redimensionnement à l'étape k coûte O(k). Sur N insertions, le coût total est O(N), soit O(1) amorti par opération. Cette borne tient pour toute séquence d'insertions, même la plus défavorable. L'analyse utilise la méthode par agrégation ou par potentiel. Complexité moyenne : si l'on considère une seule insertion tirée parmi une séquence de taille n, où un redimensionnement est déclenché avec une probabilité p, le coût attendu d'une opération est p × O(k) + (1-p) × O(1). La valeur dépend de p et de la loi de distribution des tailles de tableau. Sans préciser cette loi, la complexité moyenne n'est pas définie. Un second contraste classique : Amorti : file implémentée avec deux piles. Enfiler et défiler coûtent O(1) amorti, car chaque élément est copié au maximum deux fois sur une séquence quelconque. Moyenne : tri rapide. Le pire cas est O(n^2), le meilleur O(n log n), et la complexité moyenne est O(n log n) sous l'hypothèse que les permutations d'entrée sont équiprobables. Sans cette hypothèse, la complexité moyenne n'est pas calculable. **Résumé comparatif** Critère | Complexité amortie | Complexité moyenne Objet | Séquence d'opérations | Entrée unique tirée aléatoirement Hypothèse | Aucune (pire séquence) | Distribution de probabilité sur les entrées Garantie | Pire cas sur le long terme | Espérance mathématique Dépendance | Structure et algorithme uniquement | Algorithme + loi de probabilité des données La complexité amortie certifie qu'aucune séquence d'opérations ne dépassera une certaine charge globale, tandis que la complexité moyenne prédit le comportement attendu sur des données suivant une loi donnée.

L'algorithme standard à utiliser est **Bellman-Ford**. Sa complexité temporelle générale est O(|V| × |E|), où |V| désigne le nombre de sommets et |E| le nombre d'arêtes du graphe.

Stratégie de programmation dynamique pour la distance d’édition de Levenshtein 1. Définition des états Soit A une chaîne de longueur m et B une chaîne de longueur n. On construit une table dp de dimensions (m + 1) x (n + 1). dp[i][j] stocke le nombre minimum d’opérations élémentaires (insertion, suppression, substitution) nécessaires pour transformer les i premiers caractères de A en les j premiers caractères de B. Les indices i et j varient de 0 à m et de 0 à n respectivement. 2. Cas de base - dp[0][j] = j pour tout j dans [0, n] : transformer une chaîne vide en une chaîne de longueur j nécessite exactement j insertions. - dp[i][0] = i pour tout i dans [0, m] : transformer une chaîne de longueur i en une chaîne vide nécessite exactement i suppressions. 3. Relation de récurrence Pour chaque paire (i, j) telle que 1 <= i <= m et 1 <= j <= n : - Si A[i-1] == B[j-1] : dp[i][j] = dp[i-1][j-1] (les caractères correspondent, aucune opération n’est requise pour cette position). - Si A[i-1] != B[j-1] : dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) * dp[i-1][j] correspond à la suppression du i-ème caractère de A. * dp[i][j-1] correspond à l’insertion du j-ème caractère de B dans A. * dp[i-1][j-1] correspond à la substitution du i-ème caractère de A par le j-ème caractère de B. 4. Algorithme structuré Entrées : chaînes A, B m = longueur(A) n = longueur(B) Initialiser une table dp[m+1][n+1] Pour j de 0 à n : dp[0][j] = j Pour i de 0 à m : dp[i][0] = i Pour i de 1 à m : Pour j de 1 à n : Si A[i-1] == B[j-1] : dp[i][j] = dp[i-1][j-1] Sinon : dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) Retourner dp[m][n] 5. Analyse de complexité - Temps : O(m * n) itérations dans la boucle imbriquée, chaque itération effectue un nombre constant d’opérations (comparaison, addition, minimum). - Espace : O(m * n) pour stocker la table complète. Une optimisation standard réduit l’espace à O(min(m, n)) en conservant uniquement les deux lignes successives de la table, car dp[i][j] ne dépend que de la ligne i-1 et de la colonne j-1 courante. 6. Vérification par implémentation Python Le code suivant applique strictement la stratégie décrite. Il est exécuté pour valider le fonctionnement sur des cas standards. ```python def levenshtein(A, B): m, n = len(A), len(B) dp = [[0] * (n + 1) for _ in range(m + 1)] for j in range(n + 1): dp[0][j] = j for i in range(m + 1): dp[i][0] = i for i in range(1, m + 1): for j in range(1, n + 1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n] print(levenshtein("kitten", "sitting")) print(levenshtein("abc", "abc")) print(levenshtein("", "test")) ``` Sortie : 3 0 4 La sortie confirme que la distance de Levenshtein entre "kitten" et "sitting" est 3 (k->s substitution, e->i substitution, ajout de g insertion), entre "abc" et "abc" est 0 (chaînes identiques), et entre "" et "test" est 4 (4 insertions). La stratégie est correcte, déterministe et respecte les propriétés de sous-structure optimale et de sous-problèmes qui se chevauchent propres à la programmation dynamique.

Le problème « vérifier qu’une coloration donnée d’un graphe avec 3 couleurs est valide » appartient à la fois à P et à NP. Justification détaillée : 1) Définition de l'entrée et de la tâche - Entrée : un graphe G = (V, E) avec n sommets et m arêtes, et une affectation de couleurs c : V → {1, 2, 3}. - Tâche : déterminer si, pour toute arête (u, v) ∈ E, on a c(u) ≠ c(v). 2) Algorithme de vérification Parcourir l'ensemble des arêtes E. Pour chaque arête (u, v), comparer c(u) et c(v). Si une égalité est détectée, rejeter immédiatement. Si l'ensemble des arêtes est parcouru sans conflit, accepter. 3) Analyse de complexité - Le nombre d'opérations est proportionnel à m (nombre d'arêtes). Chaque comparaison s'exécute en temps O(1). - Complexité temporelle : O(m), soit linéaire par rapport à la taille de l'entrée. - Un algorithme déterministe résout le problème en temps polynomial. Le problème est donc dans P. 4) Appartenance à NP - La classe NP contient les problèmes dont une solution candidate peut être vérifiée en temps polynomial par une machine de Turing déterministe. La coloration fournie constitue explicitement cette solution candidate, et la vérification décrite ci-dessus s'exécute en O(m). - De plus, par inclusion formelle, P ⊆ NP. Tout problème de P appartient automatiquement à NP. - Le problème est donc dans NP. 5) Distinction cruciale avec le problème de décision - Le problème de *vérification* d'une coloration donnée (celui de l'énoncé) est polynomial. - Le problème de *décision* « Un graphe G admet-il au moins une coloration valide en 3 couleurs ? » est NP-complet. La confusion entre vérification et recherche d'une solution est fréquente mais invalide ici. Conclusion : Le problème de validation d'une coloration 3- coloriante donnée est dans P, et par inclusion dans NP. Il appartient donc aux deux classes.