Formulaire · Algorithmes

Ce formulaire rassemble, par thème et non par chapitre, ce qu'il faut avoir sous les yeux la veille d'un examen: la notation du cours, les définitions asymptotiques, le théorème maître et les récurrences résolues, les trois grandes tables de coûts — tris, structures de données, algorithmes de graphes —, les quatre patrons de conception avec l'obligation de démonstration attachée à chacun, et le vocabulaire de la $N P$ -complétude. Chaque entrée renvoie au chapitre qui la démontre: ce qui est ici est un aide-mémoire, pas une preuve, et une formule qu'on ne saurait pas justifier n'est pas une formule qu'on sait.

Deux avertissements de lecture. Premièrement, aucun coût n'est donné sans son régime: «dans le pire des cas», «en moyenne sous telle loi» ou «amorti». C'est la règle du chapitre 1 et c'est l'imprécision la plus fréquente du domaine; les tables ci-dessous portent donc une colonne pour cela. Deuxièmement, les rappels mathématiques — sommes usuelles, nombres harmoniques, logarithmes, récurrence, indicatrices et espérance — ne sont pas repris ici: ils sont à l'annexe A, dont les énoncés sont numérotés A.1 à A.9.

Notation

Objet	Notation
Taille de l'entrée	$n$
Graphe	$G = (V, E)$ , $n = ∣ V ∣$ , $m = ∣ E ∣$
Classes asymptotiques	$O$ , $Ω$ , $Θ$ ,

Les indices sont à base 0 et les tranches semi-ouvertes, y compris pour les intervalles de temps du chapitre 9: une tâche qui finit en 13 et une tâche qui commence en 13 sont compatibles. Lorsqu'un résultat classique est énoncé à base 1 dans la littérature (Knuth, CLRS), ce cours le réénonce à base 0 — c'est pourquoi les enfants d'un nœud de tas sont ici $2 i + 1$ et $2 i + 2$ , et non $2 i$ et $2 i + 1$ .

Un même symbole, plusieurs sens: la liste complète

Ce cours suit la notation de chaque littérature plutôt que de l'uniformiser, et il faut donc savoir où les collisions se trouvent. Le contexte lève chaque fois l'ambiguïté, mais seulement si l'on sait qu'elle existe.

Alpha. C'est le facteur de charge $α = n / m$ d'une table de hachage au chapitre 4 — un rapport, souvent compris entre 0 et 1 — et l'inverse de la fonction d'Ackermann $α (n)$ dans l'analyse d'union-find au chapitre 8 — une fonction de $n$ , qui vaut au plus 4 pour toute entrée concevable. La règle de reconnaissance est simple: un $α$ suivi d'un argument est celui d'Ackermann, un $α$ nu est le facteur de charge. Le même symbole désigne encore un sous-arbre dans l'invariant de rotation du chapitre 5 et une affectation booléenne dans la réduction du chapitre 11.

Croissance asymptotique

O (g) Ω (g) Θ (g) = {f : \exists c > 0, \exists n_{0}, \forall n \geq n_{0}, f (n) \leq c g (n)}, = {f : \exists c > 0, \exists n_{0}, \forall n \geq n_{0}, f (n) \geq c g (n)}, = O (g) \cap Ω (g), o (g) = {f : \forall c > 0, \exists n_{0}, \forall n \geq n_{0}, f (n) \leq c g (n)} .

Définitions du chapitre 1. Démontrer une appartenance à $O$ , c'est exhiber un couple $(c, n_{0})$ ; une démonstration qui ne nomme pas son $c$ et son $n_{0}$ n'en est pas une. Le renversement du quantificateur dans $o$ est l'essentiel: la majoration doit y valoir pour toute constante. Quand les limites existent, $f \in o (g)$ équivaut à .

$O (g)$ est un ensemble: l'écriture correcte est $T (n) \in O (n^{2})$ . L'abus $T (n) = O (n^{2})$ est admis dans le fil du texte et ne se lit que de gauche à droite: de $f = O (n^{2})$ et on ne conclut pas .

Règle	Énoncé
Réflexivité	$f \in Θ (f)$
Constante	$λ f \in Θ (f)$ pour $λ > 0$
Transitivité	$f \in O (g)$ et $g \in O (h)$ donnent

