Cours

Description

Algorithmique avancéeIUP 2Frédéric Vivien24 avril 20022Table des matières1 Introduction 91.1 Qu’est ce que l’algorithmique ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9n1.2 Motivation : calcul de x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.1 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.2 Algorithme trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2.3 Méthode binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2.4 Algorithme des facteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2.5 de l’arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2.6 Et après ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Complexité et optimalité ; premier algorithme de tri 132.1 Définition de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1.1 Notations de Landau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1.3 Modèle de machine . . . . ...

Informations

• Publié par: Phewyur
• Nombre de lectures: 52
• Langue: Français

Extrait

Algorithmique avancée

IUP 2

Frédéric Vivien

24 avril 2002

2

Table

1

2

3

des

matières

Introduction 1.1 Qu’est-ce que l’algorithmique ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Motivation : calcul dex n . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Algorithme trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Méthode binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.4 Algorithme des facteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.5 Algorithme de l’arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.6 Et après ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Complexité et optimalité ; premier algorithme de tri 2.1 Dénition de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Notations de Landau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Modèle de machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Illustration : cas du tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Problématique du tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Principe du tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

La récursivité et le paradigme « diviser pour régner » 3.1 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Récursivité simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Récursivité multiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Récursivité mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.5 Récursivité imbriquée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.6 Principe et dangers de la récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.7 Non décidabilité de la terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.8 Importance de l’ordre des appels récursifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.9 Exemple d’algorithme récursif : les tours de Hanoï . . . . . . . . . . . . . . . . . . . . . . . 3.2 Dérécursivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Récursivité terminale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Récursivité non terminale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Diviser pour régner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Premier exemple : multiplication naïve de matrices . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Analyse des algorithmes « diviser pour régner » . . . . . . . . . . . . . . . . . . . . . . . . .

3

9 9 9 9 10 10 11 12 12 12

13 13 13 13 14 14 14 14 14 14 15

17 17 17 17 17 18 18 18 19 19 20 21 21 22 23 23 23 24 24

4

4

5

6

7

8

3.3.4 3.3.5

Résolution des récurrences . . . . . . . . . . . . . Deuxième exemple : algorithme de Strassen pour la

TABLE

. . . . . . . . . . . . . . . . multiplication de matrices .

DES

. . . . . .

MATIÈRES

. . . . . . . .

Algorithmes de tri 4.1 Tri par fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Tri par tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Dénition d’un tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Conservation de la structure de tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Construction d’un tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Algorithme du tri par tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Tri rapide (Quicksort) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Structures de données élémentaires 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Piles et les . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Listes chaînées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Algorithmes de manipulation des listes chaînées . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Comparaison entre tableaux et listes chaînées . . . . . . . . . . . . . . . . . . . . . . . . . .

Programmation dynamique 6.1 Multiplication d’une suite de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Éléments de programmation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Sous-structure optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Sous-problèmes superposés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Recensement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Algorithmes gloutons 7.1 Location d’une voiture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Éléments de la stratégie gloutonne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.1 Propriété du choix glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.2 Sous-structure optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Fondements théoriques des méthodes gloutonnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Matroïdes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 Algorithmes gloutons sur un matroïde pondéré . . . . . . . . . . . . . . . . . . . . . . . . .

Graphes et arbres 8.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Parcours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Parcours des arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Parcours des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 25

29 29 29 29 30 31 31 31 32 33 33 33 36 37

39 39 39 39 40 42 42 43 44

47 47 51 51 51 51

53 53 54 54 54 55 55 55

57 57 58 60 60 61

TABLE DES MATIÈRES

9

10

11

Arbres de recherche et arbres de recherche équilibrés 9.1 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.2 Recherches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.3 Insertion d’un élément . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.4 Suppression d’un élément . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.5 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Arbres rouge et noir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.2 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.4 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.5 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Plus courts chemins 10.1 Plus courts chemins à origine unique . . . . . . . 10.1.1 Algorithme de Dijkstra . . . . . . . . . . 10.1.2 Algorithme de Bellman-Ford . . . . . . . 10.2 Plus courts chemins pour tout couple de sommets 10.2.1 Programmation dynamique naïve . . . . 10.2.2 Algorithme de Floyd-Warshall . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

NP-complétude 11.1 La classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Problèmes abstraits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 La classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.1 Algorithme de validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.2 La classe de complexité NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3.1 Réductibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3.2 Dénition de la NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3.3 Exemples de problèmes NP-complets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3.4 Preuves de NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 Heuristiques 12.1 Le problème de la couverture de sommet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.1 Heuristique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.2 Exemple d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.3 Garantie de performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Le problème du voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2.1 Exemple d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2.2 Garantie de performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

