Mathematics For Computer Science 2010.pdf

(7665 KB) Pobierz
Mathematics
for
Computer Science
Eric Lehman
F Thomson Leighton
Albert R Meyer
September,2010
Mathematics for Computer Science
revised Wednesday 8
th
September, 2010, 00:40
Eric Lehman
Google Inc.
F Thomson Leighton
Department of Mathematics and CSAIL, MIT
Akamai Technologies
Albert R Meyer
Massachusets Institute of Technology
Copyright © 2010, Eric Lehman, F Tom Leighton,
Albert R Meyer
. All rights reserved.
Contents
I
Proofs
1
Propositions
5
1.1
1.2
1.3
1.4
1.5
Compound Propositions
6
Propositional Logic in Computer Programs
Predicates and Quantifiers
11
Validity
19
Satisfiability
21
The Axiomatic Method
23
Proof by Cases
26
Proving an Implication
27
Proving an “If and Only If”
30
Proof by Contradiction
32
Proofs about Sets
33
Good
Proofs in Practice
40
The Well Ordering Principle
Ordinary Induction
46
Invariants
56
Strong Induction
64
Structural Induction
69
43
10
2
Patterns of Proof
23
2.1
2.2
2.3
2.4
2.5
2.6
2.7
3
Induction
43
3.1
3.2
3.3
3.4
3.5
4
Number Theory
81
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
Divisibility
81
The Greatest Common Divisor
87
The Fundamental Theorem of Arithmetic
94
Alan Turing
96
Modular Arithmetic
100
Arithmetic with a Prime Modulus
103
Arithmetic with an Arbitrary Modulus
108
The RSA Algorithm
113
iv
Contents
II Structures
5
Graph Theory
121
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
Definitions
121
Matching Problems
128
Coloring
143
Getting from
A
to
B
in a Graph
147
Connectivity
151
Around and Around We Go
156
Trees
162
Planar Graphs
170
Definitions
189
Tournament Graphs
192
Communication Networks
6
Directed Graphs
189
6.1
6.2
6.3
196
7
Relations and Partial Orders
213
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
Binary Relations
213
Relations and Cardinality
217
Relations on One Set
220
Equivalence Relations
222
Partial Orders
225
Posets and DAGs
226
Topological Sort
229
Parallel Task Scheduling
232
Dilworth’s Lemma
235
8
State Machines
237
III Counting
9
Sums and Asymptotics
243
9.1
9.2
9.3
9.4
9.5
9.6
The Value of an Annuity
244
Power Sums
250
Approximating Sums
252
Hanging Out Over the Edge
257
Double Trouble
269
Products
272

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin