Informações sobre o curso
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.
Nível intermediário

Nível intermediário

Horas para completar

Aprox. 12 horas para completar

Sugerido: 9 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.
Nível intermediário

Nível intermediário

Horas para completar

Aprox. 12 horas para completar

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

Inglês

Legendas: Inglês

Programa - O que você aprenderá com este curso

Semana
1
Horas para completar
1 hora para concluir

Introduction to Approximation algorithms

In the module the motivation for studying approximation algorithms will be given. We will discuss what optimization problems are, and what the difference between heuristics and approximation algorithms is. Finally, we will introduce the concept of approximation ratio, which plays a central role in the analysis of the quality of approximation algorithms....
Reading
1 vídeo (total de (Total 13 mín.) min), 1 leitura, 1 teste
Reading1 leituras
Course notes 1.130min
Quiz1 exercício prático
Introduction20min
Semana
2
Horas para completar
5 horas para concluir

The Load Balancing problem

In this module we will study various approximation algorithms for the load balancing problem. This problems asks to distribute a given set of jobs, each with a certain processing time, over a number of machine. The goal is to do this such that all jobs are finished as soon as possible. We will analyze the quality of the computed solutions computed using the concept of rho-approximation, which we saw in the previous lecture. In this analysis we will see that lower bounds on the optimal solution play a crucial role in the analysis (or, for maximization problems: upper bounds)....
Reading
3 vídeos (total de (Total 45 mín.) min), 1 leitura, 2 testes
Video3 videos
Analysis of the greedy-algorithm19min
The ordered scheduling algorithm14min
Reading1 leituras
Course notes 1.245min
Quiz1 exercício prático
The load balancing problem25min
Semana
3
Horas para completar
3 horas para concluir

LP Relaxation

In this module we will introduce the technique of LP relaxation to design approximation algorithms, and explain how to analyze the approximation ratio of an algorithm based in LP relaxation. We will do this using the (weighted) Vertex Cover problem as an example. Before we explain the technique of LP relaxation, however, we first give a simple 2-approximation algorithm for the unweighted Vertex Cover problem. ...
Reading
6 vídeos (total de (Total 69 mín.) min), 2 leituras, 1 teste
Video6 videos
An approximation algorithm for vertex-cover11min
A brief introduction to linear programming12min
Weighted vertex-cover15min
LP relaxation for weighted vertex-cover7min
LP relaxation: Analyzing approximation ratio12min
Reading2 leituras
Course notes 3.120min
Course notes 3.245min
Quiz1 exercício prático
LP Relaxation30min
Semana
4
Horas para completar
6 horas para concluir

Polynomial-time approximation schemes

In this module we will introduce the concept of Polynomial-Time Approximation Scheme (PTAS), which are algorithms that can get arbitrarily close to an optimal solution. We describe a general technique to design PTASs, and apply it to the famous Knapsack problem. Finally we will see how to analyze PTASs that are designed with the general technique....
Reading
6 vídeos (total de (Total 62 mín.) min), 2 leituras, 2 testes
Video6 videos
Knapsack Problem6min
A dynamic-programming algorithm for knapsack16min
A PTAS for knapsack12min
Analysis of the PTAS for knapsack: approximation ratio11min
Analysis of the PTAS for knapsack: running time8min
Reading2 leituras
Course notes 4.145min
Course notes 4.245min
Quiz1 exercício prático
Polynomial-time approximation schemes45min

Instrutores

Avatar

Mark de Berg

Prof.dr.
Mathematics and Computer Science

Sobre EIT Digital

EIT Digital is a pan-European education and research-based open innovation organization founded on excellence. Its mission is to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research and business, EIT Digital empowers digital top talents for the future. EIT Digital provides online "blended" Innovation and Entrepreneurship education to raise quality, increase diversity and availability of the top-level content provided by 20 reputable universities of technology around Europe. The universities all together deliver a unique blend of the best of technical excellence and entrepreneurial skills and mindset to digital engineers and entrepreneurs at all stages of their careers. The academic partners support Coursera’s bold vision to enable anyone, anywhere, to transform their lives by accessing the world’s best learning experience. This means that EIT Digital gradually shares parts of its entrepreneurial and academic education programmes to demonstrate its excellence and make it accessible to a much wider audience. EIT Digital’s online education portfolio can be used as part of blended education settings, in both Master and Doctorate programmes, and for professionals as a way to update their knowledge. EIT Digital offers an online programme in 'Internet of Things through Embedded Systems'. Achieving all certificates of the online courses and the specialization provides an opportunity to enroll in the on campus program and get a double degree. These are the courses in the online programme: ...

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.

  • Quando você adquire o Certificado, ganha acesso a todo o material do curso, incluindo avaliações com nota atribuída. Após concluir o curso, seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.

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