Limits of Computation Flashcards Preview

Paper 1 - Computer Science > Limits of Computation > Flashcards

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

Give an example of a well known optimisation problem?

The Travelling Salesman Problem

2

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

3

What is the brute force method?

The brute force method involves testing out every combination

4

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

5

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.

6

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

7

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

8

What does intractable mean?

It means insoluble

9

Give an example of a tractable problem?

Dijkstra's shortest path

10

What are the two options for solving an intractable problem?

- Brute force method
- Heuristic method

11

What is the Heuristic approach?

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

12

What are examples of using the Heuristic approach?

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

13

What does the Halting Problem show us?

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

14

What is the Halting Problem?

Determines whether for a given input, a program will halt