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
How is prefetching managed?
Prefetching is managed by algorithms which predict with high accuracy that instructions/data will be needed soon
Potential disadvantage of caching
Wrong data is fetched frequently and has to be removed, making it difficult to keep up with the correct sequence of instructions/data
Top-down design/stepwise refinement (definition)
Technique for breaking down a problem into major tasks, then further breaking these down into subtasks, until each subtask is simple enough to be a self-contained module
Advantages of decomposition
- Makes programming easier
- Makes code easier to test and maintain
- Some components may be reusable
- Specialists within a team can be designated the tasks most relevant to their speciality
Hierarchy chart (definition)
Visual tool for representing the structure of a program, showing how “levels” of modules relate to form the solution - each module is no more than a page of code
Problem recognition (definition)
Identifying where and what a problem is
Why is procedural thinking important?
Some segments are event-driven so the order in which a user behaves can be largely unpredictable
Code reuse/ libraries / validation and sanitation techniques can be applied
Consider which variables are local/global
Key aspects of procedural thinking
- Order of steps to a solution
- Identifying components of a problem
- Identifying solution functions/procedures for each problem component
How can abstract thinking be defined + summarized?
Removing unnecessary details and including only relevant details
How can thinking ahead be defined + summarized?
Identifying inputs, outputs, preconditions and reusable components of a system
How can thinking procedurally be defined + summarized?
Breaking a large complex problem down into simple subtasks
How can thinking logically be defined + summarized?
Identifying where decisions (selection) will be made, including conditions and outcome
Three fundamental parts of a program
Selection - making a choice
Sequence - following instructions in an order
Iteration - repeating until a condition has been met
