基本信息

書名:離散數學

代碼：

作者:(美)RichardJohnsonbaugh(理查德?約翰遜鮑夫)

出版社：電子工業出版社

出版日期：2018-07-01

ISBN：9787121344671

字數：1398000

頁碼：747

版次：3

裝幀：平裝

開本：16開

商品重量：

編輯推薦

習題數量近4500個，例題數量超過650個。
給出大量的應用問題，特別是計算機領域中的應用問題。
獨立的問題求解部分展示另一種求解問題的方法，說明問題求解和證明的技巧。
強調證明細節的理解與證明的構造。

內容提要

本書從算法分析和問題求解的角度，全面繫統地介紹了離散數學的基礎概念及相關知識，並在其前一版的基礎上進行了修改與擴展。書中通過大量實例，深入淺出地講解了集合與邏輯，證明，函數、序列與關繫，算法，數論，計數方法與鴿巢原理，遞推關繫，圖論，樹，網絡模型，Boole代數與組合電路，自動機、文法和語言等與計算機科學密切相關的前沿課題，既著重於各部分內容之間的緊密聯繫，又深入探討了相關的概念、理論、算法和實際應用。本書內容敘述嚴謹、推演詳盡，各章配有相當數量的習題與書後的提示和答案，為讀者迅速掌握相關知識提供了有效的幫助。

目錄

1?Sets?and?Logic?1
1.1?Sets?2
1.2?Propositions?14
1.3?Conditional?Propositions?and?Logical?Equivalence?20
1.4?Arguments?and?Rules?of?Inference?31
1.5?Quantifiers?36
1.6?Nested?Quantifiers?49
Problem-Solving?Corner:?Quantifiers?57
Chapter?1?Notes?58
Chapter?1?Review?58
Chapter?1?Self-Test?60
Chapter?1?Computer?Exercises?60
2?Proofs?62
2.1?Mathematical?Systems,?Direct?Proofs,
and?Counterexamples?63
2.2?More?Methods?of?Proof?72
Problem-Solving?Corner:?Proving?Some?Properties
of?Real?Numbers?83
2.3?Resolution?Proofs??85
2.4?Mathematical?Induction?88
Problem-Solving?Corner:?Mathematical?Induction?100
2.5?Strong?Form?of?Induction?and?the?Well-Ordering?Property?102
Chapter?2?Notes?109
Chapter?2?Review?109
Chapter?2?Self-Test?109
Chapter?2?Computer?Exercises?110
3?Functions,?Sequences,?and?Relations?111
3.1?Functions?111
Problem-Solving?Corner:?Functions?128
3.2?Sequences?and?Strings?129
3.3?Relations?141
3.4?Equivalence?Relations?151
Problem-Solving?Corner:?Equivalence?Relations?158
3.5?Matrices?of?Relations?160
3.6?Relational?Databases??165
Chapter?3?Notes?170
Chapter?3?Review?170
Chapter?3?Self-Test?171
Chapter?3?Computer?Exercises?172
4?Algorithms?173
4.1?Introduction?173
4.2?Examples?of?Algorithms?177
4.3?Analysis?of?Algorithms?184
Problem-Solving?Corner:?Design?and?Analysis
of?an?Algorithm?202
4.4?Recursive?Algorithms?204
Chapter?4?Notes?211
Chapter?4?Review?211
Chapter?4?Self-Test?212
Chapter?4?Computer?Exercises?212
5?Introduction?to?Number?Theory?214
5.1?Divisors?214
5.2?Representations?of?Integers?and?Integer?Algorithms?224
5.3?The?Euclidean?Algorithm?238
Problem-Solving?Corner:?Making?Postage?249
5.4?The?RSA?Public-Key?Cryptosystem?250
Chapter?5?Notes?252
Chapter?5?Review?253
Chapter?5?Self-Test?253
Chapter?5?Computer?Exercises?254
6?Counting?Methods?and?the?Pigeonhole
Principle?255
6.1?Basic?Principles?255
Problem-Solving?Corner:?Counting?267
6.2?Permutations?and?Combinations?269
Problem-Solving?Corner:?Combinations?281
6.3?Generalized?Permutations?and?Combinations?283
6.4?Algorithms?for?Generating?Permutations?and
Combinations?289
6.5?Introduction?to?Discrete?Probability??297
6.6?Discrete?Probability?Theory??301
6.7?Binomial?Coefficients?and?Combinatorial?Identities?313
6.8?The?Pigeonhole?Principle?319
Chapter?6?Notes?324
Chapter?6?Review?324
Chapter?6?Self-Test?325
Chapter?6?Computer?Exercises?326
7?Recurrence?Relations?327
7.1?Introduction?327
7.2?Solving?Recurrence?Relations?338
Problem-Solving?Corner:?Recurrence?Relations?350
7.3?Applications?to?the?Analysis?of?Algorithms?353
7.4?The?Closest-Pair?Problem??365
Chapter?7?Notes?370
Chapter?7?Review?371
Chapter?7?Self-Test?371
Chapter?7?Computer?Exercises?372
8?Graph?Theory?373
8.1?Introduction?373
8.2?Paths?and?Cycles?384
Problem-Solving?Corner:?Graphs?395
8.3?Hamiltonian?Cycles?and?the?Traveling?Salesperson
Problem?396
8.4?A?Shortest-Path?Algorithm?405
8.5?Representations?of?Graphs?410
8.6?Isomorphisms?of?Graphs?415
8.7?Planar?Graphs?422
8.8?Instant?Insanity??429
Chapter?8?Notes?433
Chapter?8?Review?434
Chapter?8?Self-Test?435
Chapter?8?Computer?Exercises?436
9?Trees?438
9.1?Introduction?438
9.2?Terminology?and?Characterizations?of?Trees?445
Problem-Solving?Corner:?Trees?450
9.3?Spanning?Trees?452
9.4?Minimal?Spanning?Trees?459
9.5?Binary?Trees?465
9.6?Tree?Traversals?471
9.7?Decision?Trees?and?the?Minimum?Time?for?Sorting?477
9.8?Isomorphisms?of?Trees?483
9.9?Game?Trees??493
Chapter?9?Notes?502
Chapter?9?Review?502
Chapter?9?Self-Test?503
Chapter?9?Computer?Exercises?505
10?Network?Models?506
10.1?Introduction?506
10.2?A?Mamal?Flow?Algorithm?511
10.3?The?Max?Flow,?Min?Cut?Theorem?519
10.4?Matching?523
Problem-Solving?Corner:?Matching?528
Chapter?10?Notes?529
Chapter?10?Review?530
Chapter?10?Self-Test?530
Chapter?10?Computer?Exercises?531
11?Boolean?Algebras?and?Combinatorial
Circuits?532
11.1?Combinatorial?Circuits?532
11.2?Properties?of?Combinatorial?Circuits?539
11.3?Boolean?Algebras?544
Problem-Solving?Corner:?Boolean?Algebras?549
11.4?Boolean?Functions?and?Synthesis?of?Circuits?551
11.5?Applications?556
Chapter?11?Notes?564
……

