2.2.2 Computational Methods - Alexia

Computational problems

Problems that can be solved with algorithms and programming code

Real world constraints on computational problems

Computing power, speed, and memory

For example, calculating Pi to a billion decimal places is theoretically possible but impractical due to the amount of computational resources needed

Problem Recognition

Identifying there is a problem to be solved, determining the exact problem from a scenario and if the problem can be solved with computational methods

- Identify the nature and parameters of the problem

- Undertake a thorough analysis of the current situation

- Specify the problem requirements or success criteria

Advantages of Problem Recognition

Allows programmer to determine what the problem is, what the challenges may be and what additional information is required before starting to code the solution

The identification of the key features for programmers to focus on allows for easier time programming and faster solution produced

Problem Decomposition

The action of breaking down a problem into smaller subproblems which can be solved independently.

Advantages of Problem Decomposition

By splitting the task into smaller, more manageable problems, it allows for a solution to be developed quicker

Allows the design of an effective/efficient solution that makes

best use of a processor

Allows splitting of a task to allow programmers to focus on areas they specialise in

Certain sections of the program can be implemented using pre-coded modules or libraries which saves time

Easier testing and debugging as the tasks are smaller

Divide and conquer

A strategy to make a complex task easier by breaking it into smaller, more manageable tasks

The stages of Divide and conquer:

Divide - The problem needs to be broken down into sub-problems

Conquer - The sub-problems then need be solved independently

Combine - The solutions to the sub-problems can then be combined to form the overall solution to the problem

Used in: Binary search, merge and quick sort (also known as decrease and conquer for the sort algorithms)

Advantages of Divide and conquer

Can make programs more time efficient as they are broken down.

As problems are divided into sub-problems they can make effective use of cache memory.

Disadvantages of Divide and conquer

Not all problems can be broken down and solved independently.

It can possibly cause stack overflows if recursion is being used.

Task parallelism

When several tasks or sub-tasks can be carried out concurrently (at the same time) to speed up the overall completion time

Abstraction

When excessive details are removed to simplify a problem

Advantages of Abstraction

Abstraction allows programmers to focus on the core aspects required of the solution rather than worrying about unnecessary details.

Using levels of abstraction allows a large, complex project and its functionality to be split up into simpler component parts. Individual components can then be dealt with by different teams, with details about other layers being hidden. This technique makes projects more manageable.

Disadvantages of Abstraction

Oversimplification of a program can cause it to be too simple, less interactive and less enjoyable for a user to use.

Backtracking

A problem-solving technique that involves keeping track of where in the solving process assumptions are made so that they may later be changed

Used in depth first traversal

Advantages of backtracking

It is guaranteed to find a solution if one exists.

It is easy to implement and use.

It can be be applied to a variety of logic problems.

It will comprehensively explore all possible paths to the desired solution.

Disadvantages of backtracking

Is not ideal for solving strategic problems.

Depending on the problem that you are trying to solve, it can have a high time complexity.

If there are lots of different solutions to a problem, it is not always the most efficient method.

It can consume a lot of memory.

Although it may find a solution to the problem, the solution may not always be the best solution available.

Data mining

Used to identify patterns or outliers in large sets of data, termed big data

Extracts data from databases

Looking for patterns in data - analysed and used to inform decisions

Therefore, data mining a useful tool in assisting business and marketing decisions

Pros of data mining

Data mining can be used to identify patterns and trends that may not be immediately obvious to humans.

It can help organisations make better future predictions.

Organisations can ensure demand is met during busy periods to stay ahead of local competition.

Cons of data mining

It requires very powerful computers with a lot of processing power.

Inaccurate data can produce inaccurate results.

Although it may spot patterns and trends, it may not explain the reasons why these exist.

Data mining involves the handling of personal data, which may be seen as a breach of the DPA

Heuristics

Rule of thumb /educated guess approach which is used

when unfeasible to analyse all eventualities

This leads to a "good enough" result although it is not 100% reliable.

Advantages of heuristics

Heuristics can usually find a solution close to the best solution available.

Heuristics save time as you may not to investigate every single possibility to get a definite answer.

Heuristics is very practical and can be easily implemented.

Disadvantages of heuristics

It will not guarantee that you will find the 'best' solution as it aims to find a solution quickly that is 'good enough.'

There needs to be careful consideration to be made between accuracy and time.

The heuristic values may be incorrect which can lead to inaccurate solutions being found.

Intractable problems

problems that is practically impossible to solve — i.e., there are known algorithmic solutions, but the algorithms are too inefficient to solve the problem when the number of inputs grows large

Performance modelling

When the behaviour of something is tested or simulated before it is used in the real world

It is a systematic approach that can be used for evaluating and predicting the performance characteristics of a software system

The results of performance modelling can help companies judge the capabilities of a system, how it will cope in different environments and assess whether it is safe to implement

Advantages of performance modelling

Stress testing can ensure a system can cope with a large set of data or a large number of users.

You are able to predict problems and act on them before the problems actually occur in the real world.

Cheaper, faster and safer method of testing

Disadvantages of performance modelling

The outcome of performance modelling is only as useful as the accuracy of the data that is fed into it.

If the rules that made up the model are wrong then it will produce incorrect results.

Pipelining

Data is arranged in a series, the output of one process is the input of next.

Visualisation

When data or concepts are presented in simpler form for humans to understand

It will often create a graphical or visual representation of something to understand complex systems or data

Advantages of visualisation

Visualisation can simplify concepts that are easier for humans to understand.

It can make it easier to spot new trends and patterns that have not been spotted before.

It can be used to explain complex situations to allow programmers to get a better understanding of the problems of a current system.

Disadvantages of visualisation

Although it can show data in a visual way, it cannot explain why something is the way that it is.

Different people may interpret the visualisations in different ways.

The way that the data is presented can have an impact on its understanding.