Algorithmes d'approximation, partie I Avec quelle efficacité pouvez-vous emballer des objets dans un nombre minimum de boîtes ? Dans quelle mesure pouvez-vous regrouper des nœuds de manière à séparer à moindre coût un réseau en composants autour de quelques centres ? Ce sont des exemples de problèmes d'optimisation combinatoire NP-difficile. Il est très probablement impossible de résoudre de tels problèmes efficacement. Notre objectif est donc de donner une solution approximative qui peut être calculée en temps polynomial et qui, en même temps, a des garanties prouvables sur son coût par rapport à l'optimum.
(552 avis)
Détails à connaître
34 devoirs
Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées
Il y a 5 modules dans ce cours
Nous introduisons le sujet du cours par un exemple typique d'un problème de base, appelé Vertex Cover, pour lequel nous concevrons et analyserons un algorithme d'approximation de pointe utilisant deux techniques de base, appelées Linear Programming Relaxation et Rounding. Il s'agit d'une application simple et élémentaire de techniques puissantes.
Inclus
8 vidéos13 lectures7 devoirs1 évaluation par les pairs
Ce module montre la puissance de l'arrondi en l'utilisant pour concevoir une solution quasi-optimale à un autre problème de base : le problème du Knapsack.
Inclus
7 vidéos9 lectures7 devoirs1 évaluation par les pairs
Ce module montre la sophistication de l'arrondi en utilisant une variante astucieuse pour un autre problème de base : l'emballage des cases. (Il s'agit d'un module plus avancé)
Inclus
8 vidéos10 lectures7 devoirs1 évaluation par les pairs
Ce module présente une variante simple et puissante de l'arrondi, basée sur la probabilité : l'arrondi aléatoire. Sa puissance est appliquée à un autre problème de base, le problème de la couverture d'un ensemble.
Inclus
8 vidéos11 lectures8 devoirs1 évaluation par les pairs
Ce module approfondit la compréhension de l'arrondi aléatoire en développant une variante sophistiquée et en l'appliquant à un autre problème de base, le problème de la coupe multivoie. (Il s'agit d'un module plus avancé)
Inclus
5 vidéos8 lectures5 devoirs1 évaluation par les pairs
Instructeur
Offert par
Recommandé si vous êtes intéressé(e) par Algorithmes
Codio
Peking University
University of Illinois Urbana-Champaign
The Chinese University of Hong Kong
Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?
Avis des étudiants
Affichage de 3 sur 552
552 avis
- 5 stars
76,08 %
- 4 stars
20,83 %
- 3 stars
2,17 %
- 2 stars
0,90 %
- 1 star
0 %
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.