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