FoundationsofComputerScience(英文版)资源-CSDN文库

1星需积分: 34 141 浏览量 2017-12-10 22:02:29 上传评论 3 收藏 4.49MB PDF 举报

资源详情

资源评论

资源推荐

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

foundations.of.computer.science

Foundations of Computer Science C Edition

Foundations of Computer Science C Edition by Aho, Ullman

Concrete Mathematics: A Foundation for Computer Science (2nd Edition)

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

Logical Foundations of Computer Science 无水印原版pdf

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

Foundations Of 3D Computer Graphics (高清PDF扫描版)

计算机科学基础Foundations of Computer Science

计算机科学逻辑-自动定理证明的基础Logic For Computer Science - Foundations of Automatic Theorem Proving

Computer Science: An Overview Global 12th 计算机科学概论第12版 英文版

Mathematics for Computer Science 英文版 离散数学专用

算法之美英文版Algorithms to Live by:The Computer Science of Human Decisions

Mathematical Foundations of Computer

Foundations of Data Science

Foundations of Fluid Mechanics with Applications: Problem Solving Using mma

Probabilistic Foundations of Statistical Network Analysis

Foundations of Computer Vision

Foundations for Programming Languages

Theory of Computation Formal Languages, Automata, and Complexity (高清扫描版)

Foudations of Algorthms 5th

Variable-length Codes for Data Compression

The.Data.Science.Handbook.pdf

Vector Davinci官方帮助配置使用手册（AutoSAR）.pdf

c++入门，核心，提高讲义笔记

数字图像处理 冈萨雷斯 课后习题

离散数学及其应用 第八版 奇数编号练习答案.pdf

最新资源

Computer Science: An Overview Global 12th 计算机科学概论第12版英文版

Mathematics for Computer Science 英文版离散数学专用

数字图像处理冈萨雷斯课后习题

离散数学及其应用第八版奇数编号练习答案.pdf