63 63 63 63 64 64 66 66 66 67 67 67 69

75 75 75 76 78 79 79

83 83 83 84 84 84 85 85 85 86 86 87

89 89 90 90 90 91 91 91

6

TABLE DES MATIÈRES

7

gures

des

Table

12 12

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. .

Arbre de puissances. . . . . . Schéma de calcul pourn=23.

1.1 1.2

. . . .

15

.

.

Exemple d’utilisation de l’algorithme T RI -I NSERTION . . . . . . . . . . . . . . . . . . .

.

20 23

2.1

. .

. . . . . . . .

. .

. .

3.1 3.2

Méthode de résolution du jeu des tours de Hanoï. . . . . . . . . . . . . . . . . . . . . . Exemple d’exécution de l’algorithme dérécursivé. . . . . . . . . . . . . . . . . . . . . .

30 30 31 32 32 33 34 35

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8

. . . . . . . .

. . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

40 40 41 41 41 42 42

43 45

Algorithme F USIONNER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme T RI -F USION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de tas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme E NTASSER . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple d’utilisation de l’algorithme E NTASSER . . . . . . . . .. . . . . . . . . . . . . Algorithme C ONSTRUIRE -T AS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple d’utilisation de l’algorithme C ONSTRUIRE -T AS . . . . . . . . . . . . . . . . . Exemple d’utilisation de l’algorithme T RIER -T AS  . . . . . . . . . . . . . . . . . . .. .

5.1

6.1

50

Exemple de manipulation de pile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implémentation d’une pile par un tableau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithmes de manipulation des piles implémentées par des tableaux. . . . . . . . . . . . . . . . . . Exemple de manipulation de le. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implémentation d’une le par un tableau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithmes de manipulation des les implémentées par des tableaux. . . . . . . . . . . . . . . . . . Exemple de manipulation de liste chaînée. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de manipulation de liste doublement chaînée. . . . . . . . . . . . . . . . . . . . . . . . . . Efcacités respectives des listes chaînées et des tableaux. . . . . . . . . . . . . . . . . . . . . . . . .

5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9

8.6 8.7 8.8 8.9 8.10 8.11 8.12 8.13

Illutration de l’algorithme O RDONNER -C HAÎNE D E M ATRICES  . . . . . . . . . . . . . . . . . . .. .

8.1 8.2 8.3 8.4 8.5

57 57 58 58 58 59 59 60 60 60 61 61 61

Exemple de graphe orienté. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de graphe non orienté. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de graphe contenant un cycle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de forêt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple d’arbre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple d’arbres qui ne diffèrent que s’ils sont enracinés. . . . . . . . . . . . . . . . . . . . . . . . Exemple d’arbres (enracinés) qui ne diffèrent que s’ils sont ordonnés. . . . . . . . . . . . . . . . . . Exemple d’arbres ordonnés qui ne différent que quand ils sont vus comme des arbres binaires. . . . . Algorithme de parcours en profondeur d’un arbre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Parcours préxe, inxe et postxe d’un arbre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme de parcours en largeur d’un arbre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme de parcours en profondeur d’un graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme de parcours en largeur d’un graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10 9.11 9.12 9.13 9.14 9.15

10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8

TABLE DES FIGURES

Deux arbres binaires de recherche contenant les mêmes valeurs. . . . . . . . . . . . . . . . . . . . . Localisation du successeur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme d’insertion dans un arbre binaire de recherche. . . . . . . . . . . . . . . . . . . . . . . . Cas de gure lors de la suppression d’un nœud d’un arbre binaire de recherche. . . . . . . . . . . . . Suppression d’un élément dans un arbre binaire de recherche. . . . . . . . . . . . . . . . . . . . . . . Exemple d’arbre rouge et noir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rotations sur un arbre binaire de recherche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme de rotation gauche pour un arbre binaire. . . . . . . . . . . . . . . . . . . . . . . . . . . Première série de congurations pathologiques pour l’insertion dans un arbre rouge et noir. . . . . . . Deuxième série de congurations pathologiques pour l’insertion dans un arbre rouge et noir. . . . . . Algorithme d’insertion dans un arbre rouge et noir. . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple d’insertion dans un arbre rouge et noir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Congurations pathologiques pour la suppression dans un arbre rouge et noir. . . . . . . . . . . . . . Suppression d’un élément dans un arbre rouge et noir. . . . . . . . . . . . . . . . . . . . . . . . . . . Correction d’un arbre rouge et noir après suppression d’un élément. . . . . . . . . . . . . . . . . . .

