 |
How are numbers represented in a
computer?
How can this representation be used to
perform arithmetic operations?
The unit, Discrete Mathematics for
Computing, introduces the mathematics underlying the engineering
solutions to these questions.
Binary representation and arithmetic
based on a place value system with a base of 2 using the symbols 0 and
1 (corresponding to on or off) and some of its
limitations are considered for both whole numbers and fractions.
The nature of the circuitry required to
give the results of adding two numbers is also considered.
|
 |
 |
The half adder (above)
takes two binary digits such as p and q, each of which
could be either 1 or 0 (meaning that there is, or is not, a current
flowing in the corresponding piece of wire) and delivers the correct
outputs for addition.
The outputs could come from any of
0+0 = 0; 0+1
= 1; 1+0 = 1 or 1+1 = 10.
In the last case a two digit output is
produced, so, in terms of two digits, the possible outputs are
00, 01 or 10
The first digit is called the carry
and the second the sum.
The correct output is that there will,
or will not, be current flowing in the pieces of wire marked sum
and carry as given by the addition process.
To analyse what is required in
computer circuitry, we need to be able to analyse combinations formed
using the logical operators and, or and not.
This unit therefore also deals with
logic.
Try Smullyan's book for a taste of
logical deduction.
|
| The design of computer
networks motivates the study of what technically are called graphs.
Trees, which are a special kind of graph, have
applications in decision making, in the interpretation of expressions
for calculation sequences and in
codes. Including the many applications for the Travelling Salesman
problem, graphs are significant not only in computer science but in
areas of operations research as well. The final module of the unit is
devoted to graphs. Historically, the original graph theory problem was
that of the Koenigsburg Bridges (see below) and was solved by Euler. |
 |
|
|
 |
Underlying all is the idea
of relationships between various sets of objects. In particular,
there are equivalence relationships, ordering
relationships and functional relationships. Proving things
about relationships is an important part of this unit.
Functional relationships are
particularly
important for computer professionals, since the relationship between
input
data and computer output is a functional one. Functions applied to
lists
of objects are fundamental and the unit devotes some time to
considering
them. Some time, too, is devoted to writing clear instructions for
executing
the operations required to achieve the effect of particular functions.
Written
effectively these algorithms can be translated into code for
high
level computer languages.
When the running of a computer program
(function) calls for the running of that same program on smaller data
in the process of its execution, we have what is called a recursive
function. Recursive processes (functions) are well illustrated by the Tower
of Hanoi problem (the design of the original box for this puzzle is
shown at left). Recursive functions are closely related to
iterative procedures (procedures that are repeated over and over) and
to the Principle of Mathematical Induction.
|
Hopefully this
description
makes it easier to understand the unit synopsis :
| This course introduces the
basic
elements of discrete mathematics which provide a foundation for an
understanding of algorithms and data structures used in
computing. Included are aspects
of machine representation, algorithms and data structures, logic,
proof,
recursive algorithms, graphs and trees. |
|
MAT1101 
| Helpline
![[Page]](Up.gif){kind=small}
![[Page]](Images/Up.gif){kind=small}