Théorème 1.1 pour la transitivité, théorème 1.2 pour le polynôme. La base d'un logarithme s'oublie — $lo g_{a} n \in Θ (lo g_{b} n)$ par changement de base — mais jamais un exposant: $lo g^{2} n \in / Θ (lo g n)$ et .

Θ (1) \subset Θ (lo g n) \subset Θ (n) \subset Θ (n lo g n) \subset Θ (n^{2}) \subset Θ (n^{3}) \subset Θ (2^{n}) \subset Θ (n!)

Chaque classe est un $o$ de la suivante. Un polynôme de degré $d$ à coefficient dominant positif est dans $Θ (n^{d})$ (théorème 1.2), et $lo g_{2} (n!) \in Θ (n lo g_{2} n)$ avec les constantes explicites et pour (théorème 1.3) — c'est cette minoration qui donne la borne des tris.

$n$	$n lo g_{2} n$	$n^{2}$	rapport
100	664	10 000	15
1 000	9 966	$1 0^{6}$	100
10 000	132 877	$1 0^{8}$

Classe	Taille atteinte pour $1 0^{9}$ opérations
$lo g_{2} n$	pratiquement illimitée
$n$	$1 0^{9}$
$n lo g_{2} n$

Recherche dichotomique: $⌊ lo g_{2} n ⌋ + 1$ examens au pire, soit 10 pour mille éléments, 20 pour un million, 30 pour un milliard. Doubler la vitesse de la machine fait gagner un élément sur une entrée traitée en $2^{n}$ .

Récurrences et théorème maître

T (n) = a T (n / b) + f (n), a \geq 1, b > 1, L = lo g_{b} a .

Le nombre de feuilles de l'arbre de récursion vaut $a^{l o g_{b} n} = n^{L}$ , et $L$ est l'exposant critique. Les trois cas du théorème 2.1 comparent l'exposant de $f$ à $L$ .

Cas	Hypothèse sur $f$	Conclusion	Qui domine
1	$f \in O (n^{L - ε})$ , $ε > 0$	$T \in Θ (n^{L})$

La condition de régularité du cas 3 est: il existe $κ < 1$ avec $a f (n / b) \leq κ f (n)$ pour $n$ assez grand. Elle est automatique pour $f (n) = n^{c}$ avec $c > L$ . Les cas 1 et 3 exigent un écart , un facteur — et c'est ce qui laisse une de part et d'autre du cas 2:

T (n) = 2 T (n /2) + \frac{n}{lo g _{2} n} \in Θ (n lo g lo g n) T (n) = 2 T (n /2) + n lo g_{2} n \in Θ (n lo g^{2} n)

Aucun des trois cas ne couvre ces deux récurrences: le facteur $lo g n$ n'est $n^{ε}$ pour aucun $ε > 0$ . Quand le raccourci ne s'applique pas, on redessine l'arbre — c'est la méthode qui a démontré le théorème, et elle ne tombe jamais en panne.

Récurrence	$a$	$b$	$L$	Cas	Solution	Où
$T (n /2) + Θ (1)$	1	2	0	2	$Θ (lo g n)$	dichotomie, ch. 2
$2 T (n /2) + Θ (1)$

Trois récurrences hors du théorème, à connaître par leur solution:

T (n) = T (n - 1) + Θ (n) \in Θ (n^{2}) (pire cas du tri rapide) T (n) = T (n /3) + T (2 n /3) + Θ (n) \in Θ (n lo g n) (d \overset{e}{ˊ} coupage d \overset{e}{ˊ} s \overset{e}{ˊ} quilibr \overset{e}{ˊ}) T (n) \leq T (n /5) + T (7 n /10) + Θ (n) \in Θ (n) (m \overset{e}{ˊ} diane des m \overset{e}{ˊ} dianes)

La deuxième dit que le déséquilibre ne tue pas, tant qu'il reste d'un facteur constant; la troisième que $1/5 + 7/10 = 9/10 < 1$ suffit à rendre la somme géométrique convergente. Ce qui tue un algorithme récursif, c'est un découpage qui détache une part de taille constante, comme la première.

Tris

Convention de comptage du cours, sans laquelle aucun des nombres ci-dessous n'a de sens: une comparaison par test entre deux éléments du tableau y compris celui qui fait sortir de la boucle intérieure du tri par insertion, et rien quand l'indice tombe hors du tableau par la gauche; une comparaison par comparaison de deux éléments à l'intérieur de la boucle de fusion, les queues recopiées ne coûtant rien; une comparaison par tour de la boucle de partition de Lomuto. Le même tri par insertion donne 14, 15 ou 21 sous trois conventions défendables.

Tri	Pire des cas	En moyenne	Mémoire	Stable	En place
Insertion	$n (n - 1) /2$	$Θ (n^{2})$	$Θ (1)$	oui	oui
Sélection	$n (n - 1) /2$	$Θ (n^{2})$

La moyenne est prise sur la loi uniforme des $n!$ permutations, sauf pour le tri rapide randomisé, où elle est prise sur les tirages de l'algorithme et vaut alors pour toute entrée. La mémoire du tri rapide est celle de la pile de récursion; son travail proprement dit est en place. Chapitre 3 pour tout ce tableau, chapitre 5 pour le tri par tas.

insertion: \overset{ˉ}{C} (n) = \frac{n ( n - 1 )}{4} + n - H_{n} (3.1) fusion, pire des cas: M (n) = n ⌈ lo g_{2} n ⌉ - 2^{⌈ l o g_{2} n ⌉} + 1 rapide: \overset{ˉ}{C} (n) = 2 (n + 1) H_{n} - 4 n \sim 2 n ln n \approx 1, 39 n lo g_{2} n

$n$	$⌈ lo g_{2} (n!)⌉$	Fusion, pire	$n lo g_{2} n$
5	7	8	11,6
7	13	14	19,7
10	22	25	33,2
16	45	49	64,0
100	525	573	664
1000	8 530	8 977	9 966

La borne porte sur un problème, dans un modèle, au pire des cas: les trois qualificatifs sont nécessaires. Elle n'interdit à aucune entrée particulière d'être triée en moins; elle ne concerne pas les algorithmes qui regardent les valeurs au lieu de seulement les comparer. C'est par là que passent les tris linéaires — et ils paient cette sortie: connaître la nature des clés, dépendre d'un second paramètre $k$ ou $d$ , consommer de la mémoire. Sur $n$ entiers distincts, $d \geq lo g_{b} n$ et le tri par base redevient $Ω (n lo g n)$ : la borne a le dernier mot dès qu'on compte honnêtement.

Sélection du $k$ -ième (chapitre 3). quickselect ne récurse que d'un côté: $O (n)$ comparaisons en moyenne (borne explicite $8 n$ par $\overset{ˉ}{T} (n) \leq 2 n + \overset{ˉ}{T} (3 n /4)$ ), $Θ (n^{2})$ au . La garantit au pire par un pivot qui écarte au moins éléments de chaque côté. En pratique on combine les deux (), comme l' protège le tri rapide par le tri par tas.

Question B.1

Quel est l'énoncé exact de la borne inférieure des tris par comparaison?

Structures de données

La colonne «régime» est le cœur de cette table. Un coût amorti est un pire des cas portant sur une suite d'opérations, sans aucune hypothèse probabiliste: il vaut même contre un adversaire, et il ne promet rien sur une opération isolée. Un coût moyen est une espérance sous une loi énoncée: il ne borne rien et ne vous concerne que si vos données suivent cette loi. Un coût de pire des cas borne chaque opération prise séparément. Les trois ne s'échangent jamais.

Structure	Opération	Coût	Régime
Tableau dynamique	lire l'indice $i$	$Θ (1)$	pire
	ajouter en fin	$Θ (1)$	amorti
	insérer au milieu	$Θ (n)$	pire
Liste simple	lire l'indice $i$	$Θ (i)$	pire
	insérer après un nœud connu	$Θ (1)$	pire
	supprimer un nœud connu	$Θ (n)$

«HUS» est l'hypothèse de hachage uniforme simple: chaque clé a la probabilité $1/ m$ d'aller dans chaque paquet, indépendamment des autres. C'est une hypothèse sur la loi conjointe des clés et de la fonction, pas une propriété d'un algorithme: pour une fonction fixée, un adversaire ramène toujours le pire des cas à $Θ (n)$ . La parade est le hachage universel, qui tire $h$ au hasard au démarrage — c'est ce que fait Python pour les chaînes depuis la version 3.3.

