Theory of Computation Flashcards
What is an algorithm?
A sequence of steps that can be followed to complete a task that always terminates.
What are the 4 constructs of algorithms?
1) Iteration
2) Selection
3) Variable assignment
4) Sequence
What must we consider when evaluating different algorithms?
Efficiency, how many cases does it work, and error handling
What are the 4 main techniques of computational thinking?
1) Abstraction
2) Decomposition
3) Pattern recognition
4) Algorithmic thinking
What is abstraction?
Removal of detail from a a problem to focus on what is necessary to solve
What is decomposition?
Breaking a problem down into smaller problems, each of which is easier to solve
What is pattern recognition?
Comparing a problem to similar problems that are already solved and applying the same or similar solution
What is algorithmic thinking?
Writing a solution to a problem using algorithmic constructs (iteration, sequence, assignment, selection)
What are the different forms of abstraction?
1) Procedural abstraction
2) Functional abstraction
3) Data abstraction
4) Problem abstraction / reduction
What is representational abstraction?
The representation arrived at by removing unnecessary details from the problem.
What is an example of representational abstraction?
Maps
What is information hiding?
The process of hiding all details of an object that do not contribute to its essential characteristics
What is abstraction by generalisation?
Grouping common characteristics to arrive at a hierarchical relationship of the inheritance type
What is procedural abstraction?
Abstracting values used in a computation to leave a single computational method (procedure)
What is functional abstraction?
Abstracting the method of computation and the resultant function only focuses on inputs and outputs (functions)
What is data abstraction?
Isolating how a compound data structure is used from how it is constructed
What is problem abstraction (reduction)?
Removal of detail until it is possible to solve because it reduces to one that has already been solved
What is decomposition?
The process of breaking down a complex problem into smaller sub-problems. Each sub-problem accomplishes a specific task that is easier to solve. These can be further subdivided until a problem is solvable.
What is composition?
Form of abstraction which combines procedures to form compound procedures to solve a complex problem
What is automation?
The process of using abstractions of real world phenomena (models) to solve problems
How is automation done?
Create algorithms, implement in code, making models in data structures and executing code on data structures
