Theory Of Computation Flashcards
What is an algorithm?
A sequence of steps to complete a known task and that always terminates
What are some features of a good algorithm?
- Allow for invalid inputs
- Be efficient, involving as few steps as possible
- Be understandable by others
What are the constructs of an algorithm?
- Sequence
- Assignment
- Selection
- Iteration
What is a “dry-run”
Testing an algorithm using a trace table
What can make an algorithm preferable?
- More efficient
- More robust and works in more cases
- Better at handling unexpected input
What are some techniques for interpreting algorithms?
- Reading comments that explain how the code works
- Identifiers can indicate a variable’s purpose or subroutine’s function
- “Dry-run” the algorithm to see how variables change
What is computational thinking?
Approach to solving complex problems through the application of abstraction, decomposition, pattern recognition and algorithmic thinking.
What is abstraction?
Removal of detail to focus on what is necessary to solve the problem
What is pattern recognition?
Solving problems by recognising similarities with previously solved problems and applying a similar solution
What is algorithmic thinking?
Creating a solution to a problem using algorithmic constructs
What is representational abstraction?
A representation arrived at by removing unnecessary details
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 by common characteristics to arrive at a hierarchical relationship of the “is a kind” type
What is procedural abstraction?
Abstracting away the actual values used in a computation to leave a computational method: a procedure.
What’s is functional abstraction?
Build upon procedural abstraction, abstracting the actual method computation involved. The resulting function focuses on the inputs and outputs of the function only.
What is data abstraction?
Isolates how a compound data structure is used from how it is constructed
What is problem abstraction (reduction)?
The removal of detail from a problem until it is represented in a way that is possible to solve because the problem. Reduces to one that has already been solved
What are the two main approaches to abstraction?
- Representational abstraction
- Abstraction by generalisation
What are the different form of abstraction?
- Procedural abstraction
- Functional abstraction
- Data abstraction
- Problem abstraction
What is procedural decomposition?
- Breaking down a complex problems through into small 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 compositional abstraction?
Formed by combing the procedures that together will form compound procedures to solve larger/ more complex problems
What is compound data?
Building data abstraction by combining data objects
How is automation achieved?
- Designing and writing algorithms
- Implementing algorithms in program code, utilising the data structures that represent the data that has been modelled
- Executing the code to generate a solution to an agreed degree of accuracy
