计算机科学第12版：全面理解与实践

计算机基础

5星 · 超过95%的资源需积分: 50 67 浏览量更新于2024-07-20 9 收藏 31.6MB PDF 举报

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

30元优惠券

资源详情

资源推荐

0.1 The Role of Algorithms

Figure 0.1 An algorithm for a magic trick

Step 1.

Step 2.

Step 3

Step 4.

Step 5.

Step 6.

Effect: The performer places some cards from a normal deck of playing cards face

down on a table and mixes them thoroughly while spreading them out on the table.

Then, as the audience requests either red or black cards, the performer turns over cards

of the requested color.

Secret and Patter:

From a normal deck of cards, select ten red cards and ten black cards. Deal these cards

face up in two piles on the table according to color.

Announce that you have selected some red cards and some black cards.

Pick up the red cards. Under the pretense of aligning them into a small deck, hold them

face down in your left hand and, with the thumb and first finger of your right hand, pull

back on each end of the deck so that each card is given a slightly backward curve. Then

place the deck of red cards face down on the table as you say, “Here are the red cards

in this stack.”

Pick up the black cards. In a manner similar to that in step 3, give these cards a slight

forward curve. Then return these cards to the table in a face-down deck as you say,

“And here are the black cards in this stack.”

Immediately after returning the black cards to the table, use both hands to mix the red

and black cards (still face down) as you spread them out on the tabletop. Explain that

you are thoroughly mixing the cards.

6.1. Ask the audience to request either a red or a black card.

6.2. If the color requested is red and there is a face-down card with a concave

appearance, turn over such a card while saying, “Here is a red card.”

6.3. If the color requested is black and there is a face-down card with a convex

appearance, turn over such a card while saying, “Here is a black card.”

6.4. Otherwise, state that there are no more cards of the requested color and turn over

the remaining cards to prove your claim.

As long as there are face-down cards on the table, repeatedly

execute the following steps:

Figure 0.2 The Euclidean algorithm for finding the greatest common divisor of two

positiveintegers

Description: This algorithm assumes that its input consists of two positive integers and

proceeds to compute the greatest common divisor of these two values.

Procedure:

Step 1. Assign M and N the value of the larger and smaller of the two input values, respectively.

Step 2. Divide M by N, and call the remainder R.

Step 3. If R is not 0, then assign M the value of N, assign N the value of R, and return to step 2;

otherwise, the greatest common divisor is the value currently assigned to N.

M00_BROO1160_12_SE_C00.indd 15 01/08/14 11:18 AM

Chapter 0 Introduction

understanding why the algorithm works.) In a sense, the intelligence required to

solve the problem at hand is encoded in the algorithm.

Capturing and conveying intelligence (or at least intelligent behavior) by

means of algorithms allows us to build machines that perform useful tasks.

Consequently, the level of intelligence displayed by machines is limited by

the intelligence that can be conveyed through algorithms. We can construct a

machine to perform a task only if an algorithm exists for performing that task. In

turn, if no algorithm exists for solving a problem, then the solution of that prob-

lem lies beyond the capabilities of machines.

Identifying the limitations of algorithmic capabilities solidified as a subject

in mathematics in the 1930s with the publication of Kurt Gödel’s incomplete-

ness theorem. This theorem essentially states that in any mathematical theory

encompassing our traditional arithmetic system, there are statements whose

truth or falseness cannot be established by algorithmic means. In short, any com-

plete study of our arithmetic system lies beyond the capabilities of algorithmic

activities. This realization shook the foundations of mathematics, and the study

of algorithmic capabilities that ensued was the beginning of the field known today

as computer science. Indeed, it is the study of algorithms that forms the core of

computer science.

0.2 The History of Computing

Today’s computers have an extensive genealogy. One of the earlier computing

devices was the abacus. History tells us that it probably had its roots in ancient

China and was used in the early Greek and Roman civilizations. The machine

is quite simple, consisting of beads strung on rods that are in turn mounted in

a rectangular frame (Figure0.3). As the beads are moved back and forth on the

rods, their positions represent stored values. It is in the positions of the beads that

