Problem Solving: Introduction to principles of computation
Computing is a very different course from ICT and if you have studied ICT at secondary school you should see a big difference between the two. This course will introduce you to the theory, mathematics and logic that sit behind the computing revolution. Over the course of this book I also hope to take you through the steps needed to practice computational thinking, the art of using computers to solve problems. This doesn't mean getting you to think like a computer, but it does mean getting you to think in ways that you can use computers to solve problems. Computational thinking is made up of four parts:
- Pattern recognition
- Pattern generalisation and abstraction
- Algorithm design
Let's take a look at what each of these mean:
Part of being a computer scientist is breaking down a big problem into the smaller problems that make it up. If you can break down a big problem into smaller problems then you can give them to a computer to solve. For example if I gave you a cake and asked you to bake me another one you might struggle, but if you watched me making the cake and worked out the ingredients then you'd stand a much better chance of replicating it. If you can look at a problem and work out the main steps of that problem then you'll stand a much better chance of solving it.
Let's look at an example, the equation to work out the roots of a quadratic equation.
On first look it might appear a little scary, but if we decompose it we should stand a better chance of solving it:
- repeat for
By noting the steps down to solve a problem we can often recognise patterns, and by giving a list of steps we are one step closer to creating an algorithm.
Often breaking down a problem into its components is a little harder than taking apart an algorithm, we often get given a set of raw data then are asked to find the pattern behind it:
This is pretty easy with number sets, the above has the pattern. But pattern recognition might also involve recognising shapes, sounds or images. If your camera highlights faces when you point it at some friends, then it is recognising the pattern of a face in a picture.
If your phone tells you the weather when you ask it "What is the weather like in Witham", then it has recognised the word "weather" and that "Witham" is a small town in Essex, linking them together. Pattern recognition is the computing behind why you get given tailored adverts when you log into your mail account or social network, they have recognised the pattern of what someone like you wants to buy. Pattern recognition might predict the weather, but chaos theory means that it's not always perfect.
Pattern generalisation and abstraction
Once we have recognised patterns we need to put it in its simplest terms so that it can be used whenever we need to use it. For example, if you were studying the patterns of how people speak, we might notice that all proper English sentences have a subject and predicate.
Once we have our patterns and abstractions we can start to write the steps that a computer can use to solve the problem. We do this by creating Algorithms. Algorithms aren't computer code, but are independent instructions that could be turned into computer code. We often write these independent instructions as pseudo code. Examples of algorithms could be to describe orbit of the moon, the steps involved in setting up a new online shopping account or the sequences of tasks involved for a robot to build a new car.
declare robot robot.on; robot.get(body); robot.get(roof); do robot.weld(roof, body); until (robot.weld == success) robot.off;
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by:
with seed values
(your answer might differ considerably from this, to see if it works give it to a friend to see if they can follow it)
Nowadays computers are ubiquitous and some would argue that there are no problems out there that a computer, given enough time, couldn't solve. But is this true? Is every problem solvable by a machine and can we ever know if this is the case?
The jury is still out of this one. There are people who say yes and others no, with people such as some existentialists arguing that you cannot get a computer to simulate consciousness. This line of thought soon turns into philosophy.
Very early on in modern computing, a British academic named Alan Turing devised the halting problem. This problem is to do with whether we can determine if a program will ever come to a halt or run for ever, for example:
Would write hello to the screen then stop. However, take a look at:
dim x as integer = 9 while x > 8 console.writeline("hello") end while
This would never finish, it would never come to a halt as x will always be larger than 8 and never get any smaller. This means the while loop will continue for ever, constantly printing out "hello". In the two cases shown it is easy to tell if a program will halt or not, but it isn't so easy. Imagine we get a more complex piece of code:
dim x as integer = 9 dim total as integer = 0 while total < 100 total = total + x x = x / 2 end while
This is harder but still solvable taking a little more thinking and a little time on the processor. We could get a piece of code that takes weeks, years or even thousands of years to finish. But how can we know that all programs will end or not? To determine whether the program halts we:
Surely we create a mathematical proof to determine whether code will end or not I hear you say. Well let's prove just the opposite:
Let us create a program K that will loop forever if the result of H is to halt, and halt if the result of H is to loop for ever:
function K(i): if H(i,i) = halt then loop forever else halt
We can therefore see that there are examples of programs such as K that we cannot determine whether they are ever going to halt.