Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 离散数学结构（第四版 影印版）
发信站: 哈工大紫丁香 (2002年11月09日15:15:33 星期六), 站内信件

离散数学结构（第四版 影印版） ISBN 7-04-010096-7/TP.707 P525
　　Discrete Mathematical Structures (Fourth Edition)
　　Kolman, Busby and Ross，2001.6出版，定价：29.50元
　　本书以介绍涉及计算机科学领域的离散数学知识为主，由浅入深地介绍离散数学的
有关知识。
　　第一章介绍了关于离散数学的基本知识，包括集合、子集的概念和集合的操作运算
，序数，整数的划分，矩阵，数学结构（构造）等。第二章介绍逻辑及其相关的内容，
包括方法证明和数学归纳等。第三章介绍数论的有关内容，包括排列与置换、联合、鸽
巢原理、事件概率、循环关系。第四章通过有向图来讲述关系的基本类型和基本原理。
第五章介绍映射，包括一些典型的映射在计算机科学领域中的应用。第六章介绍偏序（
次序关系），包括格与布尔代数。第七章介绍树，包括有向树与无向树及其应用。第八
章主要讲述图论的知识以及通路问题与穿程问题。第九章介绍了半群与群的基本知识。
第十章介绍有限自动机。最后一章介绍了有关的二进制代码的知识，包括二进制信息的
编码及其错误校验和解码及其错误校验。本书适合于作为计算机及其相关专业离散数学
课程教材。
　　内容：1. 基础知识 2. 逻辑 3. 数论 4. 关系与图 5. 映射 6. 偏序7. 树 8. 图
论 9. 半群与群10. 语言和自动机 11. 群与编码
　　CONTENTS:
Preface　　
1 Fundamentals
　　1.1 Sets and subsets
　　1.2 Operations on Sets
　　1.3 Sequences
　　1.4 division in the Integers
　　1.5 Matrices
　　1.6 Mathematical structures
2 Logic
　　2.1 Propositions and Logical Operations
　　2.2 conditional statements
　　2.3 Methods of Proof
　　2.4 Mathematical induction
3 Counting
　　3.1 Permutations
　　3.2 combinations
　　3.3 Pigeonhole Principle
　　3.4 elements of Probability
　　3.5 recurrence Relations
4 Relations and digraphs
　　4.1 Product Sets and Partitions
　　4.2 Relations and Digraphs
　　4.3 Paths in Relations and Digraphs
　　4.4 Properties of relations
　　4.5 Equivalence Relations
　　4.6 Computer Representation of relations and digraphs
　　4.7 Operations on relations
　　4.8 Transitive Closure and Warshall's Algorithm
5 Functions
　　5.1 Functions
　　5.2 Functions for Computer Science
　　5.3 Growth of Functions
　　5.4 Permutation Functions
6 Order Relations and Structures
　　6.1 Partially Ordered Sets
　　6.2 Extremal Elements of Partially Ordered Sets
　　6.3 Lattices
　　6.4 Finite boolean Algebras
　　6.5 Functions on Boolean Algebras
　　6.6 Circuit designs
7 Trees
　　7.1 Trees
　　7.2 Labeled Trees
　　7.3 Tree Searching
　　7.4 Undirected Trees
　　7.5 Minimal Spanning Trees
8 Topics in Graph Theory
　　8.1 Graphs
　　8.2 Euler Paths and circuits
　　8.3 Hamiltonian Paths and Circuits
　　8.4 Transport Networks
　　8.5 Matching Problems
　　8.6 Coloring Graphs
9 Semigroups and Groups
　　9.1 Semigroups
　　9.2 Products and Quotients of Semigroups
　　9.3 Groups
　　9.4 Products and Quotients of Groups
10 Languages and finite-State Machines
　　10.1 Languages
　　10.2 Representations of Special Grammars and Languages
　　10.3 Finite-State Machines
　　10.4 Semigroups, Machines, and Languages
　　10.5 Machines and Regular Languages
　　10.6 Simplification of Machines
11 Groups and Coding
　　11.1 Coding of Binary Information and Error Detecion
　　11.2 Decoding and Error Correction
Appendix A: Algorithms and Pseudocode
Appendix B: Experiments in Discrete Mathematics
Answers to Odd-Numbered Exercises
Answers to Chapter Self-Tests
Index
PREFACE
　　Discrete mathematics is a difficult course to teach and to study at the 
freshman and sophomore level for several reasons. It is a hybrid course. Its
 content is mathematics, but many of its applications and more than half its
 students are from computer science. Thus careful motivation of topics and p
