Complexité des problèmes et des algorithmes
Cours de Master – Informatique Théorique et Optimisation
Version complète – Septembre 2025
Table des matières
1
Chapitre 1
Fondements de la complexité
1.1 Notion générale
Définition 1.1. La complexité d’un algorithme mesure le coût (temps, espace) en fonc-
tion de la taille n de l’entrée.
Remarque 1.1 (Brun). Deux algorithmes réalisant la même tâche peuvent avoir des coûts
très différents ; l’analyse de complexité permet de comparer et choisir.
1.2 Mesure du temps d’exécution
Règles (Brun)
1. Instruction simple : coût constant.
2. Séquence : somme des coûts.
3. Conditionnel : test + max des branches.
4. Boucle : coût de k itérations = coût par itération ×k + tests.
Cas étudiés (Albert)
Pire cas, meilleur cas, cas moyen (espérance sur les entrées).
1.3 Exemples élémentaires
Exemple 1.1 (Boucle simple). s ← 0
pour i ← 1 à n faire s ← s + i
Θ(n) opérations.
Exemple 1.2 (Boucles imbriquées (Brun)). pour i ← 1..n pour j ← 1..n faire x ← x+1
Θ(n2 ) affectations.
Exemple 1.3 (Boucle logarithmique). h ← 1 ; tant que h n faire h ← 2h
Θ(log n) itérations.
2
1.4 Exercices guidés et corrigés (Rossi, Albert)
Exercice 1.1 (Rossi, Ex. 1.1). Analyser : while(i<n){ if(i%2==0) j=j+1; else j=j/2; i=i+1; }
Correction 1.1. Boucle n fois, coût constant par itération : Θ(n).
Exercice 1.2 (Rossi, Ex. 1.2). Double boucle avec 3 itérations internes : complexité ?
Correction 1.2. Θ(n) (interne Θ(1), externe Θ(n)).
Exercice 1.3 (Rossi, Ex. 1.3 — Convolution). Complexité de la convolution longueur p sur
signal n.
Correction 1.3. Θ((n − p + 1) p) = Θ((n − p)p).
Exercice 1.4 (Albert). Résoudre T (n) = 2T (n/2) + Θ(n).
Correction 1.4. Théorème maître : T (n) = Θ(n log n).
1.5 Résumé
Mesures (temps, espace), cas d’analyse, patrons de boucles et récurrences usuelles.
3
Chapitre 2
Fonctions de complexité
2.1 Notations asymptotiques
Définition 2.1. f = O(g) ssi ∃c, n0 , ∀n ≥ n0 , f (n) ≤ cg(n) ; f = Ω(g) ssi g = O(f ) ;
f = Θ(g) ssi f = O(g) et f = Ω(g).
2.2 Échelles usuelles et exercices
O(1) ≺ O(log n) ≺ O(n) ≺ O(n log n) ≺ O(n2 ) ≺ O(2n ) ≺ O(n!).
Exos : classement de fonctions ; Quicksort (moyen n log n, pire n2 ) ; seuil de croisement
1000n vs 5n2 (n > 200).
4
Chapitre 3
Problèmes de décision, classes P et NP
3.1 Machines de Turing et classes
Time(nk ), NP = NTIME(nk ) (ou vérificateur polynomial
S S
Définition 3.1. P = k≥1 k≥1
avec certificat).
3.2 Exemples et exercices
Tri ∈ P ; Clique ∈ N P . Exos : Hamiltonien ∈ N P (certificat chemin) ; Partition ∈ N P ;
vérif. couverture par sommets.
5
Chapitre 4
NP-complétude et réductions
4.1 Définitions
A ≤p B s’il existe f polynomiale : x ∈ A ⇔ f (x) ∈ B. NP-difficile, NP-complet.
Cook–Levin : SAT NP-complet.
4.2 Chaînes classiques et exercices
SAT ≤p 3-SAT ≤p Vertex Cover / Clique / Independent Set.
Exos corrigés : SAT → 3-SAT ; gadgets 3-SAT → V C ; Partition → Subset Sum.
6
Chapitre 5
Méthodes exactes
5.1 Backtracking
Algorithme 1 : Backtracking k-coloration
Données : G = (V, E), k
Exploration systématique avec coupures précoces. Résultat : k-colorabilité
pour ordre sur V faire
essayer couleurs compatibles ; retour en arriè
5.2 Branch & Bound (B&B)
Arbre de recherche + bornes (relaxations). Exemple : sac à dos avec borne fractionnaire.
0 1
00 01
5.3 PLNE
P P
max vi xi s.c. wi xi ≤ W, xi ∈ {0, 1}.
Exos corrigés : C4 2-coloriable ; sac à dos (2, 3), (3, 4), (4, 5), (5, 8), (9, 10), W = 10 ⇒ valeur
7 ; PLNE pour Vertex Cover.
7
Chapitre 6
Méthodes d’approximation et
métaheuristiques (applications)
6.1 Cadre général
Métaheuristiques : descente, recuit, tabou, GRASP, VNS, GLS, algorithmes génétiques
(AG), ACO, hybridations. P
Pénalités : Fλ (s) = f (s) + j λj [gj (s)]+ .
6.2 8 reines
Modèle et objectif
s = (q1 , . . . , q8 ), qi ∈ {1, . . . , 8} (ligne de la reine en colonne i). Minimiser f (s) =
#{(i, k) : i < k, |qi − qk | = |i − k|}.
Voisinages
Swap(i, k), Move(i, ℓ) (avec mise à jour incrémentale de f ).
Descente / Recuit / Tabou (gabarits)
Algorithme 2 : Descente (8 reines)
Données : s initial
tant que existe s′ ∈ N (s) avec f (s′ ) < f (s) faire
s ← s′ le meilleur voisin
Algorithme 3 : Recuit simulé (8 reines)
Données : s, T0 , α
tant que T > Tmin et f (s) > 0 faire
choisir s′ ∈ N (s) ; ∆ = f (s′ ) − f (s) ; accepter si ∆ < 0 ou e−∆/T > rand() ;
T ← αT
8
Algorithme 4 : Recherche Tabou (8 reines)
Données : s, taille tabou L, meilleure s⋆
tant que non arrêt faire
s′ ← arg min{f (u) : u ∈ N (s) \ Tabou} (aspiration si f (u) < f (s⋆ )) ;
s⋆ ← min(s⋆ , s′ ) ; marquer mouvement inverse tabou L ; s ← s′
Figure TikZ — Graphe de conflits (ex. s = (1, 5, 8, 6, 3, 6, 4, 2))
1 2 3 4
5 6 7 8
Chaque nœud = colonne ; arête rouge = conflit diagonal avec la configuration donnée.
Corrigé détaillé (delta incrémental)
P
Pour Move(i, ℓ), seuls les couples (i, k) changent : ∆ = k̸=i (1[|qk − ℓ| = |k − i|] − 1[|qk −
qi | = |k − i|]). On met à jour f en O(8) (constant).
Instances TP
Départ s = (1, 5, 8, 6, 3, 6, 4, 2) ; variante (2, 5, 7, 4, 1, 8, 6, 3).
6.3 Sac à dos 0–1
Modèle et pénalité
P P P P
Maximiser vi xi s.c. wi xi ≤ W , xi ∈ {0, 1} ; Fλ (x) = − vi xi + λ max(0, w i xi −
W ).
Voisinages et réparations
Flip(i), Swap(i, j) ; réparation gloutonne par rapport vi /wi .
Recuit simulé (avec réparation)
Algorithme 5 : Recuit (Knapsack)
Données : x, T0 , α
tant que T > Tmin faire
échantillonner Flip/Swap ⇒ x′ ; réparer si besoin ; ∆ = Fλ (x′ ) − Fλ (x) ; accepter
avec règle de Metropolis ; T ← αT
9
GRASP + descente
Algorithme 6 : GRASP (Knapsack)
Données : |RCL|
tant que itérations faire
construire par RCL sur vi /wi ; réparer ; descente locale (Flip) ; garder le meilleur
Corrigé détaillé (GRASP sur petite instance)
Instance : W = 10, (w, v) = {(2, 3), (3, 4), (4, 5), (5, 8), (9, 10)}.
Tri par v/w : items 4(1.6),1(1.5),2(1.33),3(1.25),5(1.11). RCL= {4, 1} puis {1, 2}...
Construction typique : prendre 4 puis 1 ⇒ poids 7 ; ajouter 2 ⇒ poids 10 (valeur 8 + 3 + 4 =
15) faisable ; descente ne trouve pas mieux. Optimum : 15.
6.4 Rendu de monnaie (systèmes non canoniques)
Modèle
P P P P
Minimiser yj s.c. dj yj = M ; pénalité Fλ = yj + λ| dj yj − M |.
GRASP / VNS / Recuit / Tabou
Construction biaisée vers grandes pièces, ajustements ; alternance de voisinages ; autori-
ser sur/sous somme puis réparer.
Instance et corrigé
D = {1, 4, 6}, M = 8. Glouton naïf 6 + 1 + 1 (3 pièces). Meilleur : 4 + 4 (2 pièces).
Mouvement Swap(6 → 4) suivi d’un Move(−1) sur pièce 1 donne la solution optimale.
6.5 Sudoku (4x4 et 9x9)
Codage par blocs
Chaque bloc contient un multiensemble complet ; voisinages = swaps intra-bloc ; conflits
seulement lignes/colonnes.
Fonction objectif
f = nombre de violations ligne/colonne (zéro à l’optimum).
Recuit / Tabou / VNS / GLS / AG
Recuit : décroissance T ← 0.95T ; Tabou : interdire derniers swaps ; VNS : alterner
Swap et 2-Opt bloc ; GLS : pénaliser couples (case,valeur) conflictuels ; AG : croisement
par blocs, mutation swap intra-bloc, puis descente.
10
Figure TikZ — Grille 4x4 et blocs
0 0 3 4
3 4 0 0
0 0 4 2
4 2 0 0
Figure TikZ — Schéma ACO (flux des étapes)
Construction Amélioration M
Init phéromones τ , heuristique η
solutions par fourmis locale (descente) τ←
Corrigé détaillé (Mini-Sudoku 4x4, recuit)
Initialiser chaque bloc avec {1, 2, 3, 4} en respectant les cases figées ; f = conflits ligne/colonne.
Itérations : à T0 haut, accepter des swaps qui dégradent f pour sortir des plateaux ; T ←
0.95T jusqu’à f = 0.
Sur l’instance fournie, f décroît typiquement de 7–8 vers 0 en < 200 moves.
6.6 Pseudo-codes récapitulatifs
Algorithme 7 : Tabou + VNS (générique)
Données : s initial, voisinages {Nk }, L tabou, s⋆
tant que non arrêt faire
u ← arg min{Fλ (v) : v ∈ Nk (s) \ T abou} ; aspiration sur s⋆ ; marquer
mouvement ; s ← u ; s⋆ ← min(s⋆ , s)
Algorithme 8 : GRASP (générique)
Données : h, |RCL|, voisinage d’amélioration
tant que non arrêt faire
s ← construction biaisée (RCL) ; s ← descente ; mettre à jour meilleur
Algorithme 9 : AG mémétique (générique)
Données : Population P , croisement, mutation, voisinage local
tant que non arrêt faire
sélectionner parents ; croiser ; muter ; améliorer localement ; mise à jour de P
(élitisme)
Algorithme 10 : ACO (générique)
Données : Phéromones τ , heuristique η, évaporation ρ
tant que non arrêt faire
chaque fourmi construit une solution (p ∝ η β τ α ) ; amélioration locale ; mise à
jour τ
11
6.7 Mini-banque d’instances
8 reines : (1, 5, 8, 6, 3, 6, 4, 2) ; (2, 5, 7, 4, 1, 8, 6, 3).
Knapsack : W = 10, items (2, 3), (3, 4), (4, 5), (5, 8), (9, 10).
Monnaie : D = {1, 4, 6}, M = 8 ; D = {1, 3, 4}, M = 6.
Mini-Sudoku 4x4 ci-dessus.
12
Annexe A
Corrigés regroupés
Les corrigés principaux sont inclus dans chaque chapitre ; cette annexe peut recevoir des
solutions détaillées additionnelles selon les besoins.
13