Theory of Computation Flashcards
Problem solving
The process of finding a solution to a difficult or complex issue
Algorithms
- A sequence of steps that can be followed to complete a task
- They always terminate rather than going on forever in a loop
Assignment
The process of giving a value to a variable or constant
Sequence
Instruction that are executed sequentially
Selection
The process of choosing an action to take based on the result of a comparison of values
Iteration
The process of repeating an operation
Abstraction
The name given to omitting unnecessary details from a problem, simplifying the solution
Representational abstraction
A representation of a problem arrived at by removing unnecessary details from the problem
Abstraction by generalisation
A grouping by common characteristics to arrive at a hierarchical relationship of the
“is a kind of” type
Information hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
Procedural abstraction
- Breaking down a complex model into a series of reusable procedures
- The actual values used are abstracted away to achieve a computational method
Functional abstraction
Abstracting the result of procedural abstraction, disregarding the particular method to leave just a function
Data abstraction
Specifies details of how data is actually represented, allowing for new kinds of data structures to be created
Problem abstraction
Details are removed from a problem until it is represented in a way that is solvable
Decomposition
A problem is divided into a series of smaller sub-problems that can be solved individually or further divided
Composition
Used to combine procedures to form a larger system
Automation
The process of putting abstractions of real world phenomena into action to solve
problems
Set
An abstract data type that contains unordered, unique values (that can be other sets)
Set comprehension
An alternative way of creating a set that selects the kind of values it wants from a larger set, instead of specifying each item individually
Empty sets
Sets that contain 0 elements. A = {}
Finite sets
A set with a limited number of elements
Infinite sets
A set with an unlimited number of elements
Countably infinite sets
An infinite set where you can list the elements in a sequence
Uncountably infinite sets
An infinite set where the elements cannot be listed in a sequence
Subset
Set A is a subset of Set B if it only contains items from Set B
Proper subset
Set A is a proper subset of set B if it only contains items
from set B, but not all of them
Countable sets
Sets that have the same cardinality as some subset of natural numbers
Union
The union of two sets is the set of all elements that are in either set or in both
Intersection
The intersection of two sets is the set of elements that are presented in both sets
Difference
The difference of two sets is the set of elements that are in the first set but not in the second
Regular expressions
Shorthand ways of describing sets
*
0 or more repetitions
+
1 or more repetitions
?
Previous character is optional
|
Or
()
Used to group regular expressions
Context free languages
Sets of strings and symbols that follow the rules of a context-free grammar
Context-free grammar
Production rules that describe which strings are and are not possible
Backus-Naur form
A context-free language where the left hand side is defined by the right hand side
Non-terminals
Text placed inside <>
Terminals
- Text without any brackets
- Cannot be broken down any further
Recursion in Backus-Naur form
A non-terminal can be defined in terms of itself, allowing for recursion to occur
Syntax diagrams
- A visual representation of a regular language
- Non-terminals are represented by rectangles
- Terminals are represented by ellipses
- The shapes are joined by arrows which indicate how strings can be formed from
the definitions
Big O notation
Defines the time complexity of an algorithm
Constant time
- O(C)
- Time is independent of input
Logarithmic time
- O(log2(n))
- Halves the number
of items each
iteration
Linear time
- O(n)
- In a worst case
scenario must go
through each item
once
Polynomial
- O(n^2)
- A loop inside a loop
Exponential
- O(n^3)
- Intractable
Factorial
- O(n!)
- Intractable
Intractable problems
They are theoretically solvable but cannot be solved within a useful amount of time
Tractable problems
A problem can be solved within a useful period of time
Turing machines
Formal models of computation that consist of:
- a FSM
- a read/write head
- an infinitely long tape consisting of cells that can be blank or contain a symbol
They must have a single start state and a number of halting states
Alphabet
- The set of symbols used
- It must be finite with a Turing machine
Transition functions
- Used to define the rules followed by Turing machines
- Have an equivalence with transition rules in a state transition diagram
- Written in the form:
δ(current state, read) = (new state, write, move)
Universal Turing Machines
- Can represent any finite state machine
- Read a description of a finite state machine from the same tape as the input data
- They read their instructions in sequence
before executing operations
Importance of Turing machines
- Turing machines provide a definition of what is computable
- Turing machines can be used to prove that there are problems which cannot be
solved by computers
