0% ont trouvé ce document utile (0 vote)

29 vues741 pages

Algorithmes de Complexité et Problèmes NP

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

29 vues741 pages

Algorithmes de Complexité et Problèmes NP

Transféré par

eteuboudurel

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithmique et Complexité

Emmanuel Hebrard et Mohamed Siala

Question d’un entretien d’embauche chez Google

2 / 174
Question d’un entretien d’embauche chez Google

7
4
5
4 4
3
2 2
1

Soit un histogramme avec n barres

2 / 174
Question d’un entretien d’embauche chez Google

7
4
5
4 4
3
2 2
1

Soit un histogramme avec n barres sur lequel on a versé un volume d’eau infini.

2 / 174
Question d’un entretien d’embauche chez Google

7
4
5
4 4
3
2 2
1

Soit un histogramme avec n barres sur lequel on a versé un volume d’eau infini.

I Donnez un algorithme pour calculer le volume d’eau résiduel (16).

2 / 174
Question d’un entretien d’embauche chez Google

7
4
5
4 4
3
2 2
1

Soit un histogramme avec n barres sur lequel on a versé un volume d’eau infini.

I Donnez un algorithme pour calculer le volume d’eau résiduel (16).

I Donnez un algorithme pour calculer le volume d’eau résiduel en temps linéaire.

2 / 174
Trois problèmes de pavage

Les trois problèmes ci-dessous sont-ils faciles ? Difficiles ?

3 / 174
Trois problèmes de pavage

Les trois problèmes ci-dessous sont-ils faciles ? Difficiles ?

Problème 1 : (Tetris)
Etant donné une position de Tetris et la liste des pièces à venir, est-ce qu’il
est possible de vider l’écran ?

3 / 174
Trois problèmes de pavage

Les trois problèmes ci-dessous sont-ils faciles ? Difficiles ?

3 / 174
Trois problèmes de pavage

Les trois problèmes ci-dessous sont-ils faciles ? Difficiles ?

Problème 1 : (Tetris)
Etant donné une position
Problème de Tetris et la listeendes
2 : (Portrait pièces à venir, est-ce qu’il
dominos)
est possible de vider l’écran ?
Etant donné n jeuxProblème
de dominos3 et une image,de
: (Dominos quel est le pavage qui
Wang)
reproduit l’image au mieux ?
Etant donné un ensemble fini de dominos de Wang, est-ce qu’il existe un
pavage du plan avec ces dominos ?

3 / 174
Trois problèmes de pavage

Les trois problèmes ci-dessous sont-ils faciles ? Difficiles ?

Qu’est-ce qu’être facile ? Être difficile ? Être calculable ? Comment le

montrer ?

3 / 174
Calculabilité et complexité des problèmes

Portrait en dominos est “facile”

Tetris est “difficile”

Dominos de Wang est “incalculable”

4 / 174
Calculabilité et complexité des problèmes

Portrait en dominos est “facile” (il existe un algorithme efficace)

Tetris est “difficile”

Dominos de Wang est “incalculable”

4 / 174
Calculabilité et complexité des problèmes

Portrait en dominos est “facile” (il existe un algorithme efficace)

Tetris est “difficile” (il n’existe –probablement– pas d’algorithme efficace)

Dominos de Wang est “incalculable”

4 / 174
Calculabilité et complexité des problèmes

Portrait en dominos est “facile” (il existe un algorithme efficace)

Tetris est “difficile” (il n’existe –probablement– pas d’algorithme efficace)

Dominos de Wang est “incalculable” (il n’existe pas d’algorithme)

4 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Un ordinateur plus rapide : une instruction par temps de Planck (5.39 × 10−44 s)

donnée processeur 3 GHz processeur de Planck

10 villes 1/100s
15 villes 1 heure
19 villes 1 an
27 villes 8 × âge de l’univers

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

Un ordinateur plus rapide : une instruction par temps de Planck (5.39 × 10−44 s)

donnée processeur 3 GHz processeur de Planck

10 villes 1/100s
15 villes 1 heure
19 villes 1 an
27 villes 8 × âge de l’univers
35 villes 5e+23 × âge de l’univ. 5/1000s

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

Un ordinateur plus rapide : une instruction par temps de Planck (5.39 × 10−44 s)

donnée processeur 3 GHz processeur de Planck

10 villes 1/100s
15 villes 1 heure
19 villes 1 an
27 villes 8 × âge de l’univers
35 villes 5e+23 × âge de l’univ. 5/1000s
40 villes 4e+31 × âge de l’univ. 12 heures

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

Un ordinateur plus rapide : une instruction par temps de Planck (5.39 × 10−44 s)

donnée processeur 3 GHz processeur de Planck

10 villes 1/100s
15 villes 1 heure
19 villes 1 an
27 villes 8 × âge de l’univers
35 villes 5e+23 × âge de l’univ. 5/1000s
40 villes 4e+31 × âge de l’univ. 12 heures
50 villes 1, 5e+48 × âge de l’univ. 4000 × âge de l’univers

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

Un ordinateur plus rapide : une instruction par temps de Planck (5.39 × 10−44 s)
Un ordinateur plus parallèle : remplissons l’univers de processeurs d’un mm3
donnée processeur 3 GHz processeur de Planck massivement parallèle
10 villes 1/100s
15 villes 1 heure
19 villes 1 an
27 villes 8 × âge de l’univers
35 villes 5e+23 × âge de l’univ. 5/1000s
40 villes 4e+31 × âge de l’univ. 12 heures
50 villes 1, 5e+48 × âge de l’univ. 4000 × âge de l’univers temps de planck
95 villes 5e+131 × âge de l’univ. 1, 3e+87 × âge de l’univ. 3 × âge de l’univers
5 / 174
Vaincre la Combinatoire : Algo. ou Matériel ?

Problème du Voyageur de Commerce

donnée : ensemble de villes
question : quel est le plus court chemin passant une fois par chaque ville ?

Méthode “Brute-force” : trois instructions par nano seconde

Un ordinateur plus rapide : une instruction par temps de Planck (5.39 × 10−44 s)
Un ordinateur plus parallèle : remplissons l’univers de processeurs d’un mm3
donnée processeur 3 GHz processeur de Planck massivement parallèle
10 villes 1/100s
15 villes 1 heure L’algorithme “Concorde” résout le
19 villes 1 an
27 villes 8 × âge de problème
l’univers du voyageur de commerce pour
des dizaines de5/1000s
35 villes 5e+23 × âge de l’univ. milliers de villes!
40 villes 4e+31 × âge de l’univ. 12 heures
50 villes 1, 5e+48 × âge de l’univ. 4000 × âge de l’univers temps de planck
95 villes 5e+131 × âge de l’univ. 1, 3e+87 × âge de l’univ. 3 × âge de l’univers
5 / 174
Complexité des algorithmes

Savoir développer des algorithmes efficaces

Savoir analyser l’efficacité d’un algorithme

Comprendre la notion de complexité d’un problème

6 / 174
Plan

1 Introduction à la Complexité des Algorithmes

2 Analyse Asymptotique

3 Algorithmes Récursifs

4 Programmation Dynamique

5 Algorithmes gloutons

6 Représentation des Données

7 Classes de Complexité

8 Les Classes NP et coNP

7 / 174
Informations Pratiques

Nos coordonnées :
I Emmanuel Hebrard Mohamed Siala
I Mail : [email protected] [email protected]
I Page du cours : http://homepages.laas.fr/ehebrard/teaching.html
I Volume (prévu) :
F CM : 8 séance d’1h15
F TD : 9 séance d’1h15 (3 groupes : Marie-José Huguet, Mohamed Siala)

Évaluation :
I 1 examen à la fin du cours
F Tous les documents autorisés

8 / 174
Supports de cours

