近似算法，第一部分 如何高效地将物体装入最小数量的盒子中？如何才能将节点集群，从而以低成本将网络分成几个中心周围的组件？这些都是 NP 难组合优化问题的例子。要高效地解决这类问题很可能是不可能的，因此我们的目标是给出一个近似解，该解可以在多项式时间内计算，同时还能证明其相对于最优解的成本。
近似算法第一部分
了解顶级公司的员工如何掌握热门技能
该课程共有5个模块
我们将通过一个名为顶点覆盖（Vertex Cover）的基本问题的典型示例来引入课程主题，并使用线性规划松弛和舍入这两种基本技术来设计和分析最先进的近似算法。这是强大技术的简单初级应用。
涵盖的内容
8个视频13篇阅读材料7个作业1次同伴评审
本模块通过使用四舍五入法设计另一个基本问题：Knapsack 问题的接近最优解，展示了四舍五入法的强大功能。
涵盖的内容
7个视频9篇阅读材料7个作业1次同伴评审
本模块通过使用另一个基本问题的巧妙变体来展示四舍五入的复杂性：箱包装。(这是一个更高级的模块）。
涵盖的内容
8个视频10篇阅读材料7个作业1次同伴评审
本模块介绍一种基于概率的简单而强大的舍入变体：随机舍入。它的强大功能将应用于另一个基本问题--集合覆盖问题。
涵盖的内容
8个视频11篇阅读材料8个作业1次同伴评审
本模块通过开发一个复杂的变体，并将其应用于另一个基本问题--多向切问题，加深对随机舍入的理解。(这是一个更高级的模块）。
涵盖的内容
5个视频8篇阅读材料5个作业1次同伴评审
位教师
授课教师评分
4.5 (174个评价)
从 算法 浏览更多内容
状态：免费École normale supérieure
EIT Digital
状态：免费试用University of Colorado Boulder
The Chinese University of Hong Kong
人们为什么选择 Coursera 来帮助自己实现职业发展
Felipe M.
自 2018开始学习的学生
''能够按照自己的速度和节奏学习课程是一次很棒的经历。只要符合自己的时间表和心情，我就可以学习。'
Jennifer J.
自 2020开始学习的学生
''我直接将从课程中学到的概念和技能应用到一个令人兴奋的新工作项目中。'
Larry W.
自 2021开始学习的学生
''如果我的大学不提供我需要的主题课程，Coursera 便是最好的去处之一。'
Chaitanya A.
''学习不仅仅是在工作中做的更好：它远不止于此。Coursera 让我无限制地学习。'
学生评论
4.7
555 条评论
- 5 stars
76.07%
- 4 stars
20.86%
- 3 stars
2.15%
- 2 stars
0.89%
- 1 star
0%
显示 3/555 个
KS
5
已于 May 25, 2016审阅
Excellent Course! I have learnt a lot about Approximation Algorithms in a short span of time.
MH
5
已于 May 28, 2020审阅
A great course if you want to learn about approximation algorithms from the point of view of linear programming relaxation!
VA
4
已于 Jan 18, 2016审阅
This course is quite advanced and the assignments require prerequisite skills to prove time complexity etc. If you are upto it, then for sure take this course. The instructor is quite thorough.
常见问题
要获取课程资料、作业和证书，您需要在注册课程时购买证书体验。 您可以尝试免费试听，或申请资助。课程可能提供 "完整课程，无证书"。通过该选项，您可以查看所有课程资料，提交必要的评估，并获得最终成绩。这也意味着您无法购买证书体验。
更多问题
提供助学金，
¹ 本课程的部分作业采用 AI 评分。对于这些作业，将根据 Coursera 隐私声明使用您的数据。