Computable
Computable if we can come up with an algorithm which will solve the problem in a finite number of steps
intractable problem
a problem that cannot be completely solved e.g. travelling salesperson problem
problem decomposition
The process of taking a big problem and breaking it down into smaller problems until you have fully explored each of the problems. (Each smaller problem = one module of code)
Abstraction
The process of deciding which details are needed to solve the problem and removing the unnecessary details to help solve the problem more easily.
Divide and Conquer
reduces the size of the problem over successive iterations: look at a set of rules, discard data then repeat with left over information.
Performance modelling
the process of carrying out mathematical approximations of how well models perform.
benefits of performance modelling:
- tests a program before its made, helps prevent on air failure
- saves money (the complex calculations are not actually carried out
- helps find unexpected errors
- system is more easily analysed
Pipelining
The process of taking a task and splitting it into smaller tasks then overlapping the processing to improve the overall performance
Advantages of pipelining
- improves performance, increases throughput
-
disadvantages of piplining
- doesn’t always improve performance
- physical design and code is more complex
- if a pipeline has to be flushed it wastes time
- not all instructions can take advantage of pipelines
drawbacks of performance modelling
- can be expensive to build a model
- sometimes it is difficult to interpret the results
advantages of abstraction
- simplifies the problem (it can process faster/ has better memory requirements)
disadvantages of abstraction
- may remove too much detail (i.e. the program may be too simple and not reach the users needs.
disadvantages of divide and conquer
- may not be complex enough/ may not be able to be split
- can result in full stacks
- may end up duplicating subproblems
advantages of modules
- Work can divided between a team, saves time as work takes place in parallel
- each team must only know what values to go into their subroutine and their expected functionality
- breaks problem down, easier to understand/test/debug/read
- Modules can be given to teams with specific expertise
- each subroutine can be tested individually before its combined to the main program
- code can be reused
disadvantages of modules
- it can be hard to join all the modules together
- extra memory space and time for execution required
- testing and debugging can be more time consuming
Visualisation
The ability to picture a problem and its solution in a visual way to make it easier to understand
visualisation advantages
- helps understanding
visualisation disadvantages
- time consuming
backtracking
the process of incrementally building up towards a solution, abandoning partial success then going back and trying again a different way.
concurrent programming
where one computation occurs simultaneously with another and doesn’t wait for the other one before advancing.
advantages of backtracking
- sometimes it is the best option to solve a problem
- simple to implement
disadvantages of backtracking
- not efficient for solving a strategic problem
- runtime is slow
- need alot of memory space
- to solve larger problems other algorithms may be required
Heuristic
Making use of experience to find an acceptable solution (not always the optimal solution).
e.g. rules of thumb, educated guessed, common sense. Often derived from a previous experience with a similar problem
