Discrete Math in Computer Science - Bogart , Stein.pdf

(1701 KB) Pobierz
main.tex
Discrete Math in Computer Science
Ken Bogart
Dept. of Mathematics
Dartmouth College
Cliff Stein
Dept. of Computer Science
Dartmouth College
June 23, 2002
2
This is a working draft of a textbook for a discrete mathematics course. This course is
designed to be taken by computer science students. The prerequisites are first semester calculus
(Math 3) and the introductory computer science course (CS 5). The class is meant to be taken
concurrently with or after the second computer science course, Data Structures and Computer
Programming (CS 15). This class is a prerequite to Algorithms (CS 25) and it is recommended
that it be taken before all CS courses other than 5 and 15.
c
Copyright Kenneth P. Bogart and Cliff Stein 2002
Chapter 1
Counting
1.1 Basic Counting
About the course
In these notes, student activities alternate with explanations and extensions of the point of the
activities. The best way to use these notes is to try to master the student activity before beginning
the explanation that follows. The activities are largely meant to be done in groups in class; thus
for activities done out of class we recommend trying to form a group of students to work together.
The reason that the class and these notes are designed in this way is to help students develop
their own habits of mathematical thought. There is considerable evidence that students who
are actively discovering what they are learning remember it far longer and are more likely to be
able to use it out of the context in which it was learned. Students are much more likely to ask
questions until they understand a subject when they are working in a small group with peers
rather than in a larger class with an instructor. There is also evidence that explaining ideas to
someone else helps us organize these ideas in our own minds. However, different people learn
differently. Also the amount of material in discrete mathematics that is desirable for computer
science students to learn is much more than can be covered in an academic term if all learning
is to be done through small group interaction. For these reasons about half of each section of
these notes is devoted to student activities, and half to explanation and extension of the lessons
of these activities.
Analyzing loops
1.1-1 The loop below is part of an implementation of selection sort to sort a list of items
chosen from an ordered set (numbers, alphabet characters, words, etc.) into increasing
order.
for i =1 to n
for j = i +1 to n
if ( A ( i ) >A ( j ))
exchange A ( i ) and A ( j )
3
4
CHAPTER 1. COUNTING
How many times is the comparison A(i) > A(j) made?
The Sum Principle
In Exercise 1.1-1, the segment of code
for j = i +1 to n
if ( A ( i ) >A ( j ))
exchange A ( i ) and A ( j )
is executed n times, once for each value of i between 1 and n inclusive. The first time, it makes
n
−
1 comparisons. The second time, it makes n
−
2 comparisons. The i th time, it makes n
−
i
comparisons. Thus the total number of comparisons is
( n
−
1)+( n
−
2) +
···
+1+0 .
The formula we have is not so important as the reasoning that lead us to it. In order to put
the reasoning into a format that will allow us to apply it broadly, we will describe what we were
doing in the language of sets. Think about the set of all comparisons the algorithm in Exercise
1.1-1 makes. We divided that set up into n pieces (i.e. smaller sets), the set S 1 of comparisons
made when i =1,the set S 2 of comparisons made when i =2,and so on through the set S n of
comparisons made when i = n .Wewere able to figure out the number of comparisons in each
of these pieces by observation, and added together the sizes of all the pieces in order to get the
size of the set of all comparisons.
A little bit of set theoretic terminology will help us describe a general version of the process
we used. Two sets are called disjoint when they have no elements in common. Each of the pieces
we described above is disjoint from each of the others, because the comparisons we make for one
value of i are different from those we make with another value of i .Wesay the set of pieces is a
family of mutually disjoint sets , meaning that it is a family (set) of sets, each two of which are
disjoint. With this language, we can state a general principle that explains what we were doing
without making any specific reference to the problem we were solving.
The sum principle says:
The size of a union of a family of mutually disjoint sets is the sum of the sizes of the
sets.
Thus we were, in effect, using the sum principle to solve Exercise 1.1-1. There is an algebraic
notation that we can use to describe the sum principle. For this purpose, we use
|
S
|
to stand
=3. Using this notation, we can state the sum
principle as: if S 1 , S 2 ,... S n are disjoint sets, then
|{
a, b, c
}|
|
S 1
∪
S 2
∪ ···∪
S n
|
=
|
S 1
|
+
|
S 2
|
+
···
+
|
S n
|
.
To write this without the “dots” that indicate left-out material, we write
n
i =1 |
n
|
S i
|
=
S i
|
.
i =1
for the size of the set S .For example,
1.1. BASIC COUNTING
5
The process of figuring out a general principle that “explains” why a certain computation
makes sense is an example of the mathematical process of “abstraction.” We won’t try to give a
precise definition of abstraction but rather point out examples of the process as we proceed. In a
course in set theory, we would further abstract our work and derive the sum principle from certain
principles that we would take as the axioms of set theory. In a course in discrete mathematics,
this level of abstraction is unnecessary, so from now on we will simply use the sum principle as the
basis of computations when it is convenient to do so. It may seem as though our abstraction was
simply a mindless exercise that complicates what was an “obvious” solution to Exercise 1.1-1. If
we were only working on this one exercise, that would be the case. However the principle we have
derived will prove to be useful in a wide variety of problems. This is the value of abstraction.
When you can recognize the abstract elements of a problem that helped you solve it in another
problem, then abstraction often helps you solve that second problem as well.
There is a formula you may know for the sum
( n
−
1) + ( n
−
2) +
···
1+0 ,
which we also write as
n
n
−
i.
i =1
Now, if we don’t like to deal with summing the values of ( n
−
i ), we can observe that the set
of values we are summing is n
−
1 ,n
−
2 ,..., 1, so we may write that
n
n− 1
n
−
i =
i.
i =1
i =1
There is a clever trick, usually attributed to Gauss, that gives us the formula for this sum.
We write
1+2+
···
+ n
−
2+ n
−
1
+ n
−
1+ n
−
2+
···
+2+1
n + n +
···
+ n + n
1). It is
the sum of the two sums above the line, and since these sums are equal (being identical except
for being in reverse order), the sum below the line must be twice either sum above, so either of
the sums above must be n ( n
−
1 terms each equal to n , and so it is n ( n
−
−
1) / 2. In other words, we may write
n
n
−
1
i = n ( n
−
1)
n
−
i =
.
2
i =1
i =1
While this is a lovely trick, learning tricks gives us little or no real mathematical skill; it is
learning how to think about things to discover answers that is useful. After we analyze Exercise
1.1-2 and abstract the process we are using there, we will be able to come back to this problem
and see a way that we could have discovered this formula for ourselves without any tricks.
The sum below the horizontal line has n
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin