Theory of computation Flashcards
decomposition
breaking a problem down into sub problems making it easier to execute
abstraction
Details are removed until it looks solvable
(simplifying a problem)
algorithm
sequence of instructions that performs a specific task when followed
Data abstraction
enables us to isolate how a compound data object is used from the details of how it is constructed.
how do you build data abstractions
by combining data objects to form compound data, for example tree data structure
how do you build a composition abstraction
by combining procedures to form compound procedures
representational abstraction
removing unnecessary details
information hiding
process of hiding all unnecessary details of an object
procedural abstraction
represents a computational method
functional abstraction
particular computation method is hidden
how does automation achieve putting models into action to solve problems
- creating algorithms
- implementing the algorithms in program code (instructions)
- implementing the models in data structures
- executing the code.
set and the alternative symbol for empty set
unordered collection of values in which each value occurs at most once.
Ø
finite sets
elements can be counted off by natural numbers up to a particular number
infinite set
counted off by the natural numbers.
cardinality of a finite set
number of elements in a set
Cartesian product of two sets
set of all ordered pairs
regular expression
a way of describing a set
describe the relationship between regular expressions and FSMs
Regular expressions and FSMs are equivalent ways of defining a regular language.
regular language
any language that a FSM will accept
when is a language called regular
if it can be represented by a regular expression.
explain why BNF can represent some languages that cannot be represented using regular expressions.
BNF allows for the description of nested and recursive structures, whereas regular expressions are limited in their ability to handle such complex patterns.
tractable
problems that have a polynomial (or less) time solution are called tractable problems.
intractable
problems that have no polynomial (or less) time solution are called intractable problems.
Heuristic methods
Heuristic methods are often used when tackling intractable problems.
limits of computation
algorithmic complexity and hardware impose limits on what can be computed
computable and non-computable problems
some problems cannot be solved algorithmically
halting problem
Determining if a program will halt
demonstrates that there are some problems that cannot be solved by a computer.
Explain the functionality of the * metacharacter
0 or more
Explain the functionality of the + metacharacter
1 or more repetitions
Explain the functionality of the ? metacharacter
0 or 1
explain the functionality of the () metacharacter
to group regular expression
explain the functionality of the | metacharacter
alternation
importance of turing machines
Turing machines provide a model of computation and provide a definition of what is computable.
universal turing machine
A Turing machine that can execute
equivalence between a transition function and a state transition diagram
A state transition diagram represents the transitions between states in a finite state machine, while a transition function defines the specific transitions and their corresponding outputs in a mathematical form.
