Dans ce cours en ligne, nous mettrons en œuvre (en Python) des programmes efficaces pour un problème dont les entreprises de livraison du monde entier ont besoin des millions de fois par jour - le problème du voyageur de commerce. L'objectif de ce problème est de visiter tous les lieux donnés le plus rapidement possible. Comment trouver rapidement une solution optimale à ce problème ? Nous ne disposons toujours pas d'algorithmes efficaces prouvés pour ce problème informatique difficile et c'est l'essence même du problème P versus NP, la question ouverte la plus importante de l'informatique. Néanmoins, nous allons implémenter plusieurs solutions pour des instances réelles du problème du voyageur de commerce, en nous appuyant fortement sur la matière apprise dans les cours de la spécialisation : techniques de preuve, combinatoire, probabilités, théorie des graphes. Nous verrons plusieurs exemples d'utilisation d'idées de mathématiques discrètes pour obtenir des solutions de plus en plus efficaces.
Durée limitée ! Obtenez Coursera Plus avec 30 % de réduction.
Réinitialiser. Réinventer. Atteindre de nouveaux objectifs professionnels. Profitez de votre offre maintenant.
Problème de livraison
Ce cours fait partie de Spécialisation Introduction aux mathématiques discrètes pour l'informatique
Enseigné en Anglais
Certains éléments de contenu peuvent ne pas être traduits
Instructeurs : Alexander S. Kulikov
20 821 déjà inscrits
Inclus avec 
Cours
(370 avis)
Détails à connaître
Ajouter à votre profil LinkedIn
8 quizzes
Cours
(370 avis)
Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées
Élaborez votre expertise du sujet
- Apprenez de nouveaux concepts auprès d'experts du secteur
- Acquérez une compréhension de base d'un sujet ou d'un outil
- Développez des compétences professionnelles avec des projets pratiques
- Obtenez un certificat professionnel partageable
Obtenez un certificat professionnel
Ajoutez cette qualification à votre profil LinkedIn ou à votre CV
Partagez-le sur les réseaux sociaux et dans votre évaluation de performance
Il y a 3 modules dans ce cours
Nous commençons ce module par la définition du modèle mathématique du problème de livraison - le problème classique du voyageur de commerce (généralement abrégé en TSP). Nous passerons ensuite en revue quelques-unes de ses nombreuses applications : des plus simples (livraison de marchandises, planification d'un voyage) aux moins évidentes (stockage et compression de données, assemblage de génomes). Ensuite, nous ferons ensemble les premiers pas dans l'implémentation de programmes pour TSP.
Inclus
4 vidéos1 lecture5 quizzes2 laboratoires non notés
Nous verrons deux techniques générales appliquées au problème du voyageur de commerce. La première, le branch and bound, est une approche classique de l'optimisation combinatoire utilisée pour divers problèmes. Elle peut être considérée comme une amélioration de la recherche par force brute : nous essayons de construire une permutation morceau par morceau, mais à chaque étape, nous vérifions s'il est toujours utile de continuer à construire la permutation (si ce n'est pas le cas, nous coupons simplement la branche en cours). La seconde, la programmation dynamique, est sans doute la technique algorithmique la plus populaire. Elle permet de résoudre un problème en passant par un ensemble de sous-problèmes plus petits.
Inclus
4 vidéos2 quizzes1 laboratoire non noté
Comme nous l'avons vu dans les modules précédents, il est difficile de résoudre exactement le problème du voyageur de commerce. En fait, nous ne nous attendons même pas à trouver une solution efficace dans un avenir proche. C'est pourquoi il est logique de se poser la question suivante : est-il possible de trouver efficacement une solution qui est probablement sous-optimale, mais qui est en même temps proche de l'optimum ? Il s'avère que la réponse est oui ! Nous allons apprendre deux algorithmes. Le premier garantit de trouver rapidement une solution qui est au plus deux fois plus longue que la solution optimale. Le second algorithme n'a pas de telles garanties, mais il est connu pour fonctionner assez bien en pratique.
Inclus
2 vidéos1 quiz1 laboratoire non noté
Instructeurs
Offert par
Recommandé si vous êtes intéressé(e) par Algorithmes
Fundação Instituto de Administração
Fundação Instituto de Administração
University of Colorado Boulder
Tsinghua University
Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?
Avis des étudiants
Affichage de 3 sur 370
370 avis
- 5 stars
76,21 %
- 4 stars
17,83 %
- 3 stars
2,97 %
- 2 stars
2,43 %
- 1 star
0,54 %
Ouvrez de nouvelles portes avec Coursera Plus
Accès illimité à plus de 7 000 cours de renommée internationale, à des projets pratiques et à des programmes de certificats reconnus sur le marché du travail, tous inclus dans votre abonnement
Faites progresser votre carrière avec un diplôme en ligne
Obtenez un diplôme auprès d’universités de renommée mondiale - 100 % en ligne
Rejoignez plus de 3 400 entreprises mondiales qui ont choisi Coursera pour les affaires
Améliorez les compétences de vos employés pour exceller dans l’économie numérique
Foire Aux Questions
L'accès aux cours et aux devoirs dépend de votre type d'inscription. Si vous suivez un cours en mode audit, vous pourrez consulter gratuitement la plupart des supports de cours. Pour accéder aux devoirs notés et obtenir un certificat, vous devrez acheter l'expérience de certificat, pendant ou après votre audit. Si vous ne voyez pas l'option d'audit :
Il se peut que le cours ne propose pas d'option d'audit. Vous pouvez essayer un essai gratuit ou demander une aide financière.
Le cours peut proposer l'option "Cours complet, pas de certificat" à la place. Cette option vous permet de consulter tous les supports de cours, de soumettre les évaluations requises et d'obtenir une note finale. Cela signifie également que vous ne pourrez pas acheter un certificat d'expérience.
Lorsque vous vous inscrivez au cours, vous avez accès à tous les cours de la Specializations, et vous obtenez un certificat lorsque vous terminez le travail. Votre certificat électronique sera ajouté à votre page de réalisations - de là, vous pouvez imprimer votre certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez uniquement lire et visualiser le contenu du cours, vous pouvez auditer le cours gratuitement.
Si vous vous êtes abonné, vous bénéficiez d'une période d'essai gratuite de 7 jours pendant laquelle vous pouvez annuler votre abonnement sans pénalité. Après cette période, nous ne remboursons pas, mais vous pouvez résilier votre abonnement à tout moment. Consultez notre politique de remboursement complète.