Mathematics-for-Computer-science.pdf

(13082 KB) Pobierz
“mcs” — 2017/6/5 — 19:42 — page i — #1
Mathematics for Computer Science
revised Monday 5
th
June, 2017, 19:42
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
2017, 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/6/5 — 19:42 — page ii — #2
“mcs” — 2017/6/5 — 19:42 — page iii — #3
Contents
I
Proofs
Introduction
3
0.1
References
4
1
What is a Proof?
5
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
Propositions
5
Predicates
8
The Axiomatic Method
8
Our Axioms
9
Proving an Implication
11
Proving an “If and Only If”
13
Proof by Cases
15
Proof by Contradiction
16
Good
Proofs in Practice
17
References
19
Well Ordering Proofs
29
Template for WOP Proofs
30
Factoring into Primes
32
Well Ordered Sets
33
Propositions from Propositions
48
Propositional Logic in Computer Programs
Equivalence and Validity
54
The Algebra of Propositions
57
The SAT Problem
62
Predicate Formulas
63
References
68
Sets
97
Sequences
102
Functions
103
Binary Relations
105
Finite Cardinality
109
2
The Well Ordering Principle
29
2.1
2.2
2.3
2.4
3
Logical Formulas
47
3.1
3.2
3.3
3.4
3.5
3.6
3.7
52
4
Mathematical Data Types
97
4.1
4.2
4.3
4.4
4.5
“mcs” — 2017/6/5 — 19:42 — page iv — #4
iv
Contents
5
Induction
131
5.1
5.2
5.3
Ordinary Induction
131
Strong Induction
140
Strong Induction vs. Induction vs. Well Ordering
States and Transitions
167
The Invariant Principle
168
Partial Correctness & Termination
176
The Stable Marriage Problem
181
Recursive Definitions and Structural Induction
211
Strings of Matched Brackets
215
Recursive Functions on Nonnegative Integers
219
Arithmetic Expressions
221
Games as a Recursive Data Type
226
Induction in Computer Science
230
Infinite Cardinality
258
The Halting Problem
267
The Logic of Sets
271
Does All This Really Work?
147
6
State Machines
167
6.1
6.2
6.3
6.4
7
Recursive Data Types
211
7.1
7.2
7.3
7.4
7.5
7.6
8
Infinite Sets
257
8.1
8.2
8.3
8.4
275
II Structures
Introduction
299
9
Number Theory
301
9.1
9.2
9.3
9.4
9.5
9.6
9.7
9.8
9.9
9.10
9.11
Divisibility
301
The Greatest Common Divisor
306
Prime Mysteries
313
The Fundamental Theorem of Arithmetic
315
Alan Turing
318
Modular Arithmetic
322
Remainder Arithmetic
324
Turing’s Code (Version 2.0)
327
Multiplicative Inverses and Cancelling
329
Euler’s Theorem
333
RSA Public Key Encryption
338
“mcs” — 2017/6/5 — 19:42 — page v — #5
v
Contents
9.12 What has SAT got to do with it?
9.13 References
341
340
10 Directed graphs & Partial Orders
381
10.1 Vertex Degrees
383
10.2 Walks and Paths
384
10.3 Adjacency Matrices
387
10.4 Walk Relations
390
10.5 Directed Acyclic Graphs & Scheduling
391
10.6 Partial Orders
399
10.7 Representing Partial Orders by Set Containment
10.8 Linear Orders
404
10.9 Product Orders
404
10.10 Equivalence Relations
405
10.11 Summary of Relational Properties
407
10.12 References
409
403
11 Communication Networks
441
11.1 Routing
441
11.2 Routing Measures
442
11.3 Network Designs
445
12 Simple Graphs
461
12.1 Vertex Adjacency and Degrees
461
12.2 Sexual Demographics in America
463
12.3 Some Common Graphs
465
12.4 Isomorphism
466
12.5 Bipartite Graphs & Matchings
469
12.6 Coloring
474
12.7 Walks in Simple Graphs
478
12.8 Connectivity
480
12.9 Special Walks and Tours
483
12.10
k-connected
Graphs
485
12.11 Forests & Trees
487
12.12 References
494
13 Planar Graphs
533
13.1
13.2
13.3
13.4
13.5
Drawing Graphs in the Plane
533
Definitions of Planar Graphs
533
Euler’s Formula
544
Bounding the Number of Edges in a Planar Graph
Returning to
K
5
and
K
3;3
546
545

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin