Complexité et approximation polynomiale

Auteur(s) :

Paschos, Vangelis T. Découvrir l'auteur

Résumé

Présente des notions de base sur la complexité algorithmique des problèmes, étudie la classe des problèmes NP-complets. Introduit les principes de la théorie de l'approximation polynomiale et analyse les algorithmes approchés pour quelques problèmes-paradigmes de la théorie de la complexité et de l'optimisation combinatoire.

Éditeur(s)
- Hermès science publications
Date
- 2004
Langues
- Français
Description matérielle
- 270 p. ; 24 x 16 cm
Sujet(s)
ISBN
- 2-7462-0936-5
Indice
- 511.3 Combinatoire et analyse combinatoire
Quatrième de couverture
- Cet ouvrage présente un domaine clé de l'informatique fondamentale, la théorie de la complexité et de l'approximation polynomiale des problèmes NP-difficiles. Nous ne connaissons pas actuellement d'algorithme polynomial (rapide) capable de résoudre de façon optimale ces problèmes, cependant si un algorithme polynomial existait, ne serait-ce que pour l'un d'entre eux, il permettrait de résoudre polynomialement (et à l'optimum) tous les autres problèmes NP-difficiles. En tout état de cause, l'existence de tels algorithmes est considérée comme très hautement improbable. Les problèmes les plus connus de la recherche opérationnelle et de l'optimisation combinatoire comme le voyageur de commerce (dans ses deux versions: minimisation et maximisation), l'ordonnancement, le stable ou la satisfaisabilité optimale sont des problèmes NP-difficiles.
  Ce livre traite l'approximation polynomiale sous deux angles complémentaires: d'une part, il met en évidence ses aspects opérationnels consistant à développer des stratégies efficientes pour la résolution d'un problème donné; d'autre part, en s'appuyant sur l'outil le plus classique de la théorie de la complexité, les réductions, il tente de classifier les problèmes combinatoires par rapport à l'existence d'algorithmes garantissant un certain niveau de qualité de résolution.
