没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义计算机科学的数学（英文）

计算机科学的数学（英文）

需积分: 13 25 下载量 73 浏览量 2017-06-15 14:01:26 上传评论收藏 12.78MB PDF 举报

温馨提示

试读

1006页

这是谷歌工程师 Eric Lehman，与 MIT 两位教授 Thomson Leighton 和 Albert Meyer 合著的教科书。如同书名，为计算机专业的学生提供数学基础知识

资源推荐

资源详情

资源评论

“mcs” — 2017/6/5 — 19:42 — page i — #1

Mathematics for Computer Science

revised Monday 5

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 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 WOP Proofs 30

2.3 Factoring into Primes 32

2.4 Well Ordered Sets 33

3 Logical Formulas 47

3.1 Propositions from Propositions 48

3.2 Propositional Logic in Computer Programs 52

3.3 Equivalence and Validity 54

3.4 The Algebra of Propositions 57

3.5 The SAT Problem 62

3.6 Predicate Formulas 63

3.7 References 68

4 Mathematical Data Types 97

4.1 Sets 97

4.2 Sequences 102

4.3 Functions 103

4.4 Binary Relations 105

4.5 Finite Cardinality 109

“mcs” — 2017/6/5 — 19:42 — page iv — #4

Contentsiv

5 Induction 131

5.1 Ordinary Induction 131

5.2 Strong Induction 140

5.3 Strong Induction vs. Induction vs. Well Ordering 147

6 State Machines 167

6.1 States and Transitions 167

6.2 The Invariant Principle 168

6.3 Partial Correctness & Termination 176

6.4 The Stable Marriage Problem 181

7 Recursive Data Types 211

7.1 Recursive Deﬁnitions and Structural Induction 211

7.2 Strings of Matched Brackets 215

7.3 Recursive Functions on Nonnegative Integers 219

7.4 Arithmetic Expressions 221

7.5 Games as a Recursive Data Type 226

7.6 Induction in Computer Science 230

8 Inﬁnite Sets 257

8.1 Inﬁnite Cardinality 258

8.2 The Halting Problem 267

8.3 The Logic of Sets 271

8.4 Does All This Really Work? 275

II Structures

Introduction 299

9 Number Theory 301

9.1 Divisibility 301

9.2 The Greatest Common Divisor 306

9.3 Prime Mysteries 313

9.4 The Fundamental Theorem of Arithmetic 315

9.5 Alan Turing 318

9.6 Modular Arithmetic 322

9.7 Remainder Arithmetic 324

9.8 Turing’s Code (Version 2.0) 327

9.9 Multiplicative Inverses and Cancelling 329

9.10 Euler’s Theorem 333

9.11 RSA Public Key Encryption 338

“mcs” — 2017/6/5 — 19:42 — page v — #5

Contentsv

9.12 What has SAT got to do with it? 340

9.13 References 341

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 403

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

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 Drawing Graphs in the Plane 533

13.2 Deﬁnitions of Planar Graphs 533

13.3 Euler’s Formula 544

13.4 Bounding the Number of Edges in a Planar Graph 545

13.5 Returning to K

and K

3;3

546

剩余1005页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

baidu_39183194

粉丝: 0
资源: 1

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

计算机科学的数学（英文）

计算机科学与数学

具体数学——计算机科学基础

具体数学-计算机科学基础

mcs计算机科学的数学

具体数学_计算机科学基础_第2版_中英文高清

具体数学 计算机科学基础（第2版） 中+英

离散数学：计算机科学基础（英文电子书）

像计算机科学家一样思考Python(第二版，中英文)

具体数学 英文版

《数学——计算机科学基础》

具体数学计算机科学基础

课程1：计算机科学中的数学思考

具体数学 计算机科学基础（第2版）

具体数学 计算机科学基础(第2版)

《具体数学》电子书籍英文版

2023南京大学计算机科学与技术845考研公共课和专业课资料：数学一、英语一、政治、数据结构、计算机网络、计算机系统基础、操作系

不插电的计算机科学-教材

计算机科学与技术专业2018级研究生课程表【模板】.docx

计算机科学和数学的关系.pdf

计算机科学与数学(郭百宁).pdf

计算机科学数学（中文）

组合数学在计算机科学中的应用

具体数学：计算机科学基础（英文版）

离散数学练习答案

离散数学及应用

麻省理工学院公开课：计算机科学及编程导论(公开课的中英文字幕）

《简明数学词典》作者: 沈以淡 主编 出版时间: 2003年

最新资源

具体数学计算机科学基础（第2版）中+英

具体数学英文版

具体数学计算机科学基础（第2版）

具体数学计算机科学基础(第2版)

《简明数学词典》作者: 沈以淡主编出版时间: 2003年