mathematics for computer science.pdf

发布时间：2022-06-19 发布人：admin 分类：说明书资料大小：10.17M 资料格式：pdf 举报版权申诉

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第1页.png

第1页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第2页.png

第2页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第3页.png

第3页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第4页.png

第4页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第5页.png

第5页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第6页.png

第6页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第7页.png

第7页 / 共987页

53ef203c-6cea-44e4-bc47-999a768b2463.pdf-第8页.png

第8页 / 共987页

文本预览

“mcs” — 2017/3/6 — 12:54 — page i — #1 Mathematics for Computer Science revised Monday 6th March, 2017, 12:54 Eric Lehman Google Inc. F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies Albert R Meyer Department of Electrical Engineering and Computer Science and the Computer Science and AI Laboratory, Massachussetts Institute of Technology 2016, Eric Lehman, F Tom Leighton, Albert R Meyer. This work is available under the terms of the Creative Commons Attribution-ShareAlike 3.0 license.

“mcs” — 2017/3/6 — 12:54 — page ii — #2

“mcs” — 2017/3/6 — 12:54 — page iii — #3 Contents I Proofs Introduction 3 0.1 References 4 1 What is a Proof? 5 9 8 5 Propositions Predicates The Axiomatic Method 1.1 1.2 1.3 1.4 Our Axioms Proving an Implication 1.5 Proving an “If and Only If” 1.6 Proof by Cases 1.7 1.8 Proof by Contradiction 1.9 Good Proofs in Practice 1.10 References 15 19 8 11 13 16 17 2 The Well Ordering Principle 29 29 Template for Well Ordering Proofs Factoring into Primes 32 2.1 Well Ordering Proofs 2.2 2.3 2.4 Well Ordered Sets 3 Logical Formulas 45 33 30 46 Propositions from Propositions Propositional Logic in Computer Programs Equivalence and Validity The Algebra of Propositions The SAT Problem 60 Predicate Formulas 61 3.1 3.2 3.3 3.4 3.5 3.6 3.7 References 55 52 66 50 4 Mathematical Data Types 91 Sets 91 Sequences Functions 4.1 96 4.2 97 4.3 4.4 Binary Relations 4.5 Finite Cardinality 99 103

“mcs” — 2017/3/6 — 12:54 — page iv — #4 iv Contents 123 Strong Induction Strong Induction vs. Induction vs. Well Ordering 132 139 5 6 Induction 123 5.1 Ordinary Induction 5.2 5.3 State Machines 159 6.1 6.2 6.3 6.4 States and Transitions The Invariant Principle Partial Correctness & Termination The Stable Marriage Problem 173 159 160 168 7 Recursive Data Types 203 207 Strings of Matched Brackets 213 Induction in Computer Science 7.1 Recursive Deﬁnitions and Structural Induction 7.2 7.3 Recursive Functions on Nonnegative Integers 7.4 Arithmetic Expressions 7.5 Inﬁnite Sets 245 8.1 8.2 8.3 8.4 Does All This Really Work? Inﬁnite Cardinality The Halting Problem 255 The Logic of Sets 218 246 259 262 8 203 211 II Structures Introduction 287 9 Number Theory 289 306 289 301 294 The Greatest Common Divisor Prime Mysteries The Fundamental Theorem of Arithmetic 9.1 Divisibility 9.2 9.3 9.4 9.5 Alan Turing 9.6 Modular Arithmetic 9.7 Remainder Arithmetic 9.8 9.9 Multiplicative Inverses and Cancelling 9.10 Euler’s Theorem 321 9.11 RSA Public Key Encryption 9.12 What has SAT got to do with it? 312 Turing’s Code (Version 2.0) 315 326 310 328 303 317