this “computer” represents and stores data. For control of an algorithm’s execu-

tion, the machine relies on the human operator. Thus the abacus alone is merely

a data storage system; it must be combined with a human to create a complete

computational machine.

In the time period after the Middle Ages and before the Modern Era, the

quest for more sophisticated computing machines was seeded. A few inventors

began to experiment with the technology of gears. Among these were Blaise

Pascal (1623–1662) of France, Gottfried Wilhelm Leibniz (1646–1716) of Germany,

and Charles Babbage (1792–1871) of England. These machines represented data

through gear positioning, with data being entered mechanically by establishing

initial gear positions. Output from Pascal’s and Leibniz’s machines was achieved

by observing the final gear positions. Babbage, on the other hand, envisioned

machines that would print results of computations on paper so that the possibility

of transcription errors would be eliminated.

As for the ability to follow an algorithm, we can see a progression of flex-

ibility in these machines. Pascal’s machine was built to perform only addition.

Consequently, the appropriate sequence of steps was embedded into the struc-

ture of the machine itself. In a similar manner, Leibniz’s machine had its algo-

rithms firmly embedded in its architecture, although the operator could select

from a variety of arithmetic operations it offered. Babbage’s Difference Engine

M00_BROO1160_12_SE_C00.indd 16 01/08/14 11:18 AM

0.2 The History of Computing

(ofwhich only a demonstration model was constructed) could be modified to

perform a variety of calculations, but his Analytical Engine (never funded for con-

struction) was designed to read instructions in the form of holes in paper cards.

Thus Babbage’s Analytical Engine was programmable. In fact, Augusta AdaByron

(AdaLovelace), who published a paper in which she demonstrated how Babbage’s

Analytical Engine could be programmed to perform various computations, is

often identified today as the world’s first programmer.

The idea of communicating an algorithm via holes in paper was not origi-

nated by Babbage. He got the idea from Joseph Jacquard (1752–1834), who, in

1801, had developed a weaving loom in which the steps to be performed dur-

ing the weaving process were determined by patterns of holes in large thick

cards made of wood (or cardboard). In this manner, the algorithm followed by

the loom could be changed easily to produce different woven designs. Another

beneficiary of Jacquard’s idea was Herman Hollerith (1860–1929), who applied

the concept of representing information as holes in paper cards to speed up the

tabulation process in the 1890 U.S. census. (It was this work by Hollerith that

led to the creation of IBM.) Such cards ultimately came to be known as punched

cards and survived as a popular means of communicating with computers well

into the 1970s.

Nineteenth-century technology was unable to produce the complex gear-

driven machines of Pascal, Leibniz, and Babbage cost-effectively. But with the

advances in electronics in the early 1900s, this barrier was overcome. Examples

of this progress include the electromechanical machine of George Stibitz,

completed in 1940 at Bell Laboratories, and the Mark I, completed in 1944 at

Harvard University by Howard Aiken and a group of IBM engineers. These

machines made heavy use of electronically controlled mechanical relays. In

this sense they were obsolete almost as soon as they were built, because other

researchers were applying the technology of vacuum tubes to construct totally

Figure 0.3 Chinese wooden abacus (Pink Badger/Fotolia)

M00_BROO1160_12_SE_C00.indd 17 01/08/14 11:18 AM

Chapter 0 Introduction

electronic computers. The first of these vacuum tube machines was apparently

the Atanasoff-Berry machine, constructed during the period from 1937 to 1941

at Iowa State College (now Iowa State University) by John Atanasoff and his

assistant, Clifford Berry. Another was a machine called Colossus, built under

thedirection of Tommy Flowers in England to decode German messages dur-

ingthe latter part of World War II. (Actually, as many as ten of these machines

were apparently built, but military secrecy and issues of national security kept

their existence from becoming part of the “computer family tree.”) Other, more

flexible machines, such as the ENIAC (electronic numerical integrator and calcu-

lator) developed by John Mauchly and J. Presper Eckert at the Moore School of

Electrical Engineering, University of Pennsylvania, soon followed (Figure0.4).

From that point on, the history of computing machines has been closely

