What is meany by a computable problem?
A problem that can be solved using an algorithm
Give 3 limiting factors to computable problems
- Processing power
- Processor speed
- Computer memory
- Time
State 2 factors which may be considered during the problem definition phase
- Strengths and weaknesses of current solution
- Volume/type/frequency/nature of: inputs, outputs, stored data
What is the name given to the process in which problems are continually broken down until each subproblem can be represented as a subroutine?
Problem decomposition
State 2 purposes of problem decomposition
- Identify sections which can make use of pre-coded modules or libraries
- Save time coding
- Simplify project management
- Simplify testing and maintenance
- Faster project delivery
- Develop sections in parallel
Describe how the divide and conquer technique works
- The problem size if halved with every iteration
- Each individual subproblem is then solved recursively
- The solutions to the subproblems are then recombined to form the final solution to the problem
Give 2 applications of divide and conquer
- Merge sort
- Binary search
- Quick sort
Which programming construct do many problems solve using divide and conquer use?
Recursion
What is representational abstraction?
A computational technique in which excessive details are removed to simplify a problem
What type of abstraction is used to group together sections of the problem based on their functionality?
Abstraction by generalisation
State 2 problem solving techniques
- Backtracking
- Data mining
- Abstraction
- Divide and conquer
- Visualisation
- Performance modelling
- Pipelining
What is meant by heuristics?
Heuristics are 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 or resource-intensive to find
What is meant by performance modelling?
- Provides mathematical methods to test a variety of loads on different operating systems
- Performance modelling provides a cheaper, less time-consuming, safer method of testing applications
Describe how backtracking works
- The backtracking algorithm 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. it backtracks to the previous stage and visits an alternate path
When might heuristics be used in problem-solving?
When the standard way to solve the problem is unreasonably time-consuming or resource-intensive
State 2 advantages of using performance modelling
- Safe
- Relatively inexpensive
- Less time-consuming
What is pipelining?
- A process in which tasks are developed in parallel
- The output of one process in pipelining becomes the input of another, resembling a production line
What is the name given to the technique used to identify patterns and trends in large sets of data?
Data mining
What is meany by data mining?
- Data mining is a technique used to identify patterns or outliers in large sets of data, termed big data
- Data mining is used in software designed to spot trends or identify correlations between data which are not immediately obvious
