Déjà client ? Identifiez-vous

Mot de passe oublié ?

Nouveau client ?

CRÉER VOTRE COMPTE
Complexité et approximation polynomale
Ajouter à une liste

Librairie Eyrolles - Paris 5e
Indisponible

Complexité et approximation polynomale

Complexité et approximation polynomale

Vangelis T Paschos, Vangelis T. Paschos - Collection Hermès Science

270 pages, parution le 04/06/2004

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é
Voir tout
Replier

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

Livraison à partir de 0,01 en France métropolitaine
Paiement en ligne SÉCURISÉ
Livraison dans le monde
Retour sous 15 jours
+ d'un million et demi de livres disponibles
satisfait ou remboursé
Satisfait ou remboursé
Paiement sécurisé
modes de paiement
Paiement à l'expédition
partout dans le monde
Livraison partout dans le monde
Service clients sav@commande.eyrolles.com
librairie française
Librairie française depuis 1925
Recevez nos newsletters
Vous serez régulièrement informé(e) de toutes nos actualités.
Inscription