2.2.2 Computational Methods Flashcards
What is abstraction?
- Separating ideas from reality
- Removing unnecessary details in order to simplify complex problems
What is the halting problem?
- He proved that there are problems that exist that are not computable
- Some problems cant be solved by computers
What were the limits of algorithms held on until later?
- Existing hardware
- Memory size
- Processor speed
What are tractable problems?
- A tractable problem is any problem that can be solved in polynomial time or better
- The algorithm to solve the problem will run quickly enough to be practical and usefuk
We are interested in algorithms that can solve problems …
- In a reasonable amount of time
- Using a reasonable amount of memory
What are intractable problems?
- Any problems that can’t be solved in polynomial time or better.
- As soon as input increases - computer takes longer to solve
- Can use heuristics for intractable problems that find a “good enough” answer
What are some features of tractable problems that make them great for computational methods?
- Enumeration
- Theoretical Approach
- Abstraction/ Decomposition
- Simulation and Automation
What is Enumeration?
- Designing an algorithm that performs an exhaustive search and attempts all possible solutions until the correct one is found.
What is Theoretical Approach?
- Putting a problem into pure theory and becomes easy o represent using mathematic equations.
- Computers are great at math’s - better to solve algorithms
What is Simulation?
- Process of designing a model of a real system in an attempt to understand its behaviour
What is automation?
- Building problem solving models and putting them into action
- Both simulation and automation make heavy use of abstraction and turn complex problems into 1 that can be more easily solved by algorithms.
What are the key principles of computational methods?
- Decomposition
- Pattern Recognition
- Abstraction
- Calculations and storage
What is Problem Recognition?
- It is the ability to “recognise/ acknowledge” that an issue exists or that a situation needs attention in an existing process/program
- Define the problem and determine what it is
When presented with a scenario for problem recognition what are some questions to think about?
- Is there a problem that needs to be solved?
- If so what is the nature of the problem?
- What data do you need to acquire in order to understand the problem
- What variables are in play that could alter the current state of the problem
- What techniques should be put into consideration
What is Problem Decomposition?
- Process of taking a large problem and breaking it down into several smaller problems
- Depending on size and complexity of the problem, these smaller problems can often be broken down further
- Repeat process, explore the problem until each lowest level boxes represent a single task/ action which can be put into a procedure, module, function or method.
What is step-wise refinement and top-down modular?
- Using step-wise refinement to produce a top down modular design
- Way of tackling problem decomposition
Exam Question: Describe how decomposition can be used in the design of the game Four in a Row
- Breaks a problem down into component parts
- Game can be divided into subprograms
- Subprograms can then be programmed as subroutines
What is Divide and Conquer?
- Is a technique that reduces the size of a problem with each successive iteration
- Splitting a task down into smaller tasks which are then tackled separately.
What is backtracking?
- Process of incrementally building towards a solution and abandoning partial success when the solution can’t be completed and going to a previously successful match
- Used for logic problems, path/route-finding
What is Data Mining?
- Analysing vast amounts of data gathered from a variety of sources to discover new information and trends
What can Data Mining be seen in?
- Used by companies to maximise profits.
- Weather Modelling
- Business and Economics
- Stock Market
- Medical Research
What is Heuristics
- Rule of thumb
- Make use of our experience to find a solution that is good enough
- A solution that has high probability of being correct may be acceptable and provide good results
Exam Question: A multi national retailer has a very large database, storing customers, stock and orders. The retailer uses data mining to retrieve a variety of information. Explain how they will use data mining?
- Can look for links between a customer’s purchases
- Give recommendations for further purchases
- Check for days/times/months where increases are likely and what the increase will purchase
- Matching sales
What is Performance Modelling?
- Process of approximating how well models perform using mathematical approximations and simulations
Performance Modelling: Company tested a new high-tech cloud based server. May send millions of requests - test understress. However this is expensive and hard to replicate. What can they do?
- Instead servers could be closely monitored, while low-level transactions take place.
- Mathematical modelling can be used to calculate how servers would perform under more stress
- Used in game development - may use beta testing
What is Pipelining?
- Completing 3 instructions simultaneously
- Whilst one is being fetched, another is being decoded another being executed
What is Visualisation?
- Includes a variety of techniques (diagrams, images, graphs, flow charts) that aim to illustrate what a problem entails
- Allows us to create a mental image of what a program will do
What are some benefits of Visualisation techniques?
- Can be used to explain complex tasks, scenarios or situations
- Can be used to model, represent, analyse, summarise concepts and data
- Present information which is more easy to understand
- Can offer alternative views as how to solve problems.
Exam Question: Describe the term Pipelining
- Data/ processes arranged in a series, the output of 1 process is the input of the next
Exam Question: Identify 2 advantages of using visualisation
- Visualisations benefit humans rather than computers
- Visualisations present information in a simpler form to understand
- Visualisations can best explain complex situations
