Theory of Computation Flashcards
Computational Thinking (definition)
Stating a problem in a way that can be solved using algorithms, and then constructing an algorithm to solve the problem in the most effective way
Other name for computing
Automation of abstractions
Representational abstraction (definition)
Removing excess details to represent a problem by only its key features
Data abstraction (definition + example)
Hiding details about how data is being stored
e.g. programmers can use data structures without knowing how they are implemented
Abstraction by generalisation (definition)
Grouping similarities in a problem to categorise it by a type, to then use a common solution
Layers of abstraction (explanation + example)
Highest levels are closest to the user e.g. interface
Lowest levels are closest to reality e.g. interacting with machine components
Procedural abstraction (definition + example)
Abstracting the values used in a computation (set of operations) to create a procedure e.g. using a subroutine without understanding the internal process of it
Functional abstraction (definition)
Abstracting the computation method (operations) so that only the inputs and outputs are considered, creating a function
Problem reduction/abstraction (definition)
Removing details from a problem until it can be represented in a way that is possible to solve, because it has been reduced to one that has already been solved
Why is procedural abstraction needed? (explanation + examples)
Allows non-experts to hide information that is too complex or irrelevant for the systems purpose
e.g. 1: High level languages abstract machine code, making them easier to learn
e.g. 2: TCP/IP separates application, transport, internet and link so that each layer acts independently from the others
Advantage and disadvantage of abstraction
+ allows models and predictions to be made
- too much abstraction will make a model untrue of real life
The simplest abstraction of a computer
program
\/
Input > process > output
\/
storage
Algorithm (definition)
Set of step-by-step instructions to solve a problem
Why is abstraction needed? (explanation + example)
Removing unnecessary details and highlighting the most important ones improves clarity and makes the representation more useful for a function
e.g. flowchart is an abstraction of code
Graph data structure (explanation)
Abstraction to the point where only the necessary data elements and relationships between them are shown (the nodes and connections)
Why is thinking ahead important?
Maximise code efficiency and minimise errors
What techniques would be considered “thinking ahead”?
- Identifying inputs and outputs
- Determining preconditions
- Deciding what can be a reusable component
- Caching
Precondition (definition + example)
Something that must always be true in a solution to a problem e.g. must be below budget
Reusable component (definition + examples)
Taking self-contained pre-tested code from another program and applying it the the current program
e.g. 1: subroutines
e.g. 2: libraries
Benefits of reusing components
- shortens development time
- lowers development costs
- reduces the amount of redundant code
Application Programming Interface (definition + examples)
Set of functions allowing an app to access the features/data of another program e.g. the OS
e.g. Apple/Google password save
Caching (definition + explanation)
Temporary storage of recently/frequently used instructions/data by the OS into cache
Results in faster retrieval times as less data needs to be fetched from secondary storage
Web caching (definition)
Storing of HTML pages which have been recently looked at to avoid using up bandwidth if they are loaded again
Prefetching (definition + explanation)
Data is requested from main memory before it is required
This reduces fetching time as it is faster to fetch from registers than from main memory
