课程信息
4.8
42 个评分
9 个审阅
100% 在线

100% 在线

立即开始,按照自己的计划学习。
可灵活调整截止日期

可灵活调整截止日期

根据您的日程表重置截止日期。
完成时间(小时)

完成时间大约为13 小时

建议:9 hours/week...
可选语言

英语(English)

字幕:英语(English)
100% 在线

100% 在线

立即开始,按照自己的计划学习。
可灵活调整截止日期

可灵活调整截止日期

根据您的日程表重置截止日期。
完成时间(小时)

完成时间大约为13 小时

建议:9 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分钟

关于 法国巴黎高等师范学院

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....

常见问题

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

还有其他问题吗?请访问 学生帮助中心