|
|
Join The Student Room TodayBe part of the UK's largest and fastest growing student community. It's free to join and a lot of fun - Get inspired, express your ideas, interact and share Revision:Comp1From The Student RoomTSR Wiki > Study Help > Subjects and Revision > Revision Notes > Computing > A Level > AQA > Comp1
Problem solvingPrinciples of computation
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).
What is computingComputing 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.
ProgramsA 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 automationThe two main princibles of computation are: Abstraction
Automation
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
Understand the problemA 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.
Define the problemA good definition, then problem statement, should have a clear:
If the problem is ill-definded (not enough information), then more information or understanding is need to make it a well-definded problem.
Define boundariesBoundaries 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:
Plan solution
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.
Top-down designIf 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:
this can also be displayed in a hierachy chart:
A Hierarchy char works from left to right, and has as many levels as requred.
Stepwise refinementA 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:
Check solution and carrying out plan of actionIts 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:
Finite state machinesFinite 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.
State transition diagrams
Carrying on the pen example:
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
State transition tablesYou 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:
Decision tables
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:
Algorithm designs
ProgramingInput, assignment and outputData typesSelectionRepetition (itteration)Prodcedures and functionsArraysText files and files of recordsProgram StructureStructured programmingStandard algorithmsChecking for errorsValidation and error handlingTestingData representationLogic gates and boolean algebraComputer architectureBasic machine code operations and the fetch-execute cycleThe system life cycleStages in hardware and software development |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|