Tous nos rayons

Déjà client ? Identifiez-vous

Nouveau client ?

CRÉER VOTRE COMPTE
Votre panier contient 0 article
0,00 €
Complexité et approximation polynomale

Librairie Eyrolles - Paris 5e
Indisponible

Complexité et approximation polynomale

Complexité et approximation polynomale

- Collection Hermès Science

270 pages, parution le 23/09/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

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 du livre "Complexité et approximation polynomale"

  PAPIER
Éditeur(s) Hermès - Lavoisier
Auteur(s) Vangelis T Paschos
Collection Hermès Science
Parution 23/09/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 (1)

Paiement en ligne SÉCURISÉ

Livraison dans le monde

Retour sous 15 jours

+ de 700 000 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 0 321 79 56 75 sav@commande.eyrolles.com
librairie française
Librairie française depuis 1925