Decomposition Computer Science

1 Key excerpts on "Decomposition Computer Science"

• 

  eBook - ePub

  Computational Thinking

  A beginner's guide to problem-solving and programming

  • Karl Beecher(Author)
  • 2017(Publication Date)
  • BCS, The Chartered Institute for IT

    (Publisher)

  Recursion: a technique used to simplify a problem. It defines the solution to a large, complex problem in terms of smaller, simpler problems of the same form as the original problem. This is a very powerful idea and one that is heavily used in CS.

  By applying decomposition, you aim to end up with a number of sub-problems that can be understood and solved individually. This may require you to apply the process recursively (see above). That is to say, the problem is re-formed as a series of smaller problems that, while simpler, might be still too complex, in which case they too need breaking down, and so on. Visually this gives the problem definition a tree structure.

  The conceptual idea of a tree structure is very important to CS and often goes hand in hand with the idea of recursion. A tree represents a collection of entities16 organised into hierarchical relationships. Each ‘parent’ entity may have any number of ‘child’ entities (including none). A tree has a single ‘root’ entity and all childless entities are called ‘leaves’. Visually, it resembles a tree – admittedly an upside-down one, with the ‘root’ at the top and the leaves along the bottom. Trees can represent a huge range of different structures, including something as rigidly defined as a family tree (see Figure 3.1 ).

  Figure 3.1 Royal family tree

  Or something put together arbitrarily like arranging Shakespeare’s plays by genre (Figure 3.2 ).

  Figure 3.2 Shakespeare plays arranged by genre into a tree structure

  Let’s look at an example. One task that many of us encounter during our education is the production of a dissertation. Writing an academic work some tens of thousands of words in length can inspire fear, panic or even despair. By itself, one monolithic task entitled ‘write dissertation’ is unmanageable, but by decomposing the problem you reduce it into smaller parts, each of which possesses far fewer details. You can then focus your attention on each part and deal with it much more effectively. By solving each sub-problem, you end up solving the overall problem.

  Sign up to read

  Learn more about book