Algorithme de Dijkstra pour le calcul des plus courts chemins. . . . . . . . . . . . . . . . . . . . . . Exemple d’exécution de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme de Bellman-Ford pour le calcul des plus courts chemins. . . . . . . . . . . . . . . . . . . Exemple d’exécution de l’algorithme de Bellman-Ford. . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme naïf par programmation dynamique pour le calcul des plus courts chemins. . . . . . . . . Un graphe orienté et la séquence des matrices calculées par P LUS -C OURTS -C HEMINS . . . . . . . . . Algorithme de Floyd-Warshall pour le calcul des plus courts chemins. . . . . . . . . . . . . . . . . . Exemple d’exécution de l’algorithme de Floyd-Warshall. . . . . . . . . . . . . . . . . . . . . . . . .

12.1 Exemple d’utilisation de l’algorithme C OUVERTURE -S OMMET -A PPROCHÉE . . . . . . . . . . . . . . 12.2 Exemple d’utilisation de l’algorithme T OURNÉE -A PPROCHÉE  . . . . . . . . . . . . . . . . . . . .. .

Avertissement

63 64 65 65 66 67 67 68 68 69 70 71 72 73 74

76 77 77 78 80 80 81 82

90 92

Ce cours ne traite pas : – la recherche de motifs dans une chaîne de caractères (problème supposé être abondamment traité dans le cours deProgrammation Orientée Objet) ; – l’algorithmique géométrique (supposée être traitée dans les cours liés au traitement d’image).

Chapitre

1

Introduction

1.1

Qu’est-ce que l’algorithmique ?

Dénition 1 (Algorithme).Un algorithme est suite nie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème.

Historique :Le mot « algorithme » provient de la forme latine (Algorismus) du nom du mathématicien arabe AL - ¯ ¯ K HAREZMI ou AL -K HWARIZMI auteur –entre autres mais ce n’ est pas le plus important– d’un manuel de vulga- risation sur le calcul décimal positionnel indien (v. 830) expliquant son utilisation et, surtout, la manipulation des différents algorithmes permettant de réaliser les opérations arithmétiques classiques (addition, soustraction, multipli- cation, division, extraction de racines carrées, règle de trois, etc.).

Double problématique de l’algorithmique 1.Trouver une méthodede résolution (exacte ou approchée) du problème. – Soient trois nombres réelsa,betc, quelles sont les solutions de l’équationax 2 +bx+c? (Résultat bien connu.) – Soient cinq nombres réelsa,b,c,dete, quelles sont les solutions de l’équationax 5 +bx 4 +cx 3 +dx 2 +ex+f? (Pas de méthode générale, cf. la théorie de G ALOIS .) 2. Trouver une méthodeefcace. Savoir résoudre un problème est une chose, le résoudre efcacement en est une autre, comme nous allons le voir à la section 1.2.

Différences entre algorithmes et programmes

Unprogrammeest la réalisation (l’implémentation) d’un algorithme au moyen d’un langage donné (sur une architecture donnée). Il s’agit de la mise en œuvre du principe. Par exemple, lors de la programmation on s’occupera parfois explicitement de la gestion de la mémoire (allocation dynamique en C) qui est un problème d’implémentation ignoré au niveau algorithmique.

1.2

Motivation : calcul dex n

1.2.1 Problème

Données :un entier naturelnet un réelx. On veut calculerx n . Moyens :Nous partons dey 1 =x. Nous allons construire une suite de valeursy 1 , ...,y m telle que la valeury k soit obtenue par multiplication de deux puissances dexprécédemment calculées :y k =y u ×y v , avec 1≤u,v<k, k∈[2,m].

9

10

CHAPITRE 1. INTRODUCTION

But :y m =x n . Lecoûtde l’algorithme sera alors dem−1, le nombre de multiplications faites pour obtenir le résultat recherché.

1.2.2 Algorithme trivial

y i =y i−1 ×y 1 ,i∈[2,n]. Résultat :y n =x n . Coût :m−1=n−1 multiplications.

Algorithme

y[1] = x Pouri←2ànfaire y[i] = y[i−1]×y[1] renvoyery[n]

1.2.3 Méthode binaire

Algorithme

1. Écrirensous forme binaire 2. Remplacer chaque : – « 1 » par la paire de lettres «SX» ; – « 0 » par la lettre «S». 3. Éliminer la paire «SX» la plus à gauche. 4. Résultat : un mode de calcul dex n où –S« élever au carré » (signie squaring) ; –Xsignie « multiplier parx». Le tout en partant dex.