Tables des matières
- - Complexité et approximation polynomiale
  - Vangelis Th. Paschos
  - Thermes Science
  - Avant-propos
    13
  - Chapitre 1. Notions de base sur la complexité des algorithmes
    17
  - 1.1. Problème - instance17
  - 1.2. Algorithme et complexité18
  - 1.3. Notes bibliographiques
    20
  - Chapitre 2. Eléments de la théorie de la complexité
    23
  - 2.1. Problème de décision - problème d'optimisation23
  - 2.1.1. Les problèmes de décision23
  - 2.1.2. Les problèmes du calcul de la valeur optimale24
  - 2.1.3. Les problèmes d'optimisation25
  - 2.2. La classe des problèmes NP26
  - 2.3. La classe NPO27
  - 2.4. P vs. NP28
  - 2.5. Quelques mots sur la structure de NP29
  - 2.6. Réduction polynomiale30
  - 2.6.1. La réduction de Karp31
  - 2.6.2. La réduction de Turing33
  - 2.7. Une notion de complétude pour NP34
  - 2.8. Problèmes de satisfaisabilité37
  - 2.8.1. Le problème SAT37
  - 2.8.1.1. Construction de phi39
  - 2.8.1.2. Construction de phiS41
  - 2.8.1.3. Deux exemples42
  - 2.8.2. Le problème 3SAT44
  - 2.9. Quelques autres problèmes NP-difficiles45
  - 2.9.1. Min G-Transversal46
  - 2.9.1.1. Min G-Transversal isin NP46
  - 2.9.1.2. Min G-Transversal est complet pour NP46
  - 2.9.2. Min H-Transversal49
  - 2.9.2.1. Min H-Transversal isin NP49
  - 2.9.2.2. Min H-Transversal est complet pour NP49
  - 2.9.2.3. Min H-Transversal et Min G-Transversal50
  - 2.9.3. Max stable51
  - 2.9.3.1. Max stable isin NP51
  - 2.9.3.2. Max stable est NP-difficile51
  - 2.9.3.3. La NP-difficulté de Max stable revue52
  - 2.9.4. Max clique53
  - 2.9.4.1. Max clique isin NP53
  - 2.9.4.2. Max clique est NP-difficile53
  - 2.9.5. Satisfaisabilité optimale54
  - 2.9.5.1. Max Sat et max ksat, k ge 354
  - 2.9.5.2. Max 2SAT55
  - 2.9.5.3. Min Sat56
  - 2.9.6. NP-complétude aux sens fort et faible57
  - 2.10. Optimisation vs. décision59
  - 2.11. Notes bibliographiques
    60
  - Chapitre 3. L'approximation polynomiale
    65
  - 3.1. Résolution de problèmes d'optimisation NP-difficiles65
  - 3.2. Les problèmes NPO67
  - 3.3. L'évaluation des algorithmes approchés71
  - 3.3.1. Le rapport classique71
  - 3.3.2. Le rapport différentiel72
  - 3.3.3. L'erreur74
  - 3.4. Niveaux ou degrés d'approximation75
  - 3.4.1. Approximation à rapport dépendant de l'instance75
  - 3.4.2. Les classes APX et DAPX76
  - 3.4.3. Les classes PTAS et DPTAS76
  - 3.4.4. Les classes FPTAS et DFPTAS76
  - 3.5. Les classes Max-NP et Max-SNP78
  - 3.5.1. La classe Max-NP_o78
  - 3.5.2. La classe Max-SNP_o78
  - 3.5.3. Max-NP et Max-SNP80
  - 3.6. Notes bibliographiques
    80
  - Chapitre 4. Coloration, transversalité, stabilité
    83
  - 4.1. Coloration83
  - 4.1.1. Coloration d'un graphe avec Delta couleurs83
  - 4.1.1.1. Coloriage des graphes 3-connexes84
  - 4.1.1.2. Coloriage des graphes 1- et 2-connexes85
  - 4.1.1.3. L'algorithme global87
  - 4.1.2. L'approximation de coloration87
  - 4.1.3. Approximation différentielle et coloration89
  - 4.2. Min h-transversal92
  - 4.2.1. L'algorithme glouton et le cas non-pondéré92
  - 4.2.2. L'algorithme glouton et le cas pondéré95
  - 4.2.3. Un autre algorithme pour min h-transversal pondéré97
  - 4.2.4. La stratégie maître - esclave100
  - 4.3. min g-transversal102
  - 4.3.1. L'algorithme glouton102
  - 4.3.2. L'algorithme du couplage maximal103
  - 4.3.3. Un algorithme approché basé sur la programmation linéaire105
  - 4.3.4. Un algorithme approché basé sur la méthode primal-dual106
  - 4.4. Max stable107
  - 4.4.1. L'algorithme glouton107
  - 4.4.2. Max stable et recherche locale108
  - 4.4.3. Max stable et programmation linéaire109
  - 4.4.4. Min g-transversal, max stable et rapport différentiel115
  - 4.4.5. Notes bibliographiques
    115
  - Chapitre 5. Voyageur de commerce, sac-à-dos, max sat
    121
  - 5.1. Le voyageur de commerce121
  - 5.1.1. L'algorithme du plus proche voisin pour min tsp122
  - 5.1.2. L'algorithme de Christofides pour le cas métrique125
  - 5.1.3. Un algorithme approché pour min tsp12126
  - 5.1.4. TSP et approximation différentielle129
  - 5.2. Le problème de sac-à-dos135
  - 5.2.1. Programmation dynamique et sac-à-dos135
  - 5.2.1.1. Construction des tableaux135
  - 5.2.1.2. Obtention de la solution optimale136
  - 5.2.2. Un schéma complet d'approximation polynomial138
  - 5.3. Max sat140
  - 5.3.1. L'algorithme glouton de Johnson140
  - 5.3.2. Max sat et randomized rounding142
  - 5.3.2.1. Un algorithme randomisé pour Max sat142
  - 5.3.2.2. Dérandomisation146
  - 5.4. Bin packing147
  - 5.4.1. L'algorithme first fit147
  - 5.4.2. L'algorithme first fit decreasing148
  - 5.5. Min makespan150
  - 5.6. Notes bibliographiques152
  - Chapitre 6. Réductions et transfert d'approximabilité
    155
  - 6.1. La réduction stricte158
  - 6.2. La réduction continue163
  - 6.3. La L-réduction167
  - 6.3.1. Définitions167
  - 6.3.2. Exemples de L-réductions168
  - 6.3.2.1. Max 2sat supérieur ou égal_L min 2sat168
  - 6.3.2.2. max 3sat supérieur ou égal_L max 2sat169
  - 6.3.2.3. Max 2sat supérieur ou égal_L max différent de 3sat170
  - 6.3.2.4. Max différent de 3sat supérieur ou égal_L max multi-coupe170
  - 6.4. La réduction AP171
  - 6.4.1. AP-réduction et complétude dans NPO172
  - 6.4.2. AP-réduction et complétude dans APX176
  - 6.4.3. L-réduction et complétude dans APX181
  - 6.5. Réduction affine et approximation différentielle183
  - 6.5.1. La réduction affine183
  - 6.5.2. Réductions affines pour min et max tsp186
  - 6.6. La FA-réduction188
  - 6.6.1. Max sous-graphe k-coloriable et max stable190
  - 6.6.2. Max stable et max clique191
  - 6.7. Du classique au différentiel193
  - 6.8. Encore des réductions198
  - 6.8.1. Autres réductions notoires198
  - 6.8.1.1. La P-réduction198
  - 6.8.1.2. La E-réduction198
  - 6.8.1.3. La PTAS-réduction199
  - 6.8.1.4. La F-réduction201
  - 6.8.1.5. Le positionnement de la classe Max-SNP201
  - 6.8.2. La Min-NPO-complétude de min variable wsat revue201
  - 6.9. Notes bibliographiques
    204
  - Chapitre 7. Inapproximabilité
    209
  - 7.1. Inapproximabilité et complétude209
  - 7.2. L'auto-amélioration210
  - 7.3. La GAP-réduction213
  - 7.3.1. Max 3sat et max clique220
  - 7.3.2. Max 3sat221
  - 7.3.3. Max 3sat et min g-transversal223
  - 7.4. Les systèmes PCP224
  - 7.4.1. Quelques mots sur les systèmes PCP224
  - 7.4.2. La démonstration du théorème 6.5227
  - 7.5. La classe 0-DAPX228
  - 7.5.1. Max variable-wksat230
  - 7.5.2. Min et max 0-1 programmation linéaire231
  - 7.6. Notes bibliographiques
    233
  - Annexes
    235
  - A. Rappels sur les graphes235
  - A.1. Définitions de base et vocabulaire235
  - A.2. Représentation matricielle d'un graphe236
  - A.3. Configurations particulières237
  - A.4. Familles particulières de graphes238
  - A.5. Sous-graphes et paramètres particuliers239
  - B. Programmation linéaire241
  - B.1. Quelques éléments de base241
  - B.2. Dualité242
  - B.3. Les algorithmes primal-dual243
  - C. Les problèmes d'optimisation vus dans ce livre245
  - C.1. Problèmes dans les graphes et sur les systèmes d'ensembles245
  - C.1.1. Max stable (maximum independent set)245
  - C.1.2. Max clique (maximum clique)246
  - C.1.3. Min g-transversal (minimum vertex cover)246
  - C.1.4. Min stable dominant (minimum independent dominating set)247
  - C.1.5. Max sous-graphe induit biparti (maximum size induced bipartite graph)247
  - C.1.6. Max coupe (maximum cut)248
  - C.1.7. Coloration (minimum coloring)248
  - C.1.8. Min tsp, version minimisation du voyageur de commerce (minimum travelling salesman problem)249
  - C.1.9. Max tsp, version maximisation du voyageur de commerce (maximum travelling salesman problem)250
  - C.1.10. Max sous-graphe k-coloriable (maximum size k-co-lorable induced subgraph)250
  - C.1.11. Couplage maximum (maximum matching)251
  - C.1.12. Couverture minimum d'arêtes (minimum edge cover)251
  - C.1.13. Min h-transversal, plus petit transversal d'un hypergraphe (minimum set cover)251
  - C.2. Problèmes de programmation linéaire252
  - C.2.1. Min 0-1 programmation linéaire252
  - C.2.2. Max 0-1 programmation linéaire252
  - C.2.3. Sac-à-dos (knapsack)252
  - C.3. Problèmes de logique253
  - C.3.1. Max sat (maximum satisfiability)253
  - C.3.2. Min sat (minimum satisfiability)253
  - C.3.3. Max variable-wsat254
  - C.3.4. Min variable-wsat255
  - C.3.5. Max k-fonctions sat (max k-function sat)255
  - C.4. Autres problèmes255
  - C.4.1. Bin packing bin packing)255
  - C.4.2. Min makespan
    256
  - Bibliographie
    257
  - Index 267
Origine de la notice:
- Electre