AQA 7517 4.4.4.4: Limits of computation
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
Some problems have an algorithm that solves them, but the algorithm is so slow that no computer that could ever be built would finish in time. This lesson is about that first limit: problems we can solve in principle but not in practice. Module A5 gave you Big O notation for comparing algorithms; here it becomes the line between what is practical and what is not.
- Two things limit computation
- How fast things grow
- Tractable and intractable
- The travelling robot
- Heuristics
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A6.7 Limits of computation: tractable and intractable problems Theory of computation
How complexity and hardware limit computation, tractable and intractable problems, and a heuristic route for the robot.
Try it on a robot
The task from A6.7 Limits of computation: tractable and intractable problems, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.4.4.4 and is not endorsed by the board.