دانلود کتاب Mathematics for Computer Science

فهرست مطالب :

Contents I Proofs Introduction 3 0.1 References 4 1 What is a Proof? 5 1.1 Propositions 5 1.2 Predicates 8 1.3 The Axiomatic Method 8 1.4 Our Axioms 9 1.5 Proving an Implication 11 1.6 Proving an “If and Only If” 13 1.7 Proof by Cases 15 1.8 Proof by Contradiction 16 1.9 Good Proofs in Practice 17 1.10 References 19 2 The Well Ordering Principle 29 2.1 Well Ordering Proofs 29 2.2 Template for Well Ordering Proofs 30 2.3 Factoring into Primes 32 2.4 Well Ordered Sets 33 3 Logical Formulas 45 3.1 Propositions from Propositions 46 3.2 Propositional Logic in Computer Programs 50 3.3 Equivalence and Validity 52 3.4 The Algebra of Propositions 55 3.5 The SAT Problem 60 3.6 Predicate Formulas 61 3.7 References 66 4 Mathematical Data Types 91 4.1 Sets 91 4.2 Sequences 96 4.3 Functions 97 4.4 Binary Relations 99 4.5 Finite Cardinality 103 5 Induction 123 5.1 Ordinary Induction 123 5.2 Strong Induction 132 5.3 Strong Induction vs. Induction vs. Well Ordering 139 6 State Machines 159 6.1 States and Transitions 159 6.2 The Invariant Principle 160 6.3 Partial Correctness & Termination 168 6.4 The Stable Marriage Problem 173 7 Recursive Data Types 203 7.1 Recursive Definitions and Structural Induction 203 7.2 Strings of Matched Brackets 207 7.3 Recursive Functions on Nonnegative Integers 211 7.4 Arithmetic Expressions 213 7.5 Induction in Computer Science 218 8 Infinite Sets 245 8.1 Infinite Cardinality 246 8.2 The Halting Problem 255 8.3 The Logic of Sets 259 8.4 Does All This Really Work? 262 II Structures Introduction 287 9 Number Theory 289 9.1 Divisibility 289 9.2 The Greatest Common Divisor 294 9.3 Prime Mysteries 301 9.4 The Fundamental Theorem of Arithmetic 303 9.5 Alan Turing 306 9.6 Modular Arithmetic 310 9.7 Remainder Arithmetic 312 9.8 Turing’s Code (Version 2.0) 315 9.9 Multiplicative Inverses and Cancelling 317 9.10 Euler’s Theorem 321 9.11 RSA Public Key Encryption 326 9.12 What has SAT got to do with it? 328 9.13 References 329 10 Directed graphs & Partial Orders 367 10.1 Vertex Degrees 369 10.2 Walks and Paths 370 10.3 Adjacency Matrices 373 10.4 Walk Relations 376 10.5 Directed Acyclic Graphs & Scheduling 377 10.6 Partial Orders 385 10.7 Representing Partial Orders by Set Containment 389 10.8 Linear Orders 390 10.9 Product Orders 390 10.10 Equivalence Relations 391 10.11 Summary of Relational Properties 393 11 Communication Networks 425 11.1 Routing 425 11.2 Routing Measures 426 11.3 Network Designs 429 12 Simple Graphs 445 12.1 Vertex Adjacency and Degrees 445 12.2 Sexual Demographics in America 447 12.3 Some Common Graphs 449 12.4 Isomorphism 451 12.5 Bipartite Graphs & Matchings 453 12.6 Coloring 458 12.7 Simple Walks 463 12.8 Connectivity 465 12.9 Forests & Trees 470 12.10 References 478 13 Planar Graphs 517 13.1 Drawing Graphs in the Plane 517 13.2 Definitions of Planar Graphs 517 13.3 Euler’s Formula 528 13.4 Bounding the Number of Edges in a Planar Graph 529 13.5 Returning to K5 and K3;3 530 13.6 Coloring Planar Graphs 531 13.7 Classifying Polyhedra 533 13.8 Another Characterization for Planar Graphs 536 III Counting Introduction 545 14 Sums and Asymptotics 547 14.1 The Value of an Annuity 548 14.2 Sums of Powers 554 14.3 Approximating Sums 556 14.4 Hanging Out Over the Edge 560 14.5 Products 566 14.6 Double Trouble 569 14.7 Asymptotic Notation 572 15 Cardinality Rules 597 15.1 Counting One Thing by Counting Another 597 15.2 Counting Sequences 598 15.3 The Generalized Product Rule 601 15.4 The Division Rule 605 15.5 Counting Subsets 608 15.6 Sequences with Repetitions 610 15.7 Counting Practice: Poker Hands 613 15.8 The Pigeonhole Principle 618 15.9 Inclusion-Exclusion 627 15.10 Combinatorial Proofs 633 15.11 References 637 16 Generating Functions 675 16.1 Infinite Series 675 16.2 Counting with Generating Functions 677 16.3 Partial Fractions 683 16.4 Solving Linear Recurrences 686 16.5 Formal Power Series 691 16.6 References 694 IV Probability Introduction 713 17 Events and Probability Spaces 715 17.1 Let’s Make a Deal 715 17.2 The Four Step Method 716 17.3 Strange Dice 725 17.4 The Birthday Principle 732 17.5 Set Theory and Probability 734 17.6 References 738 18 Conditional Probability 747 18.1 Monty Hall Confusion 747 18.2 Definition and Notation 748 18.3 The Four-Step Method for Conditional Probability 750 18.4 Why Tree Diagrams Work 752 18.5 The Law of Total Probability 760 18.6 Simpson’s Paradox 762 18.7 Independence 764 18.8 Mutual Independence 766 18.9 Probability versus Confidence 770 19 Random Variables 799 19.1 Random Variable Examples 799 19.2 Independence 801 19.3 Distribution Functions 802 19.4 Great Expectations 811 19.5 Linearity of Expectation 822 20 Deviation from the Mean 853 20.1 Markov’s Theorem 853 20.2 Chebyshev’s Theorem 856 20.3 Properties of Variance 860 20.4 Estimation by Random Sampling 866 20.5 Confidence in an Estimation 869 20.6 Sums of Random Variables 871 20.7 Really Great Expectations 880 21 Random Walks 905 21.1 Gambler’s Ruin 905 21.2 Random Walks on Graphs 915 V Recurrences Introduction 933 22 Recurrences 935 22.1 The Towers of Hanoi 935 22.2 Merge Sort 938 22.3 Linear Recurrences 942 22.4 Divide-and-Conquer Recurrences 949 22.5 A Feel for Recurrences 956 Bibliography 963 Glossary of Symbols 967 Index 971