このコースについて

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 reading, 1 quiz
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 reading, 2 quizzes
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 readings, 1 quiz
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 readings, 2 quizzes
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のプロフィールに追加したりできます。コースの内容の閲覧のみを希望する場合は、無料でコースを聴講できます。

さらに質問がある場合は、受講者向けヘルプセンターにアクセスしてください。