近似算法 1

Approximation Algorithms Part I

1104 次查看
法国巴黎高等师范学院
Coursera
  • 完成时间大约为 23 个小时
  • 混合难度
  • 英语
注:本课程由Coursera和Linkshare共同提供,因开课平台的各种因素变化,以上开课日期仅供参考

课程概况

近似算法,第一部分

如何有效地将物品装入最少数量的盒子?您是否可以将节点集中在一起以便将网络廉价地分成几个中心的组件?这些是NP难组合优化问题的例子。很可能无法有效地解决这些问题,因此我们的目标是给出一个可以在多项式时间内计算的近似解,并且同时对其相对于最优的成本具有可证实的保证。

本课程需要已学过本科算法课程,尤其要求会使用线性编程设计的算法这一该领域最受欢迎和最成功的技术。通过本课程,您将接触到理论计算机科学基础上的一系列问题,以及强大的设计和分析技术。完成后,当遇到新的组合优化问题时,您将能够识别它是否接近一些已知的基本问题,并且能够设计线性编程松弛并使用随机舍入来尝试解决自己的问题。课程内容和课后作业具有理论性质,没有任何编程任务。

这是关于近似算法的两部分课程中的第一部分。

课程大纲

WEEK 1
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 s... 更多

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

WEEK 3
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.)

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

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

千万首歌曲。全无广告干扰。
此外,您还能在所有设备上欣赏您的整个音乐资料库。免费畅听 3 个月,之后每月只需 ¥10.00。
Apple 广告
声明:MOOC中国十分重视知识产权问题,我们发布之课程均源自下列机构,版权均归其所有,本站仅作报道收录并尊重其著作权益。感谢他们对MOOC事业做出的贡献!
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc
  • (部分课程由Coursera、Udemy、Linkshare共同提供)

© 2008-2020 MOOC.CN 慕课改变你,你改变世界