# AQA COMPUTING COMP3 Revision

Hey guys, thought i should share the notes i made for comp3.

Enjoy and make sure you use other resources also to revise!

Good Luck!

5.0 / 5

Teacher recommended

HideShow resource information

AQA COMPUTING COMP3 RevisionWord Document 4.21 Mb

## Pages in this set

### Page 1

.

### Page 2

CONTENTS

CONTENTS

1.1 Problem SOLVING: Information hiding and Abstraction

Data representation

1.2 Comparing alogirthms

1.3 Finite state machines

Types of FSM

1.4 Turing machines(Read book)

1.5 Intractable problems(read book)

1.6 regular expressions, BNF and RPN

2.0 Programming Concepts

3.1 Real Numbers

Formats of floatingpoint numbers

4.0 Operating system

4.1 Role…

CONTENTS

1.1 Problem SOLVING: Information hiding and Abstraction

Data representation

1.2 Comparing alogirthms

1.3 Finite state machines

Types of FSM

1.4 Turing machines(Read book)

1.5 Intractable problems(read book)

1.6 regular expressions, BNF and RPN

2.0 Programming Concepts

3.1 Real Numbers

Formats of floatingpoint numbers

4.0 Operating system

4.1 Role…

### Page 3

1.1 PROBLEM SOLVING: INFORMATION HIDING AND ABSTRACTION

Interface: a boundary between the implementation of a system and the world that uses it.

It provides an abstraction of the entity behind the boundary thus separating the methods of eternal

communication from internal operation.

Information hiding means hiding design details behind a…

Interface: a boundary between the implementation of a system and the world that uses it.

It provides an abstraction of the entity behind the boundary thus separating the methods of eternal

communication from internal operation.

Information hiding means hiding design details behind a…

### Page 4

to the pigeonhole with their number of hairs on t, there must be at least wo people with the same

number of hairs on their head "

DATA REPRESENTATION

Representation abstraction is applied to problem solving. It is also known as problem abstraction or

reduction. Details are removed until it…

number of hairs on their head "

DATA REPRESENTATION

Representation abstraction is applied to problem solving. It is also known as problem abstraction or

reduction. Details are removed until it…

### Page 5

Different problems may solve the same problems;

Each step in any algorithm must be unambiguous.

The range of inputs for which an algorithm works has to be specified carefully.

Several algorithms for solving the same problem may exist

Algorithms for the same problem can be based on a very different…

Each step in any algorithm must be unambiguous.

The range of inputs for which an algorithm works has to be specified carefully.

Several algorithms for solving the same problem may exist

Algorithms for the same problem can be based on a very different…

### Page 6

Order of growth: assesses by what

factor execution time increases when

the size of the input in increased.

A problem has a linear order of growth

when an algorithm takes twice as long

to run if the input is doubled. If the

execution time increases by 4 when

the input…

### Page 7

Exponential growth: growth that has the form k(^n).

Exponential time algorithm: an algorithm whose execution grows exponentially with input size.

Polynomial growth: a growth that has the form n(^k),

Polynomial time algorithm: an algorithm those execution time grown as a polynomial of input size

Linear time algorithm: a polynomial

time…

Exponential time algorithm: an algorithm whose execution grows exponentially with input size.

Polynomial growth: a growth that has the form n(^k),

Polynomial time algorithm: an algorithm those execution time grown as a polynomial of input size

Linear time algorithm: a polynomial

time…

### Page 8

Transition Function : maps (input symbol, current state) to (output system, next state).

Transition table: tabulates that mappings (input symbol, current state) to (output symbol,

next state).

Deterministic finite state machine: an FSM that has just one next state for each pair of state and

input symbol. Each outgoing transition…

### Page 9

IN THIS TOPIC YOU HAVE COVERED

1. FSMs can be used to control traffic lights, as recognizer that specify a language and check if a

given string is in the language, to search for words in a large piece of text, and for party

checking.

2. An FSM has a…

### Page 10

Decision problem: A yes/no algorithmic problem.

Decidable: a decision problem that has a yes/no answer.

Undecidable: describes a decision type algorithmic problem that is noncomputable.

Tractable: describes a problem that has a reasonable (polynomial) time solution as the size of the

input increases.

Intractable: describes a problem for which no…

Decidable: a decision problem that has a yes/no answer.

Undecidable: describes a decision type algorithmic problem that is noncomputable.

Tractable: describes a problem that has a reasonable (polynomial) time solution as the size of the

input increases.

Intractable: describes a problem for which no…

## Related discussions on The Student Room