reviews of applications are important and necessary strategies. Moreover, th
e number of substantive and diverse topics covered in the course is high, so
 that student must absorb them rather quickly. At the same time, the student
 may also be expected to develop proof-writing skills.
APPROACH
　　First, we have limited both the areas covered and the depth of coverage 
to what we deemed prudent in a first course taught at the freshman and sopho
more level. We have identified a set of topics that we feel are of genuine u
se in computer science and elsewhere and that can be presented in a logicall
y coherent fashion. We have presented an introduction to these topics along 
with an indication of how they can be pursued in greater depth.
　　For example, we cover the simpler finite-state machines, not Turing mach
ines. We have limited the coverage of abstract algebra to a discussion of se
migroups and groups and have given application of these to the important top
ics of finite-state machines and error-detecting and error-correcting codes.
 Error-correcting codes. in turn, have been primarily restricted to simple l
inear codes.
　　Second, the material has been organized and interrelated to minimize the
 mass of definitions and the abstraction of some of the theory. Relations an
d digraphs are treated as two aspects of the same fundamental mathematical i
dea, with a directed graph being a pictorial representation of a relation. T
his fundamental idea is then used as the basis of virtually all the concepts
 introduced in the book, including functions, partial orders, graphs, and al
gebraic structures. Whenever possible, each new idea introduced in the text 
uses previously encountered material and, in turn. is developed in such a wa
y that it simplifies the more complex ideas that follow. Thus partial orders
, lattices, and Boolean algebras develop from general relations. This materi
al in turn leads naturally to other algebraic structures.
WHAT IN NEW IN THE FOURTH EDITION
　　We continue to be pleased by the reception given to earlier editions of 
this book. We still believe that the book works well in the classroom becaus
e of the unifying role played by two key concepts: relations and digraphs. F
or this edition we have modified the order of topics slightly and made exten
sive revisions of the exercise sets. The discourse on proof has been expande
d in several ways. One of these is the insertion of comments on nearly every
 proof in the book. Whatever changes we have made, our goal continues to be 
that of maximizing the clarity of presentation. As the audience for an intro
ductory discrete mathematics course changes and as the course is increasingl
y used as a bridge course, we have added the following features.
· A new section, Transport Networks, introduces this topic using ideas from
 Chapter4.
· A new section, Matching Problems, applies the techniques of transport net
works to a broad class of problems.
· The section on mathematical induction now includes the strong form of ind
uction as well.
· The discussion of proofs and proof techniques is now woven throughout the
 book with comments on most proofs, more exercises related to the mechanics 
of proving statements, and Tips for Proofs sections. Tips for Proofs highlig
ht the types of proofs commonly seen for that chapter's material and methods
 for selecting fruitful proof strategies.
· A Self-Test is provided for each chapter with answers for all problems gi
ven at the back of the book.
· Exercise Sets have a broader range of problems: more routine problems and
 more challenging problems. More exercises focus on the mechanics of proof a
nd proof techniques. As with writing in general, students learn to write pro
ofs not only by reading, analyzing, and recognizing the structure of proofs,
 but especially by writing, re-writing, and writing more proofs themselves.
EXERCISES
The exercises form an integral part of the book. Many are computational in n
ature, whereas others are of a theoretical type. many of the latter and the 
experiments, to be further described below, require verbal solutions. Exerci
ses to help develop proof-writing skills ask the student to analyze proofs, 
amplify aruments, or complete partial proofs. Answers to all odd-numbered ex
ercises appear in the back of the book. Solutions to all exercises appear in
 the Instructor's Manual, which is available (to instructors only) gratis fr
om the publisher. The Instructor's Manual also includes notes on the pedagog
ical ideas underlying each chapter, goals and grading guidelines for the exp
eriments further described below, and a test bank.
EXPERIMENTS
Appendix B contains a number of assignments that we call experiments. These 
provide an opprtunity for discovery and exploration, or a more-in-depth look
 at various topics discussed in the text. These are suitable for group work.
 Content prerequisites for each experiment are given in the Instructor's Man
