课程信息
6,518 次近期查看

100% 在线

立即开始,按照自己的计划学习。

可灵活调整截止日期

根据您的日程表重置截止日期。

完成时间大约为21 小时

建议:4 hours/week...

英语(English)

字幕:英语(English)

100% 在线

立即开始,按照自己的计划学习。

可灵活调整截止日期

根据您的日程表重置截止日期。

完成时间大约为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....
8 个视频 (总计 54 分钟), 13 个阅读材料, 8 个测验
8 个视频
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分钟
13 个阅读材料
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分钟
7 个练习
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....
7 个视频 (总计 52 分钟), 9 个阅读材料, 8 个测验
7 个视频
Lecture: Greedy algorithm5分钟
Lecture: Special dynamic program8分钟
Lecture: General dynamic program8分钟
Lecture: algorithm6分钟
Lecture: analysis7分钟
Lecture: approximation scheme4分钟
9 个阅读材料
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Practise Exercises10分钟
All slides together in one file10分钟
7 个练习
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.)...
8 个视频 (总计 74 分钟), 10 个阅读材料, 8 个测验
8 个视频
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分钟
10 个阅读材料
Slides (with typo corrected)10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Practice Exercises10分钟
All slides together in one file10分钟
7 个练习
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....
8 个视频 (总计 58 分钟), 11 个阅读材料, 9 个测验
8 个视频
Lecture: randomized rounding4分钟
Lecture: cost analysis5分钟
Lecture: coverage analysis8分钟
Lecture: iterated algorithm4分钟
Lecture: stopping time algorithm4分钟
Lecture: stopping time analysis10分钟
Lecture:final remarks6分钟
11 个阅读材料
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
A reference on this stopping time analysis10分钟
Practise Exercise10分钟
All slides together in one file10分钟
8 个练习
Quiz 12分钟
Quiz 22分钟
Quiz 32分钟
Quiz 44分钟
Quiz 52分钟
Quiz 62分钟
Quiz 72分钟
Quiz 84分钟
5
完成时间为 5 小时

Multiway Cut and Randomized Rounding

This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)...
5 个视频 (总计 71 分钟), 8 个阅读材料, 6 个测验
5 个视频
Lecture: linear programming relaxation20分钟
Lecture: randomized rounding14分钟
Lecture: analysis14分钟
Lecture: conclusion6分钟
8 个阅读材料
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Slides10分钟
Practice exercise10分钟
All Chapter Slides together in one file10分钟
Slides for all chapters of Approx Algs Part 1 together in one file10分钟
5 个练习
Quiz 1 : Some context on cuts4分钟
Quiz 26分钟
Quiz 34分钟
Quiz 44分钟
Quiz 54分钟
4.7
34 个审阅Chevron Right

热门审阅

创建者 DAJan 27th 2016

The course provides a high-level introduction to approximation algorithm. There is no programming assignments but it provides nice introduction to approximation algorithm.

创建者 ZWSep 17th 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.

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

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

常见问题

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

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