Fundamentals of Computational Thinking. Flashcards
What is logical reasoning?
The process of using a set of given facts to determine whether new facts are true or false.
What are the advantages of logical reasoning?
Helps understand the nature of problems, identify the facts relevant to the problem and to draw conclusions.
What is an algorithm?
A step-by-step procedure for carrying out a particular task.
What is automation?
Creating a computer model of a real-life situation and putting it into action.
How is automation done?
Understanding the problem
Creating suitable algorithms
Using appropriate data to solve the problem.
What are the considerations with automation?
Identify the key factors that make the model accurate and to consider what data to use and where to get it from.
What is abstraction?
To reduce problems to their essential features, ignoring the unnecessary details.
What is representational abstraction?
Process of removing unnecessary details so only information required to solve the problem remains.
What is abstraction by generalisation/ categorisation?
The concept of reducing problems by putting similar aspects of a problem into hierarchical categories.
What is procedural abstraction?
The concept that all solutions can be broken down into a series of subroutines.
What is Top-Down design?
The main system at the top and breaking it down into smaller units.
What are the considerations of Top-Down design?
What event triggers the subroutine
How subroutines link together
How errors are handled.
What is functional abstraction?
Breaking down a complex problem into a series of reusable functions.
Main processes defined in terms of functions.
What is data abstraction?
Hiding how data is represented so it is easier to build a new kind of data object.
Separates implementation from interface.
What is data composition?
Data objects are combined to create a compound structure.
What is problem abstraction?
Reducing a problem into its simplest components until the underlying processing requirements to solve the problem are identified.
What is information hiding?
The process of hiding all the details of an object that doesn’t contribute to its essential characteristics.
What is encapsulation?
A method of implementing the information hiding principle by storing data and methods within a class/ object.
What is decompositon?
Breaking down a large task into smaller more manageable subtask.
What is deprocedural composition?
The process of looking at system as a whole then breaking it down into subroutines needed to complete the task.
What is composition?
Building up a whole system from smaller units.
What is procedural composition?
Process of creating a working system from the abstraction.
Linking procedures to make compound ones and combining data structures to form compound structures.
What are finite state machines (FSM)?
Any device that stores its current status and whose status can change as the result of an input.
What are FSM used for?
Used as an conceptual model for designing and describing systems.
What are state transition diagrams?
A visual representation of an FSM.
Uses circles to represent each state and arrows to represent the transitions that occur as a result of an input.
What is a state transition table?
A tabular representation of an FSM machine.
What is a Turing machine?
A theoretical model of computation.
A FSM with the ability to read/write data to an infinite tape.
What components make up a Turing machine?
Tape divided into cells, where each cell contains a symbol. (Acts as memory)
Read/Write head which travels along the tape one cell at a time.
Finite alphabet of symbols.
What does the symbol □ mean in the Turing machine?
An empty/blank cell.
What states must the Turing machine contain?
Start state
At least one state
Halting state, which stops the Turing machine.
What is the definition of a transition function for Turing machines?
A method of indicating how the machine moves between states and what data is written at each state.
What is the formula for transition functions?
δ(CurrentState, InputSymbol) = (NextState, OutputSymbol, Movement)
What is a Universal Turing machine?
A theoretical machine that can simulate any number of Turing machines by taking their description and input data, to produce a range of outputs.
What is a regular language?
Any language that can be described with regular expressions or FSM.
What is a regular expression?
A notation containing strings of characters that can be matched to the contents of a set.
What are the uses of regular expressions?
To define and search a set.
What is a set?
A defined collection of objects that do not repeat.
What does a|b|c mean in regular expressions?
a or b or c
What does abc mean in regular expressions?
a and b and c
What does * mean in regular expressions?
Zero or more of the proceeding element.
What does + mean in regular expressions?
One or more of the proceeding element.
What does ? mean in regular expressions?
Zero or one of the proceeding element.
How can regular expressions be represented?
Using FSMs.
What does . mean in standard expressions?
Wildcard - matches to any character.
eg: .ole = mole, hole, vole
What are standard expressions?
Used to describe a sets of strings that conform to a particular pattern.
What does [] mean in standard expressions?
Matches a single character.
eg: [mh]ole = mole, hole, not vole
What does [^] mean in standard expressions?
Matches any character except the one in the brackets.
eg: [^m]ole = vole, hole, not mole
What does {a,b} mean in standard expressions?
Matches the character any number of times.
eg: a{2,5} = aa,aaaa, not a
What is a context-free language?
A method of describing the syntax of a language when the language is too complex for regular expressions.
What is Backus-Naur Form (BNF)?
A formal notation describing the syntax of a language.
How does BNF work?
Breaks down symbols until the terminal symbol is reached. (Cannot be broken down any more).
What does <> mean in BNF?
Surrounds symbols or elements.
What does ::= mean in BNF?
“is defined as”.
What is recursion in BNF and give an example?
A method that allows a set to be concise while allowing an infinite number of combinations.
<digit> = 0|1|2|3|4|5|6|7|8|9
<integer> = <digit>|<digit><integer>
</integer></digit></digit></integer></digit>
What are syntax diagrams?
A way of representing context-free languages.
What does an oval represent in syntax diagrams?
A terminal element.
What does an rectangle represent in syntax diagrams?
A non-terminal element.
What is set building/comprehension?
The process of creating sets by describing them using notation, rather than listing.
What does {} mean in terms of set comprehension?
Contains the contents of the set.
What does | mean in terms of set comprehension?
“such that”
What does ∊ mean in terms of set comprehension?
“is a member of”
What does ^ mean in terms of set comprehension?
And
What does Ø mean in terms of set comprehension?
Empty set.
What are finite sets?
Sets that have cardinality, meaning it can be counted using natural numbers.
What is the Cartesian product?
Combining elements of multiple sets to create a set of ordered pairs.
eg: A = {a,b} B = {1,2}
result = {(a,1), (a,2), (b,1), (b,2)}
What is the union of sets?
A set of all elements in bot sets.
What is the intersection of sets?
A set containing elements common in both sets.
What is the difference of set A and B (A/B)?
A set of all the elements that are in set A but not in set B.
What is a subset?
A set where all elements of one set are entirely contained within another.
A = B
What is a proper subset?
One set entirely contained within another set, where the other set has additional element.
What is an algorithm?
A set of instructions required to complete a particular problem.
How is the efficiency of an algorithm determined?
How long it takes to run (time) and how much memory is required (space)?
What is a function?
Relates an input to an output.
What is the domain?
The set of values that can go into a function.
What is a codomain?
A set of values that could be output from a function.
What is the range?
The set of values actually produced by a function.
What is Big O notation?
A method of describing the time and space complexity of an algorithm.
What does Big O notation calculate?
The maximum amount of time an algorithm would take to complete.
How much time and space it takes to execute an algorithm as the input size increases.
What is time and space complexity?
How much time and space an algorithm requires.
What is the input size?
Whatever you’re asking an algorithm to work with?
What is O(1)?
Constant time
An algorithm that executes in the same amount of time regardless of the input size.
What is an example of O(1)?
Accessing an array, as accessed directly by referring to its position.
What is O(N)?
Linear function
When the runtime of the algorithm will increase directly proportional to the input size.
What is an example of O(N)?
Looping around a list.
What is O(N²)?
Polynomial function
When the runtimes of the algorithm will increase proportionally to the square of the input size.
What is an example of O(N²)?
Nested statements
Bubble sorts
What is O(2ⁿ)?
Exponential function
When the runtime doubles with every additional unit increase in the input size.
What is the problem with O(2ⁿ)?
It is an intractable problem, meaning it can’t be solved with a computer in a reasonable amount of time if the input size is large.
What is O(logN)?
Logarithmic function
What is an example of O(logN)?
Binary search O(log₂N)
As each subsequent split of the data takes less time as only half the data is being searched.
What is Big O notation used for?
Find the most efficient solution to a problem.
What is the order of efficiency with Big O notations?
O(1)
O(logN)
O(N)
O(N²)
O(2ⁿ)
What is an tractable problem?
A problem that can be solved in an acceptable amount of time.
What is an intractable problem?
A problem that cannot be solved in an acceptable time frame, but is theoretically possible to solve.
What are heuristic algrithms?
Algorithms that provide and incomplete or approximate solution to intractable problems, buy ignoring certain elements or accepting a non-optimal solution.
What is an unsolvable problem?
A problem that has been proven to not be solved on a computer.
What is the Halting problem?
It is impossible to write a program that can work out whether another problem will halt given a particular input.