linked to advancing technology, including the invention of transistors (for which

physicists William Shockley, John Bardeen, and Walter Brattain were awarded a

Nobel Prize) and the subsequent development of complete circuits constructed

as single units, called integrated circuits (for which Jack Kilby also won a Nobel

Prize in physics). With these developments, the room-sized machines of the 1940s

were reduced over the decades to the size of single cabinets. At the same time,

the processing power of computing machines began to double every two years (a

trend that has continued to this day). As work on integrated circuitry progressed,

many of the components within a computer became readily available on the open

market as integrated circuits encased in toy-sized blocks of plastic called chips.

A major step toward popularizing computing was the development of desk-

top computers. The origins of these machines can be traced to the computer

hobbyists who built homemade computers from combinations of chips. It was

within this “underground” of hobby activity that Steve Jobs and Stephen Wozniak

Figure 0.4 Three women operating the ENIAC’s (Electronic Numerical Integrator And Computer)

main control panel while the machine was at the Moore School. The machine was later moved to

the U.S. Army’s Ballistics Research Laboratory. (Courtesy U.S. Army.)

M00_BROO1160_12_SE_C00.indd 18 01/08/14 11:18 AM

0.2 The History of Computing

built a commercially viable home computer and, in 1976, established Apple Com-

puter, Inc. (now Apple Inc.) to manufacture and market their products. Other

companies that marketed similar products were Commodore, Heathkit, and Radio

Shack. Although these products were popular among computer hobbyists, they

were not widely accepted by the business community, which continued to look

to the well-established IBM and its large mainframe computers for the majority

of its computing needs.

In 1981, IBM introduced its first desktop computer, called the personal

computer, or PC, whose underlying software was developed by a newly formed

company known as Microsoft. The PC was an instant success and legitimized

Babbage’s Difference Engine

The machines designed by Charles Babbage were truly the forerunners of modern

computer design. If technology had been able to produce his machines in an eco-

nomically feasible manner and if the data processing demands of commerce and

government had been on the scale of today’s requirements, Babbage’s ideas could

have led to a computer revolution in the 1800s. As it was, only a demonstration model

of his Difference Engine was constructed in his lifetime. This machine determined

numerical values by computing “successive differences.” We can gain an insight to

this technique by considering the problem of computing the squares of the integers.

We begin with the knowledge that the square of 0 is 0, the square of 1 is 1, the

square of 2 is 4, and the square of 3 is 9. With this, we can determine the square of

4 in the following manner (see the following diagram). We first compute the differ-

ences of the squares we already know:

- 0

= 1, 2

- 1

= 3,

and

- 2

= 5.

Then we compute the differences of these results:

3 - 1 = 2,

and

5 - 3 = 2.

Note

that these differences are both 2. Assuming that this consistency continues (mathe-

matics can show that it does), we conclude that the difference between the value

- 3

)

and the value

- 2

)

must also be 2. Hence

- 3

)

must be 2 greater

than

- 2

- 3

= 7

and thus

= 3

+ 7 = 16.

Now that we know the

square of 4, we could continue our procedure to compute the square of 5 based on

the values of

, 2

, 3

and

(Although a more in−depth discussion of successive

differences is beyond the scope of our current study, students of calculus may wish to

observe that the preceding example is based on the fact that the derivative of

y = x

is a straight line with a slope of 2.)

First

difference

Second

difference

M00_BROO1160_12_SE_C00.indd 19 01/08/14 11:18 AM

剩余640页未读，继续阅读

qq_17723077

粉丝: 3
资源: 1

计算机科学第12版：全面理解与实践

布鲁克希尔-计算机科学概论（中英文版）

计算机科学概论(12版)(英文)(带目录)

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

Computer.Science.An.Overview.12th.Global.Edition

计算机科学概论(Computer Science: An Overview)

Computer Science: an overview 9th

Computer Science: an Overview

Computer Science 计算机科学经典著作.pdf

computer science on overview

Packt.Arduino.Computer.Vision.Programming.2015

Computer.Network.Simulation.Using.NS2.epub

Overview of the Discipline of Computer Science

The shool-its unique role as a mental health resource. The critical issues-an overview

最新资源

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