ual.
END OF CHAPTER MATERIAL
Each chapter contains Tips for Proofs, a summary of Key Ideas, a set of Codi
ng Exercises, and a Self-Test covering the chapter's material.
CONTENT
　　Chapter 1 contains a miscellany of basic material required in the course
. this includes sets, subsets, and their operations; sequences; division in 
the integers; matrices; and mathematical structures. a goal of this chapter 
is to help students develop skills in identifying patterns on many levels. C
hapter 2 covers logic and related material, including methods of proof and m
athematical induction. although the discussion of proof is based on this cha
pter. the commentary continues throughout the book. Chapter 3, on counting, 
deals with permutations, combinations, the pigeonhole principle, elements of
 probability, and recurrence relations. Chapter 4 presents basic types and p
roperties of relations, along with their representation as directed graphs. 
connections with matrices and other data structures are also explored in thi
s chapter. The power of multiple representations for the concept of relation
 is fully exploited. Chapter 5 deals with the notion of a function and gives
 important examples of functions, including functions of special interest in
 computer science. An introduction to the growth of functions is developed.
　　Chapter 6 covers partially ordered sets, including lattices and Boolan a
lgebras. chapter 7 introduces directed and undirected trees along with appli
cations of these ideas. Elementary graph theory is the focus of Chapter 8. N
ew to this edition are sections on transport Networks and matching Problems;
 these build on the foundation of Chapter4.
　　In chapter8 we give the basic theory of semigroups and groups. these ide
as are applied in chapters 10 and 11. Chapter 10 is devoted to finite-state 
machines. It complements and makes effective use of ideas developedin previo
us chapters. Chapter 11 treats the subject of binary coding.
　　Appendix A discusses algorithms and pseudocode. The simplified pseudocod
e presented here is used in some text examples and exercises; these may be o
mitted without loss of continuity. appendix b gives a collection of experime
nts dealing with extensions or previews of topics in various parts of the co
urse.
USE OF THIS TEXT
　　This text can be used by students in mathematics as an introduction to t
he fundamental ideas of discrete mathematics, and as a foundation for the de
velopment of more advanced mathematical concepts. If used in this way, the t
opics dealing with specific computer science applications can be ignored or 
selected independently as important examples. The text can also be used in a
 computer science or computer engineering curriculum to present the foundati
ons of many basic computer-related concepts, and provide a coherent developm
ent and common theme for these ideas.
The instructor can easily develop a suitable course by referring to the chap
ter prerequisites, which identify material needed by that chapter.
ACKNOWLEDGMENTS
We are pleased to express our thanks to the following reviewers of the first
 three editions: Harold Fredrickson, Naval Postgraduate School;Thomas E. Ger
asch, George mason university; Samuel J. Wiley, La salle college; Kenneth b.
 Reid, Louisiana Sate University; Ron Sandstrom, Fort hays State University;
 Richard H. Austing, University of Maryland; Nina Edelman, Temple University
; Paul Gormley, Villanova University; Herman Gollwitzer and Loren N. Argabri
ght, both at Drexel Unicweairy; Bill Sands, University of Calgary, who broug
ht to our attention a number of errors in the second edition; Moshe Dror, Un
iversity of Arizona, Tucson; Lloyd Gavin, California State University at sac
raments; Robert H. Gilman, stevens Institute of Technology; Earl E. Kymala, 
California State University at Sacramento; and Art Lew, University of Hawaii
, Honolulu; and of the fourth edition: Ashok T.Amin, University of Alabama a
t Huntsville; Donald S.Hart, Rochester Institute of Technology; Minhua Liu, 
William Rainey Harper College; Charles Parry, Virginia Polytechnic Institute
 & University; Arthur T.Poe, Temple University; Suk Jai Seo, University of A
labama at Huntsville; Paul Weiner, St.Mary's University of Minnesota. The su
ggestions. comments, and criticisms of these people greatly improved the man
uscript.
We thank Dennis R.Kletzing, Stetson University, who carefully typeset the en
tire manuscript; Nina Edelman, Temple University, for critically reading pag
e proofs; Blaise DeSeas, Allentown college of St. Frances de Sales, who chec
ked the answers and solutions to all the exercises in the book; and instruct
ors and students from many institutions in the United States and other count
ries, for sharing with us their experiences with the book and for offering h
elpful suggestions.
Finally, a sincere expression of thanks goes to Betsy Williams, George Lobel
l, Gale Epps, and the entire staff at Prentice hall for their enthusiasm, in
terest, and unfailing cooperation during the conception, design, production,
 and marketing phases of this edition.
B.K.
R.C.B.
S.C.R.

--
RULE 10 - Television is NOT real life. In real life people 

actually have to leave the coffee shop and go to jobs.

                                             ——Bill Gates

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.75]