Fundamentals of Computational Thinking Flashcards
Define Automation
Creating a computer model of a real-life situation and putting it into action
Define Logical reasoning
the process of using a given set of facts to determine whether new facts are true or false.
Define representational abstraction
The process of removing unnecessary details so that only information that is required to solve the problem remains.
Define the term Algorithm
A sequence of instrucutions to achieve a specific outcome in a finite time.
Define decomopsition
Breaking down a large task into a series of subtasks
Define composition
Building up a whole system from smaller units. (Opposite of decomposition)
What is a Finite State Machine? (FSM)
Any device that stores its current status and whose status can change as the result of an input. (Mainly used as a conceptual model for designing and describing systems.)
What is a state transition diagram
A visual representation of a FSM using circles and arrows.
Single circle = state
Arrow = input
Double circle = Accepting state or final state
What is a state transition table.
A tabular representation of a FSM showing:
Inputs, Current State and Next State (3 columns)
Define the term Mealy Machine
This is a finite state machine with outputs
What is a Turing Machine
A theoretical model of computation
Define the term Alphabet in terms of a Turing Machine
The acceptable symbols, charactor and/or numbers for a given Turing Machine
What is a read/write head?
The theoretical device that writes or reads from the current cell of a tape in a Turing machine.
What is a halting state?
A state that, when reached, stops the Turing machine
What is a regular expression?
Notation that contains strings of characters that can be matched to the contents of a set.
Define the term regular language
Any language that can be described using regular expressions
What does a + mean in a regular expression?
One more more of the previous statement
What does a ? mean in a regular expression?
Either zero or one of the previous statement
What does a | mean in a regular expression?
The previous statement or the next statement
What does a * mean in a regular expression?
Zero or more of the previous statement
Therefore what is the meaning of this statement?
(a|b)c
a or b and c
What does {x, y} mean in a regular expression where x and y are different integers?
The previous statement at least x times, but no more than y times (therefore it is inclusive of those numbers)
What is a function defined as in Big O notation?
It relates each element of a set with the element of another set. E.g. f(x) = 2x
What is the domain?
All the values that may be input to a mathmatical function.
What is the codomain? (range in Maths)
All the values that may be output from a mathmatical function.
Big O notation describes two complexities of an algorithm. What are they?
1) Time complexity - how much time an algorithm requires to complete
2) Space complexity - how much space an algorithm requires to complete
What does the notation O(1) represent?
Constant time - where the time taken to run an algorithm does not vary with the input size.
What does the notation O(N) represent?
Linear Time - where the time taken to run an algorithm increases in direct proportion to the input size
What does the notation O(N^2) represent?
Polynomial time - where the time taken to run an algorithm increases in proportion to the square of the input size
What does the notation O(2^N) represent?
Exponential time - where the time taken to run an algorithm increases as an exponential function of the number of inputs.
E.g. for each additional input the time taken might double.
THIS IS BAD!
What does the notation O(logN) represent?
Logarithmic time - where the time taken to run an algorithm increased or decreases in line with a logarithm.
What is the order of efficiency of all 5 of the Big O notations?
1) O(1) or Constant Time
2) O(logN) or Logarithmic Time
3) O(N) or Linear Time
4) O(N^2) or Polynomial Time
5) O(2^N) or Exponential Time
What is a 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 within an acceptable time frame.
Define the term Heuristic.
A method for producing a ‘rule of thumb’ to produce an acceptable solution to intractable problems.
What is a Halting Problem?
An example of an unsolvable problem where it is impossible to write a program that can work out whether another problem will halt given a particular input.
