Problem Solving: Introduction to principles of computation

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 1 - ⇑ Problem Solving ⇑

Introduction to principles of computation Stages of problem solving →

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[1]:

  • Decomposition
  • Pattern recognition
  • Pattern generalisation and abstraction
  • Algorithm design

Let's take a look at what each of these mean:

Decomposition[edit]

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.

x=\frac{-b \pm \sqrt {b^2-4ac}}{2a}

On first look it might appear a little scary, but if we decompose it we should stand a better chance of solving it:

  1. b^2
  2. 4ac
  3. b^2-4ac
  4. \sqrt {b^2-4ac}
  5. -b + \sqrt {b^2-4ac}
  6. 2a
  7. x=\frac{-b + \sqrt {b^2-4ac}}{2a}
  8. repeat for -b - \sqrt {b^2-4ac}

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.

Pattern recognition[edit]

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:

1, 4, 7, 10, 13, 16, 19, 22, 25,

This is pretty easy with number sets, the above has the pattern An = (n * 3) - 2. 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.

The face was automatically detected by pattern recognition

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[edit]

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.

Algorithm design[edit]

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;
Exercise: Computational thinking
What are the four main parts of computational thinking?

Answer :

  • Decomposition
  • Pattern recognition
  • Pattern generalisation and abstraction
  • Algorithm design
Can you spot a pattern in this set of numbers?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Answer :

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by:

F_n = F_{n-1} + F_{n-2},\!\,

with seed values

F_1 = 0,\; F_2     = 1

Can you come up with an algorithm to make a cup of tea?

Answer :

(your answer might differ considerably from this, to see if it works give it to a friend to see if they can follow it)

  1. put water into kettle
  2. turn kettle on
  3. get out cup and saucer
  4. put tea bag into cup
  5. when water boiled add to cup
  6. stir with spoon
  7. remove tea bag
  8. if milk needed
    1. add milk

Limits?[edit]

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?

Exercise: Introduction to principles of computation
Do you think that every process in nature can be simulated by a computer?

Answer :

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.
Extension: The halting problem

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:

console.writeline("hello")

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:

  • run a program with a given input, if it stops we know it stops
  • BUT if it keeps running beyond a reasonable amount of time we cannot conclude that it will loop for ever (maybe we need to wait a little longer...)

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:

The halting solution H takes an input program A and a set of inputs X, it then determines whether the program will finished executing or not
You can replace the Input X with a copy of the program A. As the program A is made from code, this can be transformed into 1s and 0s, giving H a data input

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
If H says halt, K will loop. If H says loop K will halt, thus the Halting Solution H will be undecidable

We can therefore see that there are examples of programs such as K that we cannot determine whether they are ever going to halt.


References[edit]