Brainscape's Knowledge GenomeTM

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


See full index

Computing AQA A level > Paper 1 terms > Flashcards

Paper 1 terms Flashcards

1
Q

Algorithm

A

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

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

Assignment

A

The process of giving a variable or constant a value

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

Sequence

A

Instructions that follow on one from the other

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

Selection

A

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

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

Iteration

A

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)

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

Abstraction

A

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

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

Representational abstraction

A

A representation of the problem arrived at by removing unnecessary details

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

Abstraction by generalisation/categorisation

A

Grouping parts of the problem 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
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

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

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

Functional abstraction

A

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

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

Data abstraction

A

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

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

Problem abstraction/reduction

A

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

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

Decomposition

A

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

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

Composition

A

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

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

Automation

A

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

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

Set

A

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

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

Set comprehension

A

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, …}

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

Empty set notation

A

{} or Ø

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

Compact set representation

A

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)

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

Finite sets

A

Contains a finite number of items

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

Cardinality

A

Refers to the number of items in a finite set

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

Infinite sets

A

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

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

Countably infinite sets

A

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

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

Non-countable sets

A

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

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

Subset

A

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

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

Proper subsets

A

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

28
Q

Countable sets

A

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

29
Q

Membership sign (set notation)

A

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

30
Q

“Not a member of” sign (set notation)

A

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

31
Q

Set operations

A

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

32
Q

Union (set operation)

A

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

33
Q

Intersection (set operation)

A

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 ∩

34
Q

Difference (set operation)

A

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

35
Q

Regular expressions

A

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

36
Q
    • (metacharacter)
A

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

37
Q
    • (metacharacter)
A

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

38
Q

? (metacharacter)

A

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

39
Q

| (metacharacter)

(metacharacter)

A

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

40
Q

() (regular expressions)

A

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

41
Q

Context-free language

A

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

42
Q

Context-free grammar

A

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

43
Q

Backus-Naur form

A

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

44
Q

Non-terminals (Backus-Naur form)

A

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 <FullName>:</FullName>

<FullName> ::= <Title><Forename><Surname>
</Surname></Forename></Title></FullName>

45
Q

Terminals (Backus-Naur form)

A

Text without any brackets, which can’t be broken down any further and has a literal written value, e.g. the non-terminal <Number> could be described with terminals:</Number>

<Number> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

| Remember | means OR
</Number>

46
Q

Recursion in Backus-Naur form

A

Backus-Naur form can make use of recursion by using a non-terminal which can be defined in terms of itself. Regular expressions cannot support recursion like Backus-Naur form can, BN form can represent some languages that reg exps can’t. E.g. recursion to define an integer:

<Integer> ::= <Digit>|<Digit><Integer>
<Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
</Digit></Integer></Digit></Digit></Integer>

47
Q

Syntax diagrams

A

A visual representation of a regular language which uses rectangles to represent non-terminals and ellipses to represent terminals (joined by arrows to show how strings can be formed from these)

48
Q

Constant (time complexity)

A

O(C)
E.g. y = 3 (time of algorithm is unrelated to the output - it is a set value regardless)
I.e. determining whether a number is odd or even

49
Q

Linear (time complexity)

A

O(n)
E.g. y = 3x (straight diagonal line going up, increases proportionately to input, i.e. if input 5, time 10, if input 10, time 20)
I.e. linear search

50
Q

Logarithmic (time complexity)

A

O(logn)
E.g. y = log(x) (line goes up a bit and then sharp right and then stays horizontal, halves the number of items each iteration)
I.e. binary search

51
Q

Polynomial (time complexity)

A

O(n^2) or O(n^3)
E.g. y = x^2 (line curves upwards over whole graph but curves up more the further it goes, for an algorithm a loop inside a loop)
I.e. bubble sort

52
Q

Linear logarithmic (time complexity)

A

O(nlogn)
No graph example (N/A)
I.e. merge sort

53
Q

Factorial (time complexity)

A

O(n!)
No graph example (intractable algorithms which can’t be solved in a useful amount of time)
I.e. travellers problem

54
Q

Exponential (time complexity)

A

O(2^n) or O(3^n)
E.g. y = 3^x (sudden sharp curve up which basically turns into a vertical line, intractable algorithms which can’t be solved within a useful amount of time)
I.e. recursively calculating fibonacci numbers

55
Q

Big O notation

A

Describes the complexity of an algorithm for the WORST CASE scenario. Describes input in terms of n (e.g. O(n) or O(logn))

56
Q

The order of Big O functions (least to most time complex)

A

Constant
Logarithmic
Linear
Linear logarithmic
Polynomial (n^2 and then n^3)
Exponential (intractable)
Factorial (intractable)

57
Q

Tractable problems

A

Can be solved in a useful time period. Polynomial time complexity or less

58
Q

Intractable problems

A

Can’t be solved in a useful time period using today’s technology but are theoretically solvable. Known as “insoluble” due to the limits of computation. Heuristic methods may be used for these problems (approximate solutions)

59
Q

The halting problem

A

It is impossible to write an algorithm to determine if another algorithm will finish with a given input. The halting problem demonstrates that there are some problems which cannot be solved by computers/algorithmically

60
Q

Turing machines

A

A model of computation consisting of:
- a finite state machine (FSM)
- a read/write head
- a tape that is infinitely long in one direction

The tape is divided into cells which are blank or contain a symbol. Cells are written to/blanked using the read/write head. The set of symbols used is called the alphabet and is finite.

Turing machines run a single program, defined by an FSM. They stop once they’ve reached the halting state and are more powerful than FSMs because they can utilise a greater range of languages and their tape is infinitely long in one direction

61
Q

Finite state machines (FSM)

A

Has a start state and a number of states from which there are no transitions (halting states)

62
Q

Turing machine graphical representation

A

A Turing machine can be represented graphically as a series of cells, each containing a symbol, and a triangular pointer which represents the position of the machine’s read/write head. A □ symbol signifies an empty cell

63
Q

Transition functions

A

Rules that a Turing machine follows (equivalent to FSM transition rules), written in the form:
δ(current state, read) = (new state, write, move)
E.g. if the transition function is: δ (S0, □) = (S1, 1, R), this means
if the machine is in state S0 and reads an empty cell, the machine should write a 1, move to state S1 and move its read/write head to the right

64
Q

Universal Turing machines

A

Normal Turing machines are limited to just one FSM, so they are specific to one computational problem. Universal Turing machines can represent any FSM, and can act as interpreters since they read instructions in sequence before executing operations on input data

65
Q

Importance of Turing machines

A

They provide a formal model of computation and therefore a definition of what is computable. Turing machines can prove that there are problems which cannot be solved by computers

Computing AQA A level (2 decks)

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