Computer Science Unit 4.4: Theory of Computation

studied byStudied by 0 people
0.0(0)
learn
LearnA personalized and smart learning plan
exam
Practice TestTake a test on your terms and definitions
spaced repetition
Spaced RepetitionScientifically backed study method
heart puzzle
Matching GameHow quick can you match all your cards?
flashcards
FlashcardsStudy terms and definitions
Get a hint
Hint

What is computational thinking?

Get a hint
Hint

Working out how to work things out

Get a hint
Hint

What are the methods of problem solving?

Get a hint
Hint
  • Simulation

  • Enumeration

  • Trial and Error

  • Theoretical approach

  • Creative solution

1 / 57

Anonymous user
Anonymous user
encourage image

There's no tags or description

Looks like no one added any tags here yet for you.

58 Terms

1

What is computational thinking?

Working out how to work things out

New cards
2

What are the methods of problem solving?

  • Simulation

  • Enumeration

  • Trial and Error

  • Theoretical approach

  • Creative solution

New cards
3

What does decrease and conquer mean?

Involves finding a solution to a sequence of smaller, related problems until the problem is small enough to be solved directly. 

New cards
4

What’s an example of decrease and conquer?

The binary search algorithm

New cards
5

What does iteration mean?

Repetition

New cards
6

Why is structured programming possible?

The structures are built into the programming languages

New cards
7

What does structured programming use to write a computer program?

  • Top-down analysis for problem-solving. 

  • Modularisation for program structure and organisation. 

  • Structured code for individual modules. 

New cards
8

What kind of format does structured programming use?

Top-down design format

New cards
9

What is the program divided down into in a top down design?

Modules

New cards
10

Where are modules called from?

The main program

New cards
11

What can modules be broken down into?

Subtasks

New cards
12

What do the smallest of modules perform?

A single function

New cards
13

What is a hierarchy used to show?

The overall program structure

New cards
14
New cards
15

What are the benefits of structured programming?

  • Programs are more easily and quickly written

  • Programs are more reliable and have fewer errors

  • Programs take less time to test and debug

  • Programs are easier to maintain

New cards
16

What are 3 qualities of good coding practice?

  • Use meaningful names for variables and subroutines. 

  • Add lots of comments to explain each module. 

  • Each module should perform a single task.  

New cards
17

What is modular programming most useful for?

Large and complex programs

New cards
18

What is an algorithm?

A sequence of steps that can be followed to complete a task and always terminates

New cards
19
New cards
20

What is an example of a problem solved by algorithms?

Sorting large amounts of data

New cards
21

What are 3 properties of a good algorithm?

  • Has clear and precisely stated steps that produce a correct output for any set of valid inputs. 

  • Should allow for invalid inputs. 

  • Must always terminate at some point. 

New cards
22

What is the purpose of testing software?

The purpose of testing software is to reveal errors

New cards
23

What are the stages of testing?

  1. Module testing

  2. Program testing

  3. System testing

New cards
24

What does module testing do?

Makes sure each subroutine works correctly

New cards
25

What does program testing do?

Makes sure each program in the system works correctly

New cards
26

What does system testing do?

Makes sure the whole system works as expected, and does what the original specification required

New cards
27

What are the 3 types of test data?

  • Normal (typical) data

  • Boundary data

  • Erroneous (unexpected) data

New cards
28

What are hand-tracing algorithms useful for?

  • Figuring out how an algorithm works

  • Finding out why an algorithm isn’t working properly

New cards
29

What is a trace table used for?

Used to write down the contents of each variable as it changes during execution

New cards
30

What is representational abstraction?

Removing unnecessary details to concentrate on what is necessary to solve the problem

New cards
31

What is an example of information hiding?

The London Underground Map

New cards
32

What is abstraction by generalisation?

Grouping common characteristics to achieve a hierarchal structure

New cards
33

What is an example of abstraction by generalisation?

The bridges of Konigsberg

New cards
34

What is problem abstraction?

Removing details until the problem is possible to solve, as it reduces to one which has already been solved

New cards
35

What is an example of problem abstraction?

The Four Knights Problem

