FoundationsofComputerScience(英文版)

1星需积分: 34 117 浏览量更新于2023-03-16 评论 3 收藏 4.49MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

TABLE OF CONTENTS v

✦

✦ ✦

✦

Table of Contents

Preface ix

Chapter 1. Computer Science: The Mechanization of Abstraction 1

1.1. What This Book Is About 3

1.2. What This Chapter Is About 6

1.3. Data Models 6

1.4. The C Data Model 13

1.5. Algorithms and the Design of Programs 20

1.6. Some C Conventions Used Throughout the Book 22

1.7. Summary of Chapter 1 23

1.8. Bibliographic Notes for Chapter 1 24

Chapter 2. Iteration, Induction, and Recursion 25

2.1. What This Chapter Is About 27

2.2. Iteration 27

2.3. Inductive Proofs 34

2.4. Complete Induction 44

2.5. Proving Properties of Pro grams 52

2.6. Recursive Deﬁnitions 59

2.7. Recursive Functions 69

2.8. Merge Sort: A Recursive Sorting Algorithm 75

2.9. Proving Properties of Recursive Programs 8 4

2.10. Summary of Chapter 2 87

2.11. Bibliographic Notes for Chapter 2 88

Chapter 3. The Running Time of Programs 89

3.1. What This Chapter Is About 89

3.2. Choosing an Algorithm 90

3.3. Measuring Running Time 9 1

3.4. Big-Oh and Approximate Running Time 96

3.5. Simplifying Big-Oh E xpressions 101

3.6. Analyzing the Running Time of a Program 109

3.7. A Recursive Rule for Bounding Running Time 116

3.8. Analyzing P rograms with Function Calls 127

3.9. Analyzing Recur sive Functions 132

3.10. Analysis of Merge Sort 1 36

3.11. Solving Recurrence Relations 144

3.12. Summary of Chapter 3 154

3.13. Bibliographic Notes for Chapter 3 155

Chapter 4. Combinatorics and Probability 156

4.1. What This Chapter Is About 156

4.2. Counting Assignments 157

4.3. Counting Permutations 160

4.4. Ordered Selections 167

CHAPTER 1

✦

✦ ✦

✦

Computer Science:

The Mechanization

of Abstraction

Though it is a new ﬁeld, computer science already touches virtually every aspect

of human endeavor. Its impact on society is se e n in the proliferation of computers,

information systems, text editors, spreadsheets, and all of the wonderful application

programs that have been developed to make computers easier to use and people more

productive. An important part of the ﬁeld deals with how to make programming

easier and software more reliable. But fundamentally, computer science is a science

of abstraction — creating the right model for thinking about a problem and devising

Abstraction

the appropria te mechanizable techniques to solve it.

Every other science deals with the universe a s it is. The physicist’s job, for

example, is to understand how the world works, not to invent a world in which

physical laws would be simpler or more pleasant to follow. Computer scientists,

on the other hand, must create abstractions of real-world problems that can be

understood by computer users and, at the same time, that can be represented and

manipulated inside a computer.

Sometimes the process of abstraction is simple. For example, we can model the

behavior of the electronic circuits used to build computers quite well by an abstrac-

tion called “pr opo sitional logic.” The modeling of circuits by logical express ions is

not exact; it simpliﬁes, or abstracts away, many details — such as the time it takes

for electrons to ﬂow throug h circ uits and gates. Nevertheless, the propos itio nal

logic model is good enough to help us design computer circuits well. We shall have

much more to say about propositional logic in Chapter 12.

As another example, suppose we are faced with the problem of s cheduling ﬁnal

Exam

scheduling

examinations for courses. That is, we must assign course exams to time slots so

that two courses may have their exams scheduled in the same time slot only if there

is no student taking both. At ﬁrst, it may not be apparent how we should mo del

this problem. One approach is to draw a circle called a node for each co urse and

draw a line called an edge connecting two nodes if the c orresponding courses have

a student in common. Figure 1.1 suggests a possible picture for ﬁve courses; the

picture is called a course-conﬂict graph.

Given the course-conﬂict graph, we can solve the exam-scheduling problem by

repeatedly ﬁnding a nd removing “maximal independent sets” from the graph. An

剩余778页未读，继续阅读

wenmin92

2019-07-20

不值，官网提供免费下载

丽娃河畔

粉丝: 19
资源: 3

会员权益专享

Foundations of Computer Science(英文版)

评论1

会员权益专享

最新资源

Foundations of Computer Science(英文版)

评论1

foundations of computer science.pdf 深入了解计算机科学（C语言版）

Foundations of Computer Science C Edition

计算机科学基础：C版Foundations of Computer Science: C Edition

foundations of data science csdn

foundations of machine learning答案

foundations of programming languages pdf

foundations of mimo communication pdf

foundations of optimization 苏文藻

STOC/FOCS/ITCS/CCC/SODA/ICALP是啥

foundations of game engine development pdf

foundations of statistical natural language processing

有关国外学者库存管理研究现状参考文献原理

Major Minor Build Revision ----- ----- ----- -------- 5 1 19041 2673

系统测试参考文献有哪些

传输软件测试的参考文献

deep learning foundations and concepts pdf

deep learning: foundations and conceptspdf

neural network learning: theoretical foundations

我想学习自然语言处理，帮我推荐几本书籍

介绍机器人路径规划的外文文献

会员权益专享

最新资源