Complexité et approximation polynomale
Vangelis T Paschos, Vangelis T. Paschos - Collection Hermès Science
Résumé
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.
L'auteur - Vangelis T Paschos
Vangelis T Paschos est professeur d'informatique et directeur du LAMSADE.
Autres livres de Vangelis T Paschos
L'auteur - Vangelis T. Paschos
Autres livres de Vangelis T. Paschos
Sommaire
- Notions de base sur la complexité des algorythmes
- Eléments de la théorie de la complexité
- L'approximation polynomale
- Coloration, transversalité, stabilité
- Voyageur de commerce, SAC-A-DOS, MAX SAT, …
- Réductions et transfert d'approximabilité
- Inapproximabilité
Caractéristiques techniques
| PAPIER | |
| Éditeur(s) | Hermès - Lavoisier |
| Auteur(s) | Vangelis T Paschos, Vangelis T. Paschos |
| Collection | Hermès Science |
| Parution | 04/06/2004 |
| Nb. de pages | 270 |
| Format | 15,5 x 23,5 |
| Couverture | Broché |
| Poids | 422g |
| Intérieur | Noir et Blanc |
| EAN13 | 9782746209367 |
| ISBN13 | 978-2-7462-0936-7 |
Avantages Eyrolles.com
Consultez aussi
- Les meilleures ventes en Graphisme & Photo
- Les meilleures ventes en Informatique
- Les meilleures ventes en Construction
- Les meilleures ventes en Entreprise & Droit
- Les meilleures ventes en Sciences
- Les meilleures ventes en Littérature
- Les meilleures ventes en Arts & Loisirs
- Les meilleures ventes en Vie pratique
- Les meilleures ventes en Voyage et Tourisme
- Les meilleures ventes en BD et Jeunesse
- Informatique Développement d'applications Algorithmique et informatique appliquée Optimisation
- Informatique Développement d'applications Algorithmique et informatique appliquée Graphes
- Informatique Développement d'applications Algorithmique et informatique appliquée Recherche opérationnelle
- Sciences Mathématiques Mathématiques par matières Algèbre Algèbre linéaire
- Sciences Mathématiques Mathématiques par matières Recherche opérationnelle
- Sciences Mathématiques Mathématiques par matières Optimisation
- Sciences Mathématiques Mathématiques appliquées Statistiques
