Theory Of Computation Flashcards
Define algorithm
A sequence of steps that can be followed to complete a task and that always terminates
What is representational abstraction?
Representation arrived at by removing unnecessary details
What is abstraction by generalisation/categorisation?
Grouping by common characteristics to arrive at a hierarchical relationship of the ‘is kind of’ type
What does procedural abstraction represent?
A computational method
What is a computational method or pattern?
The result of abstracting away the actual values used in any particular computation is a computational pattern or method (procedure)
What is information hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
What happens to the particular computation method in functional abstraction?
It is hidden
What is the result of procedural abstraction
A procedure, not a function
What abstraction can get you a function
Functional abstraction - disregards the particular computation method
Define data abstraction
A methodology that enables us to isolate how a compound data object is used from the details of how it is constructed ie. Stack implemented as an array and pointer for top of stack
What is problem abstraction?
When details are removed until the problem is represented in a way that it is possible to solve the problem
Define procedural decomposition
Breaking a problem into a number of sub-problems so that each sub-problem accomplishes an identifiable task which might itself be further subdivided
How can you build a compositional abstraction?
By combining procedures to form compound procedures
How can you build data abstraction?
By combining data objects to form compound data for example a tree data structure
What does automation require?
Putting models into action to solve problems
