Limits of Computation Flashcards Preview

Paper 1 - Computer Science > Limits of Computation > Flashcards

Flashcards in Limits of Computation Deck (14)
Loading flashcards...

Give an example of a well known optimisation problem?

The Travelling Salesman Problem


What problem does The Travelling Salesman Problem present?

Given a list of nodes and the distances between each of them, what is the shortest possible route that can be taken, that visits each node and returns to the start


What is the brute force method?

The brute force method involves testing out every combination


Using a brute force method, with 5 cities, how many combinations would have to be tested?

4! = 24
It's always one less than the number of cities


What does computationally difficult mean in the context of The Travelling Salesman Problem?

- The problem is computationally difficult because it will take a long time for a fast computer to find the optimal solution.
- As the number of cities increases the problem becomes rapidly impossible to solve within a reasonable amount of time.


What are tractable problems?

- Problems that have a polynomial time solution.
- Polynomial time solutions have O(n^k)
- Problems with time complexities O(n), O(nlogn) and O(n^10) are tractable


What are intractable problems?

- Problems that don't have a polynomial time solution.
- Problems with time complexities O(2^n) and O(n!) are intractable
- They have a theoretical solution but are very hard to solve if the n is a large value


What does intractable mean?

It means insoluble


Give an example of a tractable problem?

Dijkstra's shortest path


What are the two options for solving an intractable problem?

- Brute force method
- Heuristic method


What is the Heuristic approach?

Finding an adequate solution by trading optimality, completeness, accuracy or precision for speed.


What are examples of using the Heuristic approach?

- The rule of thumb
- Making an educated guess
- Using common sense


What does the Halting Problem show us?

That there are some problems that cannot be solved by a computer


What is the Halting Problem?

Determines whether for a given input, a program will halt