Amortissement: les trois méthodes (chapitre 4). L'agrégat divise le coût total par le nombre d'opérations. Le comptable affiche un prix par opération et vérifie que la caisse ne devient jamais négative. Le potentiel est le seul qui se transporte:

\overset{c}{^}_{i} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1}), i = 1 \sum m c_{i} = i = 1 \sum m \overset{c}{^}_{i} - Φ (D_{m}) + Φ (D_{0}) \leq i = 1 \sum m \overset{c}{^}_{i}

à condition que $Φ (D_{i}) \geq Φ (D_{0})$ pour tout $i$ . Potentiels à connaître: $Φ = 2 s - c$ pour le tableau qui double (théorème 4.1, coût amorti 3 écritures, borne serrée), $Φ = 2 ∣ entree ∣$ pour la file par deux piles (théorème 4.2, au plus opérations de pile), pour le redimensionnement d'une table de hachage.

α = \frac{n}{m}, E [n_{j}] = α, recherche infructueuse par cha \overset{ı}{ˆ} nage = Θ (1 + α)

Théorèmes 4.3 et 4.4. L'espérance n'est pas le maximum: à $α = 1$ et $m = 1021$ , la plus longue chaîne mesure environ 5,5 maillons pour une espérance de 1, et croît comme $lo g n / lo g lo g n$ .

Résolution	Infructueuse	Fructueuse
Chaînage	$1 + α$	$1 + α /2 - α / (2 n)$
Hachage uniforme	$\frac{1}{1 - α}$

Le carré au dénominateur est le prix des amas primaires: à $α = 0, 9$ , la recherche infructueuse demande $50, 5$ sondes en sondage linéaire contre $10$ en hachage uniforme. Le double hachage $h (k, i) = (h_{1} (k) + i h_{2} (k)) mod m$ , avec premier avec , supprime l'amas primaire; il subsiste un amas secondaire, négligeable.

Arbres (chapitre 5), hauteur comptée en arêtes, l'arbre vide valant $- 1$ :

⌈ lo g_{2} (n + 1)⌉ - 1 \leq h \leq n - 1 N (h) = 1 + N (h - 1) + N (h - 2) = F_{h + 3} - 1 h_{AVL} < 1, 4405 lo g_{2} (n + 1)

$N (h)$ est le nombre minimal de nœuds d'un AVL de hauteur $h$ : $1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, \dots$ Un AVL de mille nœuds a une hauteur d'au plus 13, contre 9 pour l'arbre parfait et 999 pour le peigne. Un tas est complet, donc de hauteur exactement $⌊ lo g_{2} n ⌋$ sans le moindre effort d'équilibrage; ses indices sont , et , et les feuilles sont les indices à .

Union-find (chapitre 8): l'union par rang garantit qu'une racine de rang $r$ porte au moins $2^{r}$ éléments, donc $r \leq ⌊ lo g_{2} n ⌋$ et un trouver en $O (lo g n)$ — borne atteinte. La compression de chemin ne met jamais les rangs à jour: le rang cesse d'être la hauteur pour n'en rester qu'un majorant, ce qui suffit. Ensemble, coût amorti $O (α (n))$ , (Tarjan 1975), et optimal. pour toute entrée concevable — mais tend vers l'infini, donc «quasi constant» ne s'écrit pas .

Question B.2

Une table de hachage en adressage ouvert contient 3000 clés dans 4000 cases. Combien de sondes une recherche infructueuse demande-t-elle en moyenne en sondage linéaire?

Graphes

$G = (V, E)$ , $n$ sommets, $m$ arêtes. Lemme des poignées de main: $\sum_{u} de g (u) = 2 m$ , d'où $2 m$ maillons dans une liste d'adjacence et le nombre de sommets de degré impair toujours pair. Pour un graphe non orienté simple, $0 \leq m \leq n (n - 1) /2$ . Un arbre à sommets a arêtes; un graphe à composantes a au moins arêtes, avec égalité si et seulement si c'est une forêt.

