2.2.2 - Computational Methods

Question 1

What makes a problem solvable by
computational methods?

Answer 1

• Can be solved within a finite, realistic amount of time
• Involves calculations as some issues can be quantified - these are easier to process computationally
• Has inputs, processes and outputs
• Involves logical reasoning.

Question 2

Problem Recognition

Answer 2

Identifying that there is a problem to be solved, to determine exactly what the problem is from a description/scenario and to determine if the problem can be solved with computational methods

Question 3

Problem Decomposition

Answer 3

Splitting the problem down into more manageable subproblems until each problem can be solved independantly; allowing for the use of divide and conquer

Question 4

Divide and Conquer + ‘Best’ Example

Answer 4

• Splits a big problem into smaller parts that are then tackled
• Best Example - Binary Search

Question 5

Abstraction

Answer 5

• Removal of unnecessary elements and use of symbols to represent elements of the problem
• Increases chance of creating the program successfully, reduces programming time and factors that can detract from the program

Question 6

Backtracking

Answer 6

• The process of incrementally building towards a solution, abandoning partial success when the solution can’t be completed and going back to the last successful stage
• Especially good for logic problems that involve path/route finding; E.g. Depth-First Graph Traversal

Question 7

Data Mining

Answer 7

• Involves searching through vast amounts of unconnected data in search of relationships/correlation between data items that may not be obvious
• May include pattern matching and anomaly detection algorithms
• Can be used for business modelling and planning for future eventualities

Question 8

What are Heuristics?

Answer 8

When ‘Rules of thumb’ and personal experience are used when it is unfeasible to analyse all eventualities; leading to a “good enough” result for the given time frame although it is not 100% accurate.

Question 9

How can Heuristics be used?

Answer 9

• Can make intractable problems possible
• Can assess potential malware
• Can speed up the process of finding the solution in the A* algorithm

Question 9

Performance Modelling

Answer 9

• Simulating the behaviour of the system before it is implemented to approximate performance
• Makes use of (smaller scale) existing data and calculations to make predictions; E.g. A game during its beta testing phase
• Useful where implementation is expensive or dangerous

Question 10

Pipelining

Answer 10

Data/processes arranged in a series being developed in parallel with the output of one process in pipelining becoming the input of another

Question 11

Describe two examples of where pipelining is used in any computer system?

Answer 11

• Pipes to pass data between programs and from programs to and from peripherals, example such as | symbol in Unix, Popen() or pipe() in C.
• Instruction processing; some processors allow parts of instructions to be processed without waiting to complete the whole instruction cycle
• Graphics Pipelines

Question 12

Visualisation

Answer 12

Computer Processes and Data being presented in a way that is easier for people to grasp; visually

Question 13

Advantages of Visualisations

Answer 13

• Benefit humans rather than computers
• Presents the information in a simpler form to understand
• Can best explain complex situations