Informações sobre o curso
4.7
121 classificações
34 avaliações
100% online

100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis

Prazos flexíveis

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

Aprox. 21 horas para completar

Sugerido: 4 hours/week...
Idiomas disponíveis

Inglês

Legendas: Inglês...
100% online

100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis

Prazos flexíveis

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

Aprox. 21 horas para completar

Sugerido: 4 hours/week...
Idiomas disponíveis

Inglês

Legendas: Inglês...

Programa - O que você aprenderá com este curso

Semana
1
Horas para completar
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....
Reading
8 vídeos (Total de 54 min), 13 leituras, 8 testes
Video8 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
Reading13 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
Quiz7 exercícios práticos
Quiz 1: P vs. NP review6min
Quiz 28min
Quiz 34min
Quiz 46min
Quiz 54min
Quiz 64min
Quiz 74min
Semana
2
Horas para completar
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....
Reading
7 vídeos (Total de 52 min), 9 leituras, 8 testes
Video7 videos
Lecture: Greedy algorithm5min
Lecture: Special dynamic program8min
Lecture: General dynamic program8min
Lecture: algorithm6min
Lecture: analysis7min
Lecture: approximation scheme4min
Reading9 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Practise Exercises10min
All slides together in one file10min
Quiz7 exercícios práticos
Quiz 12min
Quiz 22min
Quiz 34min
Quiz 42min
Quiz 52min
Quiz 62min
Quiz 72min
Semana
3
Horas para completar
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.)...
Reading
8 vídeos (Total de 74 min), 10 leituras, 8 testes
Video8 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
Reading10 leituras
Slides (with typo corrected)10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Practice Exercises10min
All slides together in one file10min
Quiz7 exercícios práticos
Quiz 14min
Quiz 26min
Quiz 32min
Quiz 46min
Quiz 54min
Quiz 66min
Quiz 76min
Semana
4
Horas para completar
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....
Reading
8 vídeos (Total de 58 min), 11 leituras, 9 testes
Video8 videos
Lecture: randomized rounding4min
Lecture: cost analysis5min
Lecture: coverage analysis8min
Lecture: iterated algorithm4min
Lecture: stopping time algorithm4min
Lecture: stopping time analysis10min
Lecture:final remarks6min
Reading11 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
A reference on this stopping time analysis10min
Practise Exercise10min
All slides together in one file10min
Quiz8 exercícios práticos
Quiz 12min
Quiz 22min
Quiz 32min
Quiz 44min
Quiz 52min
Quiz 62min
Quiz 72min
Quiz 84min

Instrutores

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

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.