In this topic, we are learning how to solve problems. We will formalise the techniques used by computer scientists to help them to automate the solutions to, often complex, problems in the real world. We are learning ...- How to solve and check the solutions to logic problems
- How to Implement representation, generalisation, categorisation, procedural, functional, data and composition abstraction techniques to problem solving
- To decompose problems into smaller, more manageable chunks
- How algorithms are put into practice to solve problems
- How to describe and apply algorithms and techniques in practical situations
So that we can ...- Develop and check solutions to logic problems
- Describe the techniques of abstraction
- Representation - Generalisation / categorisation - Functional - Divide and conquer - Discuss the concept of Information hiding
- Describe the technique of decomposition / composition
- Design interfaces
- Understand the need for automation.
- Apply patterns for problem solving
*-*Backtracking*-*Data mining*-*Heuristics - Caching*-*Performance modelling*-*Pipelining*-*Visualisation to solve problems (mental models)
Computer science is about building clean, abstract models (abstractions) of messy, noisy, complex, real world objects of phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy.
Computer science deals with putting the models into actions to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.
Logic PuzzlesComputer science is mainly concerned with solving problems. Sometimes the problems are hard, sometimes not. In any event, solving logical puzzles and learning the strategies you can use is extremely valuable. Before we even talk about problem solving, I'm going to give you some tricky challenges.
Further steps, not assessed, but quite interesting (to me at least).
Most intelligent people (i.e. not cats) accept that there is generally better ways of solving logic problems that thrashing about.
Poor Preparation Prevents Proper Performance - known as the 5P's (there are 6P's in some versions ...)Let's consider each step in a
formal problem solving strategy ...STEP 1 : Understand the problemWhat is the unknown? What are the data? What is the condition? Is it possible to satisfy the condition? Is the condition sufficient to determine the unknown? Or is it insufficient? Or redundant? Or contradictory? Draw a figure. Introduce suitable notations. Separate the various parts of the condition. Can you write them down?
When a problem is well defined, we can identify ...
... which taken together give us access to and understanding of the
problem domain.
STEP 2 : Devise a planHow shall we move from the given to the goal?
- Have you seen a problem like this before? How did you solve it?
- Have you met a situation with similar resources / constraints?
- Could you change the problem to look like one you have seen before?
- Is there anything you need to do before you solve the problem? Are there any auxiliary problems?
- Do you have or indeed need all the information you have gathered? Could some be ignored?
Often, breaking down a problem in to smaller, interdependent parts makes solving the problem more manageable. The technique often used is called Top Down Design with Stepwise Refinement. Often, these are stated as separate strategies but they are interdependent ...
There are no hard and fast rules to drawing diagrams like this. They are often called
Hierarchy diagrams. There many be a series of sequential steps necessary to complete each subtask. In this case, we could draw a structure table - a list of instructions. Normally, we draw a hybrid diagram which involves both.For instance, this website is structured like this ...
... whilst a folder based directory structure in a computer filing system might have this structure ...
This incorporates the features of a hierarchy diagram and that of a structure table. As long as it works and everyone can tell what it means, it's OK! We will learn more about this strategy in 'Break it down' ...
Clearly, the remaining step to a working solution is composition where simple procedures / functions / data abstractions are combined to produce a complex working system.The outcome of Step 2 should be an
algorithm.STEP 3 : Execute your planCarrying out your plan of the solution, checking each step. Can you see clearly that each step is correct? Can you prove that it is correct? How easy is the plan to follow? Could it be improved? So many questions!
STEP 4 : Evaluate the answerTime to crack open the bubbly! Ah, but wait - are you sure you did it?
Go back to the original problem. Forget the way you solved it and the steps you took during that journey. Go through the requirements of the problem and check that your solution works.
Human beings have developed an extremely powerful technique for dealing with complexity. Unable to master the entirety of a complex object,
we ignore it's inessential detail, dealing instead with a generalised, idealised model of the object which suits our needs as a user. We abstract the object.Consider a complex object like a cat. Depending on the viewpoint, the user abstracts away all the inessential detail to leave a simpler object which is suited to their need ...
Deciding on what to leave out is a
central problem in programming and object oriented design (which we'll meet later on in the course).Abstraction is ...
- A
**process**: Performing an abstraction on a problem - A
**technique**: For identifying what information should be hidden - An
**entity**: Picasso's final bull is an abstraction of the first
You may be more familiar with the term abstraction in the context of
art. Abstract art "seeks to break away from traditional representation of physical objects. It explores the relationships of forms and colours, whereas more traditional art represents the world in recognizable images."Picasso's Bulls. Notice the persistence of the 'essential' features (ahem!)
Representation abstractionSometimes, the goal of abstraction is to reach a common representation of a problem. This common representation may allow us to use a previously successful algorithm to solve this new problem.
Problems of this type can be solved using one algorithm. They are classically map colouring problems which are solved using the general vertex colouring algorithm your teacher has shown you.
Generalisation abstractionIf we can group problems by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type, we may be able to design behaviours for the more abstract objects that apply to the more specific. For instance ...
Click to view
Designing a behaviour for 'animals' which
all animals perform reduces the amount of work I have to do in order to model the behaviour of snakes or tigers. This method of abstraction is used extensively in Object Oriented Design. Notice that the abstract concept of 'Animal' is an example of high abstraction whereas the Bear is low abstraction (closer to reality).
Functional abstractionClassically used in maths but applied to all sorts of other problems, functional abstraction takes away the actual values used in a computation leaving behind a computational pattern or method. Functional abstraction leads to the development of
functions (obviously) - sub programs which take parameters in and return results.Mathematicians use functions all the time -
sin(), cos() and tan() for instance. Programmers use functions all the time as well - print(), open(), input(). Mathematicians and programmers can design user-defined functions if there is no function available which perform some action either independently or using combinations of existing functions.As the user of the function,
I need not be aware of how the function works. For instance, do any of you actually know how the sin() function works in maths or actually know how the print() function works in Python?Do I care?
Procedural abstractionSometimes, problems lend themselves immediately to solutions using the same basic steps - the procedure. The classic Fox, Chicken Grain problem is one of a group of problems which can be solved using the same
procedure. Procedural abstraction naturally follows from the representation abstraction method which we saw earlier with the graph colouring problem where initially dissimilar problems are boiled down to similar representations to which can be applied the same procedures.
Data abstractionComputers can only store data in the form of binary digits. Yet, we can create such abstract data structures as arrays (or lists), graphs, trees, stacks and queues. Data abstraction takes the complexity of how these data structures are actually stored and manipulated in the computer and hides it, providing a simple functional interface to it's use.
However, the systems that are produced must be usable by
people, so what exactly is it that needs to be hidden or kept secret? It is the internal design of such systems - the way they operate - that is kept secret. Looking an an abstraction from the inside, as the implementer, you'd be concerned with what it's composed of and how it works. Looking at it from the outside, as the user, you are only concerned with what it is and what it does. You can look past the detail and think solely in terms of the role that the function performs.The 'machine' provides a green ball.
I don't care where the green ball comes from.
I know I always get a green ball.
The green ball machine can change.
I still get a green ball.
Information hiding is a technique which is used to obfuscate (or hide) the inner workings of a procedure / abstraction from the outside world whilst providing an interface to allow it's operation - related to functional abstraction.The interface is very similar but the implementation is very different.
It matters not which car you drive - a Bugatti or a Fiat - the basic operation of the machine is the same. It is the
implementation that varies.Two objects with the same interface can implement the action in completely different ways Taking an object, hiding the implementation and providing an interface is called
encapsulation. Encapsulation ensures that the object remains useable (as it's interface remains static) whilst it's implementation can change.Encapsulation hides the details of the implementation of an object and provides an interface for interaction with it.
Information hiding in practice - The Enigma MachineKeeping the operation of a machine secret from the outside world was vital for the operation of the German Enigma Machine - the primary method of encrypted communication in use during the latter part of the Second World War by the German military.
The Enigma Machine
In programming terms, it is
API's (Application Programming Interfaces) which provide the interface to the implementation. We will learn much more about interfaces when we study Object Oriented Design later on in the course.
Computer science deals with putting abstractions into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.
- Creating algorithms
- Implementing models as data structures
- Implementing algorithms in code
- Executing the code
Problem solving strategies / patterns commonly in use include ...
- Backtracking
- Data mining
- Heuristics
- Caching
- Performance modelling
- Pipelining
- Visualisation
Try the following activities to stretch and challenge.
- Use the vertex colouring algorithm to colour in the map of South America which is in the lesson resources.
- Investigate a possible method of applying the vertex colouring algorithm (representation abstraction) to the problem of solving a game of Sudoku. You could come up with your own problem which could be represented using the vertex colouring algorithm and share this as a challenge with your friends.
- Learn to solve a Rubik's cube.
END OF TOPIC ASSESSMENT |