Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > 4.4 Theory of computation > Flashcards

4.4 Theory of computation Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
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
2
Q

What is abstraction by generalisation or categorisation?

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
3
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
4
Q

What is procedural abstraction?

A
  • Procedural abstraction involves breaking down a complex model into a series of reusable procedures.
  • The actual values used in a computation are abstracted away and a computational method is achieved
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How is functional abstraction different from procedural abstraction?

A
  • Functional abstraction requires yet another abstraction from procedural abstraction
  • While the result of a procedural abstraction is a computational method, the function disregards the particular computation method
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is data abstraction? Give an example

A
  • The process of isolating how a compound data object is used from the details of how it is constructed. Data abstraction forms the basis of abstract data types
  • For example, a stack could be implemented as an array and a pointer for the top of the stack
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is problem abstraction/reduction?

A

The process of removing details until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved

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

What is (procedural) decomposition?

A

The process of breaking 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
9
Q

What is (procedural) composition?

A

The process of combining procedures to form compound procedures

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

What is automation? How is it achieved?

A

The process of putting models (abstractions of real world objects/phenomena) into action to solve problems. This is achieved by:
1. 📝 creating algorithms
2. 👨‍💻 implementing the algorithms in program code
3. 🔢 implementing the models in data structures
4. 🤖 executing the code.

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

When can a language be called regular?

A

If and only if it can be recognised by a FSA (or represented using a regular expression)

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

What is a finite state automaton?

A

A special case of an FSM, with exactly one start state and at least one accepting state

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

What is meant by the language recognised by an FSA?

A

The set of strings accepted by it

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

What is a set?

A

A set is an unordered collection of values in which each value occurs at most once

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

What does proper subset mean? What is its symbol?

A
  • Equality not allowed
  • (a set is a subset of itself but not a proper subset of itself)
  • ⊂
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

A\B

A

Set difference between A and B

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

What is a finite set?

A

One whose elements can be counted off by natural numbers up to a particular number

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

What is the Cartesian product of A and B?

A

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

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

What can the Cartesian product be used for?

A

Defining function types

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

What is a countable set?

A

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

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

What are regular expressions?

A

Metalanguage for defining all valid strings of a regular language

22
Q

What is the purpose of regular expressions?

A

Allow for regular languages to be described in a convenient shorthand notation

23
Q

RegEx : zero or more

A

*

24
Q

RegEx : one or more

A

+

25
Q

RegEx : zero or one lots of

A

?

26
Q

What are | ? * + called in RegEx?

A

Metacharacters

27
Q

Context free languages are a __________ of regular languages

A

Superset

28
Q

Why are context-free languages needed? (2*)

A
  • RegEx doesn’t have enough expressive power
  • This is because regular languages can be expressed in terms of a finite state machine, and a finite state machine only has finitely many states
29
Q

What is BNF?

A
  • Backus-Naur form
  • A metalanguage for describing the syntax used by a context-free language
30
Q

General statement in BNF

A

LHS ::= RHS

31
Q

What is a function?

A
  • A function is a mapping of values from a domain to a set of values from a co-domain.
  • Not all of the co-domains members needs to be outputs.
32
Q

Hierarchy of complexities (polynomial, logarithmic, constant, exponential, linear)

A

constant < logarithmic < linear < polynomial < exponential

33
Q

Permutations of n distinct objects

A

n!

34
Q

When is a problem “computable”?

A

If there is an algorithm (in principle) that solves the problem

35
Q

When is a problem “non-computable”?

A

If no algorithm can ever exist which solves the problem

36
Q

What is a intractable problem?

A

A computable problem for which a polynomial time (or better) algorithm does not exist

37
Q

How do programmers find “solutions” to intractable problems?

A

By developing tractable heuristic algorithms and methods, which find approximate (but not necessarily optimal) solutions.

38
Q

What is the trade-off that must be considered when developing heuristic algorithms?

A

speed vs correctness

39
Q

What is an undecidable problem? Give an example

A
  • A decision problem that is non-computable
  • e.g. the halting problem
40
Q

What is the halting problem?

A

The undecidable problem of determining whether any program will eventually halt on given particular input without running the program

41
Q

What is the significance of the halting problem?

A

The halting problem demonstrates that some problems are non-computable, meaning they cannot be solved by a computer

42
Q

Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?

A

Because it has an infinite amount of memory

43
Q

Name one example of a model of computation

A

Turing machine

44
Q

Describe the importance of Turing machines

A
  • Turing machines provide a formal model of computation and provide a definition of what is computable
  • They can be used to prove that there are problems which cannot be solved by computers
45
Q

What makes up a Turing machine?

A
  • Finite set of states
  • Set of transition rules
  • Finite set of symbols
  • Infinite tape with marked off squares
  • Sensing read-write head that can travel along the tape, one square at a time
46
Q

What is a halting state in a Turing machine?

A

A state with no outgoing transitions

47
Q

What is meant by a Universal Turing machine?

A
  • A Turing machine that can simulate the behaviour of any other Turing machine, by acting as an interpreter
  • It faithfully executes operations on the data precisely as the simulated TM does
  • Both the transition rules for the TM as well as the input data would be stored on the tape
48
Q

What is another way to represent the state transition diagram of a Turing machine?

A
  • Transition function
  • δ (current state, input symbol) = (next state, output symbol, movement)
49
Q

One example of where composition is used

A

In abstract data types, where a complex abstract data type is formed from smaller and simpler data types

50
Q

Notation for “the set difference between sets A and B”

A

A\B

51
Q

Set comprehension for all even natural numbers less than 10

A

{2x | x ∈ ℕ ∧ x<5}
(| means such that, ∧ means AND)

52
Q

{0ⁿ1ⁿ| n ≥ 1}

A

{ 01, 0011, 000111, 00001111, … }

Computer Science (11 decks)

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