problem recognition

Question 1

computable problems

Answer 1

a problem where there is an ALGORITHM that can solve EVERY instance of it within a FINITE number of steps (can be theoretically solvable but practically unsolvable/insoluble if takes millions of yrs to solve)

Question 2

ways of problem solving

Answer 2

enumeration
simulation
theoretical approach
creative solution

Question 3

enumeration

Answer 3

solve problems by exhaustive search (eg finding owner of DNA in database) - trying all possible solutions. Once insoluble are now soluble bc power of computers. BUT inefficient, and as size of problem inc, number of poss solutions inc exponentially. eg magic squares

Question 4

simulation

Answer 4

process of designing a model for a real system to understand the behaviour of the system and evaluate various strategies for its operation. Model used to evaluate performance or test outcomes.

Question 5

problems for simulation

Answer 5

financial risk analysis
population predictions
climate change predictions
queue problems
engineering design problems

Question 6

abstraction in simulation

Answer 6

removes unnecessary details, reducing problems to essentials

Question 7

eg of queuing problems

Answer 7

number of queues on toll roads, or checkouts at supermarkets or number of people on helplines for software support

Question 8

simulation: real life models

Answer 8

build physical model of eg spacecraft to study behaviour. When impractical, dangerous, expensive to do tests on real thing. Used to evaluate performance and test outcomes

Question 9

strategies for problem solving

Answer 9

top down design: good for breaking down into small, manageable subtasks
divide and conquer: technique that reduces size of problem with every iteration eg binary search (halves problem with each iteration), not always as fast as binary search
problem abstraction

Question 10

problem abstraction

Answer 10

removing details until problem is represented in a way that it is possible to solve because reduced to one that has already been solved

Question 11

graph unfolding

Answer 11

a method of solving a problem: eg for knights problem on p279, number squares then draw node graphs with edges to all possible moves. then open it up to a circle

Question 12

eg the knights problem is a …

Answer 12

REDUCTION to a more general problem that has already been solved in the same way

Question 13

automation

Answer 13

building and putting into action models to solve problems. Includes: what are you gonna put in the model and what assumptions you are going to make, create and implement algorithms, execute and test results

Question 14

automating the abstraction

Answer 14

tells us more about the reality we are modelling/physical scenario

Question 15

physical world scenario–> mathematical model

Answer 15

abstraction is created

Question 16

mathematical model is automated to

Answer 16

an automaton

Question 17

automaton tells us more about

Answer 17

physical world scenario

Question 18

important factor in finding a solution to a problem

Answer 18

visualisation of algorithms: how problem is presented eg computers work with binary numbers but humans prefer visual images

Question 19

eg of visualisation

Answer 19

binary tree flow diagram vs data in a table, a map, graph

Question 20

backtracking

Answer 20

methodical way of trying out different sequences until you find one that leads to a solution. go as far down one route as possible before backtracking to last decision point and go down next route as far as possible again.

Question 21

when is backtracking used

Answer 21

when you don’t have enough info to know which is the best choice
when each decision leads to a new set of choices
one or more of the sequences may be a new solution to the problem

Question 22

eg backtracking

Answer 22

mazes, depth first traversal of a graph

Question 23

big data

Answer 23

large sets of data that cannot be easily handled in a traditional database

Question 24

data mining

Answer 24

process of digging through big data sets to discover hidden connections and predict future trends: often involving the use of different kinds of software packages eg analytical tools

Question 25

intractable problems

Answer 25

although an algorithm may exist for their solution, the program may take an unreasonable amount of time to find the optimal solution eg Travelling Salesman Problem

Question 26

TSP and applica\tions

Answer 26

Given a list of towns and distances between each pair, what is the shortest possible route that the salesman can use to visit each town exactly once and return to the starting point: planning, logistics, manufacture of microchips and DNA sequencing

Question 27

TSP: num of possible routes with 5 cities. number you’d examine by brute force

Answer 27

4!

Question 28

methods to solve intractable problems

Answer 28

brute force: inefficient
finding an approximate answer or finding a solution with a high probability of being correct or solving simpler/restricted versions to give insights into possible solutions

Question 29

heuristic solution

Answer 29

employs an algorithm not guaranteed to be optimal or perfect or accurate, but is sufficient for the purpose and is completed in a reasonable time frame.

Question 30

performance modelling

Answer 30

process of simulating different user and system loads on a computer using a mathematical approximation, rather than actual performance testing (e.g. expensive and difficult.) Output from performance model can then be used to help plan a new system suited to the requirements of an organisation.

Question 31

e.g. of performance modelling

Answer 31

test performance of a network under different conditons