Limits of Computation Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Give an example of a well known optimisation problem?

A

The Travelling Salesman Problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What problem does The Travelling Salesman Problem present?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the brute force method?

A

The brute force method involves testing out every combination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

4! = 24

It’s always one less than the number of cities

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are tractable problems?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are intractable problems?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does intractable mean?

A

It means insoluble

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Give an example of a tractable problem?

A

Dijkstra’s shortest path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the two options for solving an intractable problem?

A
  • Brute force method

- Heuristic method

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the Heuristic approach?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are examples of using the Heuristic approach?

A
  • The rule of thumb
  • Making an educated guess
  • Using common sense
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does the Halting Problem show us?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the Halting Problem?

A

Determines whether for a given input, a program will halt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly