Po stopách obchodního cestujícího – Cook William (2012)

Imaginez que vous avez une liste de villes que vous devez visiter, chacune une fois, et à la fin de votre voyage, vous voulez rentrer chez vous. Comment trouvez-vous le chemin le plus court ? C'est l'essence du problème du voyageur de commerce. C'est très simple, et la solution l'est sûrement aussi - nous essayons simplement tous les itinéraires et choisissons le plus court. Mais il y a un hic : même avec 85 villes, il y a plus d'itinéraires qu'il n'y a d'atomes dans l'univers visible. C'est probablement ingérable. Trouver la connexion la plus courte entre de nombreux points est utilisé dans divers domaines, de la fabrication de microprocesseurs à la planification du mouvement du télescope Hubble, et en utilisant des méthodes de recherche avancées, des dizaines de milliards de dollars sont économisés chaque année. Cependant, pour les mathématiciens, peut-être le fait le plus important est que résoudre ce problème permettrait de surmonter simultanément l'un des sept plus grands problèmes mathématiques du troisième millénaire - P contre NP. En 2000, l'Institut de mathématiques Clay a offert une récompense d'un million de dollars pour une solution à chacun de ces problèmes, et c'est aussi une raison (bien que secondaire pour les mathématiciens altruistes) pour laquelle des centaines des meilleures esprits de la planète y travaillent depuis plusieurs décennies. Le thème du livre est présenté à un haut niveau d'expertise - son auteur appartient à un groupe restreint des figures les plus significatives...