New cards
36

What are the 4 steps of automation?

  • Building models of real world objects

  • Decide what details are relevant to the program and discard everything else.

  • Design algorithms to solve the problem. 

  • Algorithm is then implemented in program code and executed. 

New cards
37

What is an example of automation?

A financial model which calculates the likely profit from a coffee shop, based on the available data. 

New cards
38

What is decomposition?

Breaking a problem into sub-problems, so that each sub-problem accomplishes an identifiable task

New cards
39

What is composition?

Combining procedures to form a compound procedure and combining data objects to form compound data objects

New cards
40

What is procedural abstraction?

Where you separate the values used in order to keep the actual values used in a computation separate from the overall design

New cards
41

What is an example of procedural abstraction?

drawTriangle("Blue",7.8,4.2)

New cards
42

What is functional abstraction?

When you call a function to calculate a square root, or generate a random number

New cards
43

What is an example of functional abstraction?

x = sqrt(17)

New cards
44

What is data abstraction?

The data relevant to solving any problem may be in the form of an abstract data structure

New cards
45

What is an example of data abstraction?

A stack

New cards
46

What is a finite state machine (FSM)?

An abstract representation of how something changes from one state to another in response to a condition or event. 

New cards
47

What are some facts about FSMs?

  • The machine can only be in one state at a time. 

  • It can change from one state to another in response to an event or condition. 

  • Is defined by a list of its states and the conditions for each transition. 

New cards
48

What is an example of a FSM?

A turnstile

<p>A turnstile</p>
New cards
49

What are 2 examples of the uses of FSMs?

  • Robotics 

  • Video games industry 

New cards
50

What is Finite State Automation?

  • A FSM which has no output

  • It has a start state and a set of end or accept states. 

  • If the automation can reach a final state, it is said to accept the input

New cards
51
<p>What do the symbols of a FSM mean?</p>

What do the symbols of a FSM mean?

knowt flashcard image
New cards
52
term image

Accepted: aaac, adadbd, ac, bd

Rejected: badc, bdaacS

New cards
53
term image

Accepted: a, bbaa, bababaa

Rejected: abba, baaa

New cards
54
term image

Accepted: 10000

Rejected: 1011, 100011

New cards
55

What are the advantages of structured programming?

  • Easier to understand

  • Quicker to write

  • Less likely to contain errors

New cards
56

What are the disadvantages of structured programming?

  • Takes time to convert into machine code as it’s machine-independent

  • The converted machine code is not the same as assembly language

New cards
57

What is linear search?

An algorithm that searches through an array and returns the index of the value it searches for

New cards
58

What is binary search?

An algorithm that searches for the presence of an item stored within an array and requires all items to be in order.

New cards

Explore top notes

note Note
studied byStudied by 77 people
636 days ago
5.0(1)
note Note
studied byStudied by 2 people
57 days ago
5.0(1)
note Note
studied byStudied by 51 people
757 days ago
5.0(2)
note Note
studied byStudied by 37 people
706 days ago
5.0(1)
note Note
studied byStudied by 2 people
46 days ago
5.0(1)
note Note
studied byStudied by 3 people
52 days ago
5.0(1)
note Note
studied byStudied by 35 people
1037 days ago
5.0(1)
note Note
studied byStudied by 215 people
501 days ago
5.0(1)

Explore top flashcards

flashcards Flashcard (58)
studied byStudied by 4 people
790 days ago
5.0(1)
flashcards Flashcard (122)
studied byStudied by 49 people
408 days ago
5.0(1)
flashcards Flashcard (48)
studied byStudied by 5 people
9 days ago
5.0(2)
flashcards Flashcard (30)
studied byStudied by 22 people
738 days ago
5.0(2)
flashcards Flashcard (40)
studied byStudied by 388 people
696 days ago
4.0(5)
flashcards Flashcard (127)
studied byStudied by 304 people
526 days ago
5.0(4)
flashcards Flashcard (45)
studied byStudied by 191 people
752 days ago
5.0(2)
flashcards Flashcard (20)
studied byStudied by 12 people
472 days ago
5.0(1)
robot