Algorithmique et Complexité Algorithmes gloutons

Partie II

Emmanuel Hebrard et Mohamed Siala

Algorithmes gloutons 2 / 83

Rappel Algorithmes gloutons (Greedy algorithms)

Nous avons traité deux types de problèmes :

I Les problèmes de décision : Trouver une solution qui satisfait des critères (i.e., problème
de tri, problème de recherche d’élément, PGCD, etc) Contexte : typiquement pour les problèmes d’optimisation
I Les problèmes d’optimisation : Trouver une solution qui satisfait des critères et qui
minimise ou maximise un coût (e.g., parenthèsage pour la multiplication de matrices). Le Idée de base :
coût dans ce cas s’associe à une “fonction objectif”. I Résoudre le problème en une séquence d’étapes/choix
Nous avons étudié différentes approches de résolutions : I Pour chaque étape, faire un choix qui semble optimal à l’étape courante

I L’approche force brute (recherche exhaustive, énumération) Avantage : Rapide en temps de calcul
I Paradigme diviser pour régner (et les algorithmes récursifs)
I Programmation dynamique
Inconvénient : Pas de garantie sur l’optimalité

On découvre aujourd’hui une nouvelle approche de résolution (l’approche gloutonne)

et une jolie structure de représentation de problèmes qui s’appelle “les matroïdes”

Algorithmes gloutons 3 / 83 Algorithmes gloutons 4 / 83

 Exemple : Problème du Voyageur de commerce

Figure – Instance du problème du voyageur de commerce sous forme de graphe

c d
2
3
Voyageur de commerce (optimisation)
4
donnée : ensemble de villes 1
b
question : quel est le plus court cycle passant par toutes les villes une seule fois ? 5
7

Algorithmes gloutons 5 / 83 Algorithmes gloutons 6 / 83

Figure – Une solution non optimale Figure – Une solution optimale

c d c d
2 2
3 3
4 4
1 1
b b
5 5
7 7

a a

Cycle : a,b,c,d,a Cycle : a,c,b,d,a

Coût de la solution :7 + 3 + 2 + 5 = 17 Coût de la solution :1 + 3 + 4 + 5 = 13

Algorithmes gloutons 7 / 83 Algorithmes gloutons 8 / 83

 Énumération exhaustive ? Algorithme Glouton

2 Villes –> 1
3 Villes –> 1
Idée gloutonne :
4 Villes –> 3
I Construction de la solution ville par ville selon l’ordre de visite
5 Villes –> 12 I À partir de la dernière ville visitée, choisir la ville la plus proche qui est non visitée.
(n−1)!
n Villes –> (la moitié du nombre de permutations possible de taille n − 1) I Arrêter quand on visite toutes les villes
2
I Ajouter la première ville pour construire un cycle.
40 villes –> à peu près 1046 solutions à tester !
Avec une machine moderne : 3 × 1029 années (plus que AgeUnivers 3 ) !
La recherche exhaustive est inefficace ! !

Algorithmes gloutons 9 / 83 Algorithmes gloutons 10 / 83

Figure – Construction de la solution gloutonne étape par étape

Figure – Construction de la solution gloutonne étape par étape : Initialisation à
partir de “a” c d
2
c d 3
2
3 4
1
4 b
1 5
b
5 7
7
a
a
Cycle : a,c,d, b, a

Chemin initial : a Coût courant :1 + 2 + 4 + 7 = 14

Coût initial :0 C’est la solution retournée par l’algorithme glouton

Ce n’est pas une solution optimale mais c’est assez rapide à trouver

Algorithmes gloutons 11 / 83 Algorithmes gloutons 15 / 83

 Algorithme Glouton pour le voyageur de Matroïdes
commerce

Algorithme : Glouton (n, distance)

Données : n ∈ N∗ : nombre de villes, distance[i][j] ∈ R+ : la distance entre ville i et ville j
Résultat : Permutation de 1, . . . , n
début
Ensemble ← {1, . . . n} ;
element ← 1 ;
Permutation ← element ;
Ensemble ← Ensemble \ {element} ;
Résoudre des problèmes d’optimisation avec des algorithmes gloutons
tant que |Permutation| < n faire
min ← +∞ ; Un matroïde représente une structure particulière utilisée pour concevoir un
pour e ∈ Ensemble faire algorithme glouton optimal
si distance[element][e] < min alors
min ← distance[element][e] ;
ville ← e ;

Permutation ← Permutation, ville ; // Ajouter ville à la fin de Permutation

Ensemble ← Ensemble \ {ville} ;
element ← ville ;
retourner Permutation ;

Complexité : O(n2 )

Algorithmes gloutons 16 / 83 Algorithmes gloutons 17 / 83

Définition Exemple (simple) de Matroïde