Opération	Liste d'adjacence	Matrice
Espace	$Θ (n + m)$	$Θ (n^{2})$
Tester une arête	$Θ (de g u)$	$Θ (1)$
Énumérer les voisins	$Θ (de g u)$	$Θ (n)$

Presque tous les algorithmes énumèrent des voisinages au lieu de tester des arêtes: la liste gagne, sauf sur un graphe dense ou quand le test d'existence domine.

Algorithme	Coût	Hypothèse	Ce qui la casse
Parcours en largeur	$Θ (n + m)$	arêtes de poids 1	un poids quelconque
Parcours en profondeur	$Θ (n + m)$	aucune	—
Tri topologique	$Θ (n + m)$	orienté sans circuit	un circuit
Dijkstra, tas	$O ((n + m) lo g n)$

Comme $m < n^{2}$ , on a $O (m lo g m) = O (m lo g n)$ : Kruskal et Prim au tas sont dans la même classe, et le choix se fait ailleurs. Sur un graphe creux les deux se valent; sur un graphe dense, c'est Prim au tableau qui gagne, parce que payer un logarithme par arête coûte $n^{2} lo g n$ quand on doit de toute façon lire toutes les arêtes. Si les poids sont de petits entiers, un tri par dénombrement rend Kruskal quasi linéaire, en . Le coût de Kruskal est , et c'est tout ce qu'il y a à retenir.

Relaxation (chapitre 7), l'unique opération dont Dijkstra, Bellman–Ford et le passage par un ordre topologique sont faits:

si d [u] + w (u, v) < d [v] alors d [v] \leftarrow d [u] + w (u, v), parent [v] \leftarrow u .

L'inégalité est stricte: à égalité l'arbre des prédécesseurs ne change pas, ce qui rend les traces reproductibles et — plus important — ce qui permet à Bellman–Ford de détecter un circuit négatif. Invariants: $δ (s, v) \leq δ (s, u) + w (u, v)$ ; $d [v] \geq δ (s, v)$ toujours; $d [v]$ ne remonte jamais; toute valeur atteinte reste (théorème 7.1). : tout sous-chemin d'un plus court chemin est un plus court chemin (théorème 7.2) — faux pour le plus long chemin, et c'est ce qui le rend difficile.

Où la démonstration de Dijkstra utilise la positivité

Un seul pas, et il faut savoir lequel. La correction de Dijkstra (théorème 7.4) suppose que le premier sommet $y$ hors de l'ensemble figé, sur un plus court chemin vers $u$ , vérifie $δ (s, y) \leq δ (s, u)$ — c'est-à-dire qu'un sommet plus tôt sur un plus court chemin est plus près de la source. Cela tient parce que le morceau restant pèse au moins 0. Tout le reste de la démonstration vaut pour des poids quelconques.

Sur le contre-exemple minimal — quatre sommets, $P \to Q (2)$ , , , —, on a : la monotonie tombe, Dijkstra fige à 2, rend au lieu de , et . Ajouter une constante à tous les poids ne répare rien: un chemin de arêtes prend , donc les chemins longs sont pénalisés davantage et l'ordre change. La transformation qui marche est un , non constant: — c'est A* et c'est Johnson.

Bellman–Ford: $n - 1$ passes suffisent parce qu'un plus court chemin élémentaire a au plus $n - 1$ arêtes; une $n$ -ième passe qui réussit encore prouve un circuit négatif, car aucune affectation de valeurs finies ne peut satisfaire toutes les inégalités triangulaires autour d'un tel circuit.

Floyd–Warshall: $d_{ij}^{(k)} = min (d_{ij}^{(k - 1)}, d_{i, k - 1}^{(k - 1)} + d_{k - 1, j}^{(k - 1)})$ , où est le nombre de sommets — ni un temps ni un nombre d'arêtes. C'est pourquoi la boucle sur doit être la plus : à l'intérieur, elle mélange des autorisations différentes et produit des valeurs fausses sur une case et justes sur les autres. Un après exécution signale un circuit négatif, et le reste de la matrice ne veut alors plus rien dire.

