Paper 1 terms

Question 1

Algorithm

Answer 1

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

Question 2

Assignment

Answer 2

The process of giving a variable or constant a value

Question 3

Sequence

Answer 3

Instructions that follow on one from the other

Question 4

Selection

Answer 4

Choosing an action to take place based on the result of a comparison, IF, ELIF, ELSE

Question 5

Iteration

Answer 5

Looping a process. This can be finite (a set number of times - FOR), or infinite (repeating for an undefined, potentially infinite number of times - WHILE)

Question 6

Abstraction

Answer 6

The process of omitting unnecessary details from a problem, in order to simplify it to make the solution easier. There are two types of abstraction: representational abstraction, and abstraction by generalisation/categorisation

Question 7

Representational abstraction

Answer 7

A representation of the problem arrived at by removing unnecessary details

Question 8

Abstraction by generalisation/categorisation

Answer 8

Grouping parts of the problem by common characteristics to arrive at a hierarchical relationship of the “is a kind of” type

Question 9

Information hiding

Answer 9

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

Question 10

Procedural abstraction

Answer 10

Breaking down a complex model into a series of reusable procedures (involves removing actual values used to achieve a computational model)

Question 11

Functional abstraction

Answer 11

The step following procedural abstraction: this involves disregarding the particular method of a procedure and results in just a function

Question 12

Data abstraction

Answer 12

Specific details of how data is actually represented are abstracted away, allowing new kinds of data structure to be created from previously defined data structures

Question 13

Problem abstraction/reduction

Answer 13

Details are removed from a problem until it is represented in a way that is solvable

Question 14

Decomposition

Answer 14

Dividing a problem into a series of smaller sub-problems, which can be solved individually or further divided until all parts of the original problem have been solved

Question 15

Composition

Answer 15

Combining procedures to form a larger system. This is used in abstract data types, where a complex
abstract data type is formed from smaller and simpler data types

Question 16

Automation

Answer 16

The process of putting abstractions of real world phenomena (known as models) into action to solve problems

Question 17

Set

Answer 17

An abstract data type containing unordered unique (can’t have the same one twice) values. Sets can contain other sets

Question 18

Set comprehension

Answer 18

A way of creating sets which doesn’t define each individual term but rather what we want from a more general set, e.g. {x | x->N ^ x>3} = {4, 5, 6, …}

Question 19

Empty set notation

Answer 19

{} or Ø

Question 20

Compact set representation

Answer 20

A space-efficient, short-hand way of describing sets, which can describe multiple instances of a number, e.g. {0n 1n | n ≥ 1} = {01, 0011, 000111, 00001111, … } (where n is an index)

Question 21

Finite sets

Answer 21

Contains a finite number of items

Question 22

Cardinality

Answer 22

Refers to the number of items in a finite set

Question 23

Infinite sets

Answer 23

Contain an infinite number of items. There are two types of infinite sets: countable and non-countable

Question 24

Countably infinite sets

Answer 24

Where items can be counted off by the natural numbers (e.g. Integers - Z, and Natural numbers - N)

Question 25

Non-countable sets

Answer 25

Contain a larger infinity of items which can't be paired with natural numbers to "count" them (e.g. the Real numbers - R)

Question 26

Subset

Answer 26

Set A is a subset of Set B if it only contains items from Set B. The symbol for a subset is ⊆. So if A is a subset of B, the notation would be A ⊆ B, e.g. {2,4,6} ⊆ {1,2,3,4,5,6}. If two sets are the same, they are a subset of each other

Question 27

Proper subsets

Answer 27

A set is a proper subset of another if it only contains items from that set but NOT ALL OF THEM. If two sets are the same, they are subsets of each other, but NOT proper subsets

Question 28

Countable sets

Answer 28

Include finite sets and countably infinite sets. A countable set has the same cardinality as any subset of the Natural numbers

Question 29

Membership sign (set notation)

Answer 29

Indicates an item is in a set, e.g. 3 ∈ R

Question 30

"Not a member of" sign (set notation)

Answer 30

Indicates an item is not part of a set, e.g. -3.2 ∉ N

Question 31

Set operations

Answer 31

Things you can do to sets to construct new sets. The operations include union, intersection and difference

Question 32

Union (set operation)

Answer 32

Creating a new set by combining two other sets. The symbol for union is ∪. The values from each set are taken and added to the new set. Where a value appears in each set, it will only appear once in the new set Set A ∪ Set B is the same as Set B ∪ Set A

Question 33

Intersection (set operation)

Answer 33

Creating a new set with only the values that appear in BOTH of the other sets (see it an an intersection of a Venn diagram). The symbol for intersection is ∩

Question 34

Difference (set operation)

Answer 34

Creating a new set with the values that are exclusive to ONE set. The symbol for intersection is ∩

Question 35

Regular expressions

Answer 35

Short-hand ways of describing sets using metacharacters such as +, |, ?. For every regular expression set, there is an equivalent FSM

Question 36

* * (metacharacter)

Answer 36

O or more repetitions, e.g. ab* = {a, ab, abb, abbb, ...}

Question 37

* + (metacharacter)

Answer 37

1 or more repetitions, e.g. a+b = (ab, aab, aaab, ...)

Question 38

? (metacharacter)

Answer 38

Previous character optional, e.g. pink? = {pin, pink}

Question 39

| (metacharacter) | (metacharacter)

Answer 39

Or, e.g. g|h = {g, h}

Question 40

() (regular expressions)

Answer 40

Groups regular expressions, e.g. (de)|(fg)h = {deh, fgh}

Question 41

Context-free language

Answer 41

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

Question 42

Context-free grammar

Answer 42

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

Question 43

Backus-Naur form

Answer 43

A way of notating context-free languages. It uses statements in which the left hand side is defined by the right hand side

Question 44

Non-terminals (Backus-Naur form)

Answer 44

Text which is placed inside of angle brackets. Non-terminals can be broken down into more non-terminals, terminals or a combination of the two, e.g. for the non-terminal : ::=