Об этом курсе

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Промежуточный уровень

Прибл. 12 часа на выполнение

Предполагаемая нагрузка: 9 hours/week...

Английский

Субтитры: Английский

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Промежуточный уровень

Прибл. 12 часа на выполнение

Предполагаемая нагрузка: 9 hours/week...

Английский

Субтитры: Английский

Программа курса: что вы изучите

Неделя
1
1 ч. на завершение

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....
1 видео ((всего 13 мин.)), 1 материал для самостоятельного изучения, 1 тест
1 материал для самостоятельного изучения
Course notes 1.130мин
1 практическое упражнение
Introduction20мин
Неделя
2
5 ч. на завершение

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)....
3 видео ((всего 45 мин.)), 1 материал для самостоятельного изучения, 2 тестов
3 видео
Analysis of the greedy-algorithm19мин
The ordered scheduling algorithm14мин
1 материал для самостоятельного изучения
Course notes 1.245мин
1 практическое упражнение
The load balancing problem25мин
Неделя
3
3 ч. на завершение

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. ...
6 видео ((всего 69 мин.)), 2 материалов для самостоятельного изучения, 1 тест
6 видео
An approximation algorithm for vertex-cover11мин
A brief introduction to linear programming12мин
Weighted vertex-cover15мин
LP relaxation for weighted vertex-cover7мин
LP relaxation: Analyzing approximation ratio12мин
2 материала для самостоятельного изучения
Course notes 3.120мин
Course notes 3.245мин
1 практическое упражнение
LP Relaxation30мин
Неделя
4
6 ч. на завершение

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....
6 видео ((всего 62 мин.)), 2 материалов для самостоятельного изучения, 2 тестов
6 видео
Knapsack Problem6мин
A dynamic-programming algorithm for knapsack16мин
A PTAS for knapsack12мин
Analysis of the PTAS for knapsack: approximation ratio11мин
Analysis of the PTAS for knapsack: running time8мин
2 материала для самостоятельного изучения
Course notes 4.145мин
Course notes 4.245мин
1 практическое упражнение
Polynomial-time approximation schemes45мин

Преподаватели

Avatar

Mark de Berg

Prof.dr.
Mathematics and Computer Science

О EIT Digital

EIT Digital is a pan-European organization whose 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 and blended Innovation and Entrepreneurship education to raise quality, increase diversity and availability of the top-level content provided by 20 leading technical universities around Europe. The universities 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. Please visit https://www.eitdigital.eu/eit-digital-academy/ ...

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

  • Оплатив сертификацию, вы получите доступ ко всем материалам курса, включая оцениваемые задания. После успешного прохождения курса на странице ваших достижений появится электронный сертификат. Оттуда его можно распечатать или прикрепить к профилю LinkedIn. Просто ознакомиться с содержанием курса можно бесплатно.

Остались вопросы? Посетите Центр поддержки учащихся.