Petite introduction à l'algorithmique

Couverture......Page 1
Page de titre......Page 2
Avant-propos......Page 4
0.1. Qu\'est que l\'algorithmique ?......Page 10
0.2. Autour des mots « algorithme » et « algorithmique »......Page 15
1.1. Introduction......Page 18
1.2. Le tri par insertion......Page 19
1.3. Petite parenthèse sur les graphes et les arbres......Page 23
1.4. Le tri par fusion......Page 27
1.5. Le tri rapide......Page 35
1.6. Le tri par tas......Page 40
1.7. Complexité des tris comparatifs......Page 46
1.8. Cas de tris sans comparaison des éléments......Page 48
1.9. Quel algorithme choisir......Page 54
2 La programmation dynamique......Page 55
2.1. Calcul de la suite de Fibonacci......Page 56
2.2. Triangulations pondérées des polygones......Page 58
2.3. Produits de matrices......Page 78
3.1. Qu\'est-ce qu\'un algorithme glouton ?......Page 81
3.2. Les matroïdes pondérés......Page 82
3.3. Glouton......Page 86
3.4. Solution d\'un exemple......Page 90
3.5. Un problème d\'allocation de ressources......Page 93
3.6. Perturbations de la stratégie gloutonne......Page 96
3.6.1. Le recuit simulé......Page 97
3.6.2. Les algorithmes génétiques......Page 98
3.6.3. Les algorithmes de recherche taboue......Page 100
4.1. Un peu de théorie des langages......Page 101
4.2. Les classes P et NP......Page 108
4.3. La NP-complétude......Page 110
4.4.1. Présentation de SAT......Page 112
4.4.2. SAT est NP-complet......Page 115
4.5. Une petite liste de problèmes NP-complets......Page 117
4.5.4. Le voyageur de commerce......Page 118
4.5.8. Le problème du plus court vecteur......Page 119
4.6. Les algorithmes d\'approximation......Page 120
5 Épilogue......Page 125
Biographies......Page 126
Éléments de bibliographie......Page 138