E = {1, 2, 3, 4}
I = {{}, {1}, {2}, {4}, {1, 4}, {2, 4}}
Un matroïde est un couple M = (E, I) qui satisfait les conditions suivantes : Preuve
I E est un ensemble fini non vide I E est un ensemble fini non vide (évident)
I I est un ensemble de sous ensembles de E tel que : I I est héréditaire car :
F Si H ∈ I, et F ⊂ H, alors F ∈ I (on dit que I est héréditaire) F Pour {2, 4} : {} ∈ I , {2} ∈ I , {4} ∈ I
F Si F ∈ I, H ∈ I et |F | < |H|, alors ∃x ∈ H \ F tel que F ∪ {x} ∈ I (propriété d’échange) F Pour {1, 4} : {} ∈ I , {1} ∈ I , {4} ∈ I
F Pour {1} : {} ∈ I , {1} ∈ I
F Pour {2} : {} ∈ I , {2} ∈ I
Si M = (E, I) est un matroïde et H ∈ I, alors H est appelé “sous ensemble F Pour {3} : {} ∈ I , {4} ∈ I
indépendant” F Pour {} : {} ∈ I
I Propriété d’échange :
F Pour H = {1, 4} et F = {2} : F ∪ {4} ∈ I
F Pour H = {2, 4} et F = {1} : F ∪ {2} ∈ I
F Pour H = {4} et F = {} : F ∪ {4} ∈ I
F ...

Algorithmes gloutons 18 / 83 Algorithmes gloutons 19 / 83

 Matroïde pondéré Algorithme glouton

Algorithme : Glouton (M(E, I) , w )

Données : M(E, I) : matroïde, w : fonction de poids
Résultat : Sous ensemble indépendant de E (probablement de poids maximal)
début
Soit M = (E, I) un matroïde F ← {};
M est pondéré s’il existe une fonction de poids pour les éléments de E. Pour chaque n ← |E| ;
L ← Trier (E) par poids décroissant ;
x ∈ E, w (x) ∈ R+∗ est le poids de x. pour i ∈ [1..n] faire
un sous ensemble de E, alors le poids de F se définit avec
Si F est P si F ∪ {L[i]} ∈ I alors
w (F ) = x∈F w (x) F ← F ∪ {L[i]};

Problème de sous ensemble indépendant de poids maximal : retourner F ;

I Donnée : M = (E, I) : matroïde et w : fonction de poids
I Question : Trouver F ∈ I de poids maximal

Complexité : Si le test d’appartenance (ligne 7) se fait en O(f (n)), alors

la complexité de Glouton (M(E, I) , w ) est O(nlog (n) + nf (n)) avec
n = |E| (car le tri peut se faire en O(nlog (n))).

Algorithmes gloutons 20 / 83 Algorithmes gloutons 21 / 83

L’importance des matroïdes Glouton (M(E, I) , w ), alors ?

Rappel pour un problème d’optimisation :

