TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Computing > A Level > AQA > Comp1
Problem solving
Principles of computation
| Key Terms
Computation: the act of calculating something by mathematical, logial or interative methods
Computability: measures what can and cannot be computed
Computing: the study of natural and artificial information processes
|
|
|
- if:
| border: 1px solid #AAAAAA;
}}" class="cquote"
| width="20" valign="top" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| “
| Focus on studying the processes of computation and understanding why and where they are important in Computing.
| width="20" valign="bottom" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| ”
|
{{#if:AQA Computing Specification|
| {{#if:AQA Computing Specification| —AQA Computing Specification{{#if:|, {{{5}}}}} }}
}}
|
What is computation?
Orginally humans were computers (by name) who did computations (calculations). In the 1920s thousands of "computers" (humans) were employed to do the calculations manually, but were soon replaced by "computing machines", which was soon after replaced by the "computer" in the 1940s. Since these times there has has been extensive study on computation and computitiblity (what is possible to compute).
| Key Terms
Artifical intelligence: a branch (section) of computing that studies using computers to do processes that are normally proformed by humans.
|
|
|
What is computing
Computing is not constricted to (can only be) man made artefacts such as computers, but infact data is encoded in DNA of which it can be computed. Some fields of computing are Quantum, DNA, Nano, Nature-inspired computing and Artifical intelligence.
Simply, computing is the study of how to compute (do calcaltions), so is the the study of computation.
| Key Terms
Program: a description in a programming language of a process that can achive a useful result.
|
|
|
Programs
A program is a description in a programming language, however, a algorithm is seporate form any programming langauge and may be inplemented in many different langauges.
The computer itself doesn't "know" anything apart form voltages, it is the programs running that uses this infomation and turns it into something a human can interpret, like numbers.
Abstraction and automation
The two main princibles of computation are:
Abstraction
- What is the right way of thinking about the problem
- What is the simplist way to communicate the complex problem
- How can the problem be broken apart in a logical way
Automation
- How can the process be automated with minimal human input
Abstraction is turning a real life problem (if possible) into a the symplist algorthm possible.
Automation involves a programmer turning the algorthm into a program for a computer to interpret.
Stages of problem solving
- if:
| border: 1px solid #AAAAAA;
}}" class="cquote"
| width="20" valign="top" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| “
| Understand the problem. Define the problem. Define boundaries. Plan solution. Check solution.
| width="20" valign="bottom" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| ”
|
{{#if:AQA Computing Specification|
| {{#if:AQA Computing Specification| —AQA Computing Specification{{#if:|, {{{5}}}}} }}
}}
|
Understand the problem
A problem is where it is not immediately obvious how to reach a goal. To understand how to get to the goal one has to understand the problem.
Example - Man, chicken, bag of grain and dog
- initial situation - Man, chicken, bag of grain and dog on one side of a river with a rowing boat.
- goal - Man, chicken, bag of grain and dog all intact on the opposite side of the river.
- set of resources - Rowing boat and problem solving skills.
- set of constraints - One passanger and man on boat at any one time, dog and chicken and also chicken and grain must not be left together.
- owner - you plan solution and carry it through.
|
|
|
Define the problem
A good definition, then problem statement, should have a clear:
- initial situation
- goal
- set of resources
- set of constraints
- owner
If the problem is ill-definded (not enough information), then more information or understanding is need to make it a well-definded problem.
| Key Terms
Define boundaries: establishing constrants (limits) about what can and cannot be done when solving a problem.
Lateral thinking: challenenging assumptions and establishing facts giving the true boundries of a problem.
|
|
|
Define boundaries
Boundaries are constraints, most commonly time and resources. It is not good to assume something is not true, using latteral thinking you can challange assumptions and establish facts.
The genreral pattern of latteral thinking is:
- Ask extra questions, if possible.
- Identify assumptions, this is by estabishling what is given and what has been subconciously assuming.
- Make new facts from combining the orginal given facts.
Plan solution
- if:
| border: 1px solid #AAAAAA;
}}" class="cquote"
| width="20" valign="top" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| “
| Determine logical conditions and consequential actions.
| width="20" valign="bottom" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| ”
|
{{#if:AQA Computing Specification|
| {{#if:AQA Computing Specification| —AQA Computing Specification{{#if:|, {{{5}}}}} }}
}}
|
Using the boundries, you should develop a plan of action. Firstly you think about strategies, are more than one or sub-strategys requred.
It is much easyer to solve a few small smaller problems than one big one, so spitting it down can be much easyer to solve. You then think about resources, what will be used, how will you use them, in what order and are they adequate for the strategy/s being used.
To split up a problem, also known as divide and conquer, a range of methods can be used, two of them can be top-down design and stepwise refinement.
| Key Term
Top-down design: breaks a problem into smaller problems that are easier to work on.
Module: when a problem is divided into sub-problems, each corrisponds to a self-containted module.
|
|
|
Top-down design
If you are a mathematition you may be aware that you can split problems down and work at them a bit at a time, for example:
- A = 2, 12x50+AxB= 6, what is B.
- Find, 12x50
- Find, 6 - (12x50)
- Find, (6 - (12x50))/A
this can also be displayed in a hierachy chart:
A Hierarchy char works from left to right, and has as many levels as requred.
| Key Term
Stepwise refinement: the process of breaking a problem down through successive steps into smaller problems.
Structure table: an indented, numbered list of steps produced by stepwise refinement.
|
|
|
Stepwise refinement
A alternative method would be to use this method which is to break down a big problem into progressively smaller steps.
When giving directions, for example you could firstly start with a - b, then split them into major points on the way, then give the directions in between. Its good to give no more than 5-9 divisons as it gets hard to remember.
This is a example of a stepwise refinement:
| Level 0 .
| Travel from Ellesbrough to Aston Clinton
|
| Level 1
| 1 Travel from Ellesbrough to Wendover
|
|
| 2 Travel from Wendover to Weston Turville
|
|
| 3 Travel from Weston Turville to Aston Clinton
|
| Level 2
| 1.1 Travel from Ellesbrough to Butlers Cross
|
|
| 1.2 Travel from Butlers Cross to Wendover
|
| .
|
|
|
| 2.1 Travel from Wendover along A413 to junction with B4544
|
|
| 2.2 Travel along B4544 to Weston Turville
|
| .
|
|
|
| 3.1 Drive through Weston Turville to junction with A41
|
|
| 3.2 Turn southwards onto A41 to reach Aston Clinton
|
The same steps can be laid out differently in a structure table: (If you notice, it is used in this wiki page for the heading levels)
0 Travel from Ellesbrough to Aston Clinton
- 0.1 Travel from Ellesbrough to Wendover
- 0.1.1 Travel from Ellesbrough to Butlers Cross
- 0.1.2 Travel from Butlers Cross to Wendover
- 0.2 Travel from Wendover to Weston Turville
- 0.2.1 Travel from Wendover along A413 to junction with B4544
- 0.2.2 Travel along B4544 to Weston Turville
- 0.3 Travel from Weston Turville to Aston Clinton
- 0.3.1 Drive through Weston Turville to junction with A41
- 0.3.2 Turn southwards onto A41 to reach Aston Clinton
Check solution and carrying out plan of action
Its good to be observant and be thoughtful when carring out plan of action incase unexpected events which may requre rethinking and going back to a earlyer stage.
Check to see if goal has been achived:
- If sovled, see how general your solution is, and if it can be reaplied
- If not solved, go back to defining the problem
- Analyse your steps to see if there is extra unnecessary steps or over complication has been created in a attempt to simplify
- Stop working on the problem, in time you may gain expertise needed to solve it, or it is not solvable
| Key Terms
Finite state machine: a machine that consists of a fixed set of possible states with a set of allowable inputs that change the state and a set of possible outputs.
|
|
|
Finite state machines
Finite state machines are basically where a certian amount of possible states, for example a pen, down is one state, up is another, there are not infinate amount of possible combinations. The states are changed by certian possible inputs and this means there are only certian possible outputs.
| Key Terms
State transition diagram: a way of describing a finite state machine graphically. Each state is represented by a circle and each transition by a arrow labelled with the input that causes the transaction plus any output resulting from the transaction.
|
|
|
State transition diagrams
- if:
| border: 1px solid #AAAAAA;
}}" class="cquote"
| width="20" valign="top" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| “
| Draw and interpret simple state transition diagrams, transition tables.
| width="20" valign="bottom" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| ”
|
{{#if:AQA Computing Specification|
| {{#if:AQA Computing Specification| —AQA Computing Specification{{#if:|, {{{5}}}}} }}
}}
|
Carrying on the pen example:
- Finite states: Up and Down
- Inputs: Clicking
- Outputs: pen out or in
A way of describing this would be using a state transition diagram, these have states in circles and arrows which above have what input caused it to change state and possibly a "," then the output.
This is what the bullpoint pen would look like
| Key Terms
State transition table: shows the effect on the current state of an finite state machine of paticular inputs and any corrisponding outputs.
|
|
|
State transition tables
You can use a state stransition table to record what will happen to a set of inputs with a finite state machine, to carry on the ultimately exciting example of a pen, here is a example:
| Input
| Current state .
| Next state
|
| Button Clicked .
| In
| Out
|
| Button Clicked
| Out
| In
|
| Key Terms
Decision tables: a table that shows the outcome for a given logical condition.
|
|
|
Decision tables
- if:
| border: 1px solid #AAAAAA;
}}" class="cquote"
| width="20" valign="top" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| “
| Determine logical conditions and consequential actions.
| width="20" valign="bottom" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| ”
|
{{#if:AQA Computing Specification|
| {{#if:AQA Computing Specification| —AQA Computing Specification{{#if:|, {{{5}}}}} }}
}}
|
A decision table is a precise yet compact way to model complicated logic.
It is made easy to see if all possible conditions to be accounted for.
A example in engish would be:
If X is greater than 6 and Y is less than 7
then output "Pass"
else output "Fail"
The corrisponding answer in a decision table would be:
| Conditions .
| X > 6
| Y .
| Y .
| N .
| N
|
|
| Y < 7
| Y
| N
| Y
| N
|
| Actions
| Output "Pass" .
| X
|
|
|
|
|
| Output "Fail"
|
| X
| X
| X
|
Algorithm designs
| Key Terms
Algorithm: a step by step description, not using a programing langauge, of a process that achives some task.
Determinstically: without guessing a solution before confirming it.
|
|
|
- if:
| border: 1px solid #AAAAAA;
}}" class="cquote"
| width="20" valign="top" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| “
| Understand the term algorithm.
Express the solution to a simple problem as an algorithm using
flowcharts, pseudo-code or structured English and the standard
constructs:
• sequence
• assignment
• selection
• repetition
Hand trace simple algorithms.
Convert a simple algorithm from
• structured English into pseudo-code,
• pseudo-code into high level program code
Understand the standard algorithms: Bubble Sort, Linear Search.
| width="20" valign="bottom" style="color:#B2B7F2;font-size:{{#switch:
| 10px=20px
| 30px=60px
| 40px=80px
| 50px=100px
| 60px=120px
| ”
|
{{#if:AQA Computing Specification|
| {{#if:AQA Computing Specification| —AQA Computing Specification{{#if:|, {{{5}}}}} }}
}}
|
Programing
Input, assignment and output
Data types
Selection
Repetition (itteration)
Prodcedures and functions
Arrays
Text files and files of records
Program Structure
Structured programming
Standard algorithms
Checking for errors
Validation and error handling
Testing
Data representation
Logic gates and boolean algebra
Computer architecture
Basic machine code operations and the fetch-execute cycle
The system life cycle
Stages in hardware and software development
