Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Comsci > Theory Of Computation > Flashcards

Theory Of Computation Flashcards

(62 cards)

Start Studying
1
Q

What is an algorithm?

A

A sequence of steps to complete a known task and that always terminates

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

What are some features of a good algorithm?

A
  • Allow for invalid inputs
  • Be efficient, involving as few steps as possible
  • Be understandable by others
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are the constructs of an algorithm?

A
  • Sequence
  • Assignment
  • Selection
  • Iteration
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a “dry-run”

A

Testing an algorithm using a trace table

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

What can make an algorithm preferable?

A
  • More efficient
  • More robust and works in more cases
  • Better at handling unexpected input
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are some techniques for interpreting algorithms?

A
  • Reading comments that explain how the code works
  • Identifiers can indicate a variable’s purpose or subroutine’s function
  • “Dry-run” the algorithm to see how variables change
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is computational thinking?

A

Approach to solving complex problems through the application of abstraction, decomposition, pattern recognition and algorithmic thinking.

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

What is abstraction?

A

Removal of detail to focus on what is necessary to solve the problem

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

What is pattern recognition?

A

Solving problems by recognising similarities with previously solved problems and applying a similar solution

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

What is algorithmic thinking?

A

Creating a solution to a problem using algorithmic constructs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
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
12
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
13
Q

What is abstraction by generalisation?

A

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

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

What is procedural abstraction?

A

Abstracting away the actual values used in a computation to leave a computational method: a procedure.

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

What’s is functional abstraction?

A

Abstracting the actual computational method involved. The resulting function focuses on the inputs and outputs of the function only.

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

What is data abstraction?

A

Isolates how a compound data structure is used from how it is constructed

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

What is problem abstraction (reduction)?

A

The removal of detail from a problem until it is represented in a way that is possible to solve because the problem is reduced to one that has already been solved

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

What are the two main approaches to abstraction?

A
  • Representational abstraction
  • Abstraction by generalisation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the different form of abstraction?

A
  • Procedural abstraction
  • Functional abstraction
  • Data abstraction
  • Problem abstraction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is procedural decomposition?

A
  • Breaking down complex problems into small sub-problems
  • Each sub-problem accomplishes a specific task that is easier to solve
  • These can be further subdivided until a problem is solvable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is compositional abstraction?

A

Formed by combing the procedures that together will form compound procedures to solve larger/ more complex problems

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

What is compound data?

A

Building data abstraction by combining data objects

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

How is automation achieved?

A
  • Designing and writing algorithms
  • Implementing algorithms in program code, utilising the data structures that represent the data that has been modelled
  • Executing the code to generate a solution to an agreed degree of accuracy
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is a Finite State Machine (FSM)?

A

A model that shows how a machine or system can change from one state to another based on an external input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What are the 2 ways a FSM can be represented?
- Transition Diagram - State Transition Table
26
What are the essential components of a FSM?
- A finite set of input symbols (its alphabet) - A finite set of states that the machine can be in - An initial state - S0 - A state-transition function which determines which state to transition to based on the current state and input - One or more accepting states
27
In how many states can a FSM be in at once?
1
28
What is a dead state?
When it enters a state where it is no longer possible for it to reach an accepting state therefore the input must be invalid.
29
What are some systems that FSM might be used to model?
- Digital (hardware) systems - Software compilers - Syntax parsing - Network protocols - Games
30
What is the “language” of a FSM?
The set of all possible input strings that follow a path from the initial state to an accepting state.
31
What is a Finite State Automata?
A FSM with no output that always has an initial state and at least one accepting state
32
What is a Mealy Machine?
A FSM that produces an output as its inputs are being processed rather than once an accepting state has been reached
33
What are some differences of the Mealy Machines when compared to automata?
- Produce an output while the inputs are being processed - They do not have accepting states
34
What are the uses of Mealy Machines?
- Encrypting a message into cipher text - Controlling traffic lights - Vending machine payment collection and display of amount remaining - Digital logic circuits
35
What is a set?
An unordered collection of values in which each value occurs at most once
36
What is the Cartesian Product of two sets?
The Cartesian product of two sets, A and B, is written as A x B and is the set of all ordered pairs (a,b) where a ∈ A and b ∈ B
37
What is a subset?
A subset of S is a set whose values are all members of S. Written as A ⊆ B
38
What is a proper subset?
A proper subset of S is a set where every value is a member of S but it does not contain all members of S. Written as A ⊂ B.
39
What is the cardinality of a finite set?
The number of items in the finite set
40
What are the different set operations?
- Union: A ∪ B - Intersection: A ∩ B - Difference: A/B
41
What is the union of two sets?
The union of two sets , A and B, will contain all unique values in A and B.
42
What is the intersection of two sets?
The intersection of two sets, A and B, will contain all values that are present in both A and B.
43
What is the difference of two sets?
The difference of two sets, A and B, will contain all the values that are present in A but not B.
44
What are regular expressions?
They provide a way of describing a set of strings that conform to a particular pattern in a simple way
45
What is a regular language?
A language that can be represented by a regular expression
46
What are the uses of regular expressions?
- Describing regular languages in a convinient notation, including languages of FSM - Ensuring that statements or parts of statements are correctly formed in programming languages - Validating the format of user inputs such as post code or email address
47
What does the * meta character meaning in Regex?
Zero or more repetitions of the preceding element
48
What does the + meta character meaning in Regex?
One or more repetitions of the preceding element
49
What does the ? meta character mean in Regex?
Zero or one repetitions of the preceding element
50
What does the | meta character mean in Regex?
One or the other / Boolean OR
51
What is a context free language?
A set of symbols and strings that follow the rules of context-free grammar
52
What is context free grammar?
Describes what strings are possible in a language by laying out production rules
53
What are production rules?
Rules that define a set of strings
54
What is a terminal symbol?
Character or a string that cannot be broken down further
55
What is a non-terminal symbol?
A symbol that is defined by a production rule
56
What is Backus Naur Form?
A meta-language that can describe context-free languages.
57
Example of a production rule in Backus Naur Form:
::= 0|1|2|3|4|5|6|7|8|9 ::= | ::= .
58
What is a syntax diagram?
A visual way of representing context-free languages.
59
What are the symbols used in context free diagrams?
- Rectangle: Non-terminals - Oval: Terminals - Arrow: Indicate how strings could be formed
60
How are non-terminals defined in a syntax diagram?
By their own syntax diagrams
61
How to tell is a language is regular or not?
- If recursion occurs at the start of the end of the production rule then it is possible to be described using a regular language - If recursion occurs between other symbols within the production rule then the grammar is not regular so it cannot be a regular language
62
What’s is the main difference between regular languages and context-free languages?
Regular languages cannot handle nested brackets or recursion whereas context free languages can

Comsci (6 decks)

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