Theorem
I Une solution est une sortie qui respecte les exigences du problème
Glouton (M(E, I) , w ) retourne un sous ensemble indépendant optimal I Une solution optimale est une solution qui (minimise ou maximise) une fonction
(objectif).
Algorithme : Glouton (M(E, I) , w ) I Le coût d’une solution est la valeur correspondante à la fonction objectif
Données : M(E, I) : matroïde, w : fonction de poids
Résultat : Sous ensemble indépendant de E de poids maximal Pour exploiter Glouton (M(E, I) , w ) pour un problème d’optimisation P :
début I Il faut trouver un matroïde M(E, I) pondéré tel qu’une solution optimale de P
F ← {}; correspond à un sous ensemble indépendant (i.e., élément de I) de poids maximal qu’on
n ← |E| ; peut calculer à partir de Glouton (M(E, I) , w ).
L ← Trier (E) par poids décroissant ; I Dans ce cas, l’algorithme glouton est garanti de retourner une solution optimale
pour i ∈ [1..n] faire
Cette approche ne marche pas pour tous les problèmes. En particulier, il y a souvent
si F ∪ {L[i]} ∈ I alors
deux limites :
F ← F ∪ {L[i]};
1 Difficulté à définir l’ensemble I des sous ensembles indépendants
retourner F ; 2 Même si on trouve I , le test d’appartenance (F ∈ I ?) est coûteux en temps (par exemple
quand f (n) = O(2n ).

Algorithmes gloutons 22 / 83 Algorithmes gloutons 23 / 83

 Complexité en fonction de la taille de la donnée

Pourquoi calculer la complexité en fonction de la taille de la donnée ?

Sinon quel paramètre choisir ?

I Multiplication de x par y : en fonction de x ? de y ? de x + y ? de xy ?

Représentation des Données

Sinon comment comparer des algorithmes avec des données différentes ?
I Est-ce que Factorielle est plus efficace que triSélection ?

I Factorielle : Θ(x) opérations, |x| = log2 x, donc Θ(2|x| ) opérations

I triSélection : Θ(n2 ) opérations, |T | = n, donc ≥ Θ(|L|2 ) opérations

Comment connaitre la taille de la donnée ?

Représentation des Données 24 / 83 Représentation des Données 25 / 83

Calculer la taille de la donnée Encodage

On compte le nombre de bits mémoire, en ordre de grandeur (Θ) Encodage

Un encodage pour un type de donnée T est une fonction injective :
Exemples :
f : T 7→ {0, 1}k
I Types char, int, float, etc. : O(1)

I Type N : Θ(log n) (pour un entier ≤ n) Tout x ∈ T a un seul code f (x) (fonction)

I Sinon on ne peut pas toujours encoder
I Type liste d’int : Θ(n) (pour une liste de longueur ≤ n)
Pour x, y ∈ T distincts, f (x) 6= f (y ) (injective)
I Sinon on ne peut pas toujours decoder
Borne supérieure (O) Borne inférieure (Ω)
Trouver un encodage Principe des tiroirs
Exemples : ASCII, Morse,...

Représentation des Données 26 / 83 Représentation des Données 27 / 83

 Encodage d’un char Encodage d’un entier n ∈ N

0 0 0 0 0 0 0 1 0 0 1 0 1 1
0 1 0 0 1 0 1 1 | {z }
N◦ de 0 = N◦ de bits =7 26 25 24 23 22 21 20
27 26 25 24 23 22 21 20

Code en base 2 : O(log2 n) pour coder tout entier naturel ≤ n

Représenter les entiers entre 0 et 255 (char)
Problème : combien de bits allouer pour coder n’importe quel entier ? ∞ ?
7
bi 2i
P
Chaque bit repésente un terme de la somme x =
i=0 Donner le nombre de bits “utiles” en préfixe, en code unaire (autant de 0 que de bits
significatifs)
Pour x = 75 : 1 × 26 + 1 × 23 + 1 × 21 + 1 × 20
Code en O(log2 (n)) pour le préfixe + O(log2 (n)) pour le suffixe

Borne supérieure (et inféreieure) Borne supérieure

Si c est de type “char” alors |c| ∈ O(1), et donc |c| ∈ Θ(1) Si n ∈ N alors |n| ∈ O(log n)

Représentation des Données 28 / 83 Représentation des Données 29 / 83

Encodage d’un tableau de n int Borne inférieure sur la taille de la donnée

8 13 0 3 −18 2 9 11 −4 Quelques principes de base de dénombrement

size L[0] L[1] L[2] L[3] L[4] L[5] L[6] L[7]

Principe additif
Chaque int requiert 4 octets : n × O(1) Les choix mutuellement exclusifs se combinent par addition.
Ex : combien de choix possibles de plats principal si on a 3 types de viande, 2 poisson
Même astuce que pour les entiers, le nombre d’éléments en préfixe : O(log n) et 3 plats végétariens ? 3 + 2 + 3 = 8 plats

n × O(1) + O(log n) = O(n)

Principe multiplicatif
Borne supérieure Les choix indépendents se combinent par multiplication.

Si L est un tableau contenant n int, alors |L| ∈ O(n) Combien de menus s’il y a 3 entrées, 4 plats, et 4 desserts ? 3 × 4 × 4 = 48 menus
Combien de valeurs possibles pour un int sur 32 bits ? 232 valeurs

Représentation des Données 30 / 83 Représentation des Données 31 / 83

 Principes des tiroirs Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :
Principe des tiroirs f : T 7→ {0, 1}k avec f (x) ∈ {0, 1}|x|
Si m objets sont rangés dans n tiroirs, alors un tiroir en contient au moins d mn e.

Il y a 2k mots binaires de longueur k (Principe multiplicatif)

Si m > n objets sont rangés dans n tiroirs, alors un tiroir en contient au moins 2
Il faut au moins autant de mots binaires que de valeurs possibles pour la donnée
Il y a deux londoniens avec exactement le même nombre de cheveux
I Principe des tiroirs : sinon, des données distinctes ont le même code, et f est non-injective

I Il n’y a pas plus d’un million de cheveux sur un crâne, donc pas plus d’un million de
nombres de cheveux distincts Minorant pour la taille |x| d’une donnée x de type T
I Il y a plus d’un million de londoniens Soit #(T ) le nombre de valeurs possibles du type de donnée T , la mémoire
|x| nécessaire pour stocker une donné x ∈ T est telle que 2|x| ≥ #(T ), ⇒
I m londoniens à répartir parmi n chevelures possibles ⇒ au moins deux londoniens avec la
même chevelure
|x| ∈ Ω(log #(T ))

Représentation des Données 32 / 83 Représentation des Données 33 / 83

Bornes inférieures Complexité en fonction de la taille de la donnée

Calculons #(T ), le nombre de valeurs possibles pour la donnée x de type T : L’algorithme A est en Θ(f (x)) pour une donnée x
La taille |x| de la donnée est en Θ(g (x))
I Entier naturel inférieur ou égal à n : n + 1, soit Θ(n) Alors la complexité de A est en Θ(f (g −1 (x)))
Pour x un entier naturel inférieur ou égal à n : Exemple
|x| ∈ Ω(log n) et puisqu’il existe un encodage tel que |x| ∈ O(log n), alors |x| ∈ Θ(log n) Algorithme : Carré(x)
Données : un entier x
Résultat : un entier valant x 2 Complexité : Θ(x 2 )
I Tableau d’int de longueur n : (232 )n , soit Θ(232n )
r : entier;
n début Taille de la donnée |x| = Θ(log x)
232i , soit Θ(232n )
P
I Tableau d’int de longueur ≤ n : r ← 0;
i=0
pour i allant de 1 à x faire
I log2 (232n ) = 32nlog2 (2) = 32n pour j allant de 1 à x faire Autrement dit, x = Θ(2|x| )
r ← r + 1;
Pour L un tableau d’int de longueur ≤ n :
retourner r ; Donc complexité en Θ(22|x| ) (exponentielle !)
|L| ∈ Ω(n) et puisqu’il existe un encodage tel que |L| ∈ O(n), alors |L| ∈ Θ(n)

Représentation des Données 34 / 83 Représentation des Données 35 / 83

 Structure de données Structure de données

Le choix de la structure de données est très important dans la conception Un type abstrait est défini par les opérations qui sont efficaces sur ce type
d’un algorithme
Une réalisation correspond à du code (des algorithmes)

Choisir la structure pour laquelle les opérations utiles sont les plus efficaces
Type Abstrait Réalisation I A S SP SD SM
Un type abstrait est défini par les opérations qui sont efficaces sur ce type Pile Liste chainée O(1) Θ(n) Θ(n) Θ(n) O(1) Θ(n)
Liste chainée avec
File O(1) Θ(n) Θ(n) O(1) Θ(n) Θ(n)
pointeurs début et fin
I Insertion (I) : ajouter un nouvel élément Index statique Vecteur trié Θ(n) O(log n) Θ(n) N/A N/A Θ(n)
I test d’Appartenance (A) : vérifier si l’élément x est présent File de priorité Tas binaire O(log n) Θ(n) Θ(n) N/A N/A O(log n)
I Suppression (S) : supprimer un élément x O(1)∗ O(1)∗
I Suppression du Dernier (SD) : supprimer le dernier élément inséré Ensemble Table de hâchage O(1) N/A N/A Θ(n)
Θ(n) Θ(n)
I Suppression du Premier (SP) : supprimer le premier élément inséré ABR, AVL
I Suppression du Minimum (SM) : supprimer l’élément minimum Ensemble trié O(log n) O(log n) O(log n) N/A N/A O(log n)
Arbre rouge-noir

Représentation des Données 36 / 83 Représentation des Données 37 / 83

Exemple : Table de Hâchage Exemple : Table de Hâchage

Fichier des étudiants de l’INSA, il faut une clé unique pour identification T [i − 1] T [i] T [i + 1]

Tatouer chaque étudiant avec son numéro d’inscrit (1, . . . , n) ?

I Une table T avec T [x] contenant les informations pour l’étudiant x
enregistrement(x)
Utiliser le numéro de sécurité sociale ?
h(x) = h(y ) = i
I Beaucoup trop de clés possibles !
enregistrement(y )

Table de Hâchage : n enregistrements / table de taille m ∈ Θ(n)

Analyse de la complexité du test d’appartenance (A)
Soit U l’ensemble des clés possibles, avec |U| = M, m  M
I Pire des cas Tmax (n) = Θ(n) (tous les enregistrements ont la même valeur de hâchage)
Soit h : U 7→ {1, . . . , m} un fonction de hâchage : renvoie un index pour chaque clé, I Pour Tmoy (n) on suppose une distribution uniforme des valeurs de h(x) dans {1, . . . , m}
par ex. h(x) = ((ax + b) mod p) mod m) avec m  p  M premier et 0 < a, b < p
m
P
L’enregistrement de clé x est stocké dans T [h(x)]. Si h(x) = h(y ) et x 6= y on dit I Soit Li la longueur de la liste T [i], et E (Li ) l’espérance de Li : E (Li ) = n
i=1
qu’il y a une collision I Mais E (Li ) ne dépend pas de i, donc Tmoy (n) = E (Li ) = n/m ∈ O(1)

Représentation des Données 38 / 83 Représentation des Données 39 / 83

 Exemple : Tas Binaire Tri par tas
Invariants : arbre binaire complet ; sommet parent ≤ fils

1 67
2
3
Donnée : une liste L d’éléments comparables
2 67
3
5 3 6 Pour chaque x ∈ L :
Insérer x dans le tas binaire H
4 8 5 67
3
5 6 50 7 38 Tant que H n’est pas vide :
Extraire le minimum de H et l’afficher
8 12 9 95 67
3

1 2 3 4 5 6 7 8 9 10
réalisation :
22673 533675 6 8 673567 50 38 12 95 .367
parent de i : bi/2c n insertions en O(log n)
Tri par tas est optimal !
fils gauche de i : 2i
n suppressions en O(log n)
fils droit de i : 2i + 1 O(n log n) dans le pire des cas
Complexité du tri par tas : O(n log n)
Insertion : la position libre la plus à gauche possible sur le dernier niveau
I Percolation échange avec le parent jusqu’à ce que l’invariant soit rétabli O(log n)
Suppression du minimum : la racine, qu’on remplace par le “dernier” sommet
I Percolation échange avec le fils minimum jusqu’à ce que l’invariant soit rétabli O(log n)
Représentation des Données 40 / 83 Représentation des Données 41 / 83

Borne inférieure pour les algorithmes de tri

Tri par comparaison

donnée : une liste d’éléments comparables
question : quelle est la liste triée de ces éléments ?

Classes de Complexité Considérons les algorithmes de tri qui ne peuvent pas “lire” ces éléments, seulement
les comparer (e.g. un tableau de pointeurs vers une classe d’objets comparables).

Lors de son execution, cet algorithme va comparer k paires d’éléments (x, y ), le

résultat peut être 0 (x < y ) ou 1 (x ≥ y )

On peut considérer que la donnée de l’algorithme est une table de longueur k avec les
résultats des comparaisons :

x = [0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1]
| {z }
k

Classes de Complexité 42 / 83 Classes de Complexité 43 / 83

 Borne inférieure pour les algorithmes de tri Borne inférieure pour les algorithmes de tri

Un algorithme est deterministe, donc deux tables de comparaisons identiques donnent

la même exécution, et donc la même liste triée
2k ≥ n! =⇒ k ≥ log(n!)
[0, 0, 1, 0, 1, 1, 1, 1, . . .] (e1 , e2 , e3 , e4 , . . .)
[0, 0, 1, 0, 1, 1, 1, 1, . . .] (e1 , e2 , e4 , e3 , . . .) = log(n(n − 1)(n − 2) . . . 2)
[0, 1, 0, 0, 1, 0, 0, 1, . . .] (e1 , e3 , e2 , e4 , . . .) = log n + log(n − 1) + log(n − 2) + . . . + log(2)
2k [1, 0, 0, 0, 0, 1, 1, 1, . . .] (e1 , e3 , e4 , e2 , . . .) n! X n

[0, 1, 1, 0, 1, 1, 0, 0, . . .] (e1 , e4 , e2 , e3 , . . .) = log i

[1, 0, 1, 0, 0, 1, 1, 0, . . .] (e1 , e4 , e3 , e2 , . . .) i=2

[0, 0, 1, 0, 1,.. 1, 1, 1, . . .] (e1 , e2 , e..3 , e4 , . . .) n/2−1 n

. .
X X
= log i + log i
i=2 i=n/2
Au plus k comparaisons, donc au plus 2k données/exécutions distinctes n
X n
≥ log
Chacune des n! permutations de la donnée doit correspondre à une exécution distincte 2
i=n/2
n n
= log
principe des tiroirs 2 2
= Ω(n log n)
2k ≥ n!
Classes de Complexité 44 / 83 Classes de Complexité 45 / 83

Borne inférieure pour les algorithmes de tri La complexité d’un problème, à quoi ça sert ?

Théorème
Tout algorithme de tri par comparaison est en Ω(n log n) Pour pouvoir objectivement analyser un algorithme
I Optimalité

Parce que la difficulté du problème détermine le type de méthode

Attention, il existe des algorithmes de tri en O(n)
I solution approchée pour un problème difficile ?
I Mais ces algorithmes font des hypothèses sur les éléments à trier

Parce que la difficulté du problème est parfois une garantie

Dans le cas général d’éléments comparables sans propriété particulière : impossible de I Cryptographie, Block Chain
les trier avec une complexité dans le pire des cas inférieure à Ω(n log n)

Classes de Complexité 46 / 83 Classes de Complexité 47 / 83

 Problème Types de Problèmes

Définition : Problème ' fonction sur les entiers

Une question Q qui associe une donnée x à une réponse y
I “Quel est le plus court chemin de x1 vers x2 par le réseau R ?” Problèmes généraux (fonctions)
I “Quel est la valeur du carré de x ?”

Problèmes d’optimisation : la solution est le minimum d’un ensemble

Qpcc : Réseau : R, Villes : x1 , x2 7→ Route : x1 , u1 , u2 , . . . , uk , x2

Problèmes de décision : la réponse est dans {oui, non}

Qcarr : Entier : x 7→ Entier : x 2

Classes de Complexité 48 / 83 Classes de Complexité 49 / 83

Problème de décision Instance

Problème de décision Q
Fonction Q : x →
7 {oui, non}
Instance : problème avec la donnée (“Combien vaut 5672 ?”, “Quel est le plus court
chemin entre Toulouse et Paris ?”)
Pour un problème d’optimisation, on peut généralement définir un problème
polynomialement équivalent dont la réponse est dans {oui, non}, :
Ne pas confondre problème et instance
Voyageur de commerce (optimisation)
donnée : ensemble de villes En particulier, se poser la question de la difficulté d’une instance n’a pas
(beaucoup ?) de sens
question : quel est le plus court chemin passant par toutes les villes ?

Voyageur de commerce (décision) I L’algorithme qui renvoie systématiquement, et sans calcul, la solution de cette instance
(correct et en O(1))
donnée : ensemble de villes, entier k
question : est-ce qu’il existe un chemin de longueur inférieure à k passant par toutes
les villes ?

Classes de Complexité 50 / 83 Classes de Complexité 51 / 83

 Classes d’Algorithmes Classes de problèmes

Comment évaluer la complexité d’un problème ?

Un algorithme est dit :
La complexité d’un problème :
en temps constant si sa complexité dans le pire des cas est bornée par une constante
La complexité du meilleur algorithme pour le résoudre

linéaire si sa complexité dans le pire des cas est en Θ(n)

f (n)-TIME
quadratique si sa complexité dans le pire des cas est en Θ(n2 )
Ensemble des problèmes pour lesquels il existe un algorithme en O(f (n))

polynomial si sa complexité dans le pire des cas est en O(nc ) avec c > 0
Tri ∈ (n log n)-TIME
nc Recherche dans un tableau trié ∈ (log n)-TIME
exponentiel si elle est en Θ(2 ) pour un certain c > 1
Recherche du maximum dans un tableau ∈ (n)-TIME

Classes de Complexité 52 / 83 Classes de Complexité 53 / 83

Relation d’Inclusion Problème de Tri

Tri
Inclusion
donnée: Une liste L d’objet comparables
Si f (n) ∈ O(g (n)) alors f (n)-TIME ⊆ g (n)-TIME
question: La séquence triée des objets de L

n2 -TIME
Tri n-TIME
(n log n)-TIME Max ?
(log n)-TIME
n-TIME
(n log n)-TIME
(log n)-TIME
Tri ∈ (n log n)-TIME
Tout algorithme de tri est en Ω(n log n) =⇒ Tri 6∈ n-TIME
La recherche du maximum est dans n-TIME, dans (log n)-TIME ?

Classes de Complexité 54 / 83 Classes de Complexité 55 / 83

 (Non-)Appartenance à une Classe Classe “Temps Polynômial”

Rappel :
f (n)-TIME
Ensemble des problèmes pour lesquels il existe un algorithme en O(f (n)) f (n)-TIME
Ensemble des problèmes pour lesquels il existe un algorithme en O(f (n))

Pour prouver qu’un problème appartient à la classe f (n)-TIME Classe des problèmes pour lesquels il existe un algorithme polynômial :
I il suffit d’un algorithme en O(f (n))
P-TIME ou simplement : P
Ensemble des problèmes pour lesquels il existe un algorithme en O(nc )
Pour prouver qu’un problème n’appartient pas à une classe inférieure
pour une constante c.
I il faut montrer que tout algorithme est en Ω(f (n))
[
P= nc -TIME
c≥0

Classes de Complexité 56 / 83 Classes de Complexité 57 / 83

Classe “Temps Exponentiel” Classes Caractérisées par l’Espace

Classe des problèmes pour lesquels il existe un algorithme exponentiel :

EXP-TIME : On peut analyser l’espace mémoire utilisé par un algorithme de manière similaire

Ensemble des problèmes pour lesquels il existe un algorithme en O(2 ) nc

pour une constante c

f (n)-SPACE
nc
[
EXP-TIME = 2 -TIME Ensemble des problèmes pour lesquels il existe un algorithme nécessitant
c≥1 O(f (n)) octets de mémoire

Evidemment, P ⊆ EXP-TIME
EXP-TIME P On ne compte pas la taille de la donnée, mais on compte la taille de la réponse
Est-ce que P ⊂ EXP-TIME ? Oui !
Il existe des problèmes en Ω(2n )

Classes de Complexité 58 / 83 Classes de Complexité 59 / 83

 Exemple : Sous-Séquence Maximale Exemple : Sous-Séquence Maximale
z }| {

Sous-Séquence Maximale L[i] 1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 -1

s[i] 1 2 3 2 1 0 -1 0 -1 -2 -1 0 1 2 1 0 1 2 3 2 1 2 1 2 1 0 -1
donnée: Un tableau L avec n éléments dans {−1, 1}
min[i] 0 0 0 0 0 0 0 -1 -1 -1 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
Quelles sont les valeurs de s et e dans [1, n] qui maximisent
question: P
e max[i] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 1 0 -1
i=s L[i]
mss[i] 3 3 3 3 3 3 3 4 4 4 5 5 5 5 5 5 5 5 5 4 4 4 4 4 3 2 1

-1 -1 |1 1 -1 {z
1 -1 1 1} -1 -1 1 1 -1 1 Algorithme 2
3 Pi
s[i] = k=1 L[k]
Pj Pj Pi−1 Θ(1) tables de taille Θ(n)
Algorithme 1 3
I
k=i L[k] = k=1 L[k] − k=1 L[k]
Temps : Θ(n ) Temps : Θ(n)
min[i] = min(s[j] | j < i)
P1≤i ≤j ≤n:
Pour chaque Espace : Θ(log n) Espace : Θ(n)
calculer jk=i L[k] ; garder le max. I log n pour le max, la somme et le resultat
max[i] = max(s[j] | j ≥ i)
mss[i] = maxi − mini

Classes de Complexité 60 / 83 Classes de Complexité 61 / 83

Temps ou Espace Temps ou Mémoire ?

Théorème
f (n)-TIME ⊆ f (n)-SPACE

Temps Espace Supposons qu’il existe un problème A t.q. A ∈ f (n)-TIME et A 6∈ f (n)-SPACE.

Algorithme 1 Θ(n3 ) Θ(log n)

Alors tout algorithme pour A utilise Ω(g (n)) mémoire avec g (n) 6∈ O(f (n)).
Algorithme 2 Θ(n) Θ(n)
Si un algorithme nécessite Ω(g (n)) mémoire il fait Ω(g (n)) écritures.

Autrement dit, il est en Ω(g (n)) temps (contradiction).

Donc A ∈ f (n)-TIME =⇒ A ∈ f (n)-SPACE.

Classes de Complexité 62 / 83 Classes de Complexité 63 / 83

 Classe “Espace Polynomial” P-SPACE et EXP-TIME

Théorème
Classe des problèmes pour lesquels il existe un algorithme polynômial en espace : P-SPACE ⊆ EXP-TIME

P-SPACE Un problème A dans P-SPACE admet un algorithme qui utilise O(nc ) octets
Ensemble des problèmes pour lesquels il existe un algorithme qui utilise Cet algorithme est constitué de k ∈ Θ(1) instructions (' lignes de code)
O(nc ) octets de mémoire pour une constante c. c
La mémoire utilisée par cet algorithme peut être dans O(2(8n) ) configurations
c c
Il y a donc O(k2(8n) ) = O(2(n) ) configurations possibles
[
= P-SPACE nc -SPACE
c≥0 Si l’algorithme passe deux fois par la même configuration il ne s’arrête jamais

Est-ce que P-SPACE est inclu dans EXP-TIME, EXP-TIME inclu dans
P-SPACE, ou ni l’un ni l’autre ? EXP-TIME P-SPACE P

Classes de Complexité 64 / 83 Classes de Complexité 65 / 83

Problèmes “intermédiaires”

Il y a un nombre infini de classes de complexité entre P et P-SPACE !

EXP-TIME P-SPACE ? P
Les Classes NP et coNP

Il existe des problèmes pour lesquels on ne connait pas d’algorithme en temps

polynômial, sans pouvoir prouver qu’ils n’en n’ont pas
Ces problèmes sont très nombreux...
... et très intéressants : Voyageur de Commerce, Programmation Linéaire en Nombres
Entiers, SAT , Isomorphisme de Graphes, etc.

Classes de Complexité 66 / 83 Les Classes NP et coNP 67 / 83

 Classes non-déterministes Classes non-déterministes

Ces problèmes peuvent être résolus en espace polynomial

EXP-TIME P-SPACE ?NP P Pas d’algorithme en temps polynomial connu, mais aucune preuve d’impossibilité

Problèmes faciles pour des algorithmes non-déterministes

A priori difficiles (pas d’algorithme polynomial connu)

Faciles à vérifier, ex. Voyageur de Commerce Algorithme non-déterministe pour le problème Q
Composée d’instructions primitives : exécutable par une machine
TSP Déterministe : une seule exécution possible pour chaque donnée
donnée: Un ensemble de villes S, une matrice de distance D : S × S 7→ N, un entier k Non-déterministe : peut deviner un certificat (par ex. la solution !)
Correct : termine et retourne la bonne solution Q(x) pour toute valeur de la donnée x
question: Est-ce qu’il existe une route de longueur au plus k passant par toutes les villes ?

Les Classes NP et coNP 68 / 83 Les Classes NP et coNP 69 / 83

Oracle Exemple : Le problème de 3-coloration

Algorithme non-déterministe
Un algorithme non-déterministe peut avoir recours à un oracle qui, si la réponse est Donnée : Un graphe G = (S, A) (sommets S ; arêtes A)
“oui”, devine un certificat polynomial en temps O(1)
Question : Est-ce qu’il est possible de colorier les sommets de G avec au
Le certificat peut-être n’importe quoi, mais :
plus 3 couleurs en évitant que deux sommets adjacents
I Il faut pouvoir le coder en espace polynomial dans la taille de la donnée
I Il faut pouvoir prouver que “oui” est bien la réponse correcte en temps polynomial dltd
partagent la même couleur.

Quel certificat pour le problème du voyageur de commerce ?

TSP
donnée: Un ensemble de villes S, une matrice de distance D : S × S 7→ N, un entier k ?
question: Est-ce qu’il existe une route de longueur au plus k passant par toutes les villes ?

La séquence de villes : on peut vérifier la longueur de ce tour, et être convaincu que

la réponse est correcte, même si on ne sait pas comment elle a été obtenue
Les Classes NP et coNP 70 / 83 Les Classes NP et coNP 71 / 83
 3-Coloration est dans NP

Algorithme de vérification
Algorithme : verification(L, G )
Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)
Données : un graphe G = (S, A) et un tableau T
Résultat : vrai si T est une 3-coloration de G , faux sinon
début
De taille polynomiale (dans la TDLD) pour chaque arrête (i, j) de A faire
si T [i] = T [j] alors
retourner faux ;
I quelle est la taille de la donnée du problème ?
taille : |G | = Θ(|S| + |A|)
retourner vrai ;
I quelle est la taille du certificat ? Complexité : O(|A|) (liste d’adjacence)
taille : Θ(|S|)

Vérifiable en temps polynomial (dans la TDLD) : algorithme ⇒ 3-Coloration est bien dans NP

Les Classes NP et coNP 72 / 83 Les Classes NP et coNP 73 / 83

P et NP P, NP et la Cryptographie

Système d’authentification A
P est la classe des problèmes “faciles à résoudre” comparaison entre
I une clé privée y (mot de passe / pin)
I et une information publique x (login / carte bancaire)
NP est la classe des problèmes “faciles à vérifier”
autorise la transaction si et seulement si A(x) = y

Est-ce qu’il y a une différence ? (500 000 e pour la bonne réponse !)

Supposons que calculer A soit polynomial : trouver le mot de passe est facile !

I On ne connait pas d’algorithme polynomial pour Voyageur de commerce ou 3-Coloration Supposons que vérifier A(x) = y ne soit pas polynomial : authentifier est difficile !

I Mais personne ne sait s’il en existe !

La majorité des systèmes d’authentification
sont basés sur un problème A tel que A ∈ NP et A 6∈ P

Les Classes NP et coNP 74 / 83 Les Classes NP et coNP 75 / 83

 L’importance de la classe NP L’importance de la classe NP (suite)
Ces problèmes sont partout : en intelligence artificielle, en cryptographie, dans
l’industrie...
Savoir adapter la méthode à la complexité du problème ; le problème du voyageur de Conjecture P 6= NP
commerce n’a pas d’algorithme polynomial connu, mais...
I Domaine de recherche très actif, des algorithmes “intelligents” peuvent résoudre
Un des 7 “problèmes du millénaire” du Clay Mathematics Institute
(optimalement) de très grandes instances Mise-à-prix $1 000 000

Preuve de P 6= NP : un problème dans NP mais pas dans P

I Montrer qu’un problème est dans NP est facile : certificat polynomial

I Montrer qu’un problème n’est pas dans P est difficile : tout algorithme est en Ω(2n )

Prouver que P = NP ne nécessite qu’un algorithme ! (cours de 4ème année)

115 475 villes

Les Classes NP et coNP 76 / 83 Les Classes NP et coNP 77 / 83

Et si l’oracle ne devine rien ? Problème complémenaire

La réponse “oui” est accompagnée d’un certificat grace auquel on peut vérifier que la
réponse est correcte
Problème complémenaire
Si la réponse est “non”...il faut faire confiance ! Le Problème complémenaire co-A d’un problème de décision A, est le
problème qui associe la réponse “non” à toute donnée associée à “oui” dans
I Ou alors vérifier avec un algorithme qui n’est pas polynomial A, et vice versa.

Donc le problème suivant n’est pas forcément équivalent au problème du voyageur de

commerce ?
Si A est dans P alors co-A est dans P

co-TSP I Algorithme polynomial pour co-A : algorithme pour A + inversion de la réponse

donnée: Un ensemble de villes S, une matrice de distance D : S × S 7→ N, un entier k

question: Est-ce qu’il n’existe pas de route de longueur au plus k passant par toutes les Est-ce que c’est vrai pour NP ?
villes ?

Les Classes NP et coNP 78 / 83 Les Classes NP et coNP 79 / 83

 La classe coNP La classe coNP

Co-problème du voyageur de commerce

donnée : ensemble de villes, entier k
Le complémentaire de certain problèmes dans NP ne semblent pas être dans NP
question : est-ce qu’il n’existe aucun chemin passant par toutes les villes, et de
longueur inférieure à k ?

Quel est le certificat ? coNP

Ensemble des problèmes de décision dont le problème complément est dans NP
Un chemin qui ne passe pas par toutes les villes, ou de longueur > k ? pas suffisant !

Lister tous les chemins ? pas polynomial !

Le co-problème du voyageur de commerce ne semble pas avoir de certificat polynomial

Conjecture
NP 6= coNP ?
Les complémentaires de certain problèmes dans NP ne semblent pas être dans NP

Les Classes NP et coNP 80 / 83 Les Classes NP et coNP 81 / 83

Inclusion dans P-SPACE Résumé : les classes de complexité

EXP-TIME
Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.
P-SPACE
il existe un algorithme déterministe qui n’utilise pas plus d’espace :

N
N
Le certificat nécessite un espace fini (vérifiable en O(nc ) pour une donnée de taille n)

P
I

co
c P
I Il y a donc un nombre fini de certificat : O(2n ) ..
.
c
I On génère et verifie tous les certificats (en temps O(nc 2n ))
n-TIME
.
..

Théorème (log n)-TIME

NP ⊆ P-SPACE et coNP ⊆ P-SPACE

Les Classes NP et coNP 82 / 83 Les Classes NP et coNP 83 / 83