Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science A-level > Theory of computation > Flashcards

Theory of computation Flashcards

1
Q

Logical reasoning

A

The use of a set of facts (axioms) to draw conclusions and determine whether new information is true or false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Algorithms

A

A sequence of steps that can be followed to complete a task and that always terminates.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Correctness

A

An algorithm is said to be correct when it is consistent with the specification and produces the expected output for any given input.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Efficiency

A

A property of an algorithm that is related to the amount of resources (memory space and time in particular) that an algorithm uses in its execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Hand-tracing

A

The process of looking at a program’s entire code or code extract and running through the instructions as though you are the computer.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Pseudo-code

A

A human-readable method of writing the steps of an algorithm without any particular programming language.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Abstraction by generalisation or categorisation

A

Simplifying a problem by grouping together common characteristics of a problem to arrive at a hierarchical relationship.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Representational abstraction

A

Simplifying a problem by only taking into consideration the necessary details required to obtain a solution, leaving a representation without any unnecessary details.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Information hiding

A

The process of hiding all details of an object that do not contribute to its essential characteristics.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Procedural abstraction

A

Simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters. Knowledge of the implementation of each procedure is irrelevant.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Procedure

A

The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Functional abstraction

A

Simplifying a problem by breaking it down into a series of reusable functions which disregard the particular computational method.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Data abstraction

A

The storage and representation of data in a computer system along with its logical description and interaction with operators. This allows the construction of new compound data objects from existing ones.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Data objects

A

Data abstractions that hide details of how data are actually represented from the user.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Problem abstraction/reduction

A

The repeated removal of unnecessary details from a problem until an underlying problem representation is reached which is identical to a previously solved problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Procedural decomposition

A

The process of breaking down a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Composition abstraction

A

The reverse process of decomposition where a complex system of compound procedures is built from its smaller, simpler procedures.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Data abstraction composition

A

The process of combining data objects to form compound data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Automation

A

The process of creating algorithms and implementing them as data structures and models of real-life situations that run without a significant need for human intervention.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Accepting states

A

An optional state of a FSM that indicates whether or not an input has been accepted by the FSM.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Finite state machines

A

A model of computation for a machine that is always in one of a fixed number of states.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Mealy machines

A

A finite state machine that determines its outputs from the present state and from the inputs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

State transition diagrams

A

A visual representation of a FSM that uses circles to represent states and arrows to indicate transitions between states.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

State transition tables

A

A tabular representation of a FSM that contains the current state, inputs and their consequent successor state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Cardinality of a finite set

A

The number of elements in the set.

26
Q

Cartesian products of sets

A

The set of all ordered pairs (a, b) where a is a member of the first set, A, and b is a member of the second set, B.

27
Q

Countable sets

A

A set with the same cardinality as some subset of natural numbers.

28
Q

Countably infinite sets

A

A set that can be counted off by the natural numbers.

29
Q

Difference

A

An operator that produces a set containing all the elements present in either of the initial operand sets, but not both.

30
Q

Empty sets

A

A set with no elements. Represented by {} or ∅.

31
Q

Finite sets

A

A set whose elements can be counted off by natural numbers up to a particular number.

32
Q

Infinite sets

A

A set that is not finite.

33
Q

Intersection

A

An operator that produces a set containing only the elements present in both initial operand sets.

34
Q

Membership

A

The property of an element being within a set.

35
Q

Proper subsets

A

A set that is fully contained in another set, and the other set contains elements that are not present in the proper subset.

36
Q

Set comprehension

A

The creation of a set by mathematically defining the elements that qualify to be in the set, rather than listing out all its elements.

37
Q

Sets

A

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

38
Q

Subsets

A

A set such that all its elements are present in the other set being considered.

39
Q

Union

A

An operator that produces a set containing all the elements from both initial operand sets.

40
Q

Regular expressions

A

A way of describing sets and the elements present within it using strings of characters.

41
Q

Regular languages

A

A language that can be represented by a regular expression.

42
Q

Backus-Naur form (BNF)

A

A notation technique to express syntax of languages in computing.

43
Q

Space complexity

A

A measure of the amount of memory space needed by an algorithm to solve a particular problem of a given input size.

44
Q

Time complexity

A

A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size.

45
Q

Functions

A

A mapping from one set of values, the domain, to another set of values, drawn from the co-domain.

46
Q

Permutations

A

An arrangement of objects such that their ordering matters.

47
Q

O(1) (Constant time/space)

A

An algorithm that always takes a constant amount of time or memory space to execute, regardless of the input.

48
Q

O(2^n) (Exponential time/space)

A

An algorithm whose execution time or required memory space grows exponentially with input size (higher complexity than polynomial).

49
Q

O(log(n)) (Logarithmic time/space)

A

An algorithm whose execution time or required memory space grows logarithmically with input size (lower complexity than polynomial).

50
Q

O(n) (Linear time/space)

A

An algorithm whose execution time or required memory space is directly proportional to the size of its input.

51
Q

O(n^k) (Polynomial time/space)

A

An algorithm whose execution time or required memory space is proportional to the input size raised to the power of a constant (k). E.g. O(n^2), O(n^3) etc.

52
Q

Intractable problems

A

Problems that have no polynomial (or less) time solution.

53
Q

Tractable problems

A

Problems that have a polynomial (or less) time solution.

54
Q

Computable problems

A

Problems that can be solved algorithmically.

55
Q

Non-computable problems

A

Problems that cannot be solved algorithmically.

56
Q

The Halting Problem

A

The unsolvable problem of determining whether any program will eventually stop if given a particular input.

57
Q

Halting state

A

A state with no outgoing transitions that halts a Turing Machine.

58
Q

Start State

A

A Turing Machine’s initial stating state.

59
Q

Transition function

A

A function that determines how a Turing Machine moves from one state to the other. It is equivalent to a state transition diagram.

60
Q

Turing Machine

A

A formal model of computation that consists of a finite state machine that controls one or more tapes, where at least one tape is of unbounded length (i.e infinitely long).

61
Q

Universal Turing Machine

A

An interpreter that can simulate any Turing Machine by reading the description of any arbitrary Turing Machine and faithfully executing operations on data precisely as the machine would.

Computer Science A-level (13 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions