COMP3 - Problem Solving Flashcards
Generalisation Abstraction
Take specific details about an object & assume they apply to other similar objects.
Called Abstraction by Classification.
Abstraction
Representation by removing unnecessary detail.
e.g. London Underground Map.
Humans are good at it, computers are not.
Data Representation Abstraction
Removing details from a problem until it is possible to solve.
Represent the problem in a way that is possible to solve.
Information Hiding
Allows division of equipment, hardware & software.
e.g. Cars built in models allows easy modification.
Well designed program decomposes source code into modulus using info hiding principle:
- Objects can have identical interfaces.
- Common interfaces means that users don’t have to be re-trained.
- To use an object, don’t need to know about internal design. It can be kept secret.
- Allows flexibility. Modules replaced with identical interface but different internal design.
Interface
A boundary between implementation and the world that uses it.
Provides an abstraction of the entity behind the boundary.
Separates methods of external communication from internal operation.
Decision Problems
When a problem has answers yes or no.
If an algorithm is non-computable and a decision problem, then it is UNDECIDABLE.
Tractable Problems
If a problem is arithmetic and computable, getting a solution depends on size of input or limitations of hardware.
If a problem has a reasonable time (no more than polynomial time), it is TRACTABLE.
O(n^2) & O(n^3) are tractable problems.
Intractable Problems
Problems that can be solved with algorithms with a time execution larger than polynomial time.
e. g. O(n!) is INTRACTABLE.
e. g. Intractable problem = time tabling students at college.
Heuristic Algorithm
An algorithm that produces usable solutions in reasonable time.
Based on knowledge, experience & judgement to solve intractable problems (educated guess).
May not produce optimal/formally correct solution, but good solutions to a problem.
