À propos de ce cours
4.7
121 notes
34 avis
100% online

100% online

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. 21 heures pour terminer

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

Anglais

Sous-titres : Anglais...
100% online

100% online

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. 21 heures pour terminer

Recommandé : 4 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

Vertex cover and Linear Programming

We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques....
Reading
8 vidéos (Total 54 min), 13 lectures, 8 quiz
Video8 vidéos
Lecture: Definition4 min
Lecture: Integer program6 min
Lecture: A linear programming relaxation6 min
Lecture: Approximation algorithm6 min
Lecture: Analysis6 min
Lecture: General facts5 min
Half integrality (7:35 bug, fixed in pdf slides)10 min
Reading13 lectures
Slides10 min
All slides for all chapters of Approx Algs part 110 min
Attempt to upload slides in Keynote format10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Practice Exercises10 min
PDF version of the peer-graded assignment10 min
Half-integrality slides10 min
All slides together in one file10 min
Quiz7 exercices pour s'entraîner
Quiz 1: P vs. NP review6 min
Quiz 28 min
Quiz 34 min
Quiz 46 min
Quiz 54 min
Quiz 64 min
Quiz 74 min
Semaine
2
Heures pour terminer
5 heures pour terminer

Knapsack and Rounding

This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem....
Reading
7 vidéos (Total 52 min), 9 lectures, 8 quiz
Video7 vidéos
Lecture: Greedy algorithm5 min
Lecture: Special dynamic program8 min
Lecture: General dynamic program8 min
Lecture: algorithm6 min
Lecture: analysis7 min
Lecture: approximation scheme4 min
Reading9 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Practise Exercises10 min
All slides together in one file10 min
Quiz7 exercices pour s'entraîner
Quiz 12 min
Quiz 22 min
Quiz 34 min
Quiz 42 min
Quiz 52 min
Quiz 62 min
Quiz 72 min
Semaine
3
Heures pour terminer
5 heures pour terminer

Bin Packing, Linear Programming and Rounding

This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)...
Reading
8 vidéos (Total 74 min), 10 lectures, 8 quiz
Video8 vidéos
Lecture: a linear program12 min
Lecture: small items6 min
Lecture: large items, few sizes11 min
Large items, many sizes8 min
Lecture: large items analysis8 min
Lecture: general algorithm7 min
Lecture: conclusion6 min
Reading10 lectures
Slides (with typo corrected)10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Practice Exercises10 min
All slides together in one file10 min
Quiz7 exercices pour s'entraîner
Quiz 14 min
Quiz 26 min
Quiz 32 min
Quiz 46 min
Quiz 54 min
Quiz 66 min
Quiz 76 min
Semaine
4
Heures pour terminer
5 heures pour terminer

Set Cover and Randomized Rounding

This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem....
Reading
8 vidéos (Total 58 min), 11 lectures, 9 quiz
Video8 vidéos
Lecture: randomized rounding4 min
Lecture: cost analysis5 min
Lecture: coverage analysis8 min
Lecture: iterated algorithm4 min
Lecture: stopping time algorithm4 min
Lecture: stopping time analysis10 min
Lecture:final remarks6 min
Reading11 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
A reference on this stopping time analysis10 min
Practise Exercise10 min
All slides together in one file10 min
Quiz8 exercices pour s'entraîner
Quiz 12 min
Quiz 22 min
Quiz 32 min
Quiz 44 min
Quiz 52 min
Quiz 62 min
Quiz 72 min
Quiz 84 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.