Algorithmes d'approximation, partie 2 Ce cours est la suite du cours Algorithmes d'approximation, partie 1. Ici, vous apprendrez la dualité de programmation linéaire appliquée à la conception de certains algorithmes d'approximation, et la programmation semi-définie appliquée à Maxcut. En suivant les deux parties de ce cours, vous serez exposé à un éventail de problèmes aux fondements de l'informatique théorique, et à de puissantes techniques de conception et d'analyse. A la fin du cours, vous serez capable de reconnaître, face à un nouveau problème d'optimisation combinatoire, s'il est proche d'un des quelques problèmes de base connus, et vous serez capable de concevoir des relaxations de programmation linéaire et d'utiliser l'arrondi aléatoire pour tenter de résoudre votre propre problème. Le contenu du cours, et en particulier les devoirs, est de nature théorique et ne comporte pas d'exercices de programmation.
(44 avis)
Détails à connaître
33 devoirs
Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées
Il y a 4 modules dans ce cours
Ce module n'étudie pas de problème spécifique d'optimisation combinatoire. Il introduit plutôt une caractéristique centrale de la programmation linéaire, la dualité.
Inclus
9 vidéos11 lectures8 devoirs1 évaluation par les pairs
Ce module utilise la dualité de la programmation linéaire pour concevoir un algorithme pour un autre problème de base, le problème de la forêt de Steiner.
Inclus
8 vidéos9 lectures8 devoirs1 évaluation par les pairs
Ce module poursuit l'enseignement des applications algorithmiques de la dualité de la programmation linéaire en l'appliquant à un autre problème de base, le problème de localisation des installations.
Inclus
9 vidéos10 lectures8 devoirs1 évaluation par les pairs
Ce module utilise la programmation semi-définie pour concevoir un algorithme d'approximation pour un autre problème de base, le problème de la coupe maximale.
Inclus
11 vidéos12 lectures9 devoirs1 évaluation par les pairs
Instructeur
Offert par
Recommandé si vous êtes intéressé(e) par Algorithmes
École normale supérieure
EIT Digital
University of Colorado Boulder
University of Colorado Boulder
Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?
Avis des étudiants
44 avis
- 5 stars
88,63 %
- 4 stars
6,81 %
- 3 stars
2,27 %
- 2 stars
2,27 %
- 1 star
0 %
Affichage de 3 sur 44
Révisé le 28 févr. 2018
I really appreciate your valuable knowledge sharing. This is a perfect course.
Révisé le 27 oct. 2016
Demanding course with lots of great algorithm concepts based on Linear Programming.
Révisé le 13 mars 2016
It is remarkable to note that Professor Claire Mathieu explains such a complex subject in such a elegant and understandable manner.
Ouvrez de nouvelles portes avec Coursera Plus
Accès illimité à 10,000+ cours de niveau international, projets pratiques et programmes de certification prêts à l'emploi - 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.