Theory of computation

No description yet. This curated deck is ready for daily study.

Total cards: 24•Content version: v4•Public deck•Updated: 8/1/2026

Card preview (24)

Front (Question)

decomposition

Back (Answer)

breaking a problem down into sub problems making it easier to execute

Front (Question)

abstraction

Back (Answer)

Details are removed until it looks solvable (simplifying a problem)

Front (Question)

algorithm

Back (Answer)

sequence of instructions that performs a specific task when followed

Front (Question)

Data abstraction

Back (Answer)

enables us to isolate how a compound data object is used from the details of how it is constructed.

Front (Question)

how do you build data abstractions

Back (Answer)

by combining data objects to form compound data, for example tree data structure

Front (Question)

how do you build a composition abstraction

Back (Answer)

by combining procedures to form compound procedures

Front (Question)

representational abstraction

Back (Answer)

removing unnecessary details

Front (Question)

information hiding

Back (Answer)

process of hiding all unnecessary details of an object

Front (Question)

procedural abstraction

Back (Answer)

represents a computational method

#10

Front (Question)

functional abstraction

Back (Answer)

particular computation method is hidden

#11

Front (Question)

how does automation achieve putting models into action to solve problems

Back (Answer)

• creating algorithms • implementing the algorithms in program code (instructions) • implementing the models in data structures • executing the code.

#12

Front (Question)

set and the alternative symbol for empty set

Back (Answer)

unordered collection of values in which each value occurs at most once. Ø

#13

Front (Question)

finite sets

Back (Answer)

elements can be counted off by natural numbers up to a particular number

#14

Front (Question)

infinite set

Back (Answer)

counted off by the natural numbers.

#15

Front (Question)

cardinality of a finite set

Back (Answer)

number of elements in a set

#16

Front (Question)

Cartesian product of two sets

Back (Answer)

set of all ordered pairs

#17

Front (Question)

regular expression

Back (Answer)

a way of describing a set

#18

Front (Question)

describe the relationship between regular expressions and FSMs

Back (Answer)

Regular expressions and FSMs are equivalent ways of defining a regular language.

#19

Front (Question)

regular language

Back (Answer)

any language that a FSM will accept

#20

Front (Question)

when is a language called regular

Back (Answer)

if it can be represented by a regular expression.

#21

Front (Question)

explain why BNF can represent some languages that cannot be represented using regular expressions.

Back (Answer)

BNF allows for the description of nested and recursive structures, whereas regular expressions are limited in their ability to handle such complex patterns.

#22

Front (Question)

tractable

Back (Answer)

problems that have a polynomial (or less) time solution are called tractable problems.

#23

Front (Question)

intractable

Back (Answer)

problems that have no polynomial (or less) time solution are called intractable problems.

#24

Front (Question)

Heuristic methods

Back (Answer)

Heuristic methods are often used when tackling intractable problems.