Illustration avecn=23

1.n=10111

1 0 1 1 1 2. SXSX S SX SX 3. SX SXS SX 4. Nous partons dexet nous obtenons successivement : x 2 ,x 4 ,x 5 ,x 10 ,x 11 ,x 22 ,x 23 . Nous sommes donc capables de calculerx 23 en 7 multiplications au lieu de 22 !

Explication de la méthode – Écriture binaire den:n= å i=p a2 i . i=0 i – Plaçons nous au cours du calcul de puissances dex. Soitjle dernier bit de la représentation binaire denqui ait été « décodé » et soity j le dernier résultat obtenu. Initialement,j=pety p =x=x a p . – Deux cas sont possibles poura j−1 : 1.a j−1 =1.a j−1 est remplacé parSX, nous élevonsy j au carré puis multiplions le résultat parx. Le nouveau résultat esty j−1 =y 2 j ×x. 2.a j−1 =0.a j−1 est remplacé parSet nous élevons simplementy j au carré. Le nouveau résultat esty j−1 =y j 2 . Dans tous les cas nous avons :y j−1 =y j 2 ×(x a j−1 ). – D’où,y p−1 =y 2 p ×(x a p−1 ) = (x a p ) 2 ×(x a p−1 ) = (x 2×a p )×(x a p−1 ) = (x 2×a p +a p−1 ). Par récurrence, nous pouvons i= montrer quey 1 =x å i=0 p a i 2 i =x n ...

1.2. MOTIVATION : CALCUL DEX N

Complexité (coût)

11

Note : les nombres dont la représentation binaire a exactementpchiffres forment exactement l’intervalle[2 p−1 ,2 p −1]. Nombres de chiffres dans l’écriture binaire den: 1+ [log 2 n]. NotonsΗ(n)le nombre de « 1 » dans l’écriture binaire den. Nombre d’opérations effectuées : –(1+ [log 2 n])−1 élévations au carré (ne pas oublier l’étape 3) ; –Η(n)−1 multiplications parx(ne pas oublier l’étape 3). Soit en toutT(n) = [log 2 n] +Η(n)−1 multiplications. Trivialement, 1≤Η(n)≤[log 2 n]et[log 2 n]≤T(n)≤2[log 2 n]. Pourn=effectue 999 multiplications, et la méthode binaire moins de 20.1000, l’algorithme trivial

Historique

Cette méthode a été présentée avant 200 avant J.C. en Inde, mais il semblerait qu’il ait fallu attendre un millénaire avant que cette méthode ne soit connue en dehors de l’Inde [3, p. 441].

Peut-on faire mieux ?

Prenons le casn=15.

1.n=1111 1 1 1 1 2.SX SX SX SX 3.SX SX SX 4. Nous partons dexet nous obtenons successivement :x 2 ,x 3 ,x 6 ,x 7 ,x 14 ,x 15 . Nous sommes donc capables de calculerx 15 en 6 multiplications. Autre schéma de calcul :x 2 ,x 3 ,x 6 ,x 12 ,x 15 =x 12 ×x 3 . Nous obtenons ainsix 15 en 5 multiplications et la méthode binaire n’est donc pasoptimale(c’est-à-dire que l’on peut faire mieux).

1.2.4

Algorithme des facteurs

Algorithme  xsin=1 x n =   x n ( − x 1 p ) × n 0 x s si in np = re p m ; × ie n r; 0 avecpplus petit diviseur premier den.

Illustration avecn=15 1. 15=3×plus petit diviseur (facteur) premier de 15. Donc5, 3 étant le x 15 = (x 3 ) 5 . Nous réappliquons l’algorithme pour calculerx 3 ety 5 , oùy=x 3 . 2. Calcul dex 3 : (a) 3 est premier. Doncx 3 =x 2 ×x. Nous réappliquons l’algorithme pour calculerx 2 . (b) 2 est premier. Doncx 2 =x×x. (c) Finalement,x 3 est calculé comme suit :x 3 =x×x×x, soit en deux multiplications. 3. Calcul dey 5 : (a) 5 est premier. Doncy 5 =y 4 ×y. Nous réappliquons l’algorithme pour calculery 4 . (b) 4=2×2, où 2 est le plus petit facteur premier de 4. Doncy 4 = (y 2 ) 2 . (c) Finalementy 5 est calculé comme suit :t=y×y,u=t×t,y 5 =u×y, soit en 3 multiplications. 4. Finalement,x 15 est calculé en 5 multiplications.