具体描述
This course is offered to undergraduates and is an elementary discrete mathematics course oriented towards applications in computer science and engineering. Topics covered include: formal logic notation, induction, sets and relations, permutations and combinations, counting principles, and discrete probability.
作者简介
Eric Lehman
Google Inc.
F Thomson Leighton
Department of Mathematics and CSAIL, MIT
Akamai Technologies
Albert R Meyer
Massachusets Institute of Technology
目录信息
1 Propositions 5
1.1 Compound Propositions 6
1.2 Propositional Logic in Computer Programs 10
1.3 Predicates and Quantifiers 11
1.4 Validity 19
1.5 Satisfiability 21
2 Patterns of Proof 23
2.1 The Axiomatic Method 23
2.2 Proof by Cases 26
2.3 Proving an Implication 27
2.4 Proving an “If and Only If” 30
2.5 Proof by Contradiction 32
2.6 Proofs about Sets 33
2.7 Good Proofs in Practice 40
3 Induction 43
3.1 The Well Ordering Principle 43
3.2 Ordinary Induction 46
3.3 Invariants 56
3.4 Strong Induction 64
3.5 Structural Induction 69
4 Number Theory 81
4.1 Divisibility 81
4.2 The Greatest Common Divisor 87
4.3 The Fundamental Theorem of Arithmetic 94
4.4 Alan Turing 96
4.5 Modular Arithmetic 100
4.6 Arithmetic with a Prime Modulus 103
4.7 Arithmetic with an Arbitrary Modulus 108
4.8 The RSA Algorithm 113
II Structures
5 Graph Theory 121
5.1 Definitions 121
5.2 Matching Problems 128
5.3 Coloring 143
5.4 Getting from A to B in a Graph 147
5.5 Connectivity 151
5.6 Around and Around We Go 156
5.7 Trees 162
5.8 Planar Graphs 170
6 Directed Graphs 189
6.1 Definitions 189
6.2 Tournament Graphs 192
6.3 Communication Networks 196
7 Relations and Partial Orders 213
7.1 Binary Relations 213
7.2 Relations and Cardinality 217
7.3 Relations on One Set 220
7.4 Equivalence Relations 222
7.5 Partial Orders 225
7.6 Posets and DAGs 226
7.7 Topological Sort 229
7.8 Parallel Task Scheduling 232
7.9 Dilworth’s Lemma 235
8 State Machines 237
III Counting
9 Sums and Asymptotics 243
9.1 The Value of an Annuity 244
9.2 Power Sums 250
9.3 Approximating Sums 252
9.4 Hanging Out Over the Edge 257
9.5 Double Trouble 269
9.6 Products 272
9.7 Asymptotic Notation 275
10 Recurrences 283
10.1 The Towers of Hanoi 284
10.2 Merge Sort 291
10.3 Linear Recurrences 294
10.4 Divide-and-Conquer Recurrences 302
10.5 A Feel for Recurrences 309
11 Cardinality Rules 313
11.1 Counting One Thing by Counting Another 313
11.2 Counting Sequences 314
11.3 The Generalized Product Rule 317
11.4 The Division Rule 321
11.5 Counting Subsets 324
11.6 Sequences with Repetitions 326
11.7 Counting Practice: Poker Hands 329
11.8 Inclusion-Exclusion 334
11.9 Combinatorial Proofs 339
11.10 The Pigeonhole Principle 342
11.11 A Magic Trick 346
12 Generating Functions 355
12.1 Definitions and Examples 355
12.2 Operations on Generating Functions 356
12.3 Evaluating Sums 361
12.4 Extracting Coefficients 363
12.5 Solving Linear Recurrences 370
12.6 Counting with Generating Functions 374
13 Infinite Sets 379
13.1 Injections, Surjections, and Bijections 379
13.2 Countable Sets 381
13.3 Power Sets Are Strictly Bigger 384
13.4 Infinities in Computer Science 386
IV Probability
14 Events and Probability Spaces 391
14.1 Let’s Make a Deal 391
14.2 The Four Step Method 392
14.3 Strange Dice 402
14.4 Set Theory and Probability 411
14.5 Infinite Probability Spaces 413
15 Conditional Probability 417
15.1 Definition 417
15.2 Using the Four-Step Method to Determine Conditional Probability 418
15.3 A Posteriori Probabilities 424
15.4 Conditional Identities 427
16 Independence 431
16.1 Definitions 431
16.2 Independence Is an Assumption 432
16.3 Mutual Independence 433
16.4 Pairwise Independence 435
16.5 The Birthday Paradox 438
17 Random Variables and Distributions 445
17.1 Definitions and Examples 445
17.2 Distribution Functions 450
17.3 Bernoulli Distributions 452
17.4 Uniform Distributions 453
17.5 Binomial Distributions 456
18 Expectation 467
18.1 Definitions and Examples 467
18.2 Expected Returns in Gambling Games 477
18.3 Expectations of Sums 483
18.4 Expectations of Products 490
18.5 Expectations of Quotients 492
19 Deviations 497
19.1 Variance 497
19.2 Markov’s Theorem 507
19.3 Chebyshev’s Theorem 513
19.4 Bounds for Sums of Random Variables 516
19.5 Mutually Independent Events 523
20 Random Walks 533
20.1 Unbiased Random Walks 533
20.2 Gambler’s Ruin 542
20.3 Walking in Circles 549
· · · · · · (收起)
读后感
原文发表于我的个人博客 http://notebook.xyli.me/MIT6-042/mathcs/ google books https://books.google.com/books?id=EdOQswEACAAJ 豆瓣读书主页 https://book.douban.com/subject/20472991/ 2004版（339页）http://www.boazbarak.org/cs121/LehmanLeighton.pdf 2012版（800页...
原文发表于我的个人博客 http://notebook.xyli.me/MIT6-042/mathcs/ google books https://books.google.com/books?id=EdOQswEACAAJ 豆瓣读书主页 https://book.douban.com/subject/20472991/ 2004版（339页）http://www.boazbarak.org/cs121/LehmanLeighton.pdf 2012版（800页...
发表与我的知乎专栏《算法主义》 [文章链接]) 在目前的本科教学中，一门门课程就像一个个孤岛，学生们淹死在从一个孤岛游向另一个孤岛的途中。每个老师守在各自的孤岛上。能把一个孤岛打理好的老师，已属难得，对于孤岛中将要淹死的学生，实在是无力顾及。 对于计算机专业的...
发表与我的知乎专栏《算法主义》 [文章链接]) 在目前的本科教学中，一门门课程就像一个个孤岛，学生们淹死在从一个孤岛游向另一个孤岛的途中。每个老师守在各自的孤岛上。能把一个孤岛打理好的老师，已属难得，对于孤岛中将要淹死的学生，实在是无力顾及。 对于计算机专业的...
发表与我的知乎专栏《算法主义》 [文章链接]) 在目前的本科教学中，一门门课程就像一个个孤岛，学生们淹死在从一个孤岛游向另一个孤岛的途中。每个老师守在各自的孤岛上。能把一个孤岛打理好的老师，已属难得，对于孤岛中将要淹死的学生，实在是无力顾及。 对于计算机专业的...
用户评价
我拿到这本《Theory of Distributions for Locally Compact Spaces》时，内心涌现出的是一种对知识的崇敬感。封面设计简洁而典雅，散发出一种学术研究的深邃气息，让我仿佛触摸到了一位严谨的数学家对真理的不懈追求。我立刻联想到，这本书很可能是在探索如何将分布论这一强大的分析工具，从熟悉的欧几里得空间拓展到更广泛的局部紧空间上。这其中必然涉及到对拓扑学和泛函分析的深刻理解。我猜想，作者一定花费了无数心血来定义在这些更抽象的空间上的“分布”，并研究它们的性质，比如收敛性、导数、积分等。这是否会为我们研究那些在非标准空间上出现的物理现象提供新的理论基础？例如，在凝聚态物理或宇宙学中，我们经常会遇到一些具有奇异性的物理量，而如果这本书能为我们提供一套更普适的数学工具来处理这些问题，那将是莫大的福音。我迫切地想要打开这本书，看看作者是如何一步步构建起这个理论体系，又是如何将抽象的数学概念，转化为理解世界的新钥匙。
这本书的 title 给我一种既有挑战性又充满吸引力的感觉。我一直认为，能够将抽象的拓扑概念与分析工具巧妙结合的数学著作，往往蕴含着深刻的洞察力。《Theory of Distributions for Locally Compact Spaces》这个标题，让我立刻联想到“局部紧性”这个拓扑学中的重要性质，以及“分布”这一在泛函分析和PDE领域不可或缺的概念。我好奇作者是如何将分布论的强大威力，应用于更广阔的局部紧空间上的。这是否意味着，我们可以构建出在这些空间上的更精细的函数逼近理论？或者，是否能够发展出一种新的“泛函导数”或“泛函积分”的概念，来适应局部紧空间的结构？我甚至想象，这本书是否会触及到一些在黎曼几何或微分几何中出现的具有挑战性的问题，例如在不光滑流形上的分布解的构造和性质。这本书的封面虽然简洁，却散发着一种知识的力量，让我迫不及待地想一窥其内容，看作者是如何在数学的海洋中，描绘出这样一片新的疆域。
我一直对那些能够连接不同数学领域的桥梁性著作很感兴趣，而《Theory of Distributions for Locally Compact Spaces》这个书名，恰恰勾起了我的这种好奇心。在我的认知里，“分布论”是处理广义函数和积分方程的强大工具，而“局部紧空间”则是在拓扑学中扮演着至关重要的角色，尤其是在泛函分析的许多重要定理中，比如Riesz表示定理。我好奇这本书是如何将这两者有机地结合在一起的。难道是通过定义在局部紧空间上的某种新的分布空间？或者是在局部紧空间上发展出更一般的分布的积分和导数理论？我甚至联想到，这或许能为研究某些在非欧几何空间或者更一般的拓扑流形上的偏微分方程提供新的视角和方法。比如，在研究流形上的拉普拉斯算子时，对分布解的理解至关重要，而如果作者能够为这种研究提供一套新的理论框架，那无疑是一项重大的贡献。这本书的封面传递给我一种沉静而专注的学术氛围，让我相信作者一定对这两个概念有着非常深入且独到的理解，并且花费了大量的心血来构建这套理论体系。
在我的学术视野中，数学的进步往往伴随着新概念的引入和已有概念的拓展。《Theory of Distributions for Locally Compact Spaces》这个书名，让我立刻联想到了一系列经典的数学领域。分布论，作为处理奇异性问题的有力武器，早已在偏微分方程、信号处理等领域大放异彩。而“局部紧空间”，则是在拓扑学和泛函分析中构建许多重要理论的基础。我的直觉告诉我，这本书很可能在探索如何将分布论的理论框架，推广到更一般的局部紧空间上，甚至可能引入一些全新的、基于局部紧空间特性的分布构造或性质。这是否意味着，我们可以用一种更统一、更普适的方式来理解和处理那些在传统欧几里得空间中难以刻画的奇异现象？比如，在研究黎曼流形上的算子时，如果能够将分布论的理论有效地迁移过去，那将会极大地方便我们对这些空间上的方程进行分析。我期待这本书能够提供一种全新的视角，帮助我拓展我的数学工具箱，并且可能为我在未来的研究中提供新的灵感和方向。
这本书的封面设计倒是颇具匠心，那种略显陈旧的米白色封纸，上面印着深邃的藏蓝色字体，透着一股学术研究的严谨和厚重感。我拿到它的时候，就好像捧着一本尘封已久的手稿，充满了探索未知的期待。我特别留意了扉页上作者的署名，虽然名字有些陌生，但联想到“局部紧空间”和“分布论”这两个关键词，我 immediately 联想到了一些前沿的数学理论，比如泛函分析、拓扑学，甚至是更深层次的偏微分方程理论。我想象着作者在书写这本书时，一定是在一个宁静的书房里，伴随着窗外的鸟鸣，反复推敲每一个公式，每一个证明。这本书或许不仅仅是对数学概念的梳理，更像是作者在思想的星空中划出的一道璀璨的轨迹，试图连接起那些看似遥远却又相互呼应的数学分支。我迫不及待地想要翻开它，看看这本书究竟是如何将抽象的数学语言，转化为对世界运行规律的深刻洞察。我猜想，这本书的开篇一定是以对“局部紧空间”这个概念的清晰界定开始，然后逐步深入到分布论的核心。这种由宏观到微观的讲解方式，往往能让读者更好地把握全局，理解细节。
有用的书 学算法前读一读
MIT线上公开课有这个课
“Introduce notation thoughtfully. Structure long proofs. Be wary of the “obvious”.”
MIT线上公开课有这个课
没想到这书的年龄比我还大几倍，写的很有意思，主要是离散和概率方面，以及给码农示范了一下使用数学工具的规范。但最近真的没心思看了只能在硬盘吃灰，想要却找不到电子版的可以找我要。