“mcs” — 2017/3/6 — 12:54 — page v — #5 v Contents 9.13 References 329 10 Directed graphs & Partial Orders 367 376 373 369 370 10.1 Vertex Degrees 10.2 Walks and Paths 10.3 Adjacency Matrices 10.4 Walk Relations 10.5 Directed Acyclic Graphs & Scheduling 10.6 Partial Orders 10.7 Representing Partial Orders by Set Containment 390 10.8 Linear Orders 390 10.9 Product Orders 10.10 Equivalence Relations 10.11 Summary of Relational Properties 377 391 385 393 11 Communication Networks 425 425 11.1 Routing 11.2 Routing Measures 11.3 Network Designs 12 Simple Graphs 445 426 429 445 447 449 12.1 Vertex Adjacency and Degrees 12.2 Sexual Demographics in America 12.3 Some Common Graphs 12.4 Isomorphism 451 12.5 Bipartite Graphs & Matchings 12.6 Coloring 458 12.7 Simple Walks 12.8 Connectivity 12.9 Forests & Trees 12.10 References 463 465 470 453 478 13 Planar Graphs 517 528 517 517 13.1 Drawing Graphs in the Plane 13.2 Deﬁnitions of Planar Graphs 13.3 Euler’s Formula 13.4 Bounding the Number of Edges in a Planar Graph 13.5 Returning to K5 and K3;3 13.6 Coloring Planar Graphs 13.7 Classifying Polyhedra 13.8 Another Characterization for Planar Graphs 530 533 531 536 389 529

“mcs” — 2017/3/6 — 12:54 — page vi — #6 vi Contents III Counting Introduction 545 14 Sums and Asymptotics 547 548 560 14.1 The Value of an Annuity 554 14.2 Sums of Powers 14.3 Approximating Sums 556 14.4 Hanging Out Over the Edge 14.5 Products 566 14.6 Double Trouble 569 14.7 Asymptotic Notation 15 Cardinality Rules 597 572 597 598 605 608 15.1 Counting One Thing by Counting Another 15.2 Counting Sequences 15.3 The Generalized Product Rule 15.4 The Division Rule 15.5 Counting Subsets 15.6 Sequences with Repetitions 15.7 Counting Practice: Poker Hands 15.8 The Pigeonhole Principle 618 627 15.9 Inclusion-Exclusion 15.10 Combinatorial Proofs 633 15.11 References 613 637 601 610 16 Generating Functions 675 675 16.1 Inﬁnite Series 16.2 Counting with Generating Functions 16.3 Partial Fractions 16.4 Solving Linear Recurrences 16.5 Formal Power Series 691 16.6 References 686 683 694 677 IV Probability Introduction 713 17 Events and Probability Spaces 715 17.1 Let’s Make a Deal 715

“mcs” — 2017/3/6 — 12:54 — page vii — #7 vii Contents 17.2 The Four Step Method 17.3 Strange Dice 17.4 The Birthday Principle 17.5 Set Theory and Probability 17.6 References 725 738 716 732 734 18 Conditional Probability 747 747 748 18.1 Monty Hall Confusion 18.2 Deﬁnition and Notation 18.3 The Four-Step Method for Conditional Probability 18.4 Why Tree Diagrams Work 18.5 The Law of Total Probability 18.6 Simpson’s Paradox 18.7 Independence 764 18.8 Mutual Independence 18.9 Probability versus Conﬁdence 752 762 766 770 760 19 Random Variables 799 750 799 19.1 Random Variable Examples 19.2 Independence 19.3 Distribution Functions 19.4 Great Expectations 811 19.5 Linearity of Expectation 801 822 20 Deviation from the Mean 853 802 20.1 Markov’s Theorem 853 20.2 Chebyshev’s Theorem 856 20.3 Properties of Variance 860 20.4 Estimation by Random Sampling 20.5 Conﬁdence in an Estimation 20.6 Sums of Random Variables 20.7 Really Great Expectations 869 871 880 866 21 Random Walks 905 21.1 Gambler’s Ruin 21.2 Random Walks on Graphs 905 915 V Recurrences Introduction 933 22 Recurrences 935

“mcs” — 2017/3/6 — 12:54 — page viii — #8 viii Contents 935 22.1 The Towers of Hanoi 22.2 Merge Sort 22.3 Linear Recurrences 22.4 Divide-and-Conquer Recurrences 22.5 A Feel for Recurrences 938 942 956 949 Bibliography 963 Glossary of Symbols 967 Index 971

分享到：

赞收藏

资料库

mathematics for computer science.pdf

相关推荐

人工智能

热门标签

最新资料