1
Q
What is abstraction?
A
- Separating ideas from reality
- Removing unnecessary details in order to simplify complex problems
2
Q
What is the halting problem?
A
- He proved that there are problems that exist that are not computable
- Some problems cant be solved by computers
3
Q
What were the limits of algorithms held on until later?
A
- Existing hardware
- Memory size
- Processor speed
4
Q
What are tractable problems?
A
- 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
5
Q
We are interested in algorithms that can solve problems …
A
- In a reasonable amount of time
- Using a reasonable amount of memory
6
Q
What are intractable problems?
A
- 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
7
Q
What are some features of tractable problems that make them great for computational methods?
A
- Enumeration
- Theoretical Approach
- Abstraction/ Decomposition
- Simulation and Automation
8
Q
What is Enumeration?
A
- Designing an algorithm that performs an exhaustive search and attempts all possible solutions until the correct one is found.
9
Q
What is Theoretical Approach?
A
- Putting a problem into pure theory and becomes easy o represent using mathematic equations.
- Computers are great at math’s - better to solve algorithms
10
Q
What is Simulation?
A
- Process of designing a model of a real system in an attempt to understand its behaviour
11
Q
What is automation?
A
- 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.
12
Q
What are the key principles of computational methods?
A
- Decomposition
- Pattern Recognition
- Abstraction
- Calculations and storage
13
Q
What is Problem Recognition?
A
- 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
14
Q
When presented with a scenario for problem recognition what are some questions to think about?
A
- 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
15
Q
What is Problem Decomposition?
A
- 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.
16
Q
What is step-wise refinement and top-down modular?
A
- Using step-wise refinement to produce a top down modular design
- Way of tackling problem decomposition
17
Q
Exam Question: Describe how decomposition can be used in the design of the game Four in a Row
A
- Breaks a problem down into component parts
- Game can be divided into subprograms
- Subprograms can then be programmed as subroutines
18
Q
What is Divide and Conquer?
A
- 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.
19
Q
What is backtracking?
A
- 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
20
Q
What is Data Mining?
A
- Analysing vast amounts of data gathered from a variety of sources to discover new information and trends
21
Q
What can Data Mining be seen in?
A
- Used by companies to maximise profits.
- Weather Modelling
- Business and Economics
- Stock Market
- Medical Research
22
Q
What is Heuristics
A
- 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
23
Q
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?
A
- 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
24
Q
What is Performance Modelling?
A
- Process of approximating how well models perform using mathematical approximations and simulations
25
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
26
What is Pipelining?
* Completing 3 instructions simultaneously
* Whilst one is being fetched, another is being decoded another being executed
27
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
28
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.
29
Exam Question: Describe the term Pipelining
* Data/ processes arranged in a series, the output of 1 process is the input of the next
30
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
