Component 18 - Key Definitions

Question 1

Features that make a problem solvable by computational methods

Answer 1

Computational methods = maths. Features that make a problem solvable by computational methods = can you turn your problem into a mathematical form? In other words, there are certain problems which are well suited to computing – such as those which involve massive data sets, calculations, analysis of data, repetitive tasks, complex maths/physics simulations. There are others which are less trivial/suitable in nature and you should be able to recognise these (image recognition for example)

Question 2

Problem recognition

Answer 2

Being able to extract the parts of a problem which need to be solved or could be solved with code

Question 3

Problem decomposition

Answer 3

Being able to break a problem down into a set of sub-tasks or problems which themselves could be easily turned into code (in other words they are obviously functions, procedures or classes

Question 4

divide and conquer

Answer 4

A method of problem solving by splitting the problem into ever smaller tasks until they become trivially easy to solve.

Question 5

abstraction

Answer 5

As before

Question 6

backtracking

Answer 6

A technique used to “retrace the steps” an algorithm has taken. Backtracking has many applications, usually in well known algorithms like Dijkstra’s algorithm and other path finding solutions. Backtracking means a path has been followed, evaluated and found to be sub-optimal, the algorithm then goes back to a previously known good point and continues from there in an attempt to evaluate a better path

Question 7

data mining

Answer 7

The process of taking “big data” (extremely large data sets) and creating queries which elicit useful data/conclusions. Data mining recognises that a data set may be more useful than its initial intended purpose. Techniques may include uses of AI, Neural Networks or other machine learning techniques.

Question 8

heuristics

Answer 8

The use of a “best fit” approach to the solution of a problem, or the use of “best guess.” Heuristics are used to solve problems which are NP problems (in other words we cannot prove them to be solvable and therefore there exists no known “complete” solution). Heuristics may be used in other applications such as anti virus software to monitor “virus like” behaviour and best guess that a program may or may not be malicious.

Question 9

visualisation to solve problems

Answer 9

As it says on the tin – the use of diagrams to simplify the finding of solutions to problems

Question 10

pipelining

Answer 10

The ordering of instructions into the most efficient form so that program execution speed is maximised. Compilers and CPU’s will both have pipelining optimisations which enable them to re- order instructions into a more efficient or “likely” form. The processor can then maximise its execution speed by simultaneously executing one instruction, whilst decoding the next, whilst fetching the next + 1 instruction.

Question 11

performance modelling

Answer 11

The use of big O notation to investigate/represent the best and worst case time and space complexity of problems