Cours et Travaux Dirigés pour apprendre à créer des algorithmes
Table des matières
1 Introduction : calcul de xn 11
1.1 Énoncé du problème . . . . . . . . . . 11
1.2 Algorithme naïf . . . . . . . . . . . . . 11
1.3 Méthode binaire . . . . . . . . . . . . 11
1.4 Méthode des facteurs . . . . . . . . . . 12
1.5 Arbre de Knuth . . . . . . . . . . . . . 12
1.6 Résultats sur la complexité . . . . . . . . . . . . 13
1.7 Exercices . . . . . . . . . . 14
1.8 Références bibliographiques . . . . . . . . . . . . 17
2 Diviser pour régner 19
2.1 Algorithme de Strassen . . . . . . . . . 19
2.2 Produit de deux polynômes . . . . . . . . . . . . 20
2.3 Master theorem . . . . . . . . . . . . . 22
2.4 Résolution des récurrences . . . . . . . . . . . . . 23
2.4.1 Résolution des récurrences homogènes . . . . . . . . 23
2.4.2 Résolution des récurrences avec second membre . . . . . . . . . 23
2.5 Multiplication et inversion de matrices . . . . . . 24
2.6 Exercices . . . . . . . . . . 25
2.7 Références bibliographiques . . . . . . . . . . . . 33
3 Programmation dynamique 35
3.1 Pièces de Monnaies . . . . . . . . . . . 35
3.2 Le problème du sac à dos . . . . . . . . . . . . . 36
3.2.1 En glouton . . . . . . . . . . . 36
3.2.2 Par programmation dynamique . . . . . . 36
3.3 Quelques exemples de programmation dynamique . . . . . . 37
3.3.1 Chaînes de matrices . . . . . . . . . . . . 37
3.3.2 Plus longue sous-suite . . . . . . . . . . . 38
3.3.3 Location de skis . . . . . . . . 40
3.4 Exercices . . . . . . . . . . 42
3.5 Références bibliographiques . . . . . . . . . . . . 50
4 Algorithmes gloutons 51
4.1 Exemple du gymnase . . . . . . 51
4.2 Coloriage d’un graphe . . . . . 52
4.2.1 Algorithme glouton 1 . . . . . . . . 53
4.2.2 Algorithme glouton 2 . . . . . . . . 53
4.2.3 Graphe d’intervalles . . . 53
4.2.4 Algorithme de Brelaz . . . . . . . . . . . . 54
4.3 Théorie des matroïdes . . . . . . . . . 54
4.3.1 Matroïdes . . . . . . . . . . . . 55
4.3.2 Algorithme glouton . . . . . . . . . . . . . 55
4.4 Ordonnancement . . . . . . . . . . . . 56
4.5 Exercices . . . . . . . . . . 57
4.6 Références bibliographiques . . . . . . . . . . . . 62
5 Tri 63
5.1 Tri rapide . . . . . . . . . . 63
5.1.1 Coût . . . . . . . . . . . . . . . 63
5.1.2 Médiane en temps linéaire . . . . . . . . . 63
5.2 Tri fusion . . . . . . . . . . 64
5.3 Tri par tas : Heapsort . . . . . . . . . 65
5.3.1 Définitions . . . . . . . . . . . 65
5.3.2 Tri par tas . . . . . . . . . . . . 65
5.3.3 Insertion d’un nouvel élément . . . . . . . 66
5.3.4 Suppression d’un élément du tas . . . . . . . . . . . 66
5.4 Complexité du tri . . . . . . . . . . . . 67
5.4.1 Les grands théorèmes . . . . . . . . . . . 67
5.4.2 Démonstration des théorèmes . . . . . . . 67
5.4.3 Peut-on atteindre la borne? . . . . . . . . 69
5.5 Exercices . . . . . . . . . . 70
5.6 Références bibliographiques . . . . . . . . . . . . 85
6 Graphes 87
6.1 Définitions . . . . . . . . . . 87
6.2 Arbres . . . . . . . . . . . . 87
6.2.1 Caractérisation . . . . . . . . . 87
6.2.2 Parcours d’arbres binaires . . . . . . . . . 88
6.2.3 Arbres binaires de recherche . . . . . . . . 91
6.3 Structures de données pour les graphes . . . . . . 93
6.4 Accessibilité . . . . . . . . . . . . . . . 97
6.4.1 Rappels sur les relations binaires . . . . . . . . . . . 97
6.4.2 Chemins dans les graphes . . . . . . . . . 98
6.4.3 Fermeture transitive . . . . . . . . . . . . 98
6.5 Plus courts chemins . . . . . . . . . . 101
6.5.1 Définitions . . . . . . . . . . . 101
6.5.2 Présentation des plus courts chemins . . . . . . . . . 101
6.5.3 Avec des poids positifs . . . . . . . . . . . 102
6.5.4 Chemins algébriques dans les semi-anneaux . . . . . 102
6.5.5 Algorithme de Dijkstra . . . . . . . . . . . 103
6.6 Parcours en largeur . . . . . . . . . . . 105
6.7 Parcours en profondeur . . . . . . . . . 107
6.7.1 Première version . . . . . . . . 107
6.7.2 Analyse fine du parcours en profondeur . . . 108
6.8 Tri topologique . . . . . . . . . 110
6.9 Forte connexité . . . . . . . . . 110
6.10 Exercices . . . . . . 110
6.11 Références bibliographiques . . . 117
7 Tables de hachage 119
7.1 Recherche en table . . . . . . . . . . . 119
7.2 Tables de hachage . . . . . . . . . . . 119
7.3 Collisions séparées . . . . . . . . . . . 120
7.4 Adressage ouvert . . . . . . . . . . . . 121
7.5 Références bibliographiques . . . . . . . . . . . . 122
8 Analyse amortie 123
8.1 Compteur . . . . . . . . . . 123
8.1.1 Méthode des acomptes . . . . . . . . . . . 123
8.1.2 Méthode du potentiel . . . . . . . . . . . 124
8.2 Malloc primaire . . . . . . . . . . . . . 124
8.2.1 Méthode globale . . . . . . . . 124
8.2.2 Méthode des acomptes . . . . . . . . . . . 124
8.2.3 Méthode du potentiel . . . . . . . . . . . 124
8.3 Insertion ET suppression . . . . . . . . 125
8.4 Gestion des partitions . . . . . . . . . 125
8.4.1 Représentation en listes chaînées . . . . . . . . . . . 125
8.4.2 Représentation en arbres . . . . . . . . . . 125
8.5 Références bibliographiques . . . . . . . . . . . . 126
9 9NP.-ComplétudeP versus NP . . . . . . . . . . . . . . . 127
9.2 3-SAT . . . . . . . . . . . . 127
9.3 Clique . . . . . . . . . . . . 129
9.4 Couverture par les sommets . . . . . . . . . . . . 130
9.5 Circuit hamiltonien . . . . . . . . . . . 130
9.6 Coloration de graphes . . . . . . . . . 131
9.1.1 COLOR . . . . . . . . . . . . . 131
9.1.2 3-COLOR . . . . . . . . . . . . 133
9.1.3 3-COLOR-PLAN . . . . . . . . 134
9.7 Exercices . . . . . . . . . . 137
9.8 Références bibliographiques . . . . . . . . . . . . 143
10 Algorithmes d’approximation 145
10.1 Définition . . . . . . . . . . 145
10.2 Vertex cover . . . . . . . . . . . . . . . 145
10.2.1 Version classique . . . . . . . . 145
10.2.2 Version pondérée . . . . . . . . 146
10.3 Voyageur de commerce : TSP . . . . . . . . . . . 147
10.3.1 Définition . . . . . . . . . . . . 147
10.3.2 Inapproximabilité de TSP : . . . . . . . . 147
10.3.3 2-approximation dans le cas où c vérifie l’inégalité triangulaire . . . . . . . 147
10.4 Bin Packing : BP . . . . . . . . . . . . 148
10.4.1 Définition . . . . . . . . . . . . 148
10.4.2 Next Fit . . . . . . . . . 149
10.4.3 Dec First Fit . . . . . . 150
10.5 2-Partition . . . . . . 150
10.5.1 NP-complétude au sens faible et au sens fort 150
10.5.2 Approximation gloutonnes 151
10.5.3 Une (1 + !)-approximation . . . . . . . . . 152
10.5.4 FPTAS pour 2-Partition . . . . . . . . . . 154
10.6 Exercices . . . . . . . . . . 156
10.7 Références bibliographiques . . . . . . . . . . . . 158
Préface
Ce polycopié rassemble les cours et travaux dirigés (avec corrigés) du module Algorithmique de l’ENS Lyon. A l’origine prévu pour la première année du Magistère d’Informatique, le module s’intègre désormais dans la troisième année de la Licence d’Informatique. Et dire que personne ne s’est rendu compte du changement!
Cela fait à peine dix ans que j’enseigne ce cours. A défaut de changer le contenu (pour faire quoi d’autre?) ou d’utiliser autre chose que le tableau et la craie (idem?), je change les irrésistibles traits d’humour qui font tout le charme de ces séances du Mercredi (l’horaire ne change pas non plus). Et j’use toute une batterie de TD-men and women, lesquels ont apporté leur contribution au fil des ans, construisant ou améliorant des séances de travaux dirigés. Je les remercie tous sincèrement, par ordre d’apparition : Odile Millet-Botta, Tanguy Risset, Alain Darte, Bruno Durand, Frédéric Vivien, Jean-Christophe Dubacq, Olivier Bodini, Daniel Hirschkoff, Matthieu Exbrayat, Natacha Portier, Emmanuel Hyon, Eric Thierry, Michel Morvan et Yves Caniou.
Sans aucune pression ou presque, Yves Caniou et Eric Thierry ont réussi à se motiver pour rassembler les TD. L’année précédente, j’avais rassemblé les cours. Enfin, quand on dit rassembler, c’est surtout les gentils étudiants-scribes qui rassemblent, en tapotant de leurs doigts agiles la quintessence de notre enseignement inégalable.
Ce polycopié est le concurrent le plus sérieux du Cormen dans le monde, ou du moins dans le septième arrondissement de Lyon! Mais renonçant à de fabuleux droits d’auteur, l’équipe pédagogique (c’est nous) a décidé de mettre cet ouvrage à la libre disposition des nombreux étudiants assoiffés de savoir (c’est vous). Enjoy! Et merci de signaler erreurs et omissions par courrier électronique à .
Lyon, Mai 2005
Yves Robert
Biblio
Voici quelques pointeurs bibliographiques (voir aussi les références données à la fin de chaque chapitre) :
Introduction to Algorithms de T. H. Cormen, C. E. Leiserson et R. L. Rivest [2]. L’ouvrage de référence par excellence, à acheter et conserver toute sa vie d’informaticien. Il se murmure qu’une deuxième édition est parue, avec un auteur de plus. Et une traduction française.
Computers and Intractability, a Guide to the Theory of NP-Completeness de M. R. Garey et D. S. Johnson [5]. Essentiellement pour son introduction à la NP-complétude au sens fort, et quelques jolies réductions. On revient toujours à son catalogue de problèmes NP-complets.
The art of Computer Programming , les trois tomes de Knuth [6], et bientôt quatre, pour
leurs exercices incroyables
Sinon, j’aime bien :
– Types de Données et Algorithmes, le livre de Froidevaux, Gaudel et Soria [3], pour l’analyse fine des problèmes de tri
– le NP-compendium, maintenu sur le Web ( ), pour les résultats d’approximation. Le livre qui correspond, Complexity and Approximation, de Ausiello et al. [1] est vraiment très complet, avec une bonne introduction aux schémas d’approximation.
– Algorithms and Complexity, le livre de Wilf [12], dont la première édition, épuisée, est disponible librement à l’url Une jolie introduction à la NP-complétude, avec une preuve concise du théorème de Cook, plein d’algorithmes, de l’humour, dans un fichier .pdf à télécharger absolument
– Compared to what? : an introduction to the analysis of algorithms, le livre de Rawlins [8], qui contient une mine d’exercices originaux
– Introduction to Graph Theory, de West [11], mon livre préféré de graphes
Enfin, deux livres plus difficiles, à réserver aux plus aventureux : celui de Kozen [7], The design and analysis of algorithms, contient les notes de cours et exercices (certains corrigés) d’un cours de niveau avancé donné à Cornell, et celui de Vazirani [10], Approximation algorithms, dont le titre résume bien le contenu.
10
Chapitre 1
Introduction : calcul de xn
1.1 Énoncé du problème
On étudie le problème du calcul de xn, étant donnés x et n (n étant un entier positif). Soulignons que x n’est pas nécessairement un nombre, il peut s’agir d’une matrice ou d’un polynôme à plusieurs indéterminées : si la multiplication a un sens, la division n’en a pas!
On pose y0 = x, et on utilise la “règle du jeu” suivante : si j’ai déjà calculé y1,y2, ,yi?1, je peux calculer yi comme produit de deux résultats précédents arbitraires :
yi = yj · yk, avec 0 ? j,k ? i ? 1
Le but est d’atteindre xn le plus vite possible, i.e. de trouver Opt(n) = min{i/yi = xn}.
1.2 Algorithme naïf
Considérons l’algorithme naïf suivant :
yi = y0 · yi?1 On a yn?1 = xn, le coût est donc de n ? 1.
1.3 Méthode binaire
On trouve facilement un algorithme plus efficace :
xn= ! n/x2n/2 · xn/n/22 si n est pair, x" # · x" # · x si n est impair.
On peut aussi formuler l’algorithme de la façon suivante. On écrit n en écriture binaire. Puis on remplace chaque “1” par SX et chaque “0” par S, et on enlève le premier SX (celui qui est à gauche). Le mot obtenu donne un façon de calculer xn, en traduisant S par l’opération mettre au carré (squaring), et X par l’opération multiplier par x. Par exemple, pour n = 23, la chaîne obtenue est SX S SX SX SX, en enlevant le premier SX, on obtient SSXSXSX. On calcule donc dans l’ordre x2, x4, x5, x10, x11, x22, et x23.
La correction de l’algorithme se justifie facilement à partir des propriétés du système binaire.
Le coût est de :
#logn$ + ?(n) ? 1,
où ?(n) représente le nombre de 1 dans l’écriture binaire de n. Bien sûr, comme dans tout ouvrage d’informatique qui se respecte, les logarithmes sont en base 2.
Cette méthode binaire n’est pas optimale : par exemple avec n = 15, on obtient la chaîne
SXSXSX,multiplicationsd’où p6ourmutrouvltiplicationer y =2 xa43lors(y5 =que(xe·nx)r·emarquanx) puis dte q3ueautres15 =pour3 · calculer5, on a xb15eso=iny5d(eon2 applique la méthode binaire : y ,y ,y ).
1.4 Méthode des facteurs
La méthode des facteurs est basée sur la factorisation de n :
n=(xnp)1q si p est le plus petit facteur premier de n,xx ? · x sin est premier.
Remarque : Avec les puissances de 2, cette méthode est identique à la méthode binaire.
Remarque : Cette méthode n’est pas optimale, par exemple pour n = 33 on a 7 multiplications avec la méthode des facteurs et seulement 6 avec la méthode binaire.
Remarque : Il existe une infinité de nombres pour lesquels la méthode des facteurs est meilleure que la méthode binaire (prendre n = 15·2k), et réciproquement (prendre n = 33·2k).
Il faut souligner que le coût de la recherche de la décomposition de n en facteurs premiers n’est pas pris en compte dans notre formulation. C’est pourtant nécessaire pour quantifier correctement le coût de la méthode des facteurs. Le problème est qu’on ne sait pas, à ce jour, trouver la décomposition en temps polynomial en n.
1.5 Arbre de Knuth
Une autre méthode consiste à utiliser l’arbre de Knuth, représenté Figure 1.1. Le chemin menant de la racine de l’arbre à n indique une séquence d’exposants permettant de calculer xn de façon efficace.
Fig. 1.1 – Les sept premiers niveaux de l’arbre de Knuth.
Construction de l’arbre Le (k + 1)-ème niveau de l’arbre est défini à partir des k premiers niveaux de la façon suivante : prendre chaque nœud n du k-ème niveau, de gauche à droite, et les relier avec les nœuds
n + 1,n + a1,n + a2, ,n + ak?1 = 2n
(dans cet ordre), où 1,a1, ,ak?1 = n représente le chemin de la racine à n. On n’ajoutera pas un nœud si celui ci est déjà présent dans l’arbre.
Voici quelques statistiques dues à Knuth : les plus petits nombres pour lesquels la méthode n’est pas optimale sont n = 77,154,233. Le plus petit n pour lequel la méthode de l’arbre est supérieure à la fois à la méthode binaire et à celle des facteurs est n = 23. Le plus petit n pour delequeltelslacasméthosont drarese de:l’arbrepour nest? 100000moins ,bl’arbreonne quebatcelleles facteursdes facteurs88803estfois,n =fait19879matc=h 103nul 11191· 193; fois et perd seulement 6 fois.
1.6 Résultats sur la complexité
Théorème 1. Opt(n) ? &logn'
Preuve. Soit un algorithme permettant de calculer les puissances de x, avec pour tout i, yi = x?(i). Montrons par récurrence que ?(i) ? 2i. Pour la base, on a bien y0 = x d’où 1 ? 20 = 1.
Soit iun entier, il existe j et k(j,k<k) tels que yi = yj ·)yk?. O2in?1a. ?O(ni)e=n?déduit(j) + ?donc(k), qpuear l’hypothèse d’induction,?(j) ? 2j ? 2i?1et de même ?(k
?(i) ?tuitiv2i?1emen+ 2i?t,1la=preuv2i. e exprime qu’on ne peut pas faire mieux que doubler l’exposant obtenu In à chaque étape de l’algorithme.
Grâce au théorème précédent, et à l’étude de la méthode binaire, dont le nombre d’étapes est inférieur à 2logn, on a le résultat suivant :
.
Théorème 2.
Preuve. L’idée est d’améliorer la méthode binaire en appliquant cette méthode en base m.
Posons m = 2k, où k sera déterminé plus tard, et écrivons n en base m :
n = ?0mt + ?1mt?1+ ··· + ?t,
oùx chaque ?i est un “chiffre” en base m, donc compris entre 0 et m ?ltiplications.1. Puis on calculeEn fait,touson n’ales d, 1 ? d ? m ? 1) par la méthode naïve, ce qui requiert m ? 2 mu
pas forcément besoin de toutes ces valeurs, seulement des x?i, mais comme on les calcule “au vol” on peut les calculer tous sans surcoût.
Ensuite on calcule successivement :
yy12 = (x2?0)m ·?x0m?1+?1)m+?2
= (y1)m
- · x? = x(
yt = (yt?1)m · x?t = xn
On effectue pour chaque ligne k +1 opérations (k élévations au carré pour calculer la puissance m-ème, et une multiplication), d’où le coût total du calcul de xn :
t · (k + 1) + (m ? 2).
En remplaçant m par 2k, et t par #logm n$, on trouve un coût total de
Il suffit donc de prendre k tendant vers l’infini, pour que (k + 1)/k tende vers 1, et tel que 2k = o(logn), par exemple k = #1/2log(logn)$ (on aura alors 2k ? ?logn).
1.7 Exercices
Exercice 1.7.1. Le grand saut
Le problème est de déterminer à partir de quel étage d’un immeuble, sauter par une fenêtre est fatal. Vous êtes dans un immeuble à n étages (numérotés de 1 à n) et vous disposez de k étudiants. Il n’y a qu’une opération possible pour tester si la hauteur d’un étage est fatale : faire sauter un étudiant par la fenêtre. S’il survit, vous pouvez le réutiliser ensuite, sinon vous ne pouvez plus.
Vous devez proposer un algorithme pour trouver la hauteur à partir de laquelle un saut est fatal (renvoyer n + 1 si on survit encore en sautant du n-ème étage) en faisant le minimum de sauts.
1 - Si k ? &log2(n)', proposer un algorithme en O(log2(n)) sauts.
2 - Si k < &log2(n)', proposer un algorithme en sauts. 3 - Si k = 2, proposer un algorithme en O(?n) sauts.
Correction.
1 - La complexité en O(log2(n)) qui est indiquée nous aiguille vers une dichotomie. En effet,
uni à étudiann ? 1 sit ladepuisncoushutegaranleànétéèmetitf?atale,étage,alors&log2queetoù(nsur)'nl’on, =olesnojobtienétages?btieni/t2t,ledepuislebrésultatonneànrésultatjitérandanssurt(lellorsqu’illeescasproétagesconcédénetraire.desresteuri àlesLajpluséenméthotagesjetanqu’undedet en supposant que l’on a k
dichotomique
seul étage, c’est-à-dire lorsque l’on calcule pour les étages de i = j), et ce avec une complexité logarithmique dans le pire des cas.
la2 -métho Puisqu’ici de diconhotomiquene disposepqueropodséee k p<récédemmen&log2(n)' étudiant. Cepts,endanon tn,eopneutvaprasemédierappliquerau pdirectemenroblème det manière simple en appliquant une recherche dichotomique avec k ? 1Onétudianse sertts,alorsde dumanièredernierà délimiter un intervalle d’étages dans lequel se trouve l’étage recherché. étudiant restant pour parcourir l’intervalle de façon linéaire, donc en le jetant de chaque étage enétudianpartants,tsdui l’on plus n’abaspasde encore l’inter v trouvalle, é jusqu’au le bon étage,plus resteAprèsexactemenavoir jetét n/les2k?k1?étages1 premiers dans l’intervalle de recherche, d’où une complexité dans le pire des cas en O(k + n/2k?1) sauts.
3 - Dans le cas particulier où l’on a k = 2, on ne veut pas avoir à tester chaque étage de façon linéaire, c’est pourquoi on va reprendre à notre compte les idées précédentes, et notamment celle qui consiste à délimiter un intervalle de recherche. Nous découpons donc l’ensemble des étages en “tranches” de ?n étages, avant de jeter le premier étudiant de chacun des étages de début de tranche. Lorsque l’étudiant y laisse sa peau, on se ramène au dernier étage n testé qui ne soit pas fatal, et on n’a plus qu’à parcourir de manière linéaire l’intervalle allant de l’étage n+1 à l’étage fatal trouvé précédemment. On a ainsi deux séries d’essais en O(?n), et donc une complexité finale dans le pire des cas également en O(?n) sauts.
Exercice 1.7.2. Cherchez la star
Dans un groupe de n personnes (numérotées de 1 à n pour les distinguer), une star est quelqu’un qui ne connait personne mais que tous les autres connaissent. Pour démasquer une star, s’il en existe une, vous avez juste le droit de poser des questions, à n’importe quel individu i du groupe, laduvtéyrité.pe “est-ce On veut que uv nous algorithme connaissez quij ?”trouv(notée une“i ?star,j ?”),s’il on en supp existe ,oseqoueus les i non individus qui garan réptiton d en qu’il t n’y a pas de star dans le groupe, en posant le moins de questions possibles.
1 - Combien peut-il y avoir de stars dans le groupe?
2 - Ecrire le meilleur algorithme que vous pouvez et donner sa complexité en nombre de questions (on peut y arriver en O(n) questions).
3 - Donner une borne inférieure sur la complexité (en nombre de questions) de tout algorithme résolvant le problème. ((Difficile) prouver que la meilleure borne inférieure pour ce problème est 3n ? #log2(n)$ ? 3).