Brainscape's Knowledge GenomeTM

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


See full index

A-Level Computer Science > Theory Of Computation > Flashcards

Theory Of Computation Flashcards

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

What is a boundary?

A

The defined constraints that you must obey when solving a problem.

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

What are 2 examples of boundaries?

A

Time - time needed to solve problem.

Space - memory required to solve the problem.

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

What things should be considered when solving a problem?

A

The resources needed.
Are the existing resources adequate.
How will you use the resources.

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

What is automation?

A

The setting into motion of the plans put in place to solve the problem.

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

What is an advantage of abstraction and decomposition?

A

It helps with understanding the problem at hand and therefore makes the solving process easier.

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

What is representational abstraction?

A

A representation arrived at by removing unnecessary details.

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

What is abstraction by generalisation?

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

What is procedural abstraction?

A

Assumes all solutions can be broken into procedures.

We know what the procedures must do but know how.

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

What is function abstraction?

A

Grouping of common functions that can be used to solve a problem.

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

What is data abstraction?

A

Organising and structuring data to produce a particular view of the data that is useful for the programmer.

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

What is problem abstraction?

A

Reducing a problem down into its smallest component parts until the underlying processing requirements that solve the problem are identified.

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

What is information hiding?

A

The removal of unnecessary information for the user of a program. For example creating a nice and simple GUI.

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

What is a finite state machine? Hint (SOS)

A

A theoretical device that stores the status of something at any given time and can operate on inputs that allow it to change status.

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

What does an FSM consist of?

A

States, inputs and outputs.

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

What are the 4 important things about FSMs? Hint (COTM)

A

Used in controlling processes, local conditions only (direct input).
The machine is only in one state at a time.
It can move from one state to the next when initiated by a triggering event or condition (a transition).
They have limited memory (memory = number of states).

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

What are the 2 types of FSM?

A

Mealy machine.
Moore machine.

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

What is a Mealy machine?

A

A machine who’s output is determined by its current state and the values of its inputs.

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

What is a Moore machine?

A

A machine who’s output is determined solely by its current state.

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

When describing FSMs what is an output?

A

A response caused by making a transition.

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

What is the name of an FSM that produces no output?

A

Finite State Automaton (FSA)

21
Q

What was the Turing machine?

A

A Finite State Machine (FSM). A theoretical machine that carries out any algorithm and essentially produces a model.

22
Q

What 5 things are needed for the Turing machine to work?

A 
Movement.
Alphabet / symbol.
Transition functions.
Starting state.
Halting state.
23
Q

What is the main disadvantage of the Turing machine?

A

A new Turing machine is required for each new problem. This makes it problematic for large scale problems.

24
Q

What are the main requirements of the Universal machine?

A

A description of all individual Turing machines required to perform calculations.
All the inputs required for the calculations.

25
Q

What is a regular language?

A

A language that is able to be defined using Regex. (Regular expression)

26
Q

What do regular expressions do?

A

They are strings of characters that are used to match the contents of a pre specified set, allowing patterns to be found.

27
Q

What are 3 common uses of regular expressions?

A

Data validation. (Validating inputs)
Find and replace.
File searching / sorting.

28
Q

What is a context free language? Hint (SRPP)

A

A context-free language is a ​set of strings and symbols​ that follow the rules of a context-free grammar​.
Context-free grammars describe which strings are possible or not in a language by laying out ​production rules​.

29
Q

What is Backus-Naur form?

A

A way of notating context free languages.

Using statements where the left side is defined by the right side. “ ::= “

30
Q

What is Backus Naur form used for?

A

Used by the authors of programming languages to describe the grammatical set of rules in the language.

31
Q

What defines whether a piece of code is more complex or not?

A

More lines = more complex and more memory required

32
Q

What are the two types of efficiency?

A

Time - How long it takes for the algorithm to terminate with the correct solution.
Space - The memory required for the program to terminate with the correct solution.

33
Q

How do you identify the space efficiency of an algorithm?

A

The amount of data structures being used as the algorithm is being run. When considering space efficiency, the aim is to utilise data structures that use up the least memory.

34
Q

What are some examples of increasing the space efficiency of an algorithm?

A

Not using the data type real when only integers are used.

Not initialising an array of 1,000 things when only 100 are needed.

35
Q

What type of time complexity does O(1) stand for?

A

Constant Time, where the algorithm will always terminate after the same amount of time no matter the input.
For example, indexing an array.

36
Q

What type of time complexity does O(n) stand for?

A

Linear Time complexity, the runtime of the algorithm is in direct proportion to the input size.
For example, a linear search.

37
Q

What type of time complexity does O(n²) stand for?

A

Polynomial Time complexity, the runtime of the algorithm will increase in proportion to the square of the input size.
For example, bubble, insertion or selection sort would have a time complexity of O(n²).

38
Q

What type of time complexity does O(2ⁿ) stand for?

A

Exponential Time complexity, the runtime will double with every unit increase in the input size.
For example, it’s used for modelling intractable problems that aren’t suitable with polynomial time.

39
Q

What is the difference between unsolvable and intractable problems?

A

Unsolvable, cannot be solved by computers no matter the computing power available.
Intractable, can theoretically be solved by computers but not in a reasonable amount of time.

40
Q

What type of time complexity does O(logn) stand for?

A

Logarithmic Time complexity, O(logn) algorithms are efficient in that the size of input data can increase exponentially while the time complexity increases linearly. For example, a binary search algorithm, with O(logn) time complexity, may search over 4 billion items with only 32 comparisons.

41
Q

What is an algorithm?

A

A series of unambiguous instructions designed to solve a problem.

42
Q

Why is big O time complexity used?

A

It is a general measure of how long a certain task will take to complete without taking things such as processing power into consideration.

43
Q

What do {} represent when defining a set?

A

The contents of the set. (E.g, A = {1, 2, 3})

44
Q

What does | represent when defining a set?

A

‘|’ = “such that”

(E.g A = {x | x ∈ ℕ}

45
Q

How would you try to solve an intractable problem?

A

Create an algorithm, using previous knowledge to help solve the problem.
Break down the problem into a simpler version of itself.

46
Q

What is a universal Turing machine?

A

A TM that simulates the behaviour of any other TM.

Faithfully executes operations on the data as simulated by the TM.

47
Q

Why is bubble sort of time complexity O(n²)?

A

In each pass through the list n items are examined.
There are (at maximum) n passes through the list.

48
Q

What is a heuristic technique?

A

Finding a solution that might not be the best.

A-Level Computer Science (17 decks)

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