À propos de ce cours
4.8
41 notes
9 avis
100 % en ligne

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.
Heures pour terminer

Approx. 12 heures pour terminer

Recommandé : 8 hours/week...
Langues disponibles

Anglais

Sous-titres : Anglais
100 % en ligne

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.
Heures pour terminer

Approx. 12 heures pour terminer

Recommandé : 8 hours/week...
Langues disponibles

Anglais

Sous-titres : Anglais

Programme du cours : ce que vous apprendrez dans ce cours

Semaine
1
Heures pour terminer
6 heures pour terminer

Linear Programming Duality

This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality....
Reading
9 videos (Total 87 min), 11 lectures, 9 quiz
Video9 vidéos
Properties of LP duality6 min
Geometry of LP duality10 min
Proof of weak duality theorem6 min
Changing the form of the LP10 min
Complementary slackness5 min
Primal-dual algorithms5 min
Vertex cover by primal-dual23 min
Conclusion3 min
Reading11 lectures
Slides10 min
Comment10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides-all10 min
Quiz8 exercices pour s'entraîner
Quiz 16 min
Quiz 22 min
Quiz 32 min
Quiz 44 min
Quiz 54 min
Quiz 64 min
Quiz 72 min
Quiz 84 min
Semaine
2
Heures pour terminer
5 heures pour terminer

Steiner Forest and Primal-Dual Approximation Algorithms

This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem....
Reading
8 videos (Total 73 min), 9 lectures, 9 quiz
Video8 vidéos
A special case: Steiner tree12 min
LP relaxation for Steiner forest6 min
... and its dual4 min
Primal-dual algorithm, Part110 min
Primal-dual algorithm,Part 212 min
Analysis13 min
Proof of the main lemma9 min
Reading9 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides-all10 min
Quiz8 exercices pour s'entraîner
Quiz 16 min
Quiz 24 min
Quiz 34 min
Quiz 44 min
Quiz 54 min
Quiz 66 min
Quiz 74 min
Quiz 86 min
Semaine
3
Heures pour terminer
5 heures pour terminer

Facility Location and Primal-Dual Approximation Algorithms

This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem....
Reading
9 videos (Total 64 min), 10 lectures, 9 quiz
Video9 vidéos
A linear programming relaxation4 min
...and its dual8 min
A primal-dual algorithm7 min
Analyzing the service cost7 min
Analyzing the facility opening cost7 min
A better algorithm11 min
Analysis7 min
Conclusion4 min
Reading10 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides-all10 min
Quiz8 exercices pour s'entraîner
Quiz 12 min
Quiz 24 min
Quiz 34 min
Quiz 44 min
Quiz 52 min
Quiz 62 min
Quiz 72 min
Quiz 86 min
Semaine
4
Heures pour terminer
6 heures pour terminer

Maximum Cut and Semi-Definite Programming

We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem....
Reading
11 videos (Total 76 min), 12 lectures, 10 quiz
Video11 vidéos
A 2-approximation5 min
A linear programming relaxation...11 min
...with an integrality gap of almost 210 min
Proof of Lemma7 min
A quadratic programming relaxation4 min
General facts about semidefinite programming7 min
A rounding algorithm7 min
Analysis6 min
General facts about MaxCut6 min
The end!3 min
Reading12 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Sldies10 min
Slides10 min
Slides-all10 min
Comment10 min
Quiz9 exercices pour s'entraîner
Quiz 14 min
Quiz 24 min
Quiz 32 min
Quiz 42 min
Quiz 54 min
Quiz 62 min
Quiz 72 min
Quiz 82 min
Quiz 92 min

Enseignant

À propos de École normale supérieure

L’École normale supérieure (ENS) est un établissement d'enseignement supérieur pour les études prédoctorales et doctorales (graduate school) et un haut lieu de la recherche française. L'ENS offre à 300 nouveaux étudiants et 200 doctorants chaque année une formation de haut niveau, largement pluridisciplinaire, des humanités et sciences sociales aux sciences dures. Régulièrement distinguée au niveau international, l'ENS a formé 10 médailles Fields et 13 prix Nobel....

Foire Aux Questions

  • Une fois que vous êtes inscrit(e) pour un Certificat, vous pouvez accéder à toutes les vidéos de cours, et à tous les quiz et exercices de programmation (le cas échéant). Vous pouvez soumettre des devoirs à examiner par vos pairs et en examiner vous-même uniquement après le début de votre session. Si vous préférez explorer le cours sans l'acheter, vous ne serez peut-être pas en mesure d'accéder à certains devoirs.

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.