NP-Complete Problems

Learn about NP-complete problems, known as hard problems that can’t be solved efficiently, and practice solving them using algorithmic techniques.

1434 次查看
  • 完成时间大约为 3
  • 中级
  • 英语


NP-completeness and how to deal with it

How to approximate algorithms

How to use heuristic algorithms to solve a problem more quickly when classic methods are too slow


Step into the area of more complex problems and learn advanced algorithms to help solve them.

This course, part of the Algorithms and Data Structures MicroMasters program, discusses inherently hard problems that you will come across in the real-world that do not have a known provably efficient algorithm, known as NP-Complete problems.

You will practice solving large instances of some of these problems despite their hardness using very efficient specialized software and algorithmic techniques including:

Approximate algorithms
Special cases of NP-hard problems
Heuristic algorithms


Week 1: NP-Complete Problems
Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.

Week 2: Coping with NP-completeness: special cases
After the previous module you might be sad: you've just went through 5 courses in Algorithms only to learn that they are not suitable for most real-world problems. However, don't give up yet! People are creative, and they need to solve these problems anyway, so in practice there are often ways to cope with an NP-complete problem at hand. We show that some special cases on NP-complete problems can, in fact, be solved in polynomial time.

Week 3: Coping with NP-completeness: exact and approximate algorithms
We consider exact algorithms that find a solution much faster than the brute force algorithm. We conclude with approximation algorithms that work in polynomial time and find a solution that is close to being optimal.


Basic knowledge of at least one programming language and material of the Algorithmic Toolbox, Data Structures and Algorithms on Graphs classes.

此外,您还能在所有设备上欣赏您的整个音乐资料库。免费畅听 3 个月,之后每月只需 ¥10.00。
Apple 广告
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc
  • (部分课程由Coursera、Udemy、Linkshare共同提供)

© 2008-2022 CMOOC.COM 慕课改变你,你改变世界