課程信息
4.7
121 個評分
34 個審閱
100% online

100% online

立即開始,按照自己的計劃學習。
可靈活調整截止日期

可靈活調整截止日期

根據您的日程表重置截止日期。
完成時間(小時)

完成時間大約為21 小時

建議:4 hours/week...
可選語言

英語(English)

字幕:英語(English)...
100% online

100% online

立即開始,按照自己的計劃學習。
可靈活調整截止日期

可靈活調整截止日期

根據您的日程表重置截止日期。
完成時間(小時)

完成時間大約為21 小時

建議:4 hours/week...
可選語言

英語(English)

字幕:英語(English)...

教學大綱 - 您將從這門課程中學到什麼

1
完成時間(小時)
完成時間為 6 小時

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 個視頻(共 54 分鐘), 13 個閱讀材料, 8 個測驗
Video8 個視頻
Lecture: Definition4分鐘
Lecture: Integer program6分鐘
Lecture: A linear programming relaxation6分鐘
Lecture: Approximation algorithm6分鐘
Lecture: Analysis6分鐘
Lecture: General facts5分鐘
Half integrality (7:35 bug, fixed in pdf slides)10分鐘
Reading13 個閱讀材料
Slides10分鐘
All slides for all chapters of Approx Algs part 110分鐘
Attempt to upload slides in Keynote format10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Practice Exercises10分鐘
PDF version of the peer-graded assignment10分鐘
Half-integrality slides10分鐘
All slides together in one file10分鐘
Quiz7 個練習
Quiz 1: P vs. NP review6分鐘
Quiz 28分鐘
Quiz 34分鐘
Quiz 46分鐘
Quiz 54分鐘
Quiz 64分鐘
Quiz 74分鐘
2
完成時間(小時)
完成時間為 5 小時

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 個視頻(共 52 分鐘), 9 個閱讀材料, 8 個測驗
Video7 個視頻
Lecture: Greedy algorithm5分鐘
Lecture: Special dynamic program8分鐘
Lecture: General dynamic program8分鐘
Lecture: algorithm6分鐘
Lecture: analysis7分鐘
Lecture: approximation scheme4分鐘
Reading9 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Practise Exercises10分鐘
All slides together in one file10分鐘
Quiz7 個練習
Quiz 12分鐘
Quiz 22分鐘
Quiz 34分鐘
Quiz 42分鐘
Quiz 52分鐘
Quiz 62分鐘
Quiz 72分鐘
3
完成時間(小時)
完成時間為 5 小時

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 個視頻(共 74 分鐘), 10 個閱讀材料, 8 個測驗
Video8 個視頻
Lecture: a linear program12分鐘
Lecture: small items6分鐘
Lecture: large items, few sizes11分鐘
Large items, many sizes8分鐘
Lecture: large items analysis8分鐘
Lecture: general algorithm7分鐘
Lecture: conclusion6分鐘
Reading10 個閱讀材料
Slides (with typo corrected)10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Practice Exercises10分鐘
All slides together in one file10分鐘
Quiz7 個練習
Quiz 14分鐘
Quiz 26分鐘
Quiz 32分鐘
Quiz 46分鐘
Quiz 54分鐘
Quiz 66分鐘
Quiz 76分鐘
4
完成時間(小時)
完成時間為 5 小時

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 個視頻(共 58 分鐘), 11 個閱讀材料, 9 個測驗
Video8 個視頻
Lecture: randomized rounding4分鐘
Lecture: cost analysis5分鐘
Lecture: coverage analysis8分鐘
Lecture: iterated algorithm4分鐘
Lecture: stopping time algorithm4分鐘
Lecture: stopping time analysis10分鐘
Lecture:final remarks6分鐘
Reading11 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
A reference on this stopping time analysis10分鐘
Practise Exercise10分鐘
All slides together in one file10分鐘
Quiz8 個練習
Quiz 12分鐘
Quiz 22分鐘
Quiz 32分鐘
Quiz 44分鐘
Quiz 52分鐘
Quiz 62分鐘
Quiz 72分鐘
Quiz 84分鐘

關於 É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....

常見問題

  • 注册以便获得证书后,您将有权访问所有视频、测验和编程作业(如果适用)。只有在您的班次开课之后,才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程,可能无法访问某些作业。

還有其他問題嗎?請訪問 學生幫助中心