Brainscape's Knowledge GenomeTM

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


See full index

AQA Computer Science Alevel > (P1) Theory Of Computation > Flashcards

(P1) Theory Of Computation Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What is an algorithm?

A

A sequence of steps that can be followed to complete a task. It always terminates rather than forever going on a loop.

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

What is an advantage of pseudocode?

A

Allows different programmers who may not understand the same language to be able to communicate algorithms to each other.

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

What is assignment in pseudocode?

A

Process of giving a value to a variable or constant.

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

How do you write assignments in pseudocode?

A

Arrow pointing towards the variable or constant with the value fivwn on the other side.

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

What is selection?

A

The process of choosing an action to take based on the result of a comparison of values.

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

What statements are used in selection for pseudocode?

A

IF, ELSE, IF ELSE and END IF

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

What is iteration?

A

The process of repeating an operation.

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

What structures are used for iteration?

A

FOR and WHILE loops

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

What is abstraction, and why is it used?

A

Abstraction is the process of omitting unnecessary details from a problem. Used to simplify problems to make finding a solution easier.

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

What are the two distinct forms of abstraction?

A

Representational and categorisation

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

What is representational abstraction?

A

A representation of a problem arrived at by removing unnecessary details from the problem.

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

What is categorisation abstraction?

A

A grouping by common characteristics to arrive at a hierarchical relationship of the “is a kind of” type.

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

What is 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
14
Q

What is procedural abstraction?

A

Process of breaking down a complex model into a series of reusable procedures.

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

What is functional abstraction?

A

Simplifying a problem by breaking it down into a series of reusable functions that disregard the particular computational method. Results in just a function.

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

What is data abstraction?

A

Specific details of how data is actually represented are abstracted away, allowing new kinds of data structures to be created from previously defined data structures.
Data abstraction foems the basis of abstraction data types.

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

What is another name for problem abstraction?

A

Reduction

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

What is problem abstraction?

A

Details are removed froma problem until it is represented in a way that is solvable.
This works because a simplified problem os often similar to a problem that has already been solved, meaning a solution to the problem can be found.

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

What is decomposition?

A

Process of dividing a problem into a series of smaller sub-problems. These smaller problems can be solved individually or further divided until all parts of the problem have been solved.

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

What is composition?

A

Process of combining procedures to form a larger system.
Composition is used in all abstraction data types where a complex abstraction data type is formed for smaller and simpler data types.

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

What is automation?

A

Process of putting abstractions of real world phenomena (models) into action to solve problems.

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

How is automation achieved?

A

Automation is achieved by creating algorithms which are later implemented in code, implementing models in data structures and finally executing the code on the data structure.

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

What is an accepting state?

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
24
Q

What is the Finite State Machine?

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
25
Q

What is a Mealy Machine?

A

A finite state 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
26
Q

What is a state transition diagram?

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
27
Q

What is a state transition table?

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
28
Q

What is a set?

A

An abstracted data type which contains unorderes unique values. Sets can contain other sets.

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

What is set comprehension?

A

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

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

In set comprehension what does the ‘pipe’ (|) mean?

A

Such that

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

In set comprehension, what does the E mean?

A

Is a member of

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

In set comprehension, what type of brackers should be used?

A

{ }

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

In set comprehension, what does ^ mean?

A

And

34
Q

What is set that has zero elements referred to as?

A

An empty set.

35
Q

What are the symbols for an empty set?

A

{} or Circle with a diagonal line thought it, from bottom left to top right.

36
Q

What is compact set representation?

A

A space-efficient way of describing sets.

37
Q

What is the cardinality of a finite set?

A

The number of elements in the set.

38
Q

What is the Cartesian Product of Sets?

A

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

39
Q

What is a countable set?

A

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

40
Q

What is a countablt infinite set?

A

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

41
Q

What does the difference operator do?

A

Produces a set containing all the elements present in either of the intial operand sets but not both.

42
Q

What is finite set?

A

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

43
Q

What is an infinite set?

A

Set that contains an infinite number of values

44
Q

What is a countable infinite set?

A

The items in a countable infinite set can be counted off by the natural numbers.

45
Q

What is a non-countable set?

A

Contain a larger inifinty of numbers. Cannit be paired with natural numbers. Sets include real numbers.

46
Q

What does the intersection do?

A

Produces a set containing only elements present in both initial operand sets.

47
Q

What is membership?

A

The property of an element being within a set.

48
Q

What is a proper subset?

A

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

49
Q

What is a subset?

A

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

50
Q

What is the symbol for a subset?

A

C with a line underneath.

51
Q

What is the symbol for a proper subset?

A

C

52
Q

What is regular expression?

A

A way of describing sets and the elements present within jt using a string of characters.

53
Q

What is regular language?

A

A language that can be represented by a regular expression.

54
Q

What does the metacharacter * mean?

A

0 or more repetitions

55
Q

What does the metacharacter + mean?

A

1 or more repetitions.

56
Q

What does the metacharacter ? mean?

A

Previous character optional

57
Q

What does the metacharacter | mean?

A

Alternative/ or

58
Q

What does the metacharacter () mean?

A

Used to group regular expressions.

59
Q

What is a context-free language?

A

A set of strings and symbols that follow the rules of a context-free grammar.

60
Q

What are context-free grammars?

A

Describe which strings are and are not possible in a language by laying out production rules.

61
Q

What is production rule?

A

Replacing one character for another.

62
Q

What does BNF stand for?

A

Backus-Naur Form

63
Q

What is BNF?

A

A notation technique to express syntax of languages in computing. A way of notating context-free languages. It uses statements innwhich the left hand side is defined by the right hand side.

64
Q

How are non-terminals represented?

A

Inside angle brackets < >

65
Q

What are non-terminals also referred to as?

A

Meta-components or syntactic variables

66
Q

Describe non-terminals.

A

Can be broken down further into either more non-terminals, terminals or a combination of both.

67
Q

How are terminals represented?

A

Text without any brackets.

68
Q

Describe terminals.

A

Terminals cannot be broken down any further and must be taken to be the written value.

69
Q

Whay type of expressions can regular languages not support?

A

Recursion

70
Q

What does ‘::=’ mean?

A

Is defined as

71
Q

What is syntax diagram?

A

A visual representation of a regular language.

72
Q

Describe the layout of syntax diagrams?

A

Rectangles: non-terminals
Ellipses (ovals) : terminals
Each non-terminal is defined by its own syntax diagram

73
Q

What are the two ways a n algorithm can be complex?

A

Complex in terms of time or space.

74
Q

Describe an ideal algorithm.

A

Runs as quickly as possible, using as little space as possible.

75
Q

What is the graph for a constant time complexity?

A

|
|
Y|—————————————
|
|
——————————————
X

76
Q

What is the graph for a linear time constant?

A

/
| /
Y| /
| /
| /
———————
X

77
Q

What is the graph for a logarithmic time constant?

A

|
|
Y| ——————
| /
| /
————————————
X

78
Q

What is the graph of a polynomial time constant?

A

/
| /
Y| /
| /
|/
—————————
X

79
Q

What is the graph for a exponential time constant?

A

|
| |
Y| |
| /
|/
——————————————
X

80
Q

What are factorial time constants useful for?

A

Working out permutations, travelers problem and explorers problem.

81
Q

Describe Big O notation.

A

Assumes the worse case scenario.

82
Q

What is the time complexity of this algorithm and why?
n^3 + 200n^2 + 1000n + 25

A

O(n^3) (Polynomial)
The time complexity of an algorithm is the highest possible time complexity as when n is large, the other parts of the algorithm become less significant.

AQA Computer Science Alevel (9 decks)

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