Fundamentals of Computational Thinking Flashcards
Decomposition
Breaking down a large task into a series of subtasks.
http://slideplayer.com/slide/9296226/28/images/29/Decomposition+/+Composition.jpg
Composition
Building up a whole system from smaller units. This is the opposite of decomposition.
Finite State Machine (FSM)
Any device that stores its current status and whose status can change as a result of an input. Mainly used as a conceptual model for designing and describing systems.
Finite - countable
State Transition Diagram - A visual representation of a FSM using circles and arrows.
Accepting State - The state that identifies whether an input has been accepted.
State Transition Table
A tabular representation of an FSM showing inputs, current state and next state.
http://image.ibb.co/dsVUYJ/AFB6_B8_F0_9_E9_F_4409_9_A5_C_C1_F7_BC5_B8_E9_B.jpg
Mealy Machine
A type of finite state machine with outputs
http://slideplayer.com/slide/8108911/25/images/11/Mealy+machine+0%C2%A2+Reset.+5%C2%A2+N/0.+N+++D/1.+10%C2%A2+D/0.+15%C2%A2+D/1.+symbolic+state+table..jpg
Cipher
An algorithm that encrypts and decrypts data, also known as code.
Shift Cipher
A simple substitution cipher where the letters are coded by moving a certain amount forwards or backwards in the alphabet.
Turing Machine
A theoretical model of computation
Alphabet - the acceptable symbols (characters, numbers) for a given Turing Machine
Read/Write Head - the theoretical device that writes or reads from the current call of a tape in a Turing machine.
Halting State - Stops the Turing machine
Start State - The initial state of a Turing Machine
Instruction Table - A method of describing a Turing machine in tabular form.
https://www.youtube.com/watch?v=Ty57TncUSno
Transition function/rule
A method of notating how a Turing machine moves from one state to another and how the data on the tape changes.
Universal Machine
A machine that can simulate a Turing machine by reading a description of the machine along with the input of its own tape. This can solve the limitation of the Turing machine of requiring that every process will need to have its own Turing machine to do it.
Regular Language
Any language that can be described using regular expressions.
Regular Expression
Notation that contains strings of characters that can be matched to the contents of a set.
Example:
a|b|c is a regular expression, which means that the set will contain either an ‘a’ or a ‘b’ or a ‘c’. A set is a collection of data that is unordered and contains each item at most once. It is written as follows showing the name of the set and the contents within brackets:
alphabet = {a, b, c, d, e, f, g, …}
integers = {0, 1, 2, 3, 4, 5, 6, 7, …}
Common Regular Expressions
a|b|c means ‘a’ or ‘b’ or ‘c’
abc means ‘a’ and ‘b’ and ‘c’
a*bc means zero or more ‘a’ followed by ‘b’ and ‘c’
(a|b)c means ‘a’ or ‘b’ and ‘c’
a+bc means One or more ‘a’ and ‘b’ and ‘c’
ab?c means ‘a’ and either zero or one ‘b’ and ‘c’
Context-free Language
An unambiguous way of describing the syntax of a language useful where the language is complex.
Backus-Naur Form (BNF)
A form of notation for describing the syntax used by a programming language
https://www.youtube.com/watch?v=x1gGInKNCRw
Terminal - In BNF, it is the final element that required no further rules.
Syntax Diagram
A method of visualising rules written in BNF or any other context-free language
https://www.google.ae/search?biw=1282&bih=1291&tbm=isch&sa=1&ei=Z1EUW_n5CsGKU-OespAB&q=syntax+diagram&oq=Syntax+dia&gs_l=img.3.0.35i39k1j0l2j0i30k1j0i5i30k1l5j0i8i30k1.1674655.1676091.0.1677263.9.9.0.0.0.0.223.1051.0j5j1.6.0….0…1c.1.64.img..3.6.1049…0i67k1.0.xbV0nqcvbMk#imgrc=jUPa6JDOzQELZM:
Big O Notation
A method of describing the time and space complexity of an algorithm.
Space Complexity - The concept of how much space an algorithm requires.
Time Complexity - The concept of how much time an algorithm requires.
Input Size - In Big O Notation the size of what ever you are asking an algorithm to work with eg data, parameters.
Constant Time O(1)
Means that the algorithm will always execute in exactly the same amount of time regardless of the input size.
Linear Time O(N)
Means that the runtime of the algorithm will increase in direct proportion with the input size. (the more inputs, the longer it will take)
Polynormial Function O(N^2)
Means that the runtime of the algorithm will increase proportionate to the square of the input size.
Iterative or nested statements such as bubble sorts and insertion sorts are examples of these as the program has to go back through itself again with each iteration.
Exponential Time O(2^N)
Where the time taken to run an algorithm increases as an exponential function of the number of inputs.
Logarithmic Time O(logN)
Where the time taken to run an algorithm increased or decreases in line with a logarithm.
Common Algorithms with Time Complexity in Big O Notation
O(1) - Indexing an Array
O(logN) - Binary Search
O(N) - Linear Search of an Array
O(N^2) - Bubble Sort
Selection Sort
Insertion Sort
Nested Loops
O(2^N) - Interactable ProblemsTractable Problem
A problem that can be solved in an acceptable amount of time.
Intractable Problem
A problem that cannot be solved within an acceptable time frame.
Unsolvable Problem
A problem that has been proved cannot be solved on a computer
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.
Finite Set*
A set where the elements can be counted using natural numbers up to a particular number
Infinite Set
A set that is not finite
Cardinality
The number of elements in a set
Countable Set
A finite set where the elements can be counted using natural numbers.
Countability infinite sets
Sets where the elements can be put into a one-to-one correspondence with the set of natural numbers.
Cartesian Product
Combining the elements of two or more sets to create a set of ordered pairs
