English 字幕

← 01-07 Overview



Showing Revision 2 created 02/06/2019 by Michel Smits.

  1. This course has 7 units,
  2. and I'm now going to give you a brief
    overview of what we have planned.
  3. The first 3 units will introduce
    you to challenging problems,
  4. and I'm going to do this by
    telling you about some problems
  5. that are really relevant in practice,
    yet very, very hard to solve.
  6. We're also going to do a bit of the formal
    background of challenging problems
  7. through a concept known
    as NP-completeness.
  8. And I'm going to show you how
    to recognize NP-completeness
  9. so that you'll be able to develop an intuition
    when you encounter a challenging problem.
  10. So the first 3 units are basically about
    recognizing the hardness of a problem.
  11. In units 4 to 6 we are
    then going to discuss
  12. what to do if you encounter
    a hard problem,
  13. because, as I told you in
    the beginning, many people,
  14. once they've recognized that their problem
    is hard to solve, actually tend to stop.
  15. And these units here will give you various
    techniques for solving hard problems.
  16. Solving them very exactly using techniques
  17. such as optimized search
    trees and pre-processing,
  18. but also solving them almost
    optimally using techniques
  19. such as approximation and randomization.
  20. So this will give you an arsenal
    of tools that you can use to try
  21. and tackle any hard problem,
    should you encounter it.
  22. And then in the final unit we'll
    be going into computability
  23. and talk about unsolvable problems,
  24. problems that no computer can ever solve,
  25. and how you could solve them,
    nevertheless, if you come across them.