Computational Thinking Flashcards
What is representational abstraction?
The process of removing unnecessary details until its possible to represent the problem in a way that it can be solved
What is abstraction by generalisation?
The process of placing aspects of the problem into broader categories to arrive at a hierarchical representation
What is procedural abstraction?
The concept that solutions can be broken down into a series of subroutines or procedures
All of which can be solved individually and can be further broken down
What is functional abstraction?
Abstracting a procedure into a group of common functions
What is problem abstraction?
The process of reducing a problem down into its simplex components until the underlying processing requirements that solve the problems are identified.
What is information hiding?
The process of providing a definition or interface of a system whilst hiding the inner workings (e.g. GUI hides the complexity of a program)
What is decomposition?
The process of breaking large complex tasks into smaller, more manageable tasks
What is composition?
Creating a working system from the smaller processes
What is automation?
Creating computer models of real life situations and putting them into action
(e.g. Computer Model that models the profits of a coffee shop)
What is a set?
A data type which contains unordered, unique values
What is the cardinality of a set?
The number of elements within a set (only in finite sets)
What is a subset?
A set which contains items from another set, but not every item from the other set
Symbol: ⊆
Membership of a set symbols:
In a set: ∈
Not in a set: ∉
What is a union? (combining sets)
Elements in A OR B
Set A ∪ Set B
What is an intersection? (Combining Sets)
Elements in A and B
Set A ∩ Set B
What is a difference? (Combining Sets)
A set which contains items exclusive to one set
A NOT B
B NOT A
A\B = {x : x ∈ A and x ∉ B}.
What does the * represent? (Regular Expressions)
- Means 0 or more repetitions
ab* = {a, ab, abb, abbb, …}
What does the + represent? (Regular Expressions)
+ Means 1 or more repetitions
a+b = {ab, aab, aaab, …}
What does the ? represent? (Regular Expressions)
? means that the previous character is optional
a?b = {b, ab}
What does | represent? (Regular Expressions)
means or
a|b = {a, b}
What does () represent? (Regular Expressions)
() is used to group regular expressions
(ab) | (cd) e = {abe, cde}
What is Big O Notation?
Big O Notation describes the complexity of an algorithm, by assuming the worst case scenario.
What is the order of complexity? (Least Complex to Most Complex)
Constant O(1)
Logarithmic O(logN) Binary Search
Linear - O(N) Linear Search
Linear Logarithmic - O(NLogN) Merge Sort
Polynomial - O(^2) Bubble Sort
Exponential - O(2^N) Recursively Counting Fibonacci Numbers
Factorial - O(N!) Travelers Problem
What is an intractable problem?
A problem that is theoretically possible, but not within polynomial time
(e.g. Factorial or Exponential)
What is a heuristic algorithm?
An algorithm which doesn’t give a fully accurate answer, but one with an approximate solution within a polynomial time
What is the halting problem?
An unsolvable problem - it is impossible to write an algorithm to determine if another algorithm will finish giving a particular input. Therefore it isn’t possible to create a turing machine to solve it
What is a Universal Machine?
A turing machine which can simulate the behaviour of any other Turing Machine by reading the description of the turing machine and faithfully executing operations on data
Acts as an interpeter as they can read their instructions in sequence before faithfully executing instructions on their input data.
Why are Turing Machines useful?
They provide a definition of what is computable, meaning they can prove that there are problems which cannot be solved by computers - such as the halting problem
What is a turing machine?
A formal model of computation which consists of a finite state machine, a read/write head and also a tape which is infinitely long
It is viewed as a computer which runs a single program
Why is a Universal Machine deemed more powerful than a regular computer?
Contains an infinite read/write head - therefore infinite memory
State the relationship between an algorithm and a turing machine
A turing machine can only be designed to solve a problem if an algorithm already exists for the problem
Why is a UTM considered an interpreter?
Reads instructions line by line and executes them
