Cours algorithme et exercices

 

Cours Algorithme pdf

Extrait du Cours :

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.

Algorithme Cours en pdf

Table des Matières :

1 Introduction : calcul de x

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 NP-Complétude 127

9.1 P 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.6.1 COLOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

9.6.2 3-COLOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

9.6.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

Cours Algorithme pdf