- AQA Computing COMP 3- 22nd June 2016 [Exam Discussion] »
- AQA A2 Computing - COMP3 11/06/13 »
- AQA A2 COMP 3 Computing 2015 - Official Thread »
- I Need help with my COMP4 project analysis (AQA A2 ... »
- AS AQA Computer Science 2016 Revision Help »
- AQA A2 Psychology PSYA3/PSYA4 Revision Thread 2015 »
- AQA AS Computing - COMP2 - June 3rd 2015 - Exam ... »
- AQA AS Computing Skeleton Code 2014 »
- AQA COMP1 RETAKE exam 2016 »
- Aqa comp 4 2012/13 »

## Similar Computing resources:

0.0 / 5

4.5 / 5

4.0 / 5

5.0 / 5

Teacher recommended

0.0 / 5

# AQA COMPUTING COMP3 Revision

Hey guys, thought i should share the notes i made for comp3.

Enjoy and make sure you use other resources also to revise!

Good Luck!

5.0 / 5

Teacher recommended

- Created by: KnightCode
- Created on: 26-05-16 12:06

AQA COMPUTING COMP3 RevisionWord Document 4.21 Mb

## Pages in this set

### Page 1

.

### Page 2

CONTENTS

CONTENTS

1.1 Problem SOLVING: Information hiding and Abstraction

Data representation

1.2 Comparing alogirthms

1.3 Finite state machines

Types of FSM

1.4 Turing machines(Read book)

1.5 Intractable problems(read book)

1.6 regular expressions, BNF and RPN

2.0 Programming Concepts

3.1 Real Numbers

Formats of floatingpoint numbers

4.0 Operating system

4.1 Role…

CONTENTS

1.1 Problem SOLVING: Information hiding and Abstraction

Data representation

1.2 Comparing alogirthms

1.3 Finite state machines

Types of FSM

1.4 Turing machines(Read book)

1.5 Intractable problems(read book)

1.6 regular expressions, BNF and RPN

2.0 Programming Concepts

3.1 Real Numbers

Formats of floatingpoint numbers

4.0 Operating system

4.1 Role…

### Page 3

1.1 PROBLEM SOLVING: INFORMATION HIDING AND ABSTRACTION

Interface: a boundary between the implementation of a system and the world that uses it.

It provides an abstraction of the entity behind the boundary thus separating the methods of eternal

communication from internal operation.

Information hiding means hiding design details behind a…

Interface: a boundary between the implementation of a system and the world that uses it.

It provides an abstraction of the entity behind the boundary thus separating the methods of eternal

communication from internal operation.

Information hiding means hiding design details behind a…

### Page 4

to the pigeonhole with their number of hairs on t, there must be at least wo people with the same

number of hairs on their head "

DATA REPRESENTATION

Representation abstraction is applied to problem solving. It is also known as problem abstraction or

reduction. Details are removed until it…

number of hairs on their head "

DATA REPRESENTATION

Representation abstraction is applied to problem solving. It is also known as problem abstraction or

reduction. Details are removed until it…

### Page 5

Different problems may solve the same problems;

Each step in any algorithm must be unambiguous.

The range of inputs for which an algorithm works has to be specified carefully.

Several algorithms for solving the same problem may exist

Algorithms for the same problem can be based on a very different…

Each step in any algorithm must be unambiguous.

The range of inputs for which an algorithm works has to be specified carefully.

Several algorithms for solving the same problem may exist

Algorithms for the same problem can be based on a very different…

### Page 6

Order of growth: assesses by what

factor execution time increases when

the size of the input in increased.

A problem has a linear order of growth

when an algorithm takes twice as long

to run if the input is doubled. If the

execution time increases by 4 when

the input…

### Page 7

Exponential growth: growth that has the form k(^n).

Exponential time algorithm: an algorithm whose execution grows exponentially with input size.

Polynomial growth: a growth that has the form n(^k),

Polynomial time algorithm: an algorithm those execution time grown as a polynomial of input size

Linear time algorithm: a polynomial

time…

Exponential time algorithm: an algorithm whose execution grows exponentially with input size.

Polynomial growth: a growth that has the form n(^k),

Polynomial time algorithm: an algorithm those execution time grown as a polynomial of input size

Linear time algorithm: a polynomial

time…

### Page 8

Transition Function : maps (input symbol, current state) to (output system, next state).

Transition table: tabulates that mappings (input symbol, current state) to (output symbol,

next state).

Deterministic finite state machine: an FSM that has just one next state for each pair of state and

input symbol. Each outgoing transition…

### Page 9

IN THIS TOPIC YOU HAVE COVERED

1. FSMs can be used to control traffic lights, as recognizer that specify a language and check if a

given string is in the language, to search for words in a large piece of text, and for party

checking.

2. An FSM has a…

### Page 10

Decision problem: A yes/no algorithmic problem.

Decidable: a decision problem that has a yes/no answer.

Undecidable: describes a decision type algorithmic problem that is noncomputable.

Tractable: describes a problem that has a reasonable (polynomial) time solution as the size of the

input increases.

Intractable: describes a problem for which no…

Decidable: a decision problem that has a yes/no answer.

Undecidable: describes a decision type algorithmic problem that is noncomputable.

Tractable: describes a problem that has a reasonable (polynomial) time solution as the size of the

input increases.

Intractable: describes a problem for which no…

## Comments

## Similar Computing resources:

0.0 / 5

4.5 / 5

4.0 / 5

5.0 / 5

Teacher recommended

0.0 / 5

## Related discussions on The Student Room

- AQA Computing COMP 3- 22nd June 2016 [Exam Discussion] »
- AQA A2 Computing - COMP3 11/06/13 »
- AQA A2 COMP 3 Computing 2015 - Official Thread »
- I Need help with my COMP4 project analysis (AQA A2 ... »
- AS AQA Computer Science 2016 Revision Help »
- AQA A2 Psychology PSYA3/PSYA4 Revision Thread 2015 »
- AQA AS Computing - COMP2 - June 3rd 2015 - Exam ... »
- AQA AS Computing Skeleton Code 2014 »
- AQA COMP1 RETAKE exam 2016 »
- Aqa comp 4 2012/13 »

## Comments

Report