Complexité et approximation polynomale

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

270 pages, parution le 04/06/2004

Ajouter à une liste

Indisponible

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

Approximation polynomiale des problèmes NP-difficiles

Découvrir tous les livres de Vangelis T Paschos

L'auteur - Vangelis T. Paschos

Autres livres de Vangelis T. Paschos

Optimisation combinatoire

Approximation polynomiale des problèmes NP-difficiles

Découvrir tous les 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