A-Level计算机-Computer。

Revision: Computer

Problem solving

Principles of computation

"Focus on studying the processes of computation and understanding why and where they are important in Computing.”

Key Terms

Computation: the act of calculating something by mathematical, logical or interactive methods

Computability: measures what can and cannot be computed

Computing: the study of natural and artificial information processes

What is computation?

Originally 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 that time there has been extensive study on computation and computability (what is possible to compute).

Key Terms

Artificial intelligence: a branch (section) of computing that studies using computers to do processes that are normally performed by humans.

What is computing?

Computing is not constricted to (can only be) man made artifacts such as computers, but in fact data is encoded in DNA of which it can be computed. Some fields of computing are Quantum, DNA, Nano, Nature-inspired computing and Artificial intelligence.

Simply, computing is the study of how to compute (do calculations), so is the study of computation.

Key Terms

Program: a description in a programming language of a process that can achieve a useful result.

Programs

A program is a description in a programming language; however, an algorithm is separate form any programming language and may be implemented in many different languages.

The computer itself doesn't "know" anything apart form voltages, it is the programs running that uses this information and turns it into something a human can interpret, like numbers.

Abstraction and automation

The two main principles of computation are:

Abstraction

What is the right way of thinking about the problem

What is the simplest 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 simplest algorithm possible.

Automation involves a programmer turning the algorithm into a program for a computer to interpret.

Stages of problem solving

"Understand the problem. Define the problem. Define boundaries. Plan solution. Check solution.”

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 passenger 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-defined (not enough information), then more information or understanding is need to make it a well-defined problem.

Key Terms

Define boundaries: establishing constraints (limits) about what can and cannot be done when solving a problem.

Lateral thinking: challenging assumptions and establishing facts giving the true boundaries of a problem.

Define boundaries

Boundaries are constraints, most commonly time and resources. It is not good to assume something is not true, using lateral thinking you can challenge assumptions and establish facts.

The general pattern of lateral thinking is:

Ask extra questions, if possible.

Identify assumptions, this is by establishing what is given and what has been subconsciously assuming.

Make new facts from combining the original given facts.

Plan solution

"Determine logical conditions and consequential actions.”

Using the boundaries, you should develop a plan of action. Firstly you think about strategies, are more than one or sub-strategies required. It is much easier to solve a few small smaller problems than one big one, so spitting it down can be much easier 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 corresponds to a self-contained module.

Top-down design

If you are a mathematician 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 hierarchy 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 is produced by stepwise refinement.

Stepwise refinement

An 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. It’s good to give no more than 5-9 divisions as it gets hard to remember.

This is an example of a stepwise refinement:

……

Check solution and carrying out plan of action

It’s good to be observant and be thoughtful when caring out plan of action incase unexpected events which may require rethinking and going back to a earlier stage.

Check to see if goal has been achieved:

If solved, see how general your solution is, and if it can be replied

If not solved, go back to defining the problem

Analyze 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 certain amount of possible states, for example a pen, down is one state, up is another, there are not infinite amount of possible combinations. The states are changed by certain possible inputs and this means there are only certain 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 labeled with the input that causes the transaction plus any output resulting from the transaction.

State transition diagrams

"Draw and interpret simple state transition diagrams, transition tables.”

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 ballpoint pen would look like

……

Key Terms

State transition table: shows the effect on the current state of an finite state machine of particular inputs and any corresponding outputs.

State transition tables

You can use a state transition 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:

……

Key Terms

Decision tables: a table that shows the outcome for a given logical condition.

Decision tables

"Determine logical conditions and consequential actions.”

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.

An example in English would be:

If X is greater than 6 and Y is less than 7 then output "Pass" else output "Fail"

The corresponding answer in a decision table would be:

……

Key Terms

Algorithm: a step by step description, not using a programming language, of a process that achieves some task.

Deterministically: without guessing a solution before confirming it.

“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 traces 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. ”

推荐阅读

【汇总】2016年雅思听力考试回忆及真题解析汇总

【汇总】2016年雅思阅读考试回忆及真题解析汇总

【汇总】2016年雅思写作考试回忆及真题解析汇总

【汇总】2016年雅思口语考试回忆及真题解析汇总

若想获取更多详尽出国留学攻略以及雅思备考资讯，可以打开我们【上海新东方雅思网】，涵盖雅思真题机经，雅思写作、口语、听力、阅读以及留学名校介绍等，也许就能找到你真正需要的。上海新东方雅思网在这里预祝各位考生学习顺利，都能考取自己满意的学校。