Java Reference
In-Depth Information
2
Mathematical Preliminaries
This chapter presents mathematical notation, background, and techniques used
throughout the topic. This material is provided primarily for review and reference.
You might wish to return to the relevant sections when you encounter unfamiliar
notation or mathematical techniques in later chapters.
Section 2.7 on estimation might be unfamiliar to many readers. Estimation is
not a mathematical technique, but rather a general engineering skill. It is enor-
mously useful to computer scientists doing design work, because any proposed
solution whose estimated resource requirements fall well outside the problem's re-
source constraints can be discarded immediately, allowing time for greater analysis
of more promising solutions.
2.1
Sets and Relations
The concept of a set in the mathematical sense has wide application in computer
science. The notations and techniques of set theory are commonly used when de-
scribing and implementing algorithms because the abstractions associated with sets
often help to clarify and simplify algorithm design.
A set is a collection of distinguishable members or elements. The members
are typically drawn from some larger population known as the base type. Each
member of a set is either a primitive element of the base type or is a set itself.
There is no concept of duplication in a set. Each value from the base type is either
in the set or not in the set. For example, a set named P might consist of the three
integers 7, 11, and 42. In this case, P's members are 7, 11, and 42, and the base
type is integer.
Figure 2.1 shows the symbols commonly used to express sets and their rela-
tionships. Here are some examples of this notation in use. First define two sets, P
and Q.
P = f2; 3; 5g;
Q = f5; 10g:
23
