Brainscape's Knowledge GenomeTM

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


See full index

CS 1 > 1.4 Theory of computation > Flashcards

1.4 Theory of computation Flashcards

1
Q

Define automation

A

Creating a computer model of a real-life situation and putting it into action

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

Define representational abstraction

A

The process of removing unnecessary details so that only information that is required to solve the problem remains

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

Define abstraction by generalisation / categorisation

A

The concept of reducing problems by putting similar aspects of a problem into hierarchical catgegories

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

Define top-down design

A

Starts with the main system at the top and breaks it down into smaller units

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

Define functional abstraction

A

Breaking down a complex problem into a series of reusable functions

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

Define data abstraction

A

Hiding how data is represented so that it is easier to build a new kind of data object, for example building a stack from an array

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

Define problem abstraction

A

Removing unnecessary details in a problem until the underlying problem is identified to see if this is the same as a problem that has already been solved

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

Define 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
9
Q

Define finite state machine

A

Any device that stores its current status and whose status can change as the result of an input. Mainly used as a conceptual model for designing and describing systems. There are a finite number of transitions that may take place

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

What is a state transition diagram?

A

A visual representation of an FSM using circles and arrows

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

Define accepting state

A

The state that identifies whether an output has been accepted

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

Define state transition table

A

A tabular representation of an FSM showing inputs, current state, and next state

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

Define Mealy machine

A

A type of finite state machine with outputs

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

What is a Turing machine?

A

A theoretical model of computation

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

What is the alphabet of a Turing machine?

A

The acceptable symbols (characters, numbers) for a given Turing machine

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

Define read/write head

A

The theoretical device that writes or reads from the current cell of tape in a Turing machine

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

Define halting state

A

The state that stops a Turing machine

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

Define start state

A

The initial state of a Turing machine

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

Define transition function/rule

A

A method of notating how a Turing machine moves from one state to another and how the data on the tape changes

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

Define state transition diagram

A

A visual representation of the transition function of a Turing machine

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

How does a Turing machine operate?

A
  • Tape divided into an infinite number of cells which are used as memory
  • Each cell will contain a symbol, either a character or number, the range of acceptable symbols is the alphabet
  • The read/write head can either read what is in the cell, write to the cell, or erase its contents
  • The tape can move left or right one cell at a time so every cell is accessible by a read/write head
  • The machine can halt at any point if it enters the halting state or if the whole input has been processed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is needed to represent programs with a Turing machine?

A
  • A start state
  • A halting state
  • An alphabet
  • Movement
  • A transition function
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Define instruction table

A

A method of describing a Turing machine in tabular form

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

Define universal machine

A

A machine that can simulate a Turing machine by reading a description of the machine along with the input of its own tape

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

Define a regular language

A

Any language that can be described using regular expressions

26
Q

Define a regular expression

A

Notation that contains strings of characters that can be matched to the content of a set

27
Q

What symbol represents or in regex?

A

|

28
Q

What symbol represents zero or more of a character?

A

*

29
Q

What symbol represents one or more of a character?

A

+

30
Q

What symbol represents zero or one of a character?

A

?

31
Q

What symbol represents a wildcard character?

A

.

32
Q

Define a context-free language

A

An unambiguous way of describing the syntax of a language useful when a language is context

33
Q

Define Backus-Naur Form (BNF)

A

A form of notation for describing the syntax used by a programming language

34
Q

Define terminal in BNF

A

The final element that requires no further rules

35
Q

Define syntax diagram

A

A method of visualising rules written in BNF or any other context-free language

36
Q

Define set comprehension

A

The process of creating sets by describing them using notation rather than listing the elements

37
Q

Define finite set

A

A set where the elements can be counted using natural numbers up to a particular number, an infinite set is the opposite of this

38
Q

Define cardinality

A

The number of elements in a set

39
Q

Define countable set

A

A finite set where the elements can be counted using natural numbers

40
Q

Define countably infinite sets

A

Sets where the elements can be put into a one-to-one correspondence with the set of natural numbers

41
Q

Define cartesian product

A

Combining the elements of two or more sets to create a set of ordered pairs

42
Q

Define union

A

Where two sets are joined and all of the elements of both sets are included in the joined set

43
Q

Define intersection

A

Describes which elements are common to both sets when two sets are joined

44
Q

Define difference

A

Describes which elements differ when two sets are joined together

45
Q

Define subset

A

A set where the elements of one are entirely contained within the other; can include two sets that are exactly the same

46
Q

Define proper subset

A

Where one set is wholly contained within another and the other set has additional elements

47
Q

Define space complexity

A

The concept of how much space an algorithm requires

48
Q

Define input size

A

In Big O notation this is the size of whatever data you are asking an algorithm to work with

49
Q

Define time complexity

A

The concept of how much time an alogrithm requires

50
Q

Define constant time

A

In Big O notation where the time taken to run an algorithm does not vary with the input size

51
Q

Define linear time

A

In Big O notation where the time taken to run an algorithm increases in direct proportion with the input size

52
Q

Define exponential time

A

In Big O notation where the time taken to run an algorithm increases as an exponential function of the number of inputs

53
Q

Define logarithmic time

A

In Big O notation where the time taken to run an algorithm increases or decreases in line with a logarithm

54
Q

Define polynomial time

A

In Big O notation where the time taken to run an algorithm is a polynomial function of the input size

55
Q

What is Big O notation?

A

Big O notation is a way of describing the time spcae complexity of an algorithm, looking at the maximum time it could take an algorithm to complete

56
Q

Define tractable problem

A

A problem that can be solved in an acceptable amount of time

57
Q

Define intractable problem

A

A problem that cannot be solved within an acceptable time frame

58
Q

Define heuristic

A

With algorithms, it is a method for producing an acceptable but not necessarily best solution to an intractable problem

59
Q

Define unsolvable problem

A

A problem that has been proven that it cannot be solved computationally

60
Q

What is the halting problem?

A

An example of an unsolvable problem where it is impssible to write a program that can work out whether another problem will halt given a particular input

CS 1 (4 decks)

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