Transparents sur la page du cours (ils seront

9 / 174
Supports de cours

Transparents sur la page du cours (ils seront

distribués !)
Support de cours d’Olivier Bournez pour l’Ecole
Polytechnique (lien sur la page du cours)
“Introduction to Algorithms”
Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest and Clifford Stein
MIT Press.
“Computational Complexity”
Christos H. Papadimitriou
Addison-Wesley.

9 / 174
Supports de cours

Transparents sur la page du cours (ils seront

9 / 174
Introduction à la Complexité
des Algorithmes

Introduction à la Complexité des Algorithmes 10 / 174

Problème & Donnée

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

Une question Q qui associe une donnée x à une solution Q(x)
1 1
 
I “Quel est le plus court chemin de x1 vers x2 par le réseau R ?”  2 4 
3 9
 
I “Quel est la valeur du carré de x ?”
 
4 16
 
 
 5 25 
Q est une relation, pas toujours une fonction : plus court(s) chemin(s) ... ...

On peut se restreindre aux fonctions

Introduction à la Complexité des Algorithmes 11 / 174

Problème & Donnée

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

On peut se restreindre aux fonctions

Problème : “Étant donné un ensemble de villes, quel est le plus court chemin passant
une fois par chaque ville ?”

Introduction à la Complexité des Algorithmes 11 / 174

Problème & Donnée

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

On peut se restreindre aux fonctions

Problème : “Étant donné un ensemble de villes, quel est le plus court chemin passant
une fois par chaque ville ?”

Instance : “Les préfectures d’Occitanie”

Introduction à la Complexité des Algorithmes 11 / 174

Problème & Donnée

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

On peut se restreindre aux fonctions

Problème : “Étant donné un ensemble de villes, quel est le plus court chemin passant
une fois par chaque ville ?”

Instance : “Les préfectures d’Occitanie”

Solution : “Auch → Montauban → Cahors → Rodez → Mende → Nimes →

Montpellier → Albi → Toulouse → Carcassonne → Perpignan → Foix → Tarbes”

Introduction à la Complexité des Algorithmes 11 / 174

Algorithme

Un algorithme est une méthode pour calculer la solution Q(x) d’un problème, pour
toute valeur de la donnée x

Introduction à la Complexité des Algorithmes 12 / 174

Algorithme

Un algorithme est une méthode pour calculer la solution Q(x) d’un problème, pour
toute valeur de la donnée x

Algorithme pour le problème Q

Composée d’instructions primitives : exécutable par une machine
Déterministe : une seule exécution possible pour chaque donnée
Correct : termine et retourne la bonne solution Q(x) pour toute valeur de la donnée x

Introduction à la Complexité des Algorithmes 12 / 174

Algorithme

Un algorithme est une méthode pour calculer la solution Q(x) d’un problème, pour
toute valeur de la donnée x

Algorithme pour le problème Q

Qu’est-ce qu’une “instruction primitive” ?

Pas de définition formelle dans ce cours : langages de programmations classiques
(boucles, conditions, assignements, opérations arithmétiques, etc.)

Introduction à la Complexité des Algorithmes 12 / 174

Preuve de correction

Pour prouver qu’un algorithme est correct (terminaison + résultat attendu) on va

souvent utiliser la notion d’invariant de boucle

Introduction à la Complexité des Algorithmes 13 / 174

Preuve de correction

Pour prouver qu’un algorithme est correct (terminaison + résultat attendu) on va

souvent utiliser la notion d’invariant de boucle

Invariant de boucle
Initialisation : L’invariant est vrai avant la première itération de la boucle.
Conservation : Si l’invariant est vrai avant une itération de la boucle, il le reste avant
l’itération suivante a .
Terminaison : Une fois la boucle terminée, l’invariant implique que la solution est
correcte.
a. Avant une itération veut dire avant de faire le test de la boucle

Introduction à la Complexité des Algorithmes 13 / 174

Preuve de correction

Pour prouver qu’un algorithme est correct (terminaison + résultat attendu) on va

souvent utiliser la notion d’invariant de boucle

7 retourner L;

Introduction à la Complexité des Algorithmes 14 / 174

Exemple : TriSélection

L’algorithme suivant trie un tableua L de n éléments.

6 échanger L[i] et L[m];

7 retourner L;

Introduction à la Complexité des Algorithmes 14 / 174

Exemple : TriSélection

L’algorithme suivant trie un tableua L de n éléments.

6 échanger L[i] et L[m];

7 retourner L;

Introduction à la Complexité des Algorithmes 14 / 174

Exemple : TriSélection

L’algorithme suivant trie un tableua L de n éléments.

6 échanger L[i] et L[m]; i =5 0 9 17 24 29 30

7 retourner L;

Introduction à la Complexité des Algorithmes 14 / 174

Exemple : Prouver que TriSélection est correct

TriSélection termine ?

Introduction à la Complexité des Algorithmes 15 / 174

Exemple : Prouver que TriSélection est correct

TriSélection termine ? Oui car :

I En dehors de la boucle principale, il y a un nombre fini d’instructions (0)

I 2ème boucle : n est constant, j est strictement croissant et la boucle se termine pour j > n

I 1ère boucle : n est constant, i est strictement croissant, la boucle se termine pour i > n,
et la 2ème boucle termine

Introduction à la Complexité des Algorithmes 15 / 174

Exemple : Prouver que TriSélection est correct

TriSélection termine ? Oui car :

I En dehors de la boucle principale, il y a un nombre fini d’instructions (0)

I 2ème boucle : n est constant, j est strictement croissant et la boucle se termine pour j > n

I 1ère boucle : n est constant, i est strictement croissant, la boucle se termine pour i > n,
et la 2ème boucle termine

TriSélection retourne un résultat correct ?

Introduction à la Complexité des Algorithmes 15 / 174

Exemple : Prouver que TriSélection est correct

TriSélection termine ? Oui car :

I En dehors de la boucle principale, il y a un nombre fini d’instructions (0)

I 2ème boucle : n est constant, j est strictement croissant et la boucle se termine pour j > n

I 1ère boucle : n est constant, i est strictement croissant, la boucle se termine pour i > n,
et la 2ème boucle termine

TriSélection retourne un résultat correct ?

Invariant de boucle Inv(i) : Au début de la ième itération de la 1ère boucle “pour”,
(a) tri é(i) : Les i − 1 premiers éléments sont triés
(b) mins(i) : Les i − 1 premiers éléments sont les plus petits

Introduction à la Complexité des Algorithmes 15 / 174

Invariants pour TriSélection

L’algorithme suivant trie un tableau T de n éléments.

Algorithme : TriSélection
Données : tableau L de n éléments
comparables
Résultat : le tableau trié
1 pour i allant de 1 à n faire
2 m ← i;
3 pour j allant de i + 1 à n faire
4 si L[j] < L[m] alors
5 m ← j;

6 échanger L[i] et L[m];

7 retourner L;

Introduction à la Complexité des Algorithmes 16 / 174

Invariants pour TriSélection

L’algorithme suivant trie un tableau T de n éléments.

6 échanger L[i] et L[m];

7 retourner L;

Introduction à la Complexité des Algorithmes 16 / 174

Invariants pour TriSélection

L’algorithme suivant trie un tableau T de n éléments.

Invariants :
Algorithme : TriSélection
Au début de l’itération i :
Données : tableau L de n éléments
(a) i − 1 1ers éléments triés
comparables
Résultat : le tableau trié (b) i − 1 1ers éléments minimums
1 pour i allant de 1 à n faire
2 m ← i; i =1 29 30 17 9 0 24
3 pour j allant de i + 1 à n faire
4 si L[j] < L[m] alors i =2 0 30 17 9 29 24
|{z}
5 m ← j; trié

6 échanger L[i] et L[m];

7 retourner L;

Introduction à la Complexité des Algorithmes 16 / 174

Invariants pour TriSélection

L’algorithme suivant trie un tableau T de n éléments.

7 retourner L;

Introduction à la Complexité des Algorithmes 16 / 174

Invariants pour TriSélection

L’algorithme suivant trie un tableau T de n éléments.

Introduction à la Complexité des Algorithmes 16 / 174

Invariants pour TriSélection

L’algorithme suivant trie un tableau T de n éléments.

Introduction à la Complexité des Algorithmes 16 / 174

Démonstration de TriSélection par invariant
Au début de la ième itération de la 1ère boucle “pour”, 2 invariants :
(a) tri é(i) : Les i − 1 premiers éléments sont triés
(b) mins(i) : Les i − 1 premiers éléments sont les plus petits

Preuve
Initialisation : tri é(i) et mins(i) sont vrais lors de la première itération de la boucle
car pour i = 1 la liste des i − 1 premiers éléments est vide
Conservation : Supposons que les invariants soient vrais à l’itération i. On montre
qu’ils sont vrais à l’itération i + 1 :
I Les i − 1 premiers éléments du tableau L ne changent pas (le seul changement est à la
ligne 6 et m ≥ i). Donc tri é(i) et mins(i) impliquent tri é(i + 1).
I A la ligne 6, L[m] est le plus petit élément parmi L[i], . . . , L[n] a , et il et échangé avec L[i].
Donc mins(i) implique mins(i + 1).

Terminaison : La fin de la boucle correspond au début d’une itération i = n + 1, Mais

tri é(n + 1) implique que L est totalement trié et donc l’algorithme est correct.

a. Il faudrait faire une autre preuve par invariant pour montrer ça ! !

Introduction à la Complexité des Algorithmes 17 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :

Introduction à la Complexité des Algorithmes 18 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :
Évaluer la complexité d’un algorithme ;

Introduction à la Complexité des Algorithmes 18 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :
Évaluer la complexité d’un algorithme ;
Comparer deux algorithmes entre eux ;

Introduction à la Complexité des Algorithmes 18 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :
Évaluer la complexité d’un algorithme ;
Comparer deux algorithmes entre eux ;

XKCD https://xkcd.com/

Introduction à la Complexité des Algorithmes 18 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :
Évaluer la complexité d’un algorithme ;
Comparer deux algorithmes entre eux ;

XKCD https://xkcd.com/

Qu’est ce qu’un algorithme efficace ?

Critère : utilisation d’une ressource

Introduction à la Complexité des Algorithmes 18 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :
Évaluer la complexité d’un algorithme ;
Comparer deux algorithmes entre eux ;

XKCD https://xkcd.com/

Qu’est ce qu’un algorithme efficace ?

Critère : utilisation d’une ressource, e.g., le temps (d’exécution) ou l’espace (mémoire)

Introduction à la Complexité des Algorithmes 18 / 174

Complexité Algorithmique : pourquoi ?
Pour développer des algorithmes efficaces, il faut pouvoir :
Évaluer la complexité d’un algorithme ;
Comparer deux algorithmes entre eux ;

XKCD https://xkcd.com/

Qu’est ce qu’un algorithme efficace ?

Critère : utilisation d’une ressource, e.g., le temps (d’exécution) ou l’espace (mémoire)

Introduction à la Complexité des Algorithmes 18 / 174

Le temps d’exécution

Le temps d’exécution
Le temps d’exécution est la durée (en secondes, minutes, etc.) nécessaire
au programme pour s’éxecuter.

Introduction à la Complexité des Algorithmes 19 / 174

Le temps d’exécution

Le temps d’exécution
Le temps d’exécution est la durée (en secondes, minutes, etc.) nécessaire
au programme pour s’éxecuter.

de la machine ;
du système d’exploitation ;
du langage ;
de la donnée ;

On veut une méthode indépendante de l’environnement.

Introduction à la Complexité des Algorithmes 19 / 174

Nombre d’opérations élémentaires (I)

Introduction à la Complexité des Algorithmes 20 / 174

Nombre d’opérations élémentaires (I)

Opération élémentaire
Une opération élementaire est une opération qui prend un temps constant
Même temps d’exécution quelque soit la donnée

Introduction à la Complexité des Algorithmes 20 / 174

Nombre d’opérations élémentaires (I)

Opération élémentaire
Une opération élementaire est une opération qui prend un temps constant
Même temps d’exécution quelque soit la donnée

Exemples d’opérations en temps constant

Instructions assembleur
Opérations arithmétiques (+, ×, −), affectation, comparaisons

Introduction à la Complexité des Algorithmes 20 / 174

L’algorithme suivant calcule n! = n × (n − 1) × (n − 2) × · · · × 2 × 1 (avec 0! = 1).

Introduction à la Complexité des Algorithmes 21 / 174

Exemple

L’algorithme suivant calcule n! = n × (n − 1) × (n − 2) × · · · × 2 × 1 (avec 0! = 1).

Nombre d’opérations élémentaires (II)

Le nombre d’opérations dépend en général de la donnée du problème ;

(a) trier 10 entiers est plus facile que trier 1000000 entiers ?

Introduction à la Complexité des Algorithmes 23 / 174

Nombre d’opérations élémentaires (II)

Le nombre d’opérations dépend en général de la donnée du problème ;

(a) trier 10 entiers est plus facile que trier 1000000 entiers ?
(b) trier une liste très désordonnée est plus difficile ?

Introduction à la Complexité des Algorithmes 23 / 174

Nombre d’opérations élémentaires (II)

Le nombre d’opérations dépend en général de la donnée du problème ;

(a) trier 10 entiers est plus facile que trier 1000000 entiers ?
(b) trier une liste très désordonnée est plus difficile ?

Le nombre d’opérations est calculé en fonction de la donnée, mais comment tenir

compte de toutes les valeurs possibles ?

I Plusieurs types de complexités → pire/meilleur cas ou en moyenne.

Introduction à la Complexité des Algorithmes 23 / 174

Nombre d’opérations élémentaires (II)

Le nombre d’opérations dépend en général de la donnée du problème ;

(a) trier 10 entiers est plus facile que trier 1000000 entiers ?
(b) trier une liste très désordonnée est plus difficile ?

Le nombre d’opérations est calculé en fonction de la donnée, mais comment tenir

compte de toutes les valeurs possibles ?

I Plusieurs types de complexités → pire/meilleur cas ou en moyenne.

Quel paramètre choisir ? Est-il possible de comparer des algorithmes pour des
problèmes distincts ?
I On calcule la complexité en fonction de la taille de la donnée : |x| est le nombre de
bits de la représentation en mémoire de la donnée x

Introduction à la Complexité des Algorithmes 23 / 174

Nombre d’opérations élémentaires (II)

Le nombre d’opérations dépend en général de la donnée du problème ;

(a) trier 10 entiers est plus facile que trier 1000000 entiers ?
(b) trier une liste très désordonnée est plus difficile ?

Le nombre d’opérations est calculé en fonction de la donnée, mais comment tenir

compte de toutes les valeurs possibles ?

I Plusieurs types de complexités → pire/meilleur cas ou en moyenne.

Comment connait-on la taille |x| de la donnée x ? (cf. “Représentation des Données”)

Introduction à la Complexité des Algorithmes 23 / 174

Complexité en fonction de la taille de la donnée
Soit CoûtA (x) la complexité de l’algorithme A sur la donnée x de taille |x|.

Introduction à la Complexité des Algorithmes 24 / 174

Complexité en fonction de la taille de la donnée
Soit CoûtA (x) la complexité de l’algorithme A sur la donnée x de taille |x|.
Complexité dans le meilleur des cas

InfA (|x|) = min{CoûtA (x) | x de taille |x|}

Introduction à la Complexité des Algorithmes 24 / 174

Complexité en fonction de la taille de la donnée
Soit CoûtA (x) la complexité de l’algorithme A sur la donnée x de taille |x|.
Complexité dans le meilleur des cas

InfA (|x|) = min{CoûtA (x) | x de taille |x|}

Complexité dans le pire des cas

SupA (|x|) = max{CoûtA (x) | x de taille |x|}

Introduction à la Complexité des Algorithmes 24 / 174

Complexité en fonction de la taille de la donnée
Soit CoûtA (x) la complexité de l’algorithme A sur la donnée x de taille |x|.
Complexité dans le meilleur des cas

InfA (|x|) = min{CoûtA (x) | x de taille |x|}

Complexité dans le pire des cas

SupA (|x|) = max{CoûtA (x) | x de taille |x|}

Complexité en moyenne
Besoin d’une probabilité P() pour toutes les données de tailles n
X
MoyA (|x|) = P(x) · CoûtA (x)
x de taille |x|

Introduction à la Complexité des Algorithmes 24 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt
Données : un entier e et un tableau L
contenant e
Résultat : l’indice i t.q. L[i] = e
i ←0;
tant que L[i] 6= e faire
i ← i + 1;
retourner i;

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

de la donnée L :
Algorithme : RechercheElmt
Données : un entier e et un tableau L
contenant e
Résultat : l’indice i t.q. L[i] = e
i ←0;
tant que L[i] 6= e faire
i ← i + 1;
retourner i;

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

de la donnée L :
Algorithme : RechercheElmt e est dans la case 1 → 1 comp.
Données : un entier e et un tableau L
contenant e
Résultat : l’indice i t.q. L[i] = e
i ←0;
tant que L[i] 6= e faire
i ← i + 1;
retourner i;

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

de la donnée L :
Algorithme : RechercheElmt e est dans la case 1 → 1 comp.
Données : un entier e et un tableau L e est dans la case j → j comp.
contenant e
Résultat : l’indice i t.q. L[i] = e
i ←0;
tant que L[i] 6= e faire
i ← i + 1;
retourner i;

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

de la donnée L :
Algorithme : RechercheElmt e est dans la case 1 → 1 comp.
Données : un entier e et un tableau L e est dans la case j → j comp.
contenant e e est dans la case n → n comp.
Résultat : l’indice i t.q. L[i] = e (n = |L| : taille de L)
i ←0;
tant que L[i] 6= e faire
i ← i + 1;
retourner i;

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

Introduction à la Complexité des Algorithmes 25 / 174

Exemple (Recherche dans un tableau)

L’algo. suivant recherche l’élément e dans un tableau.

Le nombre de comparaisons dépend

Introduction à la Complexité des Algorithmes 25 / 174

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt Hyp. :

n+1
moyenne : 2

Introduction à la Complexité des Algorithmes 26 / 174

Complexité en moyenne (Recherche)

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt Hyp. :

Introduction à la Complexité des Algorithmes 26 / 174

Complexité en moyenne (Recherche)

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt Hyp. :

Introduction à la Complexité des Algorithmes 26 / 174

Complexité en moyenne (Recherche)

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt Hyp. :

Introduction à la Complexité des Algorithmes 26 / 174

Complexité en moyenne (Recherche)

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt Hyp. :

Introduction à la Complexité des Algorithmes 26 / 174

Complexité en moyenne (Recherche)

L’algo. suivant recherche l’élément e dans un tableau.

Algorithme : RechercheElmt Hyp. :

Introduction à la Complexité des Algorithmes 26 / 174

Complexité en moyenne (TriSélection)

InfTriSélection (n) = n(n + 4), SupTriSélection (n) = n(2n + 5)

Introduction à la Complexité des Algorithmes 27 / 174

Complexité en moyenne (TriSélection)

InfTriSélection (n) = n(n + 4), SupTriSélection (n) = n(2n + 5)

Le temps de calcul T (n) de TriSélection pour n élément est tel que :

c1 · (n2 + 4n) ≤ T (n) ≤ c2 · (2n2 + 5n)

Introduction à la Complexité des Algorithmes 27 / 174

Complexité en moyenne (TriSélection)

InfTriSélection (n) = n(n + 4), SupTriSélection (n) = n(2n + 5)

Le temps de calcul T (n) de TriSélection pour n élément est tel que :

c1 · (n2 + 4n) ≤ T (n) ≤ c2 · (2n2 + 5n)

Les valeurs des constantes c1 et c2 dépendent de :

I Le coût exact des opérations (comparaisons, affectations, etc.)
I Le matériel (processeur, RAM, etc.)
I Le logiciel (langage, compilateur, système d’exploitation, etc.)

Introduction à la Complexité des Algorithmes 27 / 174

Complexité en moyenne (TriSélection)

InfTriSélection (n) = n(n + 4), SupTriSélection (n) = n(2n + 5)

Le temps de calcul T (n) de TriSélection pour n élément est tel que :

c1 · (n2 + 4n) ≤ T (n) ≤ c2 · (2n2 + 5n)

Les valeurs des constantes c1 et c2 dépendent de :

I Le coût exact des opérations (comparaisons, affectations, etc.)
I Le matériel (processeur, RAM, etc.)
I Le logiciel (langage, compilateur, système d’exploitation, etc.)

Impossible à quantifier !

Introduction à la Complexité des Algorithmes 27 / 174

Complexité en moyenne (TriSélection)

InfTriSélection (n) = n(n + 4), SupTriSélection (n) = n(2n + 5)

Le temps de calcul T (n) de TriSélection pour n élément est tel que :

c1 · (n2 + 4n) ≤ T (n) ≤ c2 · (2n2 + 5n)

Les valeurs des constantes c1 et c2 dépendent de :

I Le coût exact des opérations (comparaisons, affectations, etc.)
I Le matériel (processeur, RAM, etc.)
I Le logiciel (langage, compilateur, système d’exploitation, etc.)

Impossible à quantifier !

Les variations de c1 et c2 sont plus importantes que le facteur (inférieur à 2) entre

n2 + 4n et 2n2 + 5n

Introduction à la Complexité des Algorithmes 27 / 174

Complexité en moyenne (TriSélection)

InfTriSélection (n) = n(n + 4), SupTriSélection (n) = n(2n + 5)

Le temps de calcul T (n) de TriSélection pour n élément est tel que :

c1 · (n2 + 4n) ≤ T (n) ≤ c2 · (2n2 + 5n)

Les valeurs des constantes c1 et c2 dépendent de :

I Le coût exact des opérations (comparaisons, affectations, etc.)
I Le matériel (processeur, RAM, etc.)
I Le logiciel (langage, compilateur, système d’exploitation, etc.)

Impossible à quantifier !

Les variations de c1 et c2 sont plus importantes que le facteur (inférieur à 2) entre

n2 + 4n et 2n2 + 5n

InfTriSélection (n) ' MoyTriSélection (n) ' SupTriSélection (n) ' cn2

Introduction à la Complexité des Algorithmes 27 / 174

Exemple : TriRapide

Algorithme : TriRapide
Données : tableau L d’elts comparables, entiers s, e
Résultat : le tableau trié entre les indices s et e
1 Procedure TriRapide(L, s, e)
2 si s < e alors
3 p ← Partition(L, s, e);
4 TriRapide(L, s, p − 1);
5 TriRapide(L, p + 1, e); 29 30 17 9 0 24
6 Procedure Partition(L, s, e)
7 pivot ← L[e];
8 i ← s;
9 pour j allant de s à e − 1 faire
10 si L[j] < pivot alors
11 échanger L[i] avec L[j];
12 i ← i + 1;

13 échanger L[i] avec L[e];

14 retourner i;

Introduction à la Complexité des Algorithmes 28 / 174

Exemple : TriRapide

échanger L[i] avec L[e];

retourner i;

Introduction à la Complexité des Algorithmes 29 / 174

Complexité de TriRapide

échanger L[i] avec L[e];

retourner i;

Introduction à la Complexité des Algorithmes 29 / 174

Complexité de TriRapide

Algorithme : TriRapide
Procedure TriRapide(L, s, e) Opération caractéristique
si s < e alors
p ← Partition(L, s, e); Ici on compte le nombre de
TriRapide(L, s, p − 1);
TriRapide(L, p + 1, e);
comparaisons, égal au nombre total
d’opérations, à une constante près.
Procedure Partition(L, s, e)
pivot ← L[e];
i ← s;
pour j allant de s à e − 1 faire
si L[j] < pivot alors
échanger L[i] avec L[j]; TriRapide fait un nombre constant (disons c1 )
i ← i + 1; d’opérations pour chaque comparaison
I Au plus un échange et entre 1 et 2
échanger L[i] avec L[e]; incrémentation(s)
retourner i;

Introduction à la Complexité des Algorithmes 29 / 174

Complexité dans le pire des cas (TriRapide)

Complexité en moyenne (TriRapide)

Complexité en moyenne (TriRapide)

Introduction à la Complexité des Algorithmes 32 / 174

Complexité en moyenne (TriRapide)

z1 z2 z3 z4 z5 z6 z7 z8 z9

Soit la liste triée des éléments de T : z1 < z2 < . . . < zn

Introduction à la Complexité des Algorithmes 32 / 174

Complexité en moyenne (TriRapide)

z1 z2 z3 z4 z5 z6 z7 z8 z9

Soit la liste triée des éléments de T : z1 < z2 < . . . < zn

Si on note p(zi , zj ) la probabilité que zi et zj soient comparés, alors l’espérance E du
nombre de comparaisons est donc :
n−1 X
X n
p(zi , zj )
i=1 j=i+1

Introduction à la Complexité des Algorithmes 32 / 174

Complexité en moyenne (TriRapide)

z1 z2 z3 z4 z5 z6 z7 z8 z9

Soit la liste triée des éléments de T : z1 < z2 < . . . < zn

Analyse Asymptotique 35 / 174

Soit deux algorithmes de complexités

I n log n + 5n → 5n va devenir “négligeable” (n >> 1000)
10
I différence entre un algorithme en 10n3 et 9n3 : effacé par une accélération de 9
de la
machine

On aura donc recours à une approximation de ce temps de calcul, représentée par les
notations O, Ω et Θ

Analyse Asymptotique 36 / 174

Ordre de grandeur : motivation

Les calculs à effectuer pour évaluer le temps d’exécution d’un algorithme peuvent
parfois être longs et pénibles ;

De plus, le degré de précision qu’ils requièrent est souvent inutile ;

I n log n + 5n → 5n va devenir “négligeable” (n >> 1000)
10
I différence entre un algorithme en 10n3 et 9n3 : effacé par une accélération de 9
de la
machine

On aura donc recours à une approximation de ce temps de calcul, représentée par les
notations O, Ω et Θ

Hypothèse simplificatrice
On ne s’intéresse qu’aux fonctions asymptotiquement positives
(positives pour tout n ≥ n0 )

Analyse Asymptotique 36 / 174

Notation O : définition

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Prouver que f (n) ∈ O(g (n)) : jeux contre un perfide adversaire ∀

Analyse Asymptotique 38 / 174

Notation O : preuve

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Prouver que f (n) ∈ O(g (n)) : jeux contre un perfide adversaire ∀

Tour du joueur ∃ objectif : f (n) ≤ cg (n) choisit c et n0

Analyse Asymptotique 38 / 174

Notation O : preuve

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Prouver que f (n) ∈ O(g (n)) : jeux contre un perfide adversaire ∀

Tour du joueur ∃ objectif : f (n) ≤ cg (n) choisit c et n0

Tour du joueur ∀ objectif : f (n) > cg (n) choisit n ≥ n0

Analyse Asymptotique 38 / 174

Notation O : preuve

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Prouver que f (n) ∈ O(g (n)) : jeux contre un perfide adversaire ∀

Tour du joueur ∃ objectif : f (n) ≤ cg (n) choisit c et n0

Tour du joueur ∀ objectif : f (n) > cg (n) choisit n ≥ n0

Arbitre détermine le gagnant : f (n) ≤ cg (n)

Analyse Asymptotique 38 / 174

Notation O : exemple

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Jeux : prouver que la fonction f2 (n) = 6n2 + 2n − 8 est en O(n2 ) :

Analyse Asymptotique 39 / 174

Notation O : exemple

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Jeux : prouver que la fonction f2 (n) = 6n2 + 2n − 8 est en O(n2 ) :

Tour du joueur ∃ choisit c = 6 et n0 = 0

Analyse Asymptotique 39 / 174

Notation O : exemple

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Jeux : prouver que la fonction f2 (n) = 6n2 + 2n − 8 est en O(n2 ) :

Tour du joueur ∃ choisit c = 6 et n0 = 0

Tour du joueur ∀ choisit n = 5

Analyse Asymptotique 39 / 174

Notation O : exemple

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R, ∀n ≥ n0 : f (n) ≤ c × g (n)

Jeux : prouver que la fonction f2 (n) = 6n2 + 2n − 8 est en O(n2 ) :

Tour du joueur ∃ choisit c = 6 et n0 = 0

Tour du joueur ∀ choisit n = 5

Arbitre 6 × 52 + 2 × 5 − 8 > 6 × 52

Analyse Asymptotique 39 / 174

O(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R+∗ , ∀n ≥ n0 : f (n) ≤ c × g (n)

c × g (n)
f ∈ O(g )

f 0 ∈ O(g )

n0 n

Exercice : 2n2 est-il en O(n2 ) ? Pareil pour 2n.

Analyse Asymptotique 42 / 174
Notation Ω : définition

Ω(g (n)) est l’ensemble de fonctions f (n) telles que :

∃n0 ∈ N, ∃c ∈ R+∗ , ∀n ≥ n0 : f (n)≥c × g (n)

Notation Θ : définition

Θ(g (n)) est l’ensemble de fonctions f (n) telles que :

∃c1 , c2 ∈ R+∗ , ∃n0 ∈ N, ∀n > n0 , c1 × g (n) ≤ f (n) ≤ c2 × g (n)

Borne supérieure et inférieure : Θ(g (n)) = Ω(g (n)) ∩ O(g (n)) ; f (n)
est en Θ(g (n)) si elle est prise en sandwich entre c1 g (n) et
c2 g (n) ;

Analyse Asymptotique 44 / 174

Focus sur Θ
f (n) est en Θ(g (n)) si :

∃c1 , c2 ∈ R+∗ , ∃n0 ∈ N, ∀n > n0 , c1 × g (n) ≤ f (n) ≤ c2 × g (n)

c2 × g (n)
f ∈ Θ(g )
c1 × g (n)

k n

Exercice : 2n2 est-il en Θ(n2 ) ? Pareil pour 2n.

Analyse Asymptotique 45 / 174
Notation asymptotique d’une fonction

Quelle est la borne asymptotique de f (n) ?

Analyse Asymptotique 46 / 174

Notation asymptotique d’une fonction

Quelle est la borne asymptotique de f (n) ?

Notation asymptotique (de l’expression fermée) d’une fonction

Les mêmes simplifications pour O, Ω et Θ :
on ne retient que les termes dominants
on supprime les constantes multiplicatives

Analyse Asymptotique 46 / 174

Notation asymptotique d’une fonction

Quelle est la borne asymptotique de f (n) ?

Notation asymptotique (de l’expression fermée) d’une fonction

Les mêmes simplifications pour O, Ω et Θ :
on ne retient que les termes dominants
on supprime les constantes multiplicatives

Exemple
Soit g (n) = 4n3 − 5n2 + 2n + 3 ;
1 on ne retient que le terme de plus haut degré : 4n3 (pour n assez grand le terme en
n3 “domine” les autres, en choisissant bien c1 , c2 , on peut avoir c1 n3 ≤ g (n) ≤ c2 n3 )
2 on supprime les constantes multiplicatives : n3 (on peut la choisir !)
et on a donc g (n) ∈ Θ(n3 )

Analyse Asymptotique 46 / 174

Ordre de grandeur : exemples

5n3 + 3n + 7 ∈ O(n3 ) ?

5n3 + 3n + 7 ∈ Θ(n3 ) ?

5n3 + 3n + 7 ∈ O(n4 ) ?

5n3 + 3n + 7 ∈ Θ(n4 ) ?

log n ∈ O(n) ?

log n ∈ Θ(n) ?

Analyse Asymptotique 47 / 174

Relation des principaux ordres de grandeur

2n n2

n log n

n
log n
n

Indépendant de la taille de la donnée : O(1)/Θ(1)

Analyse Asymptotique 48 / 174

Vocabulaire

Un algorithme dont la donnée est de taille |x| = n est dit :

Constant si sa complexité est en O(1)

Logarithmique si sa complexité est en Θ(log n)

Linéaire si sa complexité est en Θ(n)

Quadratique si sa complexité est en Θ(n2 )

Polynomial si sa complexité est en O(nO(1) )

Exponentiel si sa complexité est en Θ(c Θ(n) ) pour une constante c > 1

Analyse Asymptotique 49 / 174

Quelques remarques (à prouver comme exercice)

Analyse Asymptotique 50 / 174

Quelques remarques (à prouver comme exercice)

f ∈ O(g ) ssi g ∈ Ω(f )

f ∈ Θ(g ) ssi g ∈ Θ(f )

Analyse Asymptotique 50 / 174

Quelques remarques (à prouver comme exercice)

f ∈ Θ(g ) ssi g ∈ Θ(f )

f (n)
Si limn→∞ g (n)
= c > 0 (constante) alors f ∈ Θ(g ) (et donc g ∈ Θ(f ))

Si limn→∞ gf (n)
(n)
= 0 alors f ∈ O(g ) et f ∈
/ Ω(g )
f (n)
Si limn→∞ g (n)
= ∞ alors f ∈ Ω(g ) et f ∈
/ O(g )

Règle de l’Hôpital
f et g deux fonctions dérivables t.q. lim f (n) = lim g (n) = ∞, alors :
n→∞ n→∞

f (n) f 0 (n)
lim = lim 0 si cette limite existe.
n→∞ g (n) n→∞ (n)
g

f 0 (respectivement g 0 ) représente la dévirée de f (respectivement g )

Règles de calculs : combinaisons des complexités

Les instructions de base prennent un temps constant, noté O(1) ;

On additionne les complexités d’opérations en séquence :

Θ(f (n)) + Θ(g (n)) = Θ(f (n) + g (n))

Branchements conditionnels : max (analyse dans le pire des cas)

L’ordre de grandeur maximum est égal à la somme des ordres de grandeur :

max(Θ(f (n)), Θ(g (n))) = Θ(f (n)) + Θ(g (n))

Analyse Asymptotique 51 / 174

Règles de calculs : combinaisons des complexités

Les instructions de base prennent un temps constant, noté O(1) ;

On additionne les complexités d’opérations en séquence :

Θ(f (n)) + Θ(g (n)) = Θ(f (n) + g (n))

Branchements conditionnels : max (analyse dans le pire des cas)

L’ordre de grandeur maximum est égal à la somme des ordres de grandeur :

max(Θ(f (n)), Θ(g (n))) = Θ(f (n)) + Θ(g (n))

Calcul de la complexité asymptotique d’un
algorithme

Pour calculer la complexité d’un algorithme :

Analyse Asymptotique 53 / 174

Calcul de la complexité asymptotique d’un
algorithme

Pour calculer la complexité d’un algorithme :

1 on calcule la complexité de chaque “partie” de l’algorithme ;

Analyse Asymptotique 53 / 174

Calcul de la complexité asymptotique d’un
algorithme

Pour calculer la complexité d’un algorithme :

1 on calcule la complexité de chaque “partie” de l’algorithme ;

2 on combine ces complexités conformément aux règles qu’on vient de voir ;

Analyse Asymptotique 53 / 174

Calcul de la complexité asymptotique d’un
algorithme

Pour calculer la complexité d’un algorithme :

1 on calcule la complexité de chaque “partie” de l’algorithme ;

2 on combine ces complexités conformément aux règles qu’on vient de voir ;

3 on simplifie le résultat grâce aux règles de simplifications qu’on a vues ;

F élimination des constantes, et
F conservation du (des) termes dominants

Analyse Asymptotique 53 / 174

Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Algorithme : Factorielle(n)
nombre coût
Données : un entier n
Résultat : un entier valant n!
1 fact, i : entier;
2 début
3 fact ← 2;
4 pour i allant de 3 à n faire
5 fact ← fact ∗ i;
6 retourner fact;

Analyse Asymptotique 54 / 174

Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Algorithme : Factorielle(n)
nombre coût
Données : un entier n
Résultat : un entier valant n!
1 fact, i : entier;
2 début
3 fact ← 2; initialisation : Θ(1)× Θ(1)
4 pour i allant de 3 à n faire
5 fact ← fact ∗ i;
6 retourner fact;

Analyse Asymptotique 54 / 174

Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Analyse Asymptotique 54 / 174

Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Analyse Asymptotique 54 / 174

Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Analyse Asymptotique 54 / 174

Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Nombre total d’opérations :

Θ(1) + Θ(n) ∗ Θ(1) + Θ(n) ∗ Θ(1) + Θ(1) = Θ(n)

Analyse Asymptotique 54 / 174

Exemple : TriSélection

Algorithme : TriSélection nombre coût

Données : tableau L de n éléments comparables
Résultat : le tableau trié
1 pour i allant de 1 à n faire itérations : n× 1 op.
2 m ← i; affectation : n× 1 op.
P n
3 pour j allant de i + 1 à n faire itérations : (n − i − 1)× 1 op.
Pi=1
n
4 si L[j] < L[m] alors comparaison : i=1 (n − i − 1)× 1 op.
5 m ← j; affectation : n×?× 1 op.

6 échanger L[i] et L[m]; échange : n× 3 op.

7 retourner L;

Analyse Asymptotique 55 / 174

Exemple : TriSélection

Algorithme : TriSélection nombre coût

6 échanger L[i] et L[m]; échange : n× 3 op.

7 retourner L;

Séries arithmétiques
n n
X X 1
(n − i − 1) = n2 − n − i = n2 − n − (1 + 2 + 3 + · · · + n) = n2 − n − n(n + 1)
i=1 i=1
2

Analyse Asymptotique 55 / 174

Exemple : TriSélection

Algorithme : TriSélection nombre coût

6 échanger L[i] et L[m]; échange : n× 3 op.

7 retourner L;

Séries arithmétiques
n n
X X 1
(n − i − 1) = n2 − n − i = n2 − n − (1 + 2 + 3 + · · · + n) = n2 − n − n(n + 1)
i=1 i=1
2

Nombre total d’opérations : Θ(n2 ) = Θ(|T |2 )

Analyse Asymptotique 55 / 174
Algorithmes Récursifs

Algorithmes Récursifs 56 / 174

Force brute

Algorithmes Récursifs 57 / 174

Force brute

L’approche “force brute” est une méthode de conception d’algorithmes qui se base
simplement sur une énumération exhaustive de toutes les configurations possibles de
la solution recherchée

Exemple : Un algorithme de tri de type “force brute ” parcourt toutes les

permutations possibles de la liste jusqu’à ce qu’il trouve la permutation ordonnée.

Algorithmes Récursifs 57 / 174

Force brute

L’approche “force brute” est une méthode de conception d’algorithmes qui se base
simplement sur une énumération exhaustive de toutes les configurations possibles de
la solution recherchée

Exemple : Un algorithme de tri de type “force brute ” parcourt toutes les

permutations possibles de la liste jusqu’à ce qu’il trouve la permutation ordonnée.

Cette méthode est souvent inefficace car elle se repose sur l’énumération complète
d’un espace de recherche

Exemple (algorithme de tri de type “force brute”) : le nombre de permutations

possible est n! donc la complexité d’un tel algorithme est Θ(n!)

Algorithmes Récursifs 57 / 174

Diviser pour régner (Divide and conquer)

Algorithmes Récursifs 58 / 174

Diviser pour régner (Divide and conquer)

“Diviser pour régner” est une méthode de conception d’algorithmes qui se base sur
une “conception par décomposition” :

Algorithmes Récursifs 58 / 174

Diviser pour régner (Divide and conquer)

“Diviser pour régner” est une méthode de conception d’algorithmes qui se base sur
une “conception par décomposition” :

I Diviser le problème en sous problèmes

Algorithmes Récursifs 58 / 174

Diviser pour régner (Divide and conquer)

“Diviser pour régner” est une méthode de conception d’algorithmes qui se base sur
une “conception par décomposition” :

I Diviser le problème en sous problèmes

I Résoudre les sous problèmes par des appels récursifs

Algorithmes Récursifs 58 / 174

Diviser pour régner (Divide and conquer)

“Diviser pour régner” est une méthode de conception d’algorithmes qui se base sur
une “conception par décomposition” :

I Diviser le problème en sous problèmes

I Résoudre les sous problèmes par des appels récursifs

I Combiner les résultats des sous problèmes pour résoudre le problème initial

Algorithmes Récursifs 58 / 174

Diviser pour régner (Divide and conquer)

“Diviser pour régner” est une méthode de conception d’algorithmes qui se base sur
une “conception par décomposition” :

I Diviser le problème en sous problèmes

I Résoudre les sous problèmes par des appels récursifs

I Combiner les résultats des sous problèmes pour résoudre le problème initial

Cas idéal : le problème est décomposable en sous-problèmes indépendents

I Dans ce cas, combiner les résultats est trivial

I Parfois, les sous-problèmes sont seulement plus “faiblement” liés, et combiner les résultats
peut-être complexe

Algorithmes Récursifs 58 / 174

Exemple avec un algorithme de tri

Algorithme : TriFusion (L)

Données : une liste L
Résultat : la liste L triée
mil : entier;
si |L| ≤ 1 alors
retourner L;
sinon
|L|+1
mil ← b 2 c;
Ll ← TriFusion(L[:mil]);
Lr ← TriFusion(L[mil:]);
retourner Fusion(Ll , Lr );

Algorithmes Récursifs 59 / 174

Exemple avec un algorithme de tri

Algorithme : Fusion (L1 ,L2 )

Données : deux listes triées L1 et L2
Algorithme : TriFusion (L) Résultat : une liste L triée contenant les éléments
Données : une liste L de L1 et de L2
Résultat : la liste L triée L : liste vide;
mil : entier; i, j, k ← 1;
si |L| ≤ 1 alors tant que k < |L| faire
retourner L; si i > |L1 | ou (j ≤ |L2 | et L1 [i] > L2 [j]) alors
sinon insérer L2 [j] à la fin de L;
|L|+1
mil ← b 2 c; j ← j + 1;
Ll ← TriFusion(L[:mil]); sinon
Lr ← TriFusion(L[mil:]); insérer L1 [i] à la fin de L;
retourner Fusion(Ll , Lr ); i ← i + 1;
k ← k + 1;
retourner L

Algorithmes Récursifs 59 / 174

Tri Fusion

Algorithme : TriFusion (L)

Tri Fusion

Déroulement de l’algorithme avec la liste

h6, 2, 1, 8, 5, 4, 3, 7i :
Algorithme : TriFusion (L)
Données : une liste L I Division : h6, 2, 1, 8i h5, 4, 3, 7i
Résultat : la liste L triée I Division : h6, 2i h1, 8i
mil : entier; I Division : h6i h2i
si |L| ≤ 1 alors I Regroupement : h2, 6i
retourner L;
sinon
|L|+1
mil ← b 2 c;
Ll ← TriFusion(L[:mil]);
Lr ← TriFusion(L[mil:]);
retourner Fusion(Ll , Lr );

Algorithmes Récursifs 60 / 174

Tri Fusion

Déroulement de l’algorithme avec la liste

Algorithmes Récursifs 60 / 174

Tri Fusion

Algorithmes Récursifs 60 / 174

Preuve de correction

Terminaison :

I TriFusion ne s’appelle lui même que 2 fois

I A chaque appel récursif, la taille de la liste |L| est strictement plus petite
I Il n’y a pas d’appel récursif pour |L| ≤ 1 =⇒ nombre total d’appels récursifs est fini

Correction (TriFusion(L) est triée, par récurrence sur |L|) :

Algorithmes Récursifs 61 / 174

Analyse de la complexité d’un algorithme récursif

La structure d’un algorithme récursif AlgoRec(x) est :

si condition d’arrêt alors
retourner solution trivialle;
sinon
retourner Fusion(AlgoRec(p(x,1)),AlgoRec(p(x,2)),. . . ,AlgoRec(p(x,a)));

Algorithmes Récursifs 62 / 174

Analyse de la complexité d’un algorithme récursif

La structure d’un algorithme récursif AlgoRec(x) est :

si condition d’arrêt alors
retourner solution trivialle;
sinon
retourner Fusion(AlgoRec(p(x,1)),AlgoRec(p(x,2)),. . . ,AlgoRec(p(x,a)));

p “coupe” la donnée x (de taille |x| = n) en a morceaux de taille g (n)

Fusion “recolle” les morceaux en h(n)

Algorithmes Récursifs 62 / 174

Analyse de la complexité d’un algorithme récursif

La structure d’un algorithme récursif AlgoRec(x) est :

si condition d’arrêt alors
retourner solution trivialle;
sinon
retourner Fusion(AlgoRec(p(x,1)),AlgoRec(p(x,2)),. . . ,AlgoRec(p(x,a)));

p “coupe” la donnée x (de taille |x| = n) en a morceaux de taille g (n)

Fusion “recolle” les morceaux en h(n)

(
Θ(1) si . . .
Forme récursive de la complexité T (n) =
aT (g (n)) + h(n) sinon

Algorithmes Récursifs 62 / 174

Analyse de la complexité d’un algorithme récursif

La structure d’un algorithme récursif AlgoRec(x) est :

si condition d’arrêt alors
retourner solution trivialle;
sinon
retourner Fusion(AlgoRec(p(x,1)),AlgoRec(p(x,2)),. . . ,AlgoRec(p(x,a)));

p “coupe” la donnée x (de taille |x| = n) en a morceaux de taille g (n)

Fusion “recolle” les morceaux en h(n)

(
Θ(1) si . . .
Forme récursive de la complexité T (n) =
aT (g (n)) + h(n) sinon

On veut trouver une formule de forme close

T (n) ∈ O(f (n))

Algorithmes Récursifs 62 / 174

Exemple : TriFusion

n
TriFusion “coupe” la donnée L (de taille |L| = n) en 2 morceaux de taille 2

Fusion “recolle” les morceaux en Θ(n)

Algorithmes Récursifs 63 / 174

Exemple : TriFusion

n
TriFusion “coupe” la donnée L (de taille |L| = n) en 2 morceaux de taille 2

Fusion “recolle” les morceaux en Θ(n)

Forme récursive de la complexité :

(
Θ(1) si n ≤ 1
T (n) =
T n2 + T n2 + n

sinon

Algorithmes Récursifs 63 / 174

Exemple : TriFusion

n
TriFusion “coupe” la donnée L (de taille |L| = n) en 2 morceaux de taille 2

Fusion “recolle” les morceaux en Θ(n)

Forme récursive de la complexité :

(
Θ(1) si n ≤ 1
T (n) =
2T ( n2 ) + n sinon

Forme fermée de la complexité :

∃c, n0 ∀n > n0 T (n) ≤ cn log n

càd T (n) ∈ O(n log n)

I On va en déduire a posteriori que T (n) ∈ O(f (n))

Algorithmes Récursifs 64 / 174

Méthode par substitution

Il faut avoir une intuition sur la forme de la solution (TriFusion : O(n log n))

n

On veut montrer que T (n) = 2T 2
+ Θ(n) ∈ O(n log n)

On montre par récurrence qu’il existe f (n) t.q. ∀n T (n) ≤ f (n)

I On va en déduire a posteriori que T (n) ∈ O(f (n))

Attention !
L’hypothèse de récurrence est T (n) ≤ f (n), et non T (n) ∈ O(f (n))
L’hypothèse de récurrence “pour tout n ≤ k, T (n) ∈ O(f (n))” ne veut pas dire
grand chose puisque la notation O est définie pour n arbitrairement grand : on
remplace tous les termes en O, Ω, Θ par une fonction élément de l’ensemble

Algorithmes Récursifs 64 / 174

Méthode par substitution (condition aux limites)

n
T (n) = 2T + n ≤ cn log n
2

Il faut montrer que la formule est vraie pour les conditions limites de la récurrence
pour des données de petite taille, i.e. n = 1

Algorithmes Récursifs 65 / 174

Méthode par substitution (condition aux limites)

n
T (n) = 2T + n ≤ cn log n
2

Il faut montrer que la formule est vraie pour les conditions limites de la récurrence
pour des données de petite taille, i.e. n = 1

Problème : c’est faux pour n = 1 car c × 1 × log 1 = 0 < T (1) = 1 ;

Algorithmes Récursifs 65 / 174

Méthode par substitution (condition aux limites)

n
T (n) = 2T + n ≤ cn log n
2

Il faut montrer que la formule est vraie pour les conditions limites de la récurrence
pour des données de petite taille, i.e. n = 1

Problème : c’est faux pour n = 1 car c × 1 × log 1 = 0 < T (1) = 1 ;

Mais on cherche à montrer la complexité pour des données de grande taille : n ≥ n0

et on a le choix pour n0 =⇒ vérifier pour T (2) (et T (3))

Algorithmes Récursifs 65 / 174

Méthode par substitution (condition aux limites)

n
T (n) = 2T + n ≤ cn log n
2

Il faut montrer que la formule est vraie pour les conditions limites de la récurrence
pour des données de petite taille, i.e. n = 1

Problème : c’est faux pour n = 1 car c × 1 × log 1 = 0 < T (1) = 1 ;

Mais on cherche à montrer la complexité pour des données de grande taille : n ≥ n0

et on a le choix pour n0 =⇒ vérifier pour T (2) (et T (3))

On peut aussi borner par f (n) = cn log n + b puisque cn log n + b ∈ O(n log n)
I Ou même f (n) = cn log n + an + b

Algorithmes Récursifs 65 / 174

Méthode par substitution (condition aux limites)
n
T (n) = 2T + n ≤ cn log n
2

On vérifie que la formule tient pour T (2) et T (3)

Algorithmes Récursifs 66 / 174

Méthode par substitution (condition aux limites)
n
T (n) = 2T + n ≤ cn log n
2

On vérifie que la formule tient pour T (2) et T (3)

T (2) = 2T (2/2) + 2

Algorithmes Récursifs 66 / 174

Méthode par substitution (condition aux limites)
n
T (n) = 2T + n ≤ cn log n
2

On vérifie que la formule tient pour T (2) et T (3)

T (2) = 2T (2/2) + 2

On vérifie que c’est aussi le cas pour x = n en substituant la formule pour T (x) dans
son expression récursive :

T (n) = 2T 2n + n

≤ 2c 2n log( 2n ) + n
≤ cn log 2n + n
= cn log n − cn log 2 + n
= cn log n − cn + n
≤ cn log n (pour c ≥ 1)

On a pris c ≥ 2, pour satisfaire les conditions initiales T (2) et T (3)

Algorithmes Récursifs 67 / 174

Diviser pour régner : TriFusion

Exemple
Algorithme : TriFusion (L)
Données : une list L
Résultat : la liste L triée (
si |L| ≤ 1 alors Θ(1) si n = 1
retourner L; T (n) = n
1
sinon 2T 2 + Θ(n ) si n > 1
|L|+1
mil ← b 2 c;
Ll ← TriFusion(L[:mil]);
Lr ← TriFusion(L[mil:]);
retourner Fusion(Ll , Lr );

Algorithmes Récursifs 68 / 174

Diviser pour régner : TriFusion

Exemple
Algorithme : TriFusion (L)
Données : une list L
Résultat : la liste L triée (
si |L| ≤ 1 alors Θ(1) si n = 1
retourner L; T (n) = n
d
sinon aT b + Θ(n ) si n > 1
|L|+1
mil ← b 2 c;
Ll ← TriFusion(L[:mil]); Trifusion : a = 2, b = 2, d = 1
Lr ← TriFusion(L[mil:]);
retourner Fusion(Ll , Lr );

L’algorithme découpe la donnée en a sous-problèmes de taille bn , les résout

récursivement et rassemble les réponses en Θ(nd )

Algorithmes Récursifs 68 / 174

Diviser pour régner : RechBin

Exemple
Algorithme : RechBin (L)
Données : tableau trié L contenant e
Résultat
j :kla position de e dans L (
|L|
m← 2 ; Θ(1) si n = 1
si L[m] = e alors
T (n) = n
d
retourner m
aT b + Θ(n ) si n > 1
sinon si L[m] < e alors
retourner RechBin(L[m+1 :])
sinon
retourner RechBin(L[ :m])

L’algorithme découpe la donnée en a sous-problèmes de taille bn , les résout

récursivement et rassemble les réponses en Θ(nd )

Algorithmes Récursifs 69 / 174

2 Si d < logb a, T (n) = Θ(nlogb a ) complexité dominée par le coût du sous-problème
3 Si d = logb a, T (n) = Θ(nd log n) pas de domination

Tri fusion : (
Θ(1) si n = 1
T (n) =
2T (n/2) + Θ(n) si n > 1

a = 2, b = 2, d = 1, log2 2 = 1 = d

On est donc dans le 3ème cas et la complexité en Θ(n log n)

Algorithmes Récursifs 70 / 174

Théorème maître (général) - version simplifiée

On ne considère que les récurrences T (n) = aT ( bn ) + Θ(nd ) (ou O(nd ))

avec a ≥ 1, b > 1, d ≥ 0

2 Si d < logb a, T (n) = Θ(nlogb a ) complexité dominée par le coût du sous-problème
3 Si d = logb a, T (n) = Θ(nd log n) pas de domination

Recherche binaire : (
Θ(1) si n = 1
T (n) =
T ( 2n ) + Θ(1) si n > 1

a = 1, b = 2, d = 0, log2 1 = 0 = d

On est donc dans le cas 3 et la complexité en Θ(log n)

Nous allons résoudre ce problème avec 3 approches différentes :

1 Approche force brute

2 Algorithme récursif

3 Programmation dynamique

Programmation Dynamique 73 / 174

Le problème de multiplication de matrices

Programmation Dynamique 74 / 174

Le problème de multiplication de matrices

c11 c21 c31 c41

l1,1 l1,2 l1,3
× c12 c22 c32 c42
l2,1 l2,2 l2,3
c13 c23 c33 c43
=
. . . .
. . l2,1 c31 + l2,2 c32 + l2,3 c33 .

Programmation Dynamique 74 / 174

Le problème de multiplication de matrices

c11 c21 c31 c41

l1,1 l1,2 l1,3
× c12 c22 c32 c42
l2,1 l2,2 l2,3
c13 c23 c33 c43
=
. . . .
. . l2,1 c31 + l2,2 c32 + l2,3 c33 .
Cas général : A1 de taille t0 × t1 et A2 de taille t1 × t2 , il y a t0 × t1 × t2
multiplications à faire.

Programmation Dynamique 74 / 174

Associativité de la multiplication

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3
Il y a deux façons (la multiplication est associative) :

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3
Il y a deux façons (la multiplication est associative) :
1 A1 ∗ A2 ∗ A3 = ((A1 ∗ A2 ) ∗ A3 )
2 A1 ∗ A2 ∗ A3 = (A1 ∗ (A2 ∗ A3 ))

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3
Il y a deux façons (la multiplication est associative) :
1 A1 ∗ A2 ∗ A3 = ((A1 ∗ A2 ) ∗ A3 )
2 A1 ∗ A2 ∗ A3 = (A1 ∗ (A2 ∗ A3 ))

Nombre de multiplications nécessaires :

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3
Il y a deux façons (la multiplication est associative) :
1 A1 ∗ A2 ∗ A3 = ((A1 ∗ A2 ) ∗ A3 )
2 A1 ∗ A2 ∗ A3 = (A1 ∗ (A2 ∗ A3 ))

Nombre de multiplications nécessaires :

1 ((A1 ∗ A2 ) ∗ A3 ) :
1 10 ∗ 4 ∗ 100 = 4000 multiplications pour calculer M = A1 ∗ A2 de dimension 10 × 100
2 10 ∗ 100 ∗ 25 = 25000 multiplications pour calculer M ∗ A3
3 total : 29000 multiplications

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3
Il y a deux façons (la multiplication est associative) :
1 A1 ∗ A2 ∗ A3 = ((A1 ∗ A2 ) ∗ A3 )
2 A1 ∗ A2 ∗ A3 = (A1 ∗ (A2 ∗ A3 ))

Nombre de multiplications nécessaires :

2 (A1 ∗ (A2 ∗ A3 ))
1 4 ∗ 100 ∗ 25 = 10000 multiplications pour calculer N = A2 ∗ A3 de dimension 4 × 25
2 10 ∗ 4 ∗ 25 = 1000 multiplications pour calculer A1 ∗ N
3 total : 11000 multiplications

Programmation Dynamique 75 / 174

Associativité de la multiplication

3 matrices A1 , A2 , A3 de dimensions (10 × 4), (4 × 100), (100 × 25), respectivement.

On veut calculer A1 ∗ A2 ∗ A3
Il y a deux façons (la multiplication est associative) :
1 A1 ∗ A2 ∗ A3 = ((A1 ∗ A2 ) ∗ A3 )
2 A1 ∗ A2 ∗ A3 = (A1 ∗ (A2 ∗ A3 ))

Nombre de multiplications nécessaires :

Choisir (A1 ∗ (A2 ∗ A3 )) ! !

Programmation Dynamique 75 / 174

Problème de multiplication de matrices

Soit A1 , A2 , . . . An n matrices

Ai de taille ti−1 ∗ ti

On veut trouver un parenthésage de A1 × A2 × . . . An qui minimise le nombre de

multiplications pour calculer le produit A1 × A2 × . . . An

Programmation Dynamique 76 / 174

Force brute

Énumérer tous les partenthésages possibles

Calculer le coût de chaque parenthésage

Choisir la solution avec la valeur mimimale

Programmation Dynamique 77 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités
Pour 4 matrices

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités
Pour 4 matrices → 5 possibilités

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités
Pour 4 matrices → 5 possibilités
Pour 5 matrices

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités
Pour 4 matrices → 5 possibilités
Pour 5 matrices → 14 possibilités

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités
Pour 4 matrices → 5 possibilités
Pour 5 matrices → 14 possibilités
Pour 10 matrices ?

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

3 matrices A1 ∗ A2 ∗ A3 ?
I (A1 ∗ A2 ) ∗ A3
I A1 ∗ (A2 ∗ A3 )
I 2 possibilités
Pour 4 matrices → 5 possibilités
Pour 5 matrices → 14 possibilités
Pour 10 matrices ? → 4862 possibilités
Pour 50 matrices → 5 × 1021 possibilités
Cas général : pour n matrices, il y a C(n − 1) parenthésages possibles, où C (n) est le
nombre de Catalan C (n) = n+11
× 2nn
(à étudier en détail en TD)

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

Programmation Dynamique 78 / 174

Combien de parenthésages possibles ?

Très inefficace

Programmation Dynamique 78 / 174

Une première solution récursive (diviser pour
régner)

Programmation Dynamique 79 / 174

Une première solution récursive (diviser pour
régner)

Pour chaque solution, il faut découper la séquence A1 , ..An en deux sous séquences
A1 ..Ak et Ak+1 ..An (le calcul sera (A1 × ..Ak ) ∗ (Ak+1 × ..An ) )

Programmation Dynamique 79 / 174

Une première solution récursive (diviser pour
régner)

Programmation Dynamique 79 / 174

Une première solution récursive (diviser pour
régner)

Programmation Dynamique 79 / 174

Une première solution récursive (diviser pour
régner)

Pour chaque solution, il faut découper la séquence A1 , ..An en deux sous séquences
A1 ..Ak et Ak+1 ..An (le calcul sera (A1 × ..Ak ) ∗ (Ak+1 × ..An ) )
Soit m[i][j] le coût minimal pour la séquence Ai . . . Aj (avec i < j)
Solution du problème est m[1][n]
Pour le parenthésage (A1 ..Ak ) × (Ak+1 ..An ), le coût est
cout = m[1][k] + m[k + 1][n] + t0 × tk × tn

Programmation Dynamique 79 / 174

Une première solution récursive (diviser pour
régner)

Programmation Dynamique 79 / 174

Une première solution récursive (diviser pour
régner)

Cas général de la récursivité :

1 Si i < j, m[i][j] = mink∈[i,j−1] {m[i][k] + m[k + 1][j] + ti−1 × tk × tj } :
2 m[i][i] = 0

Programmation Dynamique 79 / 174

Algorithme récursif

Programmation Dynamique 80 / 174

Algorithme récursif

Algorithme : cout_recursif (A1 . . . An )

Données : Une liste de matrices A1 , A2 , . . . An de tailles t0 × t1 , t1 × t2 , . . . tn−1 × tn
Résultat : nombre minimal de multiplications pour calculer A1 × . . . × An
début
c, tmp : entier;
c←∞;
si n = 1 alors
retourner 0;
sinon
pour k de 1 à n − 1 faire
tmp ← cout_recursif(A1 . . . Ak ) + cout_recursif(Ak+1 , An ) + t0 × tk × tn ;
si tmp < c alors
c ← tmp ;
retourner c ;

Programmation Dynamique 80 / 174

Complexité de cout_recursif

(
c1 si n = 1
T (n) = Pn−1
k=1 (T (k) + T (n − k) + c2 ) si n > 1

Comment calculer la complexité sous une forme non-récursive ?
Le théorème maître ne s’applique pas !
On va essayer d’utiliser la méthode par substitution. D’abord on simplifie la récursion
Pn−1
Pour n > 1 : T (n) = 2 k=1 T (k) + c2 n
Pour n > 1 : T (n) − T (n − 1) = 2T (n − 1) + c2

Programmation Dynamique 81 / 174

Complexité de cout_recursif

(
c1 si n = 1
T (n) = Pn−1
k=1 (T (k) + T (n − k) + c2 ) si n > 1

Avec c1 et c2 deux constantes

Programmation Dynamique 81 / 174

Complexité de cout_recursif

(
c1 si n = 1
T (n) =
3T (n − 1) + c2 si n > 1
On applique la méthode par substitution
T (1) = c1
T (2) = 3T (1) + c2 = 3c1 + c2
T (3) = 3T (2) + c2 = 9c1 + 4c2
T (4) = 3T (4) + c2 = 27c1 + 13c2
..
Pn−2
T (n) = c1 × 3n−1 + c2 × i=0 3i (On peut le prouver par récurrence)
n
Par conséquent : T (n) ∈ Θ(3 )

Programmation Dynamique 82 / 174

Programmation Dynamique 83 / 174

Analyse de l’algorithme récursif par rapport à
l’approche force brute
n
La complexité de l’approche force brute est en Ω( n41.5 ) et la complexité de
l’algorithme récursif est en Θ(3n ). Que choisir ?
4n
Soit f (n) = n1.5
et g (n) = 3n . On veut comparer asymptotiquement f et g .
Rappel :
f (n)
I Si limn→∞ g (n)
= c > 0 (constante) alors f ∈ Θ(g ) (et donc g ∈ Θ(f ))

Programmation Dynamique 83 / 174

Règle de l’Hôpital
f et g deux fonctions dérivables t.q. lim f (n) = lim g (n) = ∞, alors :
n→∞ n→∞
0
lim f (n) = lim f 0(n) si cette limite existe.
n→∞ g (n) n→∞ g (n)

f 0 (respectivement g 0 ) représente la dévirée de f (respectivement g )

Programmation Dynamique 83 / 174

Analyse de l’algorithme récursif par rapport à
l’approche force brute

n
Rappel : la complexité de l’approche force brute est en Ω( n41.5 ) et la complexité de
l’algorithme récursif est en Θ(3n ). Que choisir ?

Programmation Dynamique 84 / 174

Analyse de l’algorithme récursif par rapport à
l’approche force brute

n
Rappel : la complexité de l’approche force brute est en Ω( n41.5 ) et la complexité de
l’algorithme récursif est en Θ(3n ). Que choisir ?

4n
4n n1.5
On va comparer n1.5
et 3n =⇒ on calcule limn→∞ 3n
?

Programmation Dynamique 84 / 174

Analyse de l’algorithme récursif par rapport à
l’approche force brute

n
Rappel : la complexité de l’approche force brute est en Ω( n41.5 ) et la complexité de
l’algorithme récursif est en Θ(3n ). Que choisir ?

4n
4n n1.5
On va comparer n1.5
et 3n =⇒ on calcule limn→∞ 3n
?

4n 4n
I n1.5 3
3n
= n1.5

I On utilise la règle de l’Hôpital :

4 n )0
(3 4)4n
ln( 3 (ln( 4 ) 4 n )0 ln( 4 4)4n
)∗ln( 3
3 3 3 3 3
limn→∞ (n1.5 )0
= limn→∞ 1.5n0.5
= limn→∞ (1.5n0.5 )0
= limn→∞ 1.5∗0.5∗n−0.5
=∞

4n
n1.5 4n 4n
I Donc limn→∞ 3n
= ∞ et par conséquent : n1.5
∈ Ω(3n ) et n1.5
/ O(3n )
∈

I L’algorithme récursif est meilleur que l’approche force brute

Programmation Dynamique 84 / 174

Calcul redondant

Programmation Dynamique 85 / 174

Calcul redondant
Algorithme : cout_recursif (A1 . . . An )
Données : Une liste de matrices A1 , A2 , . . . An de tailles t0 × t1 , t1 × t2 , . . . tn−1 × tn
Résultat : nombre minimal de multiplications pour calculer A1 × . . . × An
début
c, tmp : entier;
c←∞;
si n = 1 alors
retourner 0;
sinon
pour k de 1 à n − 1 faire
tmp ← cout_recursif(A1 . . . Ak ) + cout_recursif(Ak+1 , An ) + t0 × tk × tn ;
si tmp < c alors
c ← tmp ;
retourner c ;

cout_recursif (Ai , Aj ) est appelé plusieurs fois ( e.g. pour n = 5, on appelle

cout_recursif(3, 5) quand k = 1, k = 2, et k = 3).

Programmation Dynamique 85 / 174

Méthode de conception de type “diviser pour régner”

Souvent utilisée avec des problèmes d’optimisation (on cherche une solution qui
minimise ou maximise un critère)

Assure que chaque sous-problème est traité une seule fois afin d’éviter le problème de
redondance.

Idée clé :

I mémoriser les solutions des sous-problèmes (dans un tableau/matrice par exemple)

Programmation Dynamique 86 / 174

Programmation dynamique

Méthode de conception de type “diviser pour régner”

Souvent utilisée avec des problèmes d’optimisation (on cherche une solution qui
minimise ou maximise un critère)

Assure que chaque sous-problème est traité une seule fois afin d’éviter le problème de
redondance.

Idée clé :

I mémoriser les solutions des sous-problèmes (dans un tableau/matrice par exemple)

I approche ascendante : Soit P(n) le problème à résoudre de taille n. Pour tout k < i, si
P(i) dépend de P(k), alors résoudre P(k) avant de résoudre P(i)

Programmation Dynamique 86 / 174

Programmation dynamique pour la multiplication
des matrices

Il faut s’assurer que l’algorithme calcule le coût de chaque séquence de longueur l

avant de calculer le coût d’une séquence de taille l + 1

Programmation Dynamique 87 / 174

Programmation dynamique pour la multiplication
des matrices

Il faut s’assurer que l’algorithme calcule le coût de chaque séquence de longueur l

avant de calculer le coût d’une séquence de taille l + 1

Donc l’algorithme doit calculer (dans l’ordre)

1 Le coût des séquences de taille 2 : m[1][2], m[2][3], . . . m[n − 1][n]

2 Puis le coût des séquences de taille 3 : m[1][3], m[2][4], . . . m[n − 2][n]

3 ...

4 Finalement le coût de la séquence de taille n (coût de la solution optimale) : m[1][n]

Programmation Dynamique 87 / 174

Programmation dynamique pour la multiplication
des matrices
Algorithme : CoutMultiplication_ProgDynamique
Données : Une liste de matrices A1 , A2 , . . . An de tailles t0 × t1 , t1 × t2 , . . . tn−1 × tn
Résultat : nombre minimal de multiplications pour calculer A1 × . . . × An
l, tmp : entier;
m[][] : matrice de taille n × n ;
% m[i][j] est le coût minimal pour la séquence Ai , . . . Aj (i < j) ;
% Initialisation ;
pour i de 1 à n faire
m[i][i] = 0 ;
pour l de 2 à n faire
pour i de 1 à n − l + 1 faire
%On va calculer le coût minimal de la séquence de longeur l qui commence à Ai et le
sauvegarder dans m[i][j] avec j = i + l − 1 ;
j ←i +l −1 ;
m[i][j] ← ∞ ;
pour k de i à j − 1 faire
tmp ← m[i][k] + m[k + 1][j] + ti−1 × tk × tj ;
si tmp < m[i][j] alors
m[i][j] ← tmp ;

retourner m[1][n]
Programmation Dynamique 88 / 174
Complexité de
CoutMultiplication_ProgDynamique

Clairement CoutMultiplication_ProgDynamique ∈ O(n3 )

n
4
Meilleur que l’algorithme récursif (Θ(3n )) et la force brute (Ω( (n−1) 1.5 ) )

Programmation Dynamique 89 / 174

Programmation dynamique : résumé

Programmation Dynamique 90 / 174

Programmation dynamique : résumé

Les 5 étapes de la programmation dynamique :

1 Caractériser la structure d’une solution optimale

Programmation Dynamique 90 / 174

Programmation dynamique : résumé

Les 5 étapes de la programmation dynamique :

1 Caractériser la structure d’une solution optimale

2 Définit récursivement la valeur d’une solution optimale

Programmation Dynamique 90 / 174

Programmation dynamique : résumé

Les 5 étapes de la programmation dynamique :

1 Caractériser la structure d’une solution optimale

2 Définit récursivement la valeur d’une solution optimale

3 Calculer la valeur d’une solution optimale en remontant progressivement jusqu’au

problème initial

Programmation Dynamique 90 / 174

Programmation dynamique : résumé

Les 5 étapes de la programmation dynamique :

1 Caractériser la structure d’une solution optimale

2 Définit récursivement la valeur d’une solution optimale

3 Calculer la valeur d’une solution optimale en remontant progressivement jusqu’au

problème initial

4 Construire une solution optimale en se basant sur les informations calculées

Programmation Dynamique 90 / 174

Programmation dynamique : résumé

Les 5 étapes de la programmation dynamique :

1 Caractériser la structure d’une solution optimale

2 Définit récursivement la valeur d’une solution optimale

3 Calculer la valeur d’une solution optimale en remontant progressivement jusqu’au

problème initial

4 Construire une solution optimale en se basant sur les informations calculées

La dernière étape n’est pas obligatoire si on ne s’intéresse qu’au coût de la solution

optimale

Programmation Dynamique 90 / 174

Programmation dynamique : résumé

Les 5 étapes de la programmation dynamique :

1 Caractériser la structure d’une solution optimale

2 Définit récursivement la valeur d’une solution optimale

3 Calculer la valeur d’une solution optimale en remontant progressivement jusqu’au

problème initial

4 Construire une solution optimale en se basant sur les informations calculées

La dernière étape n’est pas obligatoire si on ne s’intéresse qu’au coût de la solution

optimale

Compléter CoutMultiplication_ProgDynamique pour retourner le parethésage

optimal.

Programmation Dynamique 90 / 174

Algorithmes gloutons

Algorithmes gloutons 91 / 174

Rappel

Algorithmes gloutons 92 / 174

Rappel

Nous avons traité deux types de problèmes :

Algorithmes gloutons 92 / 174

Rappel

Nous avons traité deux types de problèmes :

Rappel

Nous avons traité deux types de problèmes :

Algorithmes gloutons 92 / 174

Rappel

Nous avons traité deux types de problèmes :

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 92 / 174

Algorithmes gloutons (Greedy algorithms)

Algorithmes gloutons 93 / 174

Algorithmes gloutons (Greedy algorithms)

Contexte : typiquement pour les problèmes d’optimisation

Avantage : Rapide en temps de calcul

Algorithmes gloutons 93 / 174

Algorithmes gloutons (Greedy algorithms)

Contexte : typiquement pour les problèmes d’optimisation

Idée de base :
I Résoudre le problème en une séquence d’étapes/choix
I Pour chaque étape, faire un choix qui semble optimal à l’étape courante

Avantage : Rapide en temps de calcul

Inconvénient : Pas de garantie sur l’optimalité

Algorithmes gloutons 93 / 174

Exemple : Problème du Voyageur de commerce

Voyageur de commerce (optimisation)

donnée : ensemble de villes
question : quel est le plus court cycle passant par toutes les villes une seule fois ?

Algorithmes gloutons 94 / 174

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

c d
2
3
4
1
b
5
7

Algorithmes gloutons 95 / 174

Figure – Une solution non optimale

c d
2
3
4
1
b
5
7

Cycle : a,b,c,d,a
Coût de la solution :7 + 3 + 2 + 5 = 17

Algorithmes gloutons 96 / 174

Figure – Une solution optimale

c d
2
3
4
1
b
5
7

Cycle : a,c,b,d,a
Coût de la solution :1 + 3 + 4 + 5 = 13

Algorithmes gloutons 97 / 174

Énumération exhaustive ?

Énumération exhaustive ?

Algorithmes gloutons 98 / 174

Algorithme Glouton

Idée gloutonne :

Algorithmes gloutons 104 / 174

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

c d
2
3
4
1
b
5
7

Cycle : a,c,d, b, a
Coût courant :1 + 2 + 4 + 7 = 14
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 104 / 174

Algorithme Glouton pour le voyageur de
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} ;
tant que |Permutation| < n faire
min ← +∞ ;
pour e ∈ Ensemble faire
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 105 / 174

Matroïdes

Résoudre des problèmes d’optimisation avec des algorithmes gloutons

Algorithmes gloutons 106 / 174

Matroïdes

Résoudre des problèmes d’optimisation avec des algorithmes gloutons

Un matroïde représente une structure particulière utilisée pour concevoir un
algorithme glouton optimal

Algorithmes gloutons 106 / 174

Définition

Algorithmes gloutons 107 / 174

Définition

Un matroïde est un couple M = (E, I) qui satisfait les conditions suivantes :

indépendant”

Algorithmes gloutons 107 / 174

Exemple (simple) de Matroïde

E = {1, 2, 3, 4}
I = {{}, {1}, {2}, {4}, {1, 4}, {2, 4}}

Algorithmes gloutons 108 / 174

Exemple (simple) de Matroïde

E = {1, 2, 3, 4}
I = {{}, {1}, {2}, {4}, {1, 4}, {2, 4}}
Preuve
I E est un ensemble fini non vide (évident)

Algorithmes gloutons 108 / 174

Exemple (simple) de Matroïde

E = {1, 2, 3, 4}
I = {{}, {1}, {2}, {4}, {1, 4}, {2, 4}}
Preuve
I E est un ensemble fini non vide (évident)
I I est héréditaire car :

Algorithmes gloutons 108 / 174

Exemple (simple) de Matroïde

Algorithmes gloutons 108 / 174

Exemple (simple) de Matroïde

E = {1, 2, 3, 4}
I = {{}, {1}, {2}, {4}, {1, 4}, {2, 4}}
Preuve
I E est un ensemble fini non vide (évident)
I I est héréditaire car :
F Pour {2, 4} : {} ∈ I , {2} ∈ I , {4} ∈ I
F Pour {1, 4} : {} ∈ I , {1} ∈ I , {4} ∈ I
F Pour {1} : {} ∈ I , {1} ∈ I
F Pour {2} : {} ∈ I , {2} ∈ I
F Pour {3} : {} ∈ I , {4} ∈ I
F Pour {} : {} ∈ I
I Propriété d’échange :

Algorithmes gloutons 108 / 174

Exemple (simple) de Matroïde

Algorithmes gloutons 108 / 174

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 110 / 174

L’importance des matroïdes

Algorithmes gloutons 111 / 174

L’importance des matroïdes

Theorem
Glouton (M(E, I) , w ) retourne un sous ensemble indépendant optimal

Algorithmes gloutons 111 / 174

L’importance des matroïdes

Theorem
Glouton (M(E, I) , w ) retourne un sous ensemble indépendant optimal
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 de poids maximal
début
F ← {};
n ← |E| ;
L ← Trier (E) par poids décroissant ;
pour i ∈ [1..n] faire
si F ∪ {L[i]} ∈ I alors
F ← F ∪ {L[i]};

retourner F ;

Algorithmes gloutons 111 / 174

Glouton (M(E, I) , w ), alors ?

Rappel pour un problème d’optimisation :

I Il faut trouver un matroïde M(E, I) pondéré tel qu’une solution optimale de P
correspond à un sous ensemble indépendant (i.e., élément de I) de poids maximal qu’on
peut calculer à partir de Glouton (M(E, I) , w ).
I Dans ce cas, l’algorithme glouton est garanti de retourner une solution optimale
Cette approche ne marche pas pour tous les problèmes. En particulier, il y a souvent
deux limites :
1 Difficulté à définir l’ensemble I des sous ensembles indépendants

Algorithmes gloutons 112 / 174

Glouton (M(E, I) , w ), alors ?

Rappel pour un problème d’optimisation :

Pour exploiter Glouton (M(E, I) , w ) pour un problème d’optimisation P :

Algorithmes gloutons 112 / 174

Représentation des Données

Représentation des Données 113 / 174

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

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

Représentation des Données 114 / 174

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 114 / 174

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 ?

Sinon comment comparer des algorithmes avec des données différentes ?

I Est-ce que Factorielle est plus efficace que triSélection ?

Représentation des Données 114 / 174

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 ?

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

Représentation des Données 114 / 174

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 ?

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 114 / 174

Calculer la taille de la donnée

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

Représentation des Données 115 / 174

Calculer la taille de la donnée

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

Exemples :
I Types char, int, float, etc. : O(1)

Représentation des Données 115 / 174

Calculer la taille de la donnée

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

Exemples :
I Types char, int, float, etc. : O(1)

I Type N : Θ(log n) (pour un entier ≤ n)

Représentation des Données 115 / 174

Calculer la taille de la donnée

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

Exemples :
I Types char, int, float, etc. : O(1)

I Type N : Θ(log n) (pour un entier ≤ n)

I Type liste d’int : Θ(n) (pour une liste de longueur ≤ n)

Représentation des Données 115 / 174

Calculer la taille de la donnée

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

Exemples :
I Types char, int, float, etc. : O(1)

I Type N : Θ(log n) (pour un entier ≤ n)

I Type liste d’int : Θ(n) (pour une liste de longueur ≤ n)

Borne supérieure (O)

Trouver un encodage

Représentation des Données 115 / 174

Calculer la taille de la donnée

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

Exemples :
I Types char, int, float, etc. : O(1)

I Type N : Θ(log n) (pour un entier ≤ n)

I Type liste d’int : Θ(n) (pour une liste de longueur ≤ n)

Borne supérieure (O) Borne inférieure (Ω)

Trouver un encodage Principe des tiroirs

Représentation des Données 115 / 174

Encodage

Encodage
Un encodage pour un type de donnée T est une fonction injective :

f : T 7→ {0, 1}k

Tout x ∈ T a un seul code f (x) (fonction)

I Sinon on ne peut pas toujours encoder
Pour x, y ∈ T distincts, f (x) 6= f (y ) (injective)
I Sinon on ne peut pas toujours decoder

Exemples : ASCII, Morse,...

Représentation des Données 116 / 174

Encodage d’un char

7 6 5 4 3 2 1 0

Représenter les entiers entre 0 et 255 (char)

Représentation des Données 117 / 174

Encodage d’un char

27 26 25 24 23 22 21 20

Représenter les entiers entre 0 et 255 (char)

7
bi 2i
P
Chaque bit repésente un terme de la somme x =
i=0

Représentation des Données 117 / 174

Encodage d’un char

0 1 0 0 1 0 1 1

27 26 25 24 23 22 21 20

Représenter les entiers entre 0 et 255 (char)

7
bi 2i
P
Chaque bit repésente un terme de la somme x =
i=0

Pour x = 75 : 1 × 26 + 1 × 23 + 1 × 21 + 1 × 20

Représentation des Données 117 / 174

Encodage d’un char

0 1 0 0 1 0 1 1

27 26 25 24 23 22 21 20

Représenter les entiers entre 0 et 255 (char)

7
bi 2i
P
Chaque bit repésente un terme de la somme x =
i=0

Pour x = 75 : 1 × 26 + 1 × 23 + 1 × 21 + 1 × 20

Borne supérieure (et inféreieure)

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

Problème : combien de bits allouer pour coder n’importe quel entier ? ∞ ?

Donner le nombre de bits “utiles” en préfixe, en code unaire (autant de 0 que de bits
significatifs)

Code en O(log2 (n)) pour le préfixe + O(log2 (n)) pour le suffixe

Représentation des Données 118 / 174

Encodage d’un entier n ∈ N

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

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

Problème : combien de bits allouer pour coder n’importe quel entier ? ∞ ?

Donner le nombre de bits “utiles” en préfixe, en code unaire (autant de 0 que de bits
significatifs)

Code en O(log2 (n)) pour le préfixe + O(log2 (n)) pour le suffixe

Borne supérieure
Si n ∈ N alors |n| ∈ O(log n)

Représentation des Données 118 / 174

Encodage d’un tableau de n int

Représentation des Données 119 / 174

Encodage d’un tableau de n int

13 0 3 −18 2 9 11 −4

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

Chaque int requiert 4 octets : n × O(1)

Représentation des Données 119 / 174

Encodage d’un tableau de n int

8 13 0 3 −18 2 9 11 −4

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

Chaque int requiert 4 octets : n × O(1)

Même astuce que pour les entiers, le nombre d’éléments en préfixe : O(log n)

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

Représentation des Données 119 / 174

Encodage d’un tableau de n int

8 13 0 3 −18 2 9 11 −4

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

Chaque int requiert 4 octets : n × O(1)

Même astuce que pour les entiers, le nombre d’éléments en préfixe : O(log n)

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

Borne supérieure
Si L est un tableau contenant n int, alors |L| ∈ O(n)

Représentation des Données 119 / 174

Borne inférieure sur la taille de la donnée

Quelques principes de base de dénombrement

Principe additif
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
et 3 plats végétariens ?

Représentation des Données 120 / 174

Borne inférieure sur la taille de la donnée

Quelques principes de base de dénombrement

Principe additif
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
et 3 plats végétariens ? 3 + 2 + 3 = 8 plats

Représentation des Données 120 / 174

Borne inférieure sur la taille de la donnée

Quelques principes de base de dénombrement

Principe multiplicatif
Les choix indépendents se combinent par multiplication.
Combien de menus s’il y a 3 entrées, 4 plats, et 4 desserts ?

Représentation des Données 120 / 174

Borne inférieure sur la taille de la donnée

Quelques principes de base de dénombrement

Principe multiplicatif
Les choix indépendents se combinent par multiplication.
Combien de menus s’il y a 3 entrées, 4 plats, et 4 desserts ? 3 × 4 × 4 = 48 menus

Représentation des Données 120 / 174

Borne inférieure sur la taille de la donnée

Quelques principes de base de dénombrement

Principe multiplicatif
Les choix indépendents se combinent par multiplication.
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 ?

Représentation des Données 120 / 174

Borne inférieure sur la taille de la donnée

Quelques principes de base de dénombrement

Représentation des Données 120 / 174

Principes des tiroirs

Principe des tiroirs

Si m objets sont rangés dans n tiroirs, alors un tiroir en contient au moins d mn e.

Si m > n objets sont rangés dans n tiroirs, alors un tiroir en contient au moins 2

Représentation des Données 121 / 174

Principes des tiroirs

Principe des tiroirs

Si m objets sont rangés dans n tiroirs, alors un tiroir en contient au moins d mn e.

Si m > n objets sont rangés dans n tiroirs, alors un tiroir en contient au moins 2

Il y a deux londoniens avec exactement le même nombre de cheveux

Représentation des Données 121 / 174

Principes des tiroirs

Principe des tiroirs

Si m objets sont rangés dans n tiroirs, alors un tiroir en contient au moins d mn e.

Si m > n objets sont rangés dans n tiroirs, alors un tiroir en contient au moins 2

Il y a deux londoniens avec exactement le même nombre de cheveux

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

Représentation des Données 121 / 174

Principes des tiroirs

Principe des tiroirs

Si m objets sont rangés dans n tiroirs, alors un tiroir en contient au moins d mn e.

Si m > n objets sont rangés dans n tiroirs, alors un tiroir en contient au moins 2

Il y a deux londoniens avec exactement le même nombre de cheveux

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

I Il y a plus d’un million de londoniens

Représentation des Données 121 / 174

Principes des tiroirs

Principe des tiroirs

Si m objets sont rangés dans n tiroirs, alors un tiroir en contient au moins d mn e.

Si m > n objets sont rangés dans n tiroirs, alors un tiroir en contient au moins 2

Il y a deux londoniens avec exactement le même nombre de cheveux

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

I Il y a plus d’un million de londoniens

I m londoniens à répartir parmi n chevelures possibles ⇒ au moins deux londoniens avec la

même chevelure

Représentation des Données 121 / 174

Minorant pour l’espace mémoire

Représentation des Données 122 / 174

Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :

f : T 7→ {0, 1}k

Représentation des Données 122 / 174

Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :

f : T 7→ {0, 1}k avec f (x) ∈ {0, 1}|x|

Représentation des Données 122 / 174

Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :

f : T 7→ {0, 1}k avec f (x) ∈ {0, 1}|x|

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

Représentation des Données 122 / 174

Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :

f : T 7→ {0, 1}k avec f (x) ∈ {0, 1}|x|

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

Il faut au moins autant de mots binaires que de valeurs possibles pour la donnée

I Principe des tiroirs : sinon, des données distinctes ont le même code, et f est non-injective

Représentation des Données 122 / 174

Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :

f : T 7→ {0, 1}k avec f (x) ∈ {0, 1}|x|

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

Il faut au moins autant de mots binaires que de valeurs possibles pour la donnée

I Principe des tiroirs : sinon, des données distinctes ont le même code, et f est non-injective

Minorant pour la taille |x| d’une donnée x de type T

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 )

Représentation des Données 122 / 174

Minorant pour l’espace mémoire

un encodage est une fonction injective d’un type de donnée vers les mots binaires :

f : T 7→ {0, 1}k avec f (x) ∈ {0, 1}|x|

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

Il faut au moins autant de mots binaires que de valeurs possibles pour la donnée

I Principe des tiroirs : sinon, des données distinctes ont le même code, et f est non-injective

Minorant pour la taille |x| d’une donnée x de type T

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 ), ⇒

|x| ∈ Ω(log #(T ))

Représentation des Données 122 / 174

Bornes inférieures

Représentation des Données 123 / 174

I Tableau d’int de longueur ≤ n :

Représentation des Données 123 / 174

Bornes inférieures

Calculons #(T ), le nombre de valeurs possibles pour la donnée x de type T :

I Entier naturel inférieur ou égal à n : n + 1, soit Θ(n)

Pour x un entier naturel inférieur ou égal à n :

|x| ∈ Ω(log n) et puisqu’il existe un encodage tel que |x| ∈ O(log n), alors |x| ∈ Θ(log n)

I Tableau d’int de longueur n : (232 )n , soit Θ(232n )

n
232i , soit Θ(232n )
P
I Tableau d’int de longueur ≤ n :
i=0

Représentation des Données 123 / 174

Bornes inférieures

Calculons #(T ), le nombre de valeurs possibles pour la donnée x de type T :

I Entier naturel inférieur ou égal à n : n + 1, soit Θ(n)

Pour x un entier naturel inférieur ou égal à n :

|x| ∈ Ω(log n) et puisqu’il existe un encodage tel que |x| ∈ O(log n), alors |x| ∈ Θ(log n)

I Tableau d’int de longueur n : (232 )n , soit Θ(232n )

n
232i , soit Θ(232n )
P
I Tableau d’int de longueur ≤ n :
i=0

I log2 (232n ) = 32nlog2 (2) = 32n

Pour L un tableau d’int de longueur ≤ n :

|L| ∈ Ω(n) et puisqu’il existe un encodage tel que |L| ∈ O(n), alors |L| ∈ Θ(n)

Représentation des Données 123 / 174

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

Exemple

Algorithme : Carré(x)
Données : un entier x
Résultat : un entier valant x 2
r : entier;
début
r ← 0;
pour i allant de 1 à x faire
pour j allant de 1 à x faire
r ← r + 1;

retourner r ;

Représentation des Données 124 / 174

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

L’algorithme A est en Θ(f (x)) pour une donnée x

Exemple

Algorithme : Carré(x)
Données : un entier x
Résultat : un entier valant x 2 Complexité : Θ(x 2 )
r : entier;
début
r ← 0;
pour i allant de 1 à x faire
pour j allant de 1 à x faire
r ← r + 1;

retourner r ;

Représentation des Données 124 / 174

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

L’algorithme A est en Θ(f (x)) pour une donnée x

La taille |x| de la donnée est en Θ(g (x))

Exemple

Algorithme : Carré(x)
Données : un entier x
Résultat : un entier valant x 2 Complexité : Θ(x 2 )
r : entier;
début Taille de la donnée |x| = Θ(log x)
r ← 0;
pour i allant de 1 à x faire
pour j allant de 1 à x faire
r ← r + 1;

retourner r ;

Représentation des Données 124 / 174

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

L’algorithme A est en Θ(f (x)) pour une donnée x

La taille |x| de la donnée est en Θ(g (x))
Alors la complexité de A est en Θ(f (g −1 (x)))
Exemple

retourner r ;

Représentation des Données 124 / 174

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

L’algorithme A est en Θ(f (x)) pour une donnée x

La taille |x| de la donnée est en Θ(g (x))
Alors la complexité de A est en Θ(f (g −1 (x)))
Exemple

retourner r ; Donc complexité en Θ(22|x| ) (exponentielle !)

Représentation des Données 124 / 174

Structure de données

Le choix de la structure de données est très important dans la conception

d’un algorithme

Choisir la structure pour laquelle les opérations utiles sont les plus efficaces

Un type abstrait est défini par les opérations qui sont efficaces sur ce type

I Insertion (I) : ajouter un nouvel élément

I test d’Appartenance (A) : vérifier si l’élément x est présent
I Suppression (S) : supprimer un élément x
I Suppression du Dernier (SD) : supprimer le dernier élément inséré
I Suppression du Premier (SP) : supprimer le premier élément inséré
I Suppression du Minimum (SM) : supprimer l’élément minimum

Représentation des Données 125 / 174

Structure de données

Un type abstrait est défini par les opérations qui sont efficaces sur ce type

Une réalisation correspond à du code (des algorithmes)

Type Abstrait Réalisation I A S SP SD SM

Pile Liste chainée O(1) O(1)
Liste chainée avec
File O(1) O(1)
pointeurs début et fin
Index statique Vecteur trié O(log n)
File de priorité Tas binaire O(log n) O(log n)
O(1)∗ O(1)∗
Ensemble Table de hâchage O(1)
Θ(n) Θ(n)
ABR, AVL
Ensemble trié O(log n) O(log n) O(log n) O(log n)
Arbre rouge-noir

Représentation des Données 126 / 174

Structure de données

Un type abstrait est défini par les opérations qui sont efficaces sur ce type

Une réalisation correspond à du code (des algorithmes)

Type Abstrait Réalisation I A S SP SD SM

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
Index statique Vecteur trié Θ(n) O(log n) Θ(n) N/A N/A Θ(n)
File de priorité Tas binaire O(log n) Θ(n) Θ(n) N/A N/A O(log n)
O(1)∗ O(1)∗
Ensemble Table de hâchage O(1) N/A N/A Θ(n)
Θ(n) Θ(n)
ABR, AVL
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 126 / 174

Exemple : Table de Hâchage

Fichier des étudiants de l’INSA, il faut une clé unique pour identification

Représentation des Données 127 / 174

Exemple : Table de Hâchage

Fichier des étudiants de l’INSA, il faut une clé unique pour identification

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

Représentation des Données 127 / 174

Exemple : Table de Hâchage

Fichier des étudiants de l’INSA, il faut une clé unique pour identification

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

Utiliser le numéro de sécurité sociale ?

I Beaucoup trop de clés possibles !

Représentation des Données 127 / 174

Exemple : Table de Hâchage

Fichier des étudiants de l’INSA, il faut une clé unique pour identification

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

T [i − 1] T [i] T [i + 1]

enregistrement(x)

h(x) = h(y ) = i
enregistrement(y )

Analyse de la complexité du test d’appartenance (A)

Représentation des Données 128 / 174

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

1 2

2 5 3 6

4 8 5 67 6 50 7 38

8 12 9 95

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
2 5 6 8 67 50 38 12 95 .
fils droit de i : 2i + 1

Représentation des Données 129 / 174

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

1 2

2 5 3 6

4 8 5 67 6 50 7 38

8 12 9 95 3

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
2 5 6 8 67 50 38 12 95 3
fils droit de i : 2i + 1

Insertion : la position libre la plus à gauche possible sur le dernier niveau

Représentation des Données 129 / 174

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

1 2

2 5 3 6

4 8 5 3 6 50 7 38

8 12 9 95 67

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
2 5 6 8 3 50 38 12 95 67
fils droit de i : 2i + 1

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

Représentation des Données 129 / 174

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

1 2

2 3 3 6

4 8 5 5 6 50 7 38

8 12 9 95 67

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
2 3 6 8 5 50 38 12 95 67
fils droit de i : 2i + 1

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

Représentation des Données 129 / 174

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

1 2

2 3 3 6

4 8 5 5 6 50 7 38

8 12 9 95 67

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
2 3 6 8 5 50 38 12 95 67
fils droit de i : 2i + 1

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

Représentation des Données 129 / 174

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

1 2

2 3 3 6

4 8 5 5 6 50 7 38

8 12 9 95 67

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
2 3 6 8 5 50 38 12 95 67
fils droit de i : 2i + 1

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
Suppression du minimum : la racine, qu’on remplace par le “dernier” sommet

Représentation des Données 129 / 174

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

1 67

1 3

2 5 3 6

4 8 5 67 6 50 7 38

8 12 9 95

parent de i : bi/2c
1 2 3 4 5 6 7 8 9 10
réalisation : fils gauche de i : 2i
3 5 6 8 67 50 38 12 95 .
fils droit de i : 2i + 1

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 129 / 174
Tri par tas

Pour chaque x ∈ L :
Insérer x dans le tas binaire H
Tant que H n’est pas vide :
Extraire le minimum de H et l’afficher

n insertions en O(log n)
Tri par tas est optimal !
n suppressions en O(log n)
O(n log n) dans le pire des cas
Complexité du tri par tas : O(n log n)

Représentation des Données 130 / 174

Institut d’Intelligence Artificielle de Toulouse

https://aniti.univ-toulouse.fr

Représentation des Données 131 / 174

Objectif : doubler le nombre de diplômés (Master) en IA à Toulouse

Représentation des Données 132 / 174

Objectif : doubler le nombre de diplômés (Master) en IA à Toulouse

Un nouveau Master d’Intelligence Artificielle dès 2020-2021

Représentation des Données 132 / 174

Objectif : doubler le nombre de diplômés (Master) en IA à Toulouse

Un nouveau Master d’Intelligence Artificielle dès 2020-2021

Des stages de Master

Représentation des Données 132 / 174

Objectif : doubler le nombre de diplômés (Master) en IA à Toulouse

Un nouveau Master d’Intelligence Artificielle dès 2020-2021

Des stages de Master

Des bourses de thèse

Représentation des Données 132 / 174

Objectif : doubler le nombre de diplômés (Master) en IA à Toulouse

Un nouveau Master d’Intelligence Artificielle dès 2020-2021

Des stages de Master

Des bourses de thèse

Des Postdocs

Représentation des Données 132 / 174

DeepLEVER (http://anitideeplever.laas.fr)

Représentation des Données 133 / 174

DeepLEVER (http://anitideeplever.laas.fr)

Représentation des Données 133 / 174

DeepLEVER (http://anitideeplever.laas.fr)

Vérification : trouver des contre-exemples à une prédiction d’un RN

Explication : trouver des conditions suffisantes pour une prédiction
Synthèse : générer un réseau de neurones explicable et robuste
Représentation des Données 133 / 174
Classes de Complexité

Classes de Complexité 134 / 174

Borne inférieure pour les algorithmes de tri

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 ?

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é 135 / 174

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

Classes de Complexité 136 / 174

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

[0, 0, 1, 0, 1, 1, 1, 1, . . .]
[0, 0, 1, 0, 1, 1, 1, 1, . . .]
[0, 1, 0, 0, 1, 0, 0, 1, . . .]
2k [1, 0, 0, 0, 0, 1, 1, 1, . . .]
[0, 1, 1, 0, 1, 1, 0, 0, . . .]
[1, 0, 1, 0, 0, 1, 1, 0, . . .]
[0, 0, 1, 0, 1,.. 1, 1, 1, . . .]
.

Au plus k comparaisons, donc au plus 2k données/exécutions distinctes

Classes de Complexité 136 / 174

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

[0, 0, 1, 0, 1, 1, 1, 1, . . .] (e1 , e2 , e3 , e4 , . . .)
[0, 0, 1, 0, 1, 1, 1, 1, . . .] (e1 , e2 , e4 , e3 , . . .)
[0, 1, 0, 0, 1, 0, 0, 1, . . .] (e1 , e3 , e2 , e4 , . . .)
2k [1, 0, 0, 0, 0, 1, 1, 1, . . .] (e1 , e3 , e4 , e2 , . . .) n!
[0, 1, 1, 0, 1, 1, 0, 0, . . .] (e1 , e4 , e2 , e3 , . . .)
[1, 0, 1, 0, 0, 1, 1, 0, . . .] (e1 , e4 , e3 , e2 , . . .)
[0, 0, 1, 0, 1,.. 1, 1, 1, . . .] (e1 , e2 , e..3 , e4 , . . .)
. .

Au plus k comparaisons, donc au plus 2k données/exécutions distinctes

Chacune des n! permutations de la donnée doit correspondre à une exécution distincte

Classes de Complexité 136 / 174

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

Au plus k comparaisons, donc au plus 2k données/exécutions distinctes

Chacune des n! permutations de la donnée doit correspondre à une exécution distincte

Classes de Complexité 136 / 174

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

Au plus k comparaisons, donc au plus 2k données/exécutions distinctes

Chacune des n! permutations de la donnée doit correspondre à une exécution distincte

principe des tiroirs

2k ≥ n!
Classes de Complexité 136 / 174
Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2
= log n + log(n − 1) + log(n − 1) + . . . + log(2)

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2
= log n + log(n − 1) + log(n − 1) + . . . + log(2)
X n
= log i
i=2

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2
= log n + log(n − 1) + log(n − 1) + . . . + log(2)
X n
= log i
i=2
n/2−1 n
X X
= log i + log i
i=2 i=n/2

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2
= log n + log(n − 1) + log(n − 1) + . . . + log(2)
X n
= log i
i=2
n/2−1 n
X X
= log i + log i
i=2 i=n/2
n
X n
≥ log
2
i=n/2

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2
= log n + log(n − 1) + log(n − 1) + . . . + log(2)
X n
= log i
i=2
n/2−1 n
X X
= log i + log i
i=2 i=n/2
n
X n
≥ log
2
i=n/2
n n
= log
2 2

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

2k ≥ n! =⇒ k ≥ log(n!)
= log n(n − 1)(n − 1) . . . 2
= log n + log(n − 1) + log(n − 1) + . . . + log(2)
X n
= log i
i=2
n/2−1 n
X X
= log i + log i
i=2 i=n/2
n
X n
≥ log
2
i=n/2
n n
= log
2 2
= Ω(n log n)

Classes de Complexité 137 / 174

Borne inférieure pour les algorithmes de tri

Théorème
Tout algorithme de tri par comparaison est en Ω(n log n)

Classes de Complexité 138 / 174

Classes de Complexité 140 / 174

Problème

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 ?”
I “Quel est la valeur du carré de x ?”

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

Qcarr : Entier : x 7→ Entier : x 2

Classes de Complexité 140 / 174

Types de Problèmes

Problèmes généraux (fonctions)

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

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

donnée : ensemble de villes
question : quel est le plus court chemin passant par toutes les villes ?

Classes de Complexité 142 / 174

Problème de décision

Problème de décision Q
Fonction Q : x →
7 {oui, non}

Pour un problème dont la réponse n’est pas dans {oui, non}, on peut définir un
problème polynomialement équivalent :

Voyageur de commerce (optimisation)

donnée : ensemble de villes
question : quel est le plus court chemin passant par toutes les villes ?

Voyageur de commerce (décision)

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é 142 / 174

Instance

Instance : problème avec la donnée (“Combien vaut 5672 ?”, “Quel est le plus court
chemin entre Toulouse et Paris ?”)

Classes de Complexité 143 / 174

Instance

Instance : problème avec la donnée (“Combien vaut 5672 ?”, “Quel est le plus court
chemin entre Toulouse et Paris ?”)

Ne pas confondre problème et instance

Classes de Complexité 143 / 174

Instance

Instance : problème avec la donnée (“Combien vaut 5672 ?”, “Quel est le plus court
chemin entre Toulouse et Paris ?”)

Ne pas confondre problème et instance

En particulier, se poser la question de la difficulté d’une instance n’a pas

(beaucoup ?) de sens

Classes de Complexité 143 / 174

Instance

Instance : problème avec la donnée (“Combien vaut 5672 ?”, “Quel est le plus court
chemin entre Toulouse et Paris ?”)

Ne pas confondre problème et instance

En particulier, se poser la question de la difficulté d’une instance n’a pas

(beaucoup ?) de sens

I L’algorithme qui renvoie systématiquement, et sans calcul, la solution de cette instance

(correct et en O(1))

Classes de Complexité 143 / 174

Classes d’Algorithmes

Un algorithme est dit :

en temps constant si sa complexité dans le pire des cas est bornée par une constante

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

quadratique si sa complexité dans le pire des cas est en Θ(n2 )

polynomial si sa complexité dans le pire des cas est en O(nc ) avec c > 0

c
exponentiel si elle est en Θ(2n ) pour un certain c > 1

Classes de Complexité 144 / 174

Classes d’Algorithmes

Un algorithme est dit :

en temps constant si sa complexité dans le pire des cas est bornée par une constante

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

quadratique si sa complexité dans le pire des cas est en Θ(n2 )

polynomial si sa complexité dans le pire des cas est en O(nc ) avec c > 0

c
exponentiel si elle est en Θ(2n ) pour un certain c > 1

Classes de Complexité 144 / 174

Classes de problèmes

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

Classes de Complexité 145 / 174

Classes de problèmes

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

La complexité d’un problème :

La complexité du meilleur algorithme pour le résoudre

Classes de Complexité 145 / 174

Classes de problèmes

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

La complexité d’un problème :

La complexité du meilleur algorithme pour le résoudre

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

Classes de Complexité 145 / 174

Classes de problèmes

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

La complexité d’un problème :

La complexité du meilleur algorithme pour le résoudre

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

Tri ∈ (n log n)-TIME

Classes de Complexité 145 / 174

Classes de problèmes

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

La complexité d’un problème :

La complexité du meilleur algorithme pour le résoudre

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

Tri ∈ (n log n)-TIME

Recherche dans un tableau trié ∈ (log n)-TIME

Classes de Complexité 145 / 174

Classes de problèmes

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

La complexité d’un problème :

La complexité du meilleur algorithme pour le résoudre

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

Tri ∈ (n log n)-TIME

Recherche dans un tableau trié ∈ (log n)-TIME
Recherche du maximum dans un tableau ∈ (n)-TIME

Relation d’Inclusion

Inclusion
Si f (n) ∈ O(g (n)) alors f (n)-TIME ⊆ g (n)-TIME

n2 -TIME

n-TIME
(n log n)-TIME
(log n)-TIME

Classes de Complexité 146 / 174

Problème de Tri

Tri
donnée: Une liste L d’objet comparables
question: La séquence triée des objets de L

n-TIME
(n log n)-TIME
(log n)-TIME

Classes de Complexité 147 / 174

Problème de Tri

Tri
donnée: Une liste L d’objet comparables
question: La séquence triée des objets de L

n-TIME
(n log n)-TIME
(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é 147 / 174

(Non-)Appartenance à une Classe

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

Classes de Complexité 148 / 174

(Non-)Appartenance à une Classe

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

I il suffit d’un algorithme en O(f (n))

Classes de Complexité 148 / 174

(Non-)Appartenance à une Classe

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

I il suffit d’un algorithme en O(f (n))

Pour prouver qu’un problème n’appartient pas à une classe inférieure

I il faut montrer que tout algorithme est en Ω(f (n))

Classes de Complexité 148 / 174

Classe “Temps Polynômial”

Rappel :

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

Classes de Complexité 149 / 174

Classe “Temps Polynômial”

Classes de Complexité 150 / 174

Classe “Temps Exponentiel”

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

EXP-TIME :
c
Ensemble des problèmes pour lesquels il existe un algorithme en O(2n )
pour une constante c
c
[
EXP-TIME = 2n -TIME
c≥1

Evidemment, P ⊆ EXP-TIME
EXP-TIME P
Est-ce que P ⊂ EXP-TIME ? Oui !
Il existe des problèmes en Ω(2n )

Classes de Complexité 150 / 174

Classes Caractérisées par l’Espace

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

Classes de Complexité 151 / 174

Classes Caractérisées par l’Espace

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

f (n)-SPACE
Ensemble des problèmes pour lesquels il existe un algorithme nécessitant
O(f (n)) octets de mémoire

Classes de Complexité 151 / 174

Classes Caractérisées par l’Espace

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

f (n)-SPACE
Ensemble des problèmes pour lesquels il existe un algorithme nécessitant
O(f (n)) octets de mémoire

On ne compte pas la taille de la donnée, mais on compte la taille de la réponse

Classes de Complexité 151 / 174

Exemple : Sous-Séquence Maximale

Sous-Séquence Maximale
donnée: Un tableau L avec n éléments dans {−1, 1}
Quelles sont les valeurs de s et e dans [1, n] qui maximisent
question: P
e
i=s L[i]

Classes de Complexité 152 / 174

Exemple : Sous-Séquence Maximale

Sous-Séquence Maximale
donnée: Un tableau L avec n éléments dans {−1, 1}
Quelles sont les valeurs de s et e dans [1, n] qui maximisent
question: P
e
i=s L[i]

-1 -1 |1 1 -1 {z
1 -1 1 1} -1 -1 1 1 -1 1
3

Classes de Complexité 152 / 174

Exemple : Sous-Séquence Maximale

Sous-Séquence Maximale
donnée: Un tableau L avec n éléments dans {−1, 1}
Quelles sont les valeurs de s et e dans [1, n] qui maximisent
question: P
e
i=s L[i]

-1 -1 |1 1 -1 {z
1 -1 1 1} -1 -1 1 1 -1 1
3

Algorithme 1 Temps : Θ(n3 )

P1≤i ≤j ≤n:
Pour chaque Espace : Θ(log n)
calculer jk=i L[k] ; garder le max. I log n pour le max, la somme et le resultat

Classes de Complexité 152 / 174

Exemple : 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

Classes de Complexité 153 / 174

Exemple : 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

Algorithme 2
Pi
s[i] = k=1 L[k]

Classes de Complexité 153 / 174

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

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

Algorithme 2
Pi
s[i] = k=1 L[k]
Pj Pj Pi−1
I
k=i L[k] = k=1 L[k] − k=1 L[k]

Classes de Complexité 153 / 174

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

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
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

Algorithme 2
Pi
s[i] = k=1 L[k]
Pj Pj Pi−1
I
k=i L[k] = k=1 L[k] − k=1 L[k]
min[i] = min(s[j] | j < i)

Classes de Complexité 153 / 174

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

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
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
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

Algorithme 2
Pi
s[i] = k=1 L[k]
Pj Pj Pi−1
I
k=i L[k] = k=1 L[k] − k=1 L[k]
min[i] = min(s[j] | j < i)
max[i] = max(s[j] | j ≥ i)

Classes de Complexité 153 / 174

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

Algorithme 2
Pi
s[i] = k=1 L[k]
Pj Pj Pi−1
I
k=i L[k] = k=1 L[k] − k=1 L[k]
min[i] = min(s[j] | j < i)
max[i] = max(s[j] | j ≥ i)
mss[i] = maxi − mini

Classes de Complexité 153 / 174

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

Algorithme 2
Pi
s[i] = k=1 L[k]
Pj Pj Pi−1 Θ(1) tables de taille Θ(n)
I
k=i L[k] = k=1 L[k] − k=1 L[k]
Temps : Θ(n)
min[i] = min(s[j] | j < i)
Espace : Θ(n)
max[i] = max(s[j] | j ≥ i)
mss[i] = maxi − mini

Classes de Complexité 153 / 174

Temps ou Espace

Temps Espace
Algorithme 1 Θ(n3 ) Θ(log n)
Algorithme 2 Θ(n) Θ(n)

Classes de Complexité 154 / 174

Temps ou Mémoire ?

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

Classes de Complexité 155 / 174

Temps ou Mémoire ?

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

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

Classes de Complexité 155 / 174

Temps ou Mémoire ?

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

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

Alors tout algorithme pour A utilise Ω(g (n)) mémoire avec g (n) 6∈ O(f (n)).

Classes de Complexité 155 / 174

Temps ou Mémoire ?

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

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

Alors tout algorithme pour A utilise Ω(g (n)) mémoire avec g (n) 6∈ O(f (n)).

Si un algorithme nécessite Ω(g (n)) mémoire il fait Ω(g (n)) écritures.

Classes de Complexité 155 / 174

Temps ou Mémoire ?

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

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

Alors tout algorithme pour A utilise Ω(g (n)) mémoire avec g (n) 6∈ O(f (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é 155 / 174

Classe “Espace Polynomial”

Classe des problèmes pour lesquels il existe un algorithme polynômial en espace :

P-SPACE
Ensemble des problèmes pour lesquels il existe un algorithme qui utilise
O(nc ) octets de mémoire pour une constante c.
[
P= nc -SPACE
c≥0

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

Classes de Complexité 156 / 174

P-SPACE et EXP-TIME

Théorème
P-SPACE ⊆ EXP-TIME

Classes de Complexité 157 / 174

P-SPACE et EXP-TIME

Théorème
P-SPACE ⊆ EXP-TIME

Classes de Complexité 157 / 174

EXP-TIME P-SPACE ? P

Les Classes NP et coNP 160 / 174

Classes non-déterministes

EXP-TIME P-SPACE NP P

A priori difficiles (pas d’algorithme polynomial connu)

Les Classes NP et coNP 160 / 174

Classes non-déterministes

EXP-TIME P-SPACE NP P

A priori difficiles (pas d’algorithme polynomial connu)

Faciles à vérifier, ex. 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 ?
Les Classes NP et coNP 160 / 174
Classes non-déterministes

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

Les Classes NP et coNP 161 / 174

Classes non-déterministes

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

Pas d’algorithme en temps polynomial connu, mais aucune preuve d’impossibilité

Les Classes NP et coNP 161 / 174

Classes non-déterministes

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

Pas d’algorithme en temps polynomial connu, mais aucune preuve d’impossibilité

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

Les Classes NP et coNP 161 / 174

Classes non-déterministes

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

Pas d’algorithme en temps polynomial connu, mais aucune preuve d’impossibilité

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

Algorithme non-déterministe pour le problème Q

Les Classes NP et coNP 161 / 174

Classes non-déterministes

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

Pas d’algorithme en temps polynomial connu, mais aucune preuve d’impossibilité

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

Algorithme non-déterministe pour le problème Q

Composée d’instructions primitives : exécutable par une machine
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

Les Classes NP et coNP 161 / 174

Classes non-déterministes

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

Pas d’algorithme en temps polynomial connu, mais aucune preuve d’impossibilité

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

Algorithme non-déterministe pour le problème Q

Les Classes NP et coNP 161 / 174

Oracle
Algorithme non-déterministe
Un algorithme non-déterministe peut avoir recours à un oracle qui, si la réponse est
“oui”, devine un certificat polynomial en temps O(1)
Le certificat peut-être n’importe quoi, mais :
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

Les Classes NP et coNP 162 / 174

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 ?

Les Classes NP et coNP 162 / 174

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 162 / 174
Exemple : Le problème de 3-coloration

Donnée : Un graphe G = (S, A) (sommets S ; arêtes A)

Les Classes NP et coNP 163 / 174

Exemple : Le problème de 3-coloration

Donnée : Un graphe G = (S, A) (sommets S ; arêtes A)

Question : Est-ce qu’il est possible de colorier les sommets de G avec au

plus 3 couleurs en évitant que deux sommets adjacents
partagent la même couleur.

Les Classes NP et coNP 163 / 174

Exemple : Le problème de 3-coloration

Donnée : Un graphe G = (S, A) (sommets S ; arêtes A)

Question : Est-ce qu’il est possible de colorier les sommets de G avec au

plus 3 couleurs en évitant que deux sommets adjacents
partagent la même couleur.

Les Classes NP et coNP 163 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

Les Classes NP et coNP 164 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

De taille polynomiale (dans la TDLD)

Les Classes NP et coNP 164 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

De taille polynomiale (dans la TDLD)

I quelle est la taille de la donnée du problème ?

Les Classes NP et coNP 164 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

De taille polynomiale (dans la TDLD)

I quelle est la taille de la donnée du problème ?

taille : |G | = Θ(|S| + |A|)

Les Classes NP et coNP 164 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

De taille polynomiale (dans la TDLD)

I quelle est la taille de la donnée du problème ?

taille : |G | = Θ(|S| + |A|)

I quelle est la taille du certificat ?

Les Classes NP et coNP 164 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

De taille polynomiale (dans la TDLD)

I quelle est la taille de la donnée du problème ?

taille : |G | = Θ(|S| + |A|)

I quelle est la taille du certificat ?

taille : Θ(|S|)

Les Classes NP et coNP 164 / 174

3-Coloration est dans NP

Certificat : La coloration (tableau – couleur du i-ème sommet dans la case i)

De taille polynomiale (dans la TDLD)

I quelle est la taille de la donnée du problème ?

taille : |G | = Θ(|S| + |A|)

I quelle est la taille du certificat ?

taille : Θ(|S|)

Vérifiable en temps polynomial (dans la TDLD) : algorithme

Les Classes NP et coNP 164 / 174

Algorithme de vérification
Algorithme : verification(L, G )
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
pour chaque arrête (i, j) de A faire
si T [i] = T [j] alors
retourner faux ;

retourner vrai ;

Complexité : O(|A|) (liste d’adjacence)

Les Classes NP et coNP 165 / 174

retourner vrai ;

Complexité : O(|A|) (liste d’adjacence)

⇒ 3-Coloration est bien dans NP

Les Classes NP et coNP 165 / 174

P est la classe des problèmes “faciles à résoudre”

NP est la classe des problèmes “faciles à vérifier”

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

I On ne connait pas d’algorithme polynomial pour Voyageur de commerce ou 3-Coloration

I Mais personne ne sait s’il en existe !

Les Classes NP et coNP 166 / 174

L’importance de la classe NP

Les Classes NP et coNP 167 / 174

L’importance de la classe NP
Ces problèmes sont partout : en intelligence artificielle, en cryptographie, dans
l’industrie...

Les Classes NP et coNP 167 / 174

L’importance de la classe NP
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
commerce n’a pas d’algorithme polynomial connu, mais...
I Domaine de recherche très actif, des algorithmes “intelligents” peuvent résoudre
(optimalement) de très grandes instances

Les Classes NP et coNP 167 / 174

115 475 villes

Les Classes NP et coNP 167 / 174
L’importance de la classe NP (suite)

Les Classes NP et coNP 168 / 174

L’importance de la classe NP (suite)

Conjecture P 6= NP
Un des 7 “problèmes du millénaire” du Clay Mathematics Institute
Mise-à-prix $1 000 000

Les Classes NP et coNP 168 / 174

L’importance de la classe NP (suite)

Conjecture P 6= NP
Un des 7 “problèmes du millénaire” du Clay Mathematics Institute
Mise-à-prix $1 000 000

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

Les Classes NP et coNP 168 / 174

L’importance de la classe NP (suite)

Conjecture P 6= NP
Un des 7 “problèmes du millénaire” du Clay Mathematics Institute
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 )

Les Classes NP et coNP 168 / 174

L’importance de la classe NP (suite)

Conjecture P 6= NP
Un des 7 “problèmes du millénaire” du Clay Mathematics Institute
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)

Les Classes NP et coNP 168 / 174

Et si l’oracle ne devine rien ?

La réponse “oui” est accompagnée d’un certificat grace auquel on peut vérifier que la
réponse est correcte

Si la réponse est “non”...

Les Classes NP et coNP 169 / 174

Et si l’oracle ne devine rien ?

La réponse “oui” est accompagnée d’un certificat grace auquel on peut vérifier que la
réponse est correcte

Si la réponse est “non”...il faut faire confiance !

I Ou alors vérifier avec un algorithme qui n’est pas polynomial

Les Classes NP et coNP 169 / 174

Et si l’oracle ne devine rien ?

La réponse “oui” est accompagnée d’un certificat grace auquel on peut vérifier que la
réponse est correcte

Si la réponse est “non”...il faut faire confiance !

I Ou alors vérifier avec un algorithme qui n’est pas polynomial

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

commerce ?

co-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 n’existe pas de route de longueur au plus k passant par toutes les
villes ?

Les Classes NP et coNP 169 / 174

Problème complémenaire

Problème complémenaire
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
A, et vice versa.

Les Classes NP et coNP 170 / 174

Problème complémenaire

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

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

Les Classes NP et coNP 170 / 174

Problème complémenaire

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

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

Est-ce que c’est vrai pour NP ?

Les Classes NP et coNP 170 / 174

La classe coNP

Co-problème du voyageur de commerce

donnée : ensemble de villes, entier k
question : est-ce qu’il n’existe aucun chemin passant par toutes les villes, et de
longueur inférieure à k ?

Un chemin qui ne passe pas par toutes les villes, ou de longueur > k ? pas suffisant !

Lister tous les chemins ?

Les Classes NP et coNP 171 / 174

La classe coNP

Co-problème du voyageur de commerce

donnée : ensemble de villes, entier k
question : est-ce qu’il n’existe aucun chemin passant par toutes les villes, et de
longueur inférieure à k ?

Quel est le certificat ?

Un chemin qui ne passe pas par toutes les villes, ou de longueur > k ? pas suffisant !

Lister tous les chemins ? pas polynomial !

Les Classes NP et coNP 171 / 174

La classe coNP

Co-problème du voyageur de commerce

donnée : ensemble de villes, entier k
question : est-ce qu’il n’existe aucun chemin passant par toutes les villes, et de
longueur inférieure à k ?

Quel est le certificat ?

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

Les Classes NP et coNP 171 / 174

La classe coNP

Co-problème du voyageur de commerce

donnée : ensemble de villes, entier k
question : est-ce qu’il n’existe aucun chemin passant par toutes les villes, et de
longueur inférieure à k ?

Quel est le certificat ?

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

Les complémentaires de certain problèmes dans NP ne semblent pas être dans NP

Les Classes NP et coNP 171 / 174

La classe coNP

Le complémentaire de certain problèmes dans NP ne semblent pas être dans NP

Les Classes NP et coNP 172 / 174

La classe coNP

Le complémentaire de certain problèmes dans NP ne semblent pas être dans NP

coNP
Ensemble des problèmes de décision dont le problème complément est dans NP

Conjecture
NP 6= coNP ?

Les Classes NP et coNP 172 / 174

Inclusion dans P-SPACE

Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.

Les Classes NP et coNP 173 / 174

Inclusion dans P-SPACE

Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.

il existe un algorithme déterministe qui n’utilise pas plus d’espace :

Les Classes NP et coNP 173 / 174

Inclusion dans P-SPACE

Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.

il existe un algorithme déterministe qui n’utilise pas plus d’espace :

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

Les Classes NP et coNP 173 / 174

Inclusion dans P-SPACE

Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.

il existe un algorithme déterministe qui n’utilise pas plus d’espace :

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

c
I Il y a donc un nombre fini de certificat : O(2n )

Les Classes NP et coNP 173 / 174

Inclusion dans P-SPACE

Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.

il existe un algorithme déterministe qui n’utilise pas plus d’espace :

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

c
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 ))

Les Classes NP et coNP 173 / 174

Inclusion dans P-SPACE

Soit un algorithme non-déterministe en O(nc ) temps, et donc mémoire.

il existe un algorithme déterministe qui n’utilise pas plus d’espace :

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

c
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 ))

Théorème
NP ⊆ P-SPACE et coNP ⊆ P-SPACE

Les Classes NP et coNP 173 / 174

Résumé : les classes de complexité
Résumé : les classes de complexité

P
Résumé : les classes de complexité

(log n)-TIME
Résumé : les classes de complexité

P
..
.

n-TIME
..
.

(log n)-TIME
Résumé : les classes de complexité

N
P
P
..
.

n-TIME
..
.

(log n)-TIME
Résumé : les classes de complexité

N
N

P
co

P
..
.

n-TIME
..
.

(log n)-TIME
Résumé : les classes de complexité

P-SPACE

N
N

P
co

P
..
.

n-TIME
..
.

(log n)-TIME
Résumé : les classes de complexité

EXP-TIME

P-SPACE

N
N

P
co

P
..
.

n-TIME
..
.

(log n)-TIME

Les Classes NP et coNP 174 / 174

Vous aimerez peut-être aussi

Algorithmes et Complexité en Informatique
Pas encore d'évaluation
Algorithmes et Complexité en Informatique
810 pages
Programmation Dynamique du TSP
Pas encore d'évaluation
Programmation Dynamique du TSP
115 pages
Algorithmique Avancé Et Complexité - Algorithme A Etoile PDF
Pas encore d'évaluation
Algorithmique Avancé Et Complexité - Algorithme A Etoile PDF
26 pages
Recherche opérationnelle et CSP en 60h
Pas encore d'évaluation
Recherche opérationnelle et CSP en 60h
71 pages
Programmation dynamique pour le TSP
Pas encore d'évaluation
Programmation dynamique pour le TSP
41 pages
Problème Du Voyageur de Commerce: Une Et Une Seule Fois
Pas encore d'évaluation
Problème Du Voyageur de Commerce: Une Et Une Seule Fois
19 pages
Handout
Pas encore d'évaluation
Handout
45 pages
Complexité et Algorithmes Efficaces
Pas encore d'évaluation
Complexité et Algorithmes Efficaces
25 pages
Optimisation des Transports en Commun
0% (1)
Optimisation des Transports en Commun
3 pages
Génération de labyrinthes parfaits
Pas encore d'évaluation
Génération de labyrinthes parfaits
90 pages
Examen Algorithmique M1 - Corrigé
Pas encore d'évaluation
Examen Algorithmique M1 - Corrigé
7 pages
Algorithmes Gloutons Activités
Pas encore d'évaluation
Algorithmes Gloutons Activités
4 pages
Le Probeme de Voyageur de Commerce Et La Coloration Des Sommets D'un Graphe
Pas encore d'évaluation
Le Probeme de Voyageur de Commerce Et La Coloration Des Sommets D'un Graphe
9 pages
Agro Veto TB 0725 SP
Pas encore d'évaluation
Agro Veto TB 0725 SP
6 pages
Recherche Operationnelle Chap1
Pas encore d'évaluation
Recherche Operationnelle Chap1
34 pages
Introduction à la recherche opérationnelle
100% (1)
Introduction à la recherche opérationnelle
34 pages
ESP 1 Intro
Pas encore d'évaluation
ESP 1 Intro
51 pages
Problèmes d'exploration en IA
Pas encore d'évaluation
Problèmes d'exploration en IA
4 pages
Algorithme de Dijkstra et Modélisation des Chemins
Pas encore d'évaluation
Algorithme de Dijkstra et Modélisation des Chemins
36 pages
Cours Algo Recherche
Pas encore d'évaluation
Cours Algo Recherche
46 pages
Algorithmes de Recherche et Résolution de Puzzles
Pas encore d'évaluation
Algorithmes de Recherche et Résolution de Puzzles
199 pages
Algorithme A* pour Tactical RPG
Pas encore d'évaluation
Algorithme A* pour Tactical RPG
8 pages
Output
Pas encore d'évaluation
Output
41 pages
Modélisation et Représentation des Graphes
Pas encore d'évaluation
Modélisation et Représentation des Graphes
29 pages
PVC: Étude Théorique et Expérimentale
100% (1)
PVC: Étude Théorique et Expérimentale
22 pages
Fabrique D' Ecrans: Aide ' Alad Ecision en Entreprise
Pas encore d'évaluation
Fabrique D' Ecrans: Aide ' Alad Ecision en Entreprise
2 pages
Recherche Operationnelle Chap2
Pas encore d'évaluation
Recherche Operationnelle Chap2
70 pages
Algorithmes de recherche et stratégies
Pas encore d'évaluation
Algorithmes de recherche et stratégies
81 pages
Introduction à l'optimisation combinatoire
Pas encore d'évaluation
Introduction à l'optimisation combinatoire
45 pages
TP IA : Programmation de Labyrinthe
Pas encore d'évaluation
TP IA : Programmation de Labyrinthe
3 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
70 pages
Optimisation Combinatoire IX
Pas encore d'évaluation
Optimisation Combinatoire IX
18 pages
Résolution de Problèmes et Algorithmes
Pas encore d'évaluation
Résolution de Problèmes et Algorithmes
39 pages
Recherche de Chemin par Cartographie
Pas encore d'évaluation
Recherche de Chemin par Cartographie
21 pages
Exercices de récursivité et algorithmes
Pas encore d'évaluation
Exercices de récursivité et algorithmes
26 pages
Exemples d'algorithmes récursifs en C
Pas encore d'évaluation
Exemples d'algorithmes récursifs en C
26 pages
Devoir sur Algorithmes et Structures
Pas encore d'évaluation
Devoir sur Algorithmes et Structures
3 pages
Introduction à la Recherche Opérationnelle
Pas encore d'évaluation
Introduction à la Recherche Opérationnelle
2 pages
Introduction à l'IA et théorie des jeux
Pas encore d'évaluation
Introduction à l'IA et théorie des jeux
36 pages
Chemins les plus courts à Maroua
Pas encore d'évaluation
Chemins les plus courts à Maroua
17 pages
Examen final INF4705 : Algorithmes et Complexité
Pas encore d'évaluation
Examen final INF4705 : Algorithmes et Complexité
5 pages
Optimisation du Voyageur de Commerce
Pas encore d'évaluation
Optimisation du Voyageur de Commerce
16 pages
Recherche Opérationnelle et Graphes
Pas encore d'évaluation
Recherche Opérationnelle et Graphes
138 pages
Complexité des Algorithmes et Problèmes
Pas encore d'évaluation
Complexité des Algorithmes et Problèmes
4 pages
Concours X 2015 : Épreuve Informatique PSI PT
Pas encore d'évaluation
Concours X 2015 : Épreuve Informatique PSI PT
6 pages
Problèmes NP-complets en graphes
Pas encore d'évaluation
Problèmes NP-complets en graphes
3 pages
Itc Xpsi2015
Pas encore d'évaluation
Itc Xpsi2015
5 pages
Chapitre 1
Pas encore d'évaluation
Chapitre 1
17 pages
Méthodes de résolution de problèmes
Pas encore d'évaluation
Méthodes de résolution de problèmes
57 pages
CentraleSupélec 2023 MPI Informatique e
Pas encore d'évaluation
CentraleSupélec 2023 MPI Informatique e
7 pages
Tpe Introduction A La Logigue
Pas encore d'évaluation
Tpe Introduction A La Logigue
17 pages
UPL1874579932732877547 Claire Mathieu LI2017
Pas encore d'évaluation
UPL1874579932732877547 Claire Mathieu LI2017
77 pages
Résolution du problème du voyageur de commerce
100% (1)
Résolution du problème du voyageur de commerce
3 pages
1 La Complexit e de Certaines Probl Ematiques
Pas encore d'évaluation
1 La Complexit e de Certaines Probl Ematiques
4 pages
3 Recherche
Pas encore d'évaluation
3 Recherche
88 pages
Systèmes de numération et conversions numériques
Pas encore d'évaluation
Systèmes de numération et conversions numériques
2 pages
Automates et Langages Réguliers en OCaml
Pas encore d'évaluation
Automates et Langages Réguliers en OCaml
2 pages
Transcodage et codage binaire explicatif
Pas encore d'évaluation
Transcodage et codage binaire explicatif
6 pages
Algèbre de Boole : Concepts et Méthodes
Pas encore d'évaluation
Algèbre de Boole : Concepts et Méthodes
62 pages
Optimisation du Bin Packing
Pas encore d'évaluation
Optimisation du Bin Packing
106 pages
Problèmes NP-complets en algorithmique
Pas encore d'évaluation
Problèmes NP-complets en algorithmique
28 pages
Suites numériques : propriétés et limites
Pas encore d'évaluation
Suites numériques : propriétés et limites
77 pages
Devoir Electronique Numerique 1
100% (1)
Devoir Electronique Numerique 1
6 pages
Codes Numériques en Systèmes de Caisse
Pas encore d'évaluation
Codes Numériques en Systèmes de Caisse
5 pages
Automates : Définition et Représentation
Pas encore d'évaluation
Automates : Définition et Représentation
35 pages
1ste Atc Exercices 32 35
Pas encore d'évaluation
1ste Atc Exercices 32 35
4 pages
Conversion et Analyse des Bases Numériques
Pas encore d'évaluation
Conversion et Analyse des Bases Numériques
3 pages
Correction Examen TLA Janvier2024
Pas encore d'évaluation
Correction Examen TLA Janvier2024
4 pages
628393d26101b Revision BAC TP
100% (2)
628393d26101b Revision BAC TP
11 pages
Exercices d'Électronique Numérique 2022-2023
Pas encore d'évaluation
Exercices d'Électronique Numérique 2022-2023
3 pages
Examen Logique Informatique: Exercices et Solutions
Pas encore d'évaluation
Examen Logique Informatique: Exercices et Solutions
2 pages
Correction des TD sur les systèmes numériques
Pas encore d'évaluation
Correction des TD sur les systèmes numériques
7 pages
Exercices sur Circuits Logiques et Codage
Pas encore d'évaluation
Exercices sur Circuits Logiques et Codage
72 pages
Introduction aux Systèmes Numériques
Pas encore d'évaluation
Introduction aux Systèmes Numériques
10 pages
Devoir de contrôle en systèmes de numération
Pas encore d'évaluation
Devoir de contrôle en systèmes de numération
3 pages
Complexité et NP-complétude
Pas encore d'évaluation
Complexité et NP-complétude
71 pages
Systèmes de Numération : Décimal, Binaire, Hexadécimal
Pas encore d'évaluation
Systèmes de Numération : Décimal, Binaire, Hexadécimal
8 pages
Conversion entre bases numériques
Pas encore d'évaluation
Conversion entre bases numériques
10 pages
Electicite Electronique
Pas encore d'évaluation
Electicite Electronique
185 pages
Le Système Binaire
Pas encore d'évaluation
Le Système Binaire
3 pages
C1 - Representation Numerique
Pas encore d'évaluation
C1 - Representation Numerique
3 pages
Theme1-1 Système de Numération Et Codage
Pas encore d'évaluation
Theme1-1 Système de Numération Et Codage
9 pages
Raisonnement Par Recurrence Exercices Methode
Pas encore d'évaluation
Raisonnement Par Recurrence Exercices Methode
2 pages
33 Wine French 2018 C
Pas encore d'évaluation
33 Wine French 2018 C
3 pages
Cours
Pas encore d'évaluation
Cours
85 pages