A central theme in computing is the design of a process for carrying out a task. The task might be sorting names into alphabetical order, finding the cheapest way to link a set of computing sites into a network, converting a number to its representation in the binary system, encrypting a message for secure transmission, designing a digital circuit for a microchip, or determining the shortest path to be followed by a robotic arm. There will be many occasions throughout this book when we will find ourselves investigating problems of this nature, and asking: How can this task be performed by a person or a computer? In each case, the answer will take the form of a precise sequence of steps known as an algorithm.
Numbers can be represented in various ways. For example, the number ‘four’ can be written in the usual notation as 4, in Roman numerals as IV, or even just as four tally marks, IIII. Similarly, ‘two-and-a-half’ can be written as the mixed number 2½, as the improper fraction 5/2, or as the decimal number 2.5. In particular, numbers can be represented using systems similar to the familiar decimal system but based on numbers other than 10. In this chapter, we investigate the representation of numbers using different number bases, paying particular attention to the number systems used in computing.
In Chapter 2, we looked at how numbers can be represented in the binary number system. In this chapter, we shall use the techniques we developed in Chapter 2 to investigate the ways in which numbers are represented and manipulated in binary form in a computer.
In this chapter, we will introduce the study of logic from a mathematical point of view. Mathematical logic finds applications in many areas of computing. The laws of logic are employed in the design of the digital circuitry in a computer. Logical expressions occur as conditions in the control structures in algorithms and computer programs, and in the commands used for querying databases. Expert systems employing knowledge-based software use rules of logical inference to draw conclusions from known facts. Formal specification documents, which state in a precise way what computer systems are required to do, are written in specification languages, such as Z, which use the theory and notation of symbolic logic.
In this chapter, we will present some basic mathematical ideas about sets and relations. Some of the material on sets may be familiar to you already, in which case you may wish to scan over those sections fairly briefly. The main reason for introducing sets is to provide some useful terminology and notation for the work that follows; we will not be studying the mathematical theory of sets as such. Relations arise in computing in the area of relational databases, and we will also need them in Chapter 12 when we study congruences.
If you have already studied functions in mathematics, it is likely that what you were studying was a type of function known as a ‘real-valued function of a real variable’. If this is the case, then you probably think of a function as ‘something that has a mathematical formula’ such as x2 − 2x + 3, or ‘something you can draw the graph of’ using x and y axes.
The main purpose of this chapter is to introduce recursion. Recursion is a simple yet powerful idea that can be enormously useful in developing algorithms for solving complex problems. This is especially true if an algorithm is to be implemented in Lisp or a related programming language such as Scheme. We will also introduce the method of proof by induction, a technique closely related to recursion. In addition to being one of the standard proof techniques in mathematics, induction is a useful technique for verifying the correctness of algorithms.
In this chapter we will take a look at the branch of mathematics known as Boolean algebra. There are two main reasons for studying Boolean algebra at this point. Firstly, we will be able to see how Boolean algebra draws together into a unified theory many of the concepts in propositional logic and sets that we met in Chapters 4 and 5. The idea of incorporating two (or more) separate topics into a single theory is a powerful concept, which has played an important role in the development of mathematics. By identifying the common rules that underlie logic and sets, we will be able to derive results that can be applied to both areas.
Combinatorics is the branch of mathematics devoted to calculating the number of ways in which a specified process can be carried out. Problems of this type often occur in computing. A typical example is the problem of determining how many times a particular sequence of steps in an algorithm will be executed, as part of the larger problem of estimating how long the algorithm will take to run. For example, a simple algorithm for determining the shortest path for a signal to travel through a communications network might begin by calculating the lengths of all the possible paths through the network. A better algorithm might arrive at the correct answer after calculating just the lengths of a particular selection of the paths. In order to determine how efficient or inefficient these algorithms are, and to be able to compare them with each other and with other algorithms, we must first answer the question: ‘How many such paths are there altogether?’
The objects that we study in the branch of mathematics known as graph theory are not graphs drawn with x and y axes. In this chapter, the word ‘graph’ refers to a structure consisting of points (called ‘vertices’), some of which may be joined to other vertices by lines (called ‘edges’) to form a network. Structures of this type abound in computing. The computers on a site may be connected into a local area network, which in turn may be linked to national and international communications networks. The circuitry inside a computer (which we represented schematically by digital circuit diagrams in Chapter 8) is another example of a graph or network structure. At a more abstract level, we saw in Chapter 5 how a relation on a set can be depicted using a diagram that takes the form of a graph.
In this chapter we will study the particular type of graph known as a tree, and investigate some applications of trees to practical problems. Trees arise in the problem of designing a communications network as cheaply as possible, and in the representation of hierarchical structures and decision processes, as well as in many other situations.
No doubt you have been familiar with the natural numbers since childhood. For this reason, it might seem that there could be little more to learn about them, at least in comparison with other types of numbers: fractions, negative numbers, irrational numbers and complex numbers. Nothing could be further from the truth; in fact, some of the most challenging problems in mathematics involve just the natural numbers. Since ancient times, mathematicians have been intrigued by the subtle properties that underlie the apparent simplicity of these numbers.
In Chapter 1 we introduced the concept of an algorithm. Our main purpose at that stage was to define a language, or pseudocode, in which algorithms could be written. We have been using the ideas of Chapter 1, and the pseudocode notation in particular, throughout this book.
