Informações sobre o curso
6,170

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Aprox. 21 horas para completar

Sugerido: 4 hours/week...

Inglês

Legendas: Inglês

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Aprox. 21 horas para completar

Sugerido: 4 hours/week...

Inglês

Legendas: Inglês

Programa - O que você aprenderá com este curso

Semana
1
6 horas para concluir

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....
8 vídeos (total de (Total 54 mín.) min), 13 leituras, 8 testes
8 videos
Lecture: Definition4min
Lecture: Integer program6min
Lecture: A linear programming relaxation6min
Lecture: Approximation algorithm6min
Lecture: Analysis6min
Lecture: General facts5min
Half integrality (7:35 bug, fixed in pdf slides)10min
13 leituras
Slides10min
All slides for all chapters of Approx Algs part 110min
Attempt to upload slides in Keynote format10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Practice Exercises10min
PDF version of the peer-graded assignment10min
Half-integrality slides10min
All slides together in one file10min
7 exercícios práticos
Quiz 1: P vs. NP review6min
Quiz 28min
Quiz 34min
Quiz 46min
Quiz 54min
Quiz 64min
Quiz 74min
Semana
2
5 horas para concluir

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....
7 vídeos (total de (Total 52 mín.) min), 9 leituras, 8 testes
7 videos
Lecture: Greedy algorithm5min
Lecture: Special dynamic program8min
Lecture: General dynamic program8min
Lecture: algorithm6min
Lecture: analysis7min
Lecture: approximation scheme4min
9 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Practise Exercises10min
All slides together in one file10min
7 exercícios práticos
Quiz 12min
Quiz 22min
Quiz 34min
Quiz 42min
Quiz 52min
Quiz 62min
Quiz 72min
Semana
3
5 horas para concluir

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.)...
8 vídeos (total de (Total 74 mín.) min), 10 leituras, 8 testes
8 videos
Lecture: a linear program12min
Lecture: small items6min
Lecture: large items, few sizes11min
Large items, many sizes8min
Lecture: large items analysis8min
Lecture: general algorithm7min
Lecture: conclusion6min
10 leituras
Slides (with typo corrected)10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Practice Exercises10min
All slides together in one file10min
7 exercícios práticos
Quiz 14min
Quiz 26min
Quiz 32min
Quiz 46min
Quiz 54min
Quiz 66min
Quiz 76min
Semana
4
5 horas para concluir

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....
8 vídeos (total de (Total 58 mín.) min), 11 leituras, 9 testes
8 videos
Lecture: randomized rounding4min
Lecture: cost analysis5min
Lecture: coverage analysis8min
Lecture: iterated algorithm4min
Lecture: stopping time algorithm4min
Lecture: stopping time analysis10min
Lecture:final remarks6min
11 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
A reference on this stopping time analysis10min
Practise Exercise10min
All slides together in one file10min
8 exercícios práticos
Quiz 12min
Quiz 22min
Quiz 32min
Quiz 44min
Quiz 52min
Quiz 62min
Quiz 72min
Quiz 84min
Semana
5
5 horas para concluir

Multiway Cut and Randomized Rounding

This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)...
5 vídeos (total de (Total 71 mín.) min), 8 leituras, 6 testes
5 videos
Lecture: linear programming relaxation20min
Lecture: randomized rounding14min
Lecture: analysis14min
Lecture: conclusion6min
8 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Practice exercise10min
All Chapter Slides together in one file10min
Slides for all chapters of Approx Algs Part 1 together in one file10min
5 exercícios práticos
Quiz 1 : Some context on cuts4min
Quiz 26min
Quiz 34min
Quiz 44min
Quiz 54min
4.7
34 avaliaçõesChevron Right

Melhores avaliações

por DAJan 27th 2016

The course provides a high-level introduction to approximation algorithm. There is no programming assignments but it provides nice introduction to approximation algorithm.

por ZWSep 17th 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.

Instrutores

Sobre Escola Normal Superior de Paris

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....

Perguntas Frequentes – FAQ

  • Ao se inscrever para um Certificado, você terá acesso a todos os vídeos, testes e tarefas de programação (se aplicável). Tarefas avaliadas pelos colegas apenas podem ser enviadas e avaliadas após o início da sessão. Caso escolha explorar o curso sem adquiri-lo, talvez você não consiga acessar certas tarefas.

Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.