Computational Methods Flashcards
What are the features that make a problem solvable by computational methods
- A problem that can be solved using an algorithm is computable
- Problems can only be solved if they can be solved within a finite, realistic amount of time
- Problems are constrained, therefore, by factors such as processing power, speed and memory.
- Breakthroughs in technology have made it feasible to solve more problems computationally than ever before
What is Problem Recongintion
- Clearly identifying what the problem is
- Stakeholders state what they require from the finished product and this information is used to clearly define the problem
What is Decomposition
- Decomposition splits a problem into smaller sub problems
- Repeated decomposition gives soluable parts
- Each part can lead to a sub routine / module
- Each part can be given to a different team so the work can be split
- One team can work on one part while another team works on another one (Parallel Creation)
What is the method of Divide and Conquer
- Divide - involves halving the size of the problem with every iteration
- Conquer - Each individual subproblem is solved
- Merge - the solutions to the subproblems are then recombined
What are some examples of the Divide and Conquer method
- Binary search
- Quick sort and Merge sort
What are the Different Types of Abstraction
- Representational Abstraction - analysing what is relevant to a given scenario and simplifying a problem based on this information
- Abstraction by Generalisation - involves grouping together similarities within a problem to identify what kind of problem it is
- Data abstraction - details about how data is being stored are hidden. As a result, programmers can make use of abstract data structures such as stacks and queues without concerning themselves with how these structures are implemented
- Procedural Abstraction - pushing and popping items to and from a stack without having any knowledge about the code used to implement this functionality.
What is Backtracking
- Works by methodically visiting each path and building a solution based on the paths found to be correct.
- If a path is found to be invalid at any point, the algorithm backtracks to the previous stage and visits an alternate path.
- An eample of this is a Depth-first graph traversals
What is Data Mining
- A technique used to identify patterns or outliers in large sets of data, termed big data.
- Big data is typically collected from a variety of sources
- An example of data mining is that it is used in software designed to spot trends and make predictions about the future based on previous trends
What is the Potential Problem of Data Mining
As data mining often involves the handling of personal data, it is crucial that it is dealt with in accordance with the data protection law
What is Heuristics
- A non-optimal, ‘rule-of-thumb’ approach to problem-solving which are used to find an approximate solution to a problem when the standard solution is unreasonably time-consuming to find
- The solution found through using heuristics is not perfectly accurate but does find a find quick solution
- Examples of Heuristics are the Travelling Salesman Problem, the A* grade algorithm and machine learning
What is Performance Modelling
Performance modelling providing mathematical methods to test a variety of loads on different operating systems
What are the Advantages of Performance Modelling
- Cheaper
- Less time-consuming
- Safer method of testing applications
- An example of Performance Modelling is in safety-critical computer systems where it is not safe to do a real trial run before the system can be implemented (such as in a plane)
What is Pipelining
A process that allows for projects to be complete in parallel as modules are divided into individual tasks
What is Visualisation
- When data can be presented in a way that is easier for us to understand
- Depending on the type of data, data may be represented as graphs, trees, charts and tables.
- An example of visualisation is that in businesses it is used to pick up on patterns which can be used to inform business decisions