作者介紹

Richard Johnsonbaugh是美國芝加哥DePaul大學的計算機科學、通信與信息繫統的Emeritus教授，並在DePaul大學的從事了20年教學工作，之前曾任莫爾豪斯學院和芝加哥州立大學的數學繫教師和繫主任一職。Johnsonbaugh教授在耶魯大學獲得數學學士學位、碩士學位，並獲得俄勒岡大學的數學博士學位以及伊利諾伊大學的計算機碩士學位。Johnsonbaugh教授近期的研究領域包括模式識別、程序設計語言、算法和離散數學，他也是這些領域眾多書籍和文章的作者或合著者。Johnsonbaugh教授的幾本專著已被譯成各種語言出版，他也是美國數學協會的成員。
Richard Johnsonbaugh是美國芝加哥DePaul大學的計算機科學、通信與信息繫統的Emeritus教授，並在DePaul大學的從事了20年教學工作，之前曾任莫爾豪斯學院和芝加哥州立大學的數學繫教師和繫主任一職。Johnsonbaugh教授在耶魯大學獲得數學學士學位、碩士學位，並獲得俄勒岡大學的數學博士學位以及伊利諾伊大學的計算機碩士學位。Johnsonbaugh教授近期的研究領域包括模式識別、程序設計語言、算法和離散數學，他也是這些領域眾多書籍和文章的作者或合著者。Johnsonbaugh教授的幾本專著已被譯成各種語言出版，他也是美國數學協會的成員。

序言