English subtitles

← 10-43 Practical Scenarios

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. Now just to familiarize yourself with these problems a little bit more,
  2. I would like to do the same thing that we have done here for these five problems.
  3. I will now give you a number of practical scenarios.
  4. What I would like you to tell me is which of these problems would probably be most useful
  5. for attempting an NP completeness proof?
  6. So again we will give these problems here numbers, one, two, three, and four,
  7. and I will give you six practical scenarios where you can then choose
  8. which problem to match to the scenarios, so you could have a scenario in Bioinformatics,
  9. but you would like to compare DNA sequences to each other.
  10. And what you are trying to find out is how much information they have in common.
  11. You could have a scenario where you want to schedule computer programs.
  12. What I mean by this is you have a bunch of computer programs.
  13. You know approximately how much time you took those programs is going to take.
  14. And you have a number of machines and of course you want to get as much work done as possible
  15. within let's say the next hour so you have to decide which program to run on which machine
  16. or you could have a question about let's say classrooms where you say,
  17. "How many classrooms do we actually need for the next semester to teach our courses?"
  18. So there will be certain courses that take place at a certain time or that cannot be scheduled together.
  19. A new question is how many different rooms would we actually need?
  20. Or you could have the scenario where two programmers
  21. have been working on the same programming code.
  22. And one of the programmers has made some changes and the other one has made some changes.
  23. And now you need to get these two codes back together again,
  24. and you do that by figuring out what they actually still have in common.
  25. Another problem could be that you have a number of vans or delivery trucks
  26. that you would like to fill and you want to find out
  27. how many vans you need to transport all of these packages here.
  28. They have different sizes. They have different priorities and so on.
  29. And finally, a scenario that is none of the above so something else.
  30. Please match the practical scenarios to the NP complete problem
  31. that is most likely to occur in that scenario, and I want you to do this by entering numbers here
  32. that correspond to these four problems.
  33. You'll have to use some of these problems here more than once.