Discrete mathematics
著者
書誌事項
Discrete mathematics
Addison-Wesley, c2002
4th ed
大学図書館所蔵 全5件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
Bibliography: p. 572-575
Includes indexes
内容説明・目次
内容説明
For one or two term introductory courses in discrete mathematics. This book provides an accessible introduction to discrete mathematics through an algorithmic approach that focuses on problem-solving techniques with woven techniques of proofs into the text as a running theme. Each chapter has a problem-solving corner that shows students how to attack and solve problems. The topics are based upon the recommendations of various professional organizations, including those of the MAAs Panel on Discrete Mathematics in the First Two Years, the NCTMs Principles and Standards for School Mathematics, and the CBMSs recommendations for the mathematical education of teachers. Although designed for a one-semester course, the book contains more material then can be covered in either one semester or two quarters. Consequently, instructors will have freedom to choose topics tailored to the particular needs and interests of their students. The sequence of chapters allows considerable flexibility in teaching a course from this book.
Although this book assumes only the familiarity with logic and proofs ordinarily gained in high-school geometry, Appendix A is provided for those who prefer a more formal treatment. If this appendix is covered, it may be taught at any time as an independent unit or in combination with Chapter 9. The exercise sets in this book have been designed for flexibility. Many straightforward computational and algorithmic exercises are included after each section. These exercises give students hands-on practice with the concepts and algorithms of discrete mathematics and are especially important for students whose mathematical backgrounds are weak. Other exercises extend the material in the text or introduce new concepts not treated there. At the end of each chapter, a set of supplementary exercises is provided. Historical comments have been also added and enhanced to put the material in context. These are included at the end of each chapter. Chapters 3 and 4 have been rewritten so as to give the breadth-first search algorithm a more prominent role.
Many examples in these chapters have been rewritten to be more useful to instructors who do not wish to discuss the details of the formal presentations of the algorithms. Each chapter ends with a set of computer projects related to its content, algorithmic or otherwise. These are purposely stated in general terms, so as to be appropriate to students using various computing systems and languages.
目次
(Each Chapter, excluding Chapter 7, concludes with "Historical Notes," "Supplement Exercises," "Computer Projects," and "Suggested Readings.").
1. An Introduction to Combinatorial Problems and Techniques.
The Time to Complete a Project.
A Matching Problem.
A Knapsack Problem.
Algorithms and Their Efficiency.
2. Sets, Relations, and Functions.
Set Operations.
Equivalence Relations.
Congruence.
Partial Ordering Relations.
Functions.
Mathematical Induction.
Applications.
3. Graphs.
Graphs and Their Representations.
Paths and Circuits.
Shortest Paths and Distance.
Coloring a Graph.
Directed Graphs and Multi Graphs.
4. Trees.
Properties of Trees.
Spanning Trees.
Depth-First Search.
Rooted Trees.
Binary Trees and Traversals.
Optimal Binary Trees and Binary Search Trees.
5. Matching.
Systems of Distinct Representatives.
Matching in Graphs.
A Matching Algorithm.
Applications of the Algorithm.
The Hungarian Method.
6. Network Flows.
Flows and Cuts.
A Flow Augmentation Algorithm.
The Max-Flow Min-Cut Theorem.
Flows and Matchings.
7. Counting Techniques.
Pascal's Triangle and the Binomial Theorem.
Three Fundamental Principles.
Permutations and Combinations.
Arrangements and Selections with Repetitions.
Probability.
*The Principle of Inclusion-Exclusion.
*Generating Permutations and r-Combinations.
8. Recurrence Relations and Generating Functions.
Recurrence Relations.
The Method of Iteration.
Linear Difference Equations with Constant Coefficients.
*Analyzing the Efficiency of Algorithms with Recurrence Relations.
Counting with Generating Functions.
The Algebra of Generating Functions.
9. Combinatorial Circuits and Finite State Machines.
Logical Gates.
Creating Combinatorial Circuits.
Karnaugh Maps.
Finite State Machines.
Appendix A: An Introduction to Logic and Proof.
Statements and Connectives.
Logical Equivalence.
Methods of Proof.
Appendix B: Matrices.
Appendix C: The Algorithms in this Book.
Bibliography.
Answers to Odd-Numbered Exercises.
Index.
*Optional Sections.
「Nielsen BookData」 より