Stanford公开课《Algorithm: Design and Analysis》推荐的一本有关计算机科学的数学基础类读物。本书为英文版本，如果阅读起来有困难，我个人建议大家阅读中文版《离散数学及其应用》。mcs-ftl-20109/8-0:40-page#3ContentsProofs1 Propositions 51. 1 Compound propositions 61. 2 Propositional logic in Computer programs 101.3 Predicates and Quantifiers 111. 4 Valid191.5 Satisfiability 212 Patterns of proof 232.1 The Axiomatic Method 232.2 Proof by cases 262.3 Proving an Implication 2724 Proving an‘ If and Only If”302.5 Proof by Contradiction 322.6 Proofs about sets 332.7 Good Proofs in Practic3 Induction 433.1 The Well Ordering Principle 433.2 Ordinary Induction 463.3 Invariants 563.4 Strong Induction 643.5 Structural Induction 694 Number Theory 814.1 Divisibility 814.2 The greatest Common divisor 874.3 The Fundamental Theorem of Arithmetic 944.4 Alan Turing 964.5 Modular arithmetic 1004.6 Arithmetic with a Prime modulus 1034.7 Arithmetic with an arbitrary Modulus 1084.8 The rsa algorithm 113mcs-ftl”-2010/980:40— page Iv-井4Contentsu Structures5 Graph Theory 1215. 1 Definitions 1215.2 Matching Problems 1285.3 Coloring 1435.4 Getting from a to b in a graph1475.5 Connectivity 1515.6 Around and Around We go 1565. 7 Trees 1625.8 Planar Graphs 1706 Directed Graphs 1896.1 Definitions 1896.2 Tournament Graphs 1926.3 Communication Nctworks 1967 Relations and Partial Orders 2137.1 Binary relations 2137.2 Relations and Cardinality 217.3 Relaon One set 2207.4 Equivalence Relations 2227.5 Partial Orders 2257.6 Posets and DAGs 2267.7 Topological Sort 2297. 8 Parallel task scheduling 2327. 9 Dilworth's Lemma 2358 State machines 237I Counting9 Sums and Asymptotics 2439. 1 The value of an annuity 2449.2 Power Sums 2509.3 Approximating Sums 2529.4 Hanging out Over the edge 2579.5 Double Trouble 2699.6 Products 272mct-20109/8-0:40— page v-#5Contents9.7 Asymptotic Notation 27510 Recurrences 28310.1 The Towers of hanoi 2840.2 Merge Sort 29110.3 Linear Recurrences 29410.4 Divide-and-Conquer Recurrences 30210.5 A Feel for Recurrences 30911 Cardinality Rules 31311. 1 Counting One Thing by Counting Another 31311.2 Counting Sequences 31411. 3 The generalized product rule 31711. 4 The division rule 32111. 5 Counting subsets 32411.6 Sequences with Repetitions 32611.7 Counting Practice: Poker hands 32911. 8 Inclusion-Exclusion 3 3411.9 Combinatorial Proofs 33911.10 The Pigeonhole principle 34211.11 A Magic Trick 34612 Generating Functions 3.5.512.1 Definitions and Examples 35512.2 Operations on Generating Functions 35612.3 Evaluating Sums 36112.4 Extracting Coefficients 36312.5 Solving linear recurrences 37012.6 Counting with Generating Functions 37413 nfinite sets 37913. 1 Injections, Surjections, and Bijections 37913.2 Countable sets 38113.3 Power Sets Are Strictly Bigger 3843.4 Infinities in Computer Science 386ly Probability14 Events and probability spaces 3914.1 Let's make a deal 39114.2 The Four Step method 39220109/80:40age vI#6Contents14.3 Strange Dice 40214.4 Set Theory and probability 41114.5 Infinite Probability s41315 Conditional Probability 41715.1 Definition 41715.2 Using the Four-Step method to determine Conditional probability 41815.3 A Posteriori Probabilities 42415.4 Conditional Identities 42716 Independence 43116.1 Definitions 43116.2 Independence Is an Assumption 43216. 3 Mutual Independence 43316.4 Pairwise Independence 43516.5 The Birthday Paradox 43817 Random variables and distributions 44517. 1 Definitions and Examples 44517.2 Distribution functi45017.3 Bernoulli Distributions 45217 4 Uniform Distributions 45317.5 Binomial Distributions 45618 Expectation 46718.1 Definitions and Examples 46718.2 Expected Returns in Gambling Games 4778.3 Expectations of Sums 48318.4 Expectations of Products 49018.5 Expectations of Quotients 49219 Deviations 49719.1 Variance 49719.2 Markov's Theorem 50719.3 Chebyshevs Theorem 51319.4 Bounds for Sums of Random Variables 51619.5 Mutually Independent events 52320 Random Walks 53320.1 Unbiased Random Walks 53320.2 Gamblers ruin 54220.3 Walking in Circles 549mcs-f2010/9/80:40age7I Proofsmcs-f2010/9/80:40age8mct-20109/8-0:40—page3-IntroductionThis text explains how to use mathematical models and methods to analyze problems that arise in computer science. The notion of a proof plays a central role inthis workSimply put, a proof is a method of establishing truth. Like beauty, truth sometimes depends on the eye of the beholder, and it should not be surprising that whatconstitutes a proof differs among fields. For example, in the judicial system, legaltruth is decided by a jury based on the allowable evidence presented at trial. In thebusiness world, authoritative truth is specified by a trusted person or organizationor maybe just your boss. In fields such as physics and biology, scientific truthisconfirmed by experiment. In statistics, probable truth is established by statisticalanalysis of sample datPhilosophical proof involves careful exposition and persuasion typically basedon a series of small, plausible arguments. The best example begins with "Cogitoergo sum, a Latin sentence that translates as"I think, therefore I am. It comesfrom the beginning of a 17th century essay by the mathematician/philosopher, ReneDescartes, and it is one of the most famous quotes in the world: do a web searchon the phrase and you will be flooded with hitsDeducing your existence from the fact that you're thinking about your existenceis a pretty cool and persuasive-sounding idea. However, with just a few more linesof argument in this vein, Descartes goes on to conclude that there is an infinitelbeneficent God. Whether or not you believe in a beneficent God, you'll probablyagree that any very short proof of God's existence is bound to be far-fetched. SoActually, only scientific falsehood can be demonstrated by an experiment--when the experimentfails to behave as predicted But no amount of experiment can confirm that the next experiment wontfail. for this reasof truth but rather of theories thatrateland anticipated future, experimentsmcs-ft”-2010(9/8—0:40—page4—#10PartI Proofseven in masterful hands, this approach is not reliableMathematics has its own specific notion of"proofDefinition. A mathematical proof of a proposition is a chain of logical deductionsleading to the proposition from a base set of axiomsThe three key ideas in this definition are highlighted: proposition, logical deduction, and axiom. These three ideas are explained in the following chapters,beginning with propositions in Chapter 1. We will then provide lots of examples ofproofs and even some examples of false proofs"(that is, arguments that look likea proof but that contain missteps or deductions that aren t so logical when examined closely ). False proofs are often even more important as examples than correctproofs, because they are uniquely helpful with honing your skills at making sureeach step of a proof follows logically from prior stepsCreating a good proof is a lot like creating a beautiful work of art In factmathematicians often refer to really good proofs as being"elegant or"beautifulAs with any endeavor, it will probably take a little practice before your fellowstudents use such praise when referring to your proofs, but to get you started inthe right direction, we will provide templates for the most useful proof techniquesin Chapters 2 and 3. We then apply these techniques in Chapter 4 to establishsome important facts about numbers: facts that form the underpinning of one of theworld's most widely-used cryptosystems