課程信息
4.8
41 個評分
9 個審閱
100% online

100% online

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

可靈活調整截止日期

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

完成時間大約為12 小時

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

英語(English)

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

100% online

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

可靈活調整截止日期

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

完成時間大約為12 小時

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

英語(English)

字幕:英語(English)...

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

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

Linear Programming Duality

This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality....
Reading
9 個視頻(共 87 分鐘), 11 個閱讀材料, 9 個測驗
Video9 個視頻
Properties of LP duality6分鐘
Geometry of LP duality10分鐘
Proof of weak duality theorem6分鐘
Changing the form of the LP10分鐘
Complementary slackness5分鐘
Primal-dual algorithms5分鐘
Vertex cover by primal-dual23分鐘
Conclusion3分鐘
Reading11 個閱讀材料
Slides10分鐘
Comment10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides-all10分鐘
Quiz8 個練習
Quiz 16分鐘
Quiz 22分鐘
Quiz 32分鐘
Quiz 44分鐘
Quiz 54分鐘
Quiz 64分鐘
Quiz 72分鐘
Quiz 84分鐘
2
完成時間(小時)
完成時間為 5 小時

Steiner Forest and Primal-Dual Approximation Algorithms

This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem....
Reading
8 個視頻(共 73 分鐘), 9 個閱讀材料, 9 個測驗
Video8 個視頻
A special case: Steiner tree12分鐘
LP relaxation for Steiner forest6分鐘
... and its dual4分鐘
Primal-dual algorithm, Part110分鐘
Primal-dual algorithm,Part 212分鐘
Analysis13分鐘
Proof of the main lemma9分鐘
Reading9 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides-all10分鐘
Quiz8 個練習
Quiz 16分鐘
Quiz 24分鐘
Quiz 34分鐘
Quiz 44分鐘
Quiz 54分鐘
Quiz 66分鐘
Quiz 74分鐘
Quiz 86分鐘
3
完成時間(小時)
完成時間為 5 小時

Facility Location and Primal-Dual Approximation Algorithms

This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem....
Reading
9 個視頻(共 64 分鐘), 10 個閱讀材料, 9 個測驗
Video9 個視頻
A linear programming relaxation4分鐘
...and its dual8分鐘
A primal-dual algorithm7分鐘
Analyzing the service cost7分鐘
Analyzing the facility opening cost7分鐘
A better algorithm11分鐘
Analysis7分鐘
Conclusion4分鐘
Reading10 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides-all10分鐘
Quiz8 個練習
Quiz 12分鐘
Quiz 24分鐘
Quiz 34分鐘
Quiz 44分鐘
Quiz 52分鐘
Quiz 62分鐘
Quiz 72分鐘
Quiz 86分鐘
4
完成時間(小時)
完成時間為 6 小時

Maximum Cut and Semi-Definite Programming

We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem....
Reading
11 個視頻(共 76 分鐘), 12 個閱讀材料, 10 個測驗
Video11 個視頻
Definition5分鐘
A 2-approximation5分鐘
A linear programming relaxation...11分鐘
...with an integrality gap of almost 210分鐘
Proof of Lemma7分鐘
A quadratic programming relaxation4分鐘
General facts about semidefinite programming7分鐘
A rounding algorithm7分鐘
Analysis6分鐘
General facts about MaxCut6分鐘
The end!3分鐘
Reading12 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Sldies10分鐘
Slides10分鐘
Slides-all10分鐘
Comment10分鐘
Quiz9 個練習
Quiz 14分鐘
Quiz 24分鐘
Quiz 32分鐘
Quiz 42分鐘
Quiz 54分鐘
Quiz 62分鐘
Quiz 72分鐘
Quiz 82分鐘
Quiz 92分鐘

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

常見問題

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

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