Propriété de coupe (théorème 8.2): si $A$ est contenu dans un arbre couvrant minimal, si la coupe $(S, V ∖ S)$ respecte $A$ — aucune arête de $A$ ne la traverse — et si $e$ est de poids minimal parmi les traversantes, alors $A \cup {e}$ est encore contenu dans un arbre couvrant minimal. Sa jumelle, la propriété de cycle (théorème 8.3): une arête strictement la plus lourde d'un cycle n'appartient à aucun arbre couvrant minimal. Enfin: des poids deux à deux distincts entraînent l'unicité de l'arbre couvrant minimal, la réciproque est fausse, et le poids de l'arbre est de toute façon unique.

Patrons de conception

Quatre schémas, chacun avec l'obligation de démonstration qui lui est attachée. C'est l'obligation qui distingue un algorithme d'une conviction.

Définition B.2 · algorithme glouton et argument d'échange

Recette. Trier selon un critère fixé d'avance, puis parcourir en prenant tout ce qui reste admissible. Le critère est local — il ne simule pas l'avenir — et la décision irrévocable.

Obligation. Démontrer la propriété du choix glouton: il existe au moins une solution optimale contenant le premier choix du critère. Puis la sous-structure optimale: ce qui reste est une instance du même problème. La démonstration standard est l'argument d'échange, en quatre temps — (1) prendre une solution optimale quelconque $S$ ; (2) repérer le premier choix où $S$ diffère du glouton $G$ ; (3) y substituer le choix de $G$ , en démontrant les deux moitiés: $S^{'}$ reste et sa valeur n'est ; (4) conclure par récurrence, s'obtenant en un nombre fini d'échanges.

Définition B.3 · programmation dynamique

Recette. (1) Nommer le sous-problème en une phrase complète, en français, avec ses quantificateurs. (2) Écrire la récurrence en énumérant les choix de la dernière décision. (3) Écrire les cas de base. (4) Fixer un ordre de calcul où toute case est remplie après celles dont elle dépend.

Obligation. Démontrer la sous-structure optimale par découpe-recollage: si une partie d'une solution optimale n'était pas optimale pour sa sous-instance, la remplacer donnerait une solution admissible de valeur strictement meilleure. La partie qui demande de l'attention n'est jamais l'échange: c'est la vérification que le recollage reste admissible. Il faut aussi le chevauchement des sous-problèmes, sans quoi mémoriser ne rapporte rien.

Signe qu'il ne s'applique pas. Le sous-problème hérite d'une contrainte du reste de la solution — des objets déjà pris, des sommets déjà visités, une ressource consommée ailleurs. C'est le cas du plus long chemin simple, où les deux moitiés se disputent les sommets.

Méthode	Ce qu'elle essaie	Ce qu'elle coûte	Démontré par
Diviser pour régner	un découpage	un tri ou un balayage	ch. 2
Glouton	un seul premier choix	un tri	ch. 9
Programmation dynamique	tous les premiers choix	une table	ch. 10
Séparation et évaluation	tous, moins ceux qu'on élague	exponentiel	ch. 11

La différence entre le glouton et la programmation dynamique tient en une phrase: les deux exigent la sous-structure optimale; le glouton n'essaie qu'un premier choix, la table les essaie tous. Le glouton n'est donc légitime que lorsqu'on a démontré que ce choix-là n'a pas besoin d'être comparé aux autres.

Question B.3

Remettez dans l'ordre les étapes d'un argument d'échange démontrant qu'un algorithme glouton est optimal.

Glissez les éléments pour les mettre dans le bon ordre

Remplacer ce choix par celui du glouton, obtenant une solution

S^{'}

Conclure que la solution gloutonne s'obtient en un nombre fini d'échanges

Repérer le premier choix sur lequel

S

diffère de la solution gloutonne

Prendre une solution optimale quelconque

S

, sans rien supposer d'autre

Vérifier que

S^{'}

est encore admissible, puis que sa valeur n'est pas dégradée

P, NP et approximation

Terme	Définition
Taille d'une instance	la longueur de son codage en bits
Pseudo-polynomial	polynomial en la valeur des nombres, exponentiel en leur écriture
$P$	décidable en temps polynomial
$N P$	vérifiable en temps polynomial, par un certificat de taille polynomiale
$A \leq_{p} B$	$f$ polynomiale avec $x$ positive si et seulement si $f (x)$ positive

$P \subseteq N P \subseteq E X P T I M E$ , et $P ⊊ E X P T I M E$ : au moins l'une des deux premières inclusions est stricte, on ne sait pas laquelle. Un seul problème $N P$ -complet dans $P$ donnerait . La -complétude de SAT et de 3-SAT est le , admis; tout le reste s'obtient par réductions, à la manière de Karp (1972).

Le certificat de $N P$ ne couvre que le oui: rien, dans «ce graphe n'a aucun cycle hamiltonien», ne se certifie brièvement de façon évidente, et savoir si $N P = co - N P$ est une seconde question ouverte.

Problème	Question de décision	Certificat
SAT, 3-SAT	la formule est-elle satisfaisable?	une affectation
Couverture par sommets	une couverture de taille $\leq k$ ?	l'ensemble
Clique	$k$ sommets deux à deux adjacents?	les $k$ sommets
Ensemble indépendant	$k$ sommets deux à deux non adjacents?	les $k$ sommets
Cycle hamiltonien	un cycle passant une fois par sommet?	l'ordre des sommets
Voyageur de commerce	une tournée de longueur $\leq B$ ?	l'ordre des villes
Partition	deux parts de même somme?	l'une des parts
Sac à dos	poids $\leq W$ et valeur ?

Les trois derniers du catalogue sont liés par des transformations triviales: $S$ est une couverture si et seulement si $V ∖ S$ est un ensemble indépendant, et $C$ est une clique de $G$ si et seulement si $C$ est un ensemble indépendant de $\overline{G}$ . Une réduction transporte la difficulté exacte; elle ne transporte pas l'approximabilité.

Problème	Meilleure garantie connue
Couverture par sommets	2, par couplage maximal
Voyageur métrique	$3/2$ (Christofides); 2 par l'arbre couvrant
Sac à dos 0/1	$(1 - ε)$ pour tout $ε > 0$
Ensemble indépendant	aucune constante, sauf si $P = N P$
Voyageur général	aucune constante, sauf si $P = N P$

Le mécanisme de toute démonstration d'approximation est là: l'algorithme ne connaît pas $OPT$ , mais il connaît une minoration calculable de $OPT$ — ici $∣ M ∣$ , là le poids d'un arbre couvrant minimal — et il borne son résultat par un multiple de cette minoration. Pour le voyageur métrique: $w (T) \leq OPT$ parce qu'une tournée privée d'une arête est un arbre couvrant; la marche qui double l'arbre coûte $2 w (T)$ ; les raccourcis ne coûtent rien par l'inégalité triangulaire. Sans cette hypothèse, aucune garantie constante n'existe: le même problème passe de «2-approché» à «inapprochable», et l'hypothèse porte tout le résultat.

$Θ (nW)$ pour le sac à dos est pseudo-polynomial: $W$ s'écrit en $⌊ lo g_{2} W ⌋ + 1$ bits, donc le coût est exponentiel en la taille de l'entrée. Cent objets et des poids de quarante bits donnent $1, 1 \times 1 0^{14}$ cases pour une instance de 4000 bits. Le même piège attend le test de primalité par divisions jusqu'à .

Ce qu'un énoncé de NP-complétude ne dit pas

Il porte sur le pire des cas d'une famille infinie d'instances. Il ne dit rien de l'instance que vous avez sur votre bureau, qui peut être petite, structurée, presque planaire ou tout simplement facile: des solveurs SAT industriels traitent couramment des formules à des millions de variables. Quatre chemins restent ouverts — exact avec élagage, complexité paramétrée, heuristique sans garantie, approximation avec garantie — et ils resteraient intacts même si $P \neq = N P$ était démontré.

Enfin, «on ne connaît pas d'algorithme polynomial» et «il n'existe pas d'algorithme polynomial» ne sont pas la même phrase. La première décrit l'état de nos connaissances; la seconde serait un théorème, et personne ne l'a démontré pour aucun problème de $N P$ .

Les données témoins du cours

Tous les chapitres travaillent sur les mêmes données. Voici leurs valeurs fixées, rassemblées pour servir de contrôle: si un calcul refait à la main ne les retrouve pas, c'est le calcul qui se trompe.

Tableau témoin a = [38, 27, 43, 3, 9, 82, 10], trié [3, 9, 10, 27, 38, 43, 82].

Quantité	Valeur
Tri par insertion	15 comparaisons, 11 décalages
Tri par insertion, trié / inversé	6 / 21 comparaisons
Tri fusion	13 comparaisons, en six fusions
Tri rapide, Lomuto	11 comparaisons, en quatre partitions
Tri rapide sur le tableau trié	21 comparaisons
Tri par tas	19 comparaisons (8 pour Floyd, 11 d'extraction)
`quickselect` de la médiane	10 comparaisons, valeur 27
ABR témoin	racine 38, hauteur 4 arêtes
Peigne (clés triées)	hauteur 6
Min-tas de Floyd	`[3, 9, 10, 27, 38, 82, 43]`
Max-tas de Floyd	`[82, 27, 43, 3, 9, 38, 10]`

Graphe témoin, non orienté, 7 sommets et 11 arêtes de poids $A B 4$ , $A C 2$ , $B C 1$ , $B D 5$ , $C D 8$ , $C E 10$ , $D E 2$ , $D F 6$ , , , , de somme 52.

Quantité	Valeur
Degrés	2, 3, 4, 4, 4, 3, 2, de somme $2 m = 22$
Dijkstra depuis $A$	$0, 3, 2, 8, 10, 13, 17$
Ordre d'extraction	$A, C, B, D, E, F, G$

Table de hachage témoin: $m = 11$ , $h (k) = k mod 11$ , clés 22, 31, 4, 15, 28, 17, 88, 59 dans cet ordre. Images $0, 9, 4, 4, 6, 6, 0, 4$ . Par chaînage: ${22, 88}$ , , , . Par sondage linéaire: pour , et .

Huffman: $e : 45$ , $s : 16$ , $a : 13$ , $i : 12$ , $n : 9$ , $r : 5$ . Codes $e = 0$ , $i = 100$ , $a = 101$ , , , ; contre 300, soit par caractère. Le coût total est aussi la somme des poids des nœuds internes, .

Sac à dos: $W = 9$ , $A (2, 3)$ , $B (3, 4)$ , $C (4, 5)$ , $D (5, 8)$ . Dernière ligne de la table [0, 0, 3, 4, 5, 8, 8, 11, 12, 13].

Question	Réponse
Glouton par rapport $v / p$ , version 0/1	11, par ${D, A}$ , deux unités perdues
Optimum 0/1	13, par ${C, D}$ , poids exactement 9, unique
Optimum fractionnaire	41/3, soit $D$ , $A$ , puis deux tiers de $B$

L'ordre $11 < 13 < 41/3$ n'est pas un accident: l'optimum fractionnaire majore toujours l'optimum 0/1, puisque toute solution 0/1 est une solution fractionnaire particulière. Sur cette seule instance, les critères «valeur décroissante» et «poids décroissant» trouvent 13 — la bonne réponse pour la mauvaise raison. La seconde instance, $W = 10$ avec $X (6, 10)$ , $Y (5, 7)$ , $Z (5, 7)$ , d'optimum par , les réfute: chacun des quatre critères usuels trouve l'optimum sur l'une des deux instances et le manque sur l'autre.

Sous-séquence commune: ALGORITHME et LOGARITHME ont une plus longue sous-séquence commune de longueur 8 — LGRITHME, ou LORITHME selon la règle de départage, la longueur étant unique et la sous-séquence non — et une distance d'édition de 3, atteinte par trois substitutions.

Références

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — la référence de tout ce formulaire; l'annexe A de l'ouvrage pour les sommes, le chapitre 4 pour le théorème maître, le chapitre 16 pour l'analyse amortie.
Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française, utile pour fixer le vocabulaire: «coût amorti», «arête sûre», «sous-structure optimale», «vérificateur».
Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — les tables de coûts comparées et les variantes d'implémentation, avec des mesures plutôt que des classes.
Kleinberg & Tardos, Algorithm Design, Pearson — la meilleure exposition des quatre patrons de conception, et la distinction décision / optimisation traitée explicitement.
Garey & Johnson, Computers and Intractability, Freeman — le catalogue des problèmes $N P$ -complets, à consulter quand un problème nouveau ressemble à un problème connu.