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.
Il n'y a pas encore de discussion sur ce livre
Soyez le premier à en lancer une !
"On n'est pas dans le futurisme, mais dans un drame bourgeois ou un thriller atmosphérique"
L'auteur se glisse en reporter discret au sein de sa propre famille pour en dresser un portrait d'une humanité forte et fragile
Au Rwanda, l'itinéraire d'une femme entre rêve d'idéal et souvenirs destructeurs
Participez et tentez votre chance pour gagner des livres !
