链接：https://pan.baidu.com/s/1DSdLJhTBuVmNNdULBgAgfw 

提取码：5qbd

Computers and Programs

Almost everyone has used a computer at one time or another. Perhaps you have played computer games or

used a computer to write a paper or balance your checkbook. Computers are used to predict the weather,

design airplanes, make movies, run businesses, perform financial transactions, and control factories.

Have you ever stopped to wonder what exactly a computer is? How can one device perform so many

different tasks? These basic questions are the starting point for learning about computers and computer

programming.

1.1 The Universal Machine

A modern computer might be defined as “a machine that stores and manipulates information under the con￾trol of a changeable program.” There are two key elements to this definition. The first is that computers

are devices for manipulating information. This means that we can put information into a computer, and it

can transform the information into new, useful forms, and then output or display the information for our

interpretation.

Computers are not the only machines that manipulate information. When you use a simple calculator to

add up a column of numbers, you are entering information (the numbers) and the calculator is processing the

information to compute a running sum which is then displayed. Another simple example is a gas pump. As

you fill your tank, the pump uses certain inputs: the current price of gas per gallon and signals from a sensor

that reads the rate of gas flowing into your car. The pump transforms this input into information about how

much gas you took and how much money you owe.

We would not consider either the calculator or the gas pump as full-fledged computers, although modern

versions of these devices may actually contain embedded computers. They are different from computers in

that they are built to perform a single, specific task. This is where the second part of our definition comes into

the picture: computers operate under the control of a changeable program. What exactly does this mean?

A computer program is a detailed, step-by-step set of instructions telling a computer exactly what to do.

If we change the program, then the computer performs a different sequence of actions, and hence, performs

a different task. It is this flexibility that allows your PC to be at one moment a word processor, at the next

moment a financial planner, and later on, an arcade game. The machine stays the same, but the program

controlling the machine changes.

Every computer is just a machine for executing (carrying out) programs. There are many different kinds

of computers. You might be familiar with Macintoshes and PCs, but there are literally thousands of other

kinds of computers both real and theoretical. One of the remarkable discoveries of computer science is

the realization that all of these different computers have the same power; with suitable programming, each

computer can basically do all the things that any other computer can do. In this sense, the PC that you might

have sitting on your desk is really a universal machine. It can do anything you want it to, provided you can

describe the task to be accomplished in sufficient detail. Now that’s a powerful machine!

1

2 CHAPTER 1. COMPUTERS AND PROGRAMS

1.2 Program Power

You have already learned an important lesson of computing: Software (programs) rules the hardware (the

physical machine). It is the software that determines what any computer can do. Without programs, computers would just be expensive paperweights. The process of creating software is called programming, and that

is the main focus of this book.

Computer programming is a challenging activity. Good programming requires an ability to see the big

picture while paying attention to minute detail. Not everyone has the talent to become a first-class programmer, just as not everyone has the skills to be a professional athlete. However, virtually anyone can learn how

to program computers. With some patience and effort on your part, this book will help you to become a

programmer.

There are lots of good reasons to learn programming. Programming is a fundamental part of computer

science and is, therefore, important to anyone interested in becoming a computer professional. But others can

also benefit from the experience. Computers have become a commonplace tool in our society. Understanding

the strengths and limitations of this tool requires an understanding of programming. Non-programmers often

feel they are slaves of their computers. Programmers, however, are truly the masters. If you want to become

a more intelligent user of computers, then this book is for you.

Programming can also be loads of fun. It is an intellectually engaging activity that allows people to

express themselves through useful and sometimes remarkably beautiful creations. Believe it or not, many

people actually write computer programs as a hobby. Programming also develops valuable problem-solving

skills, especially the ability to analyze complex systems by reducing them to interactions of understandable

subsystems.

As you probably know, programmers are in great demand. More than a few liberal arts majors have turned

a couple computer programming classes into a lucrative career option. Computers are so commonplace in the

business world today that the ability to understand and program computers might just give you the edge over

your competition, regardless of your occupation.

1.3 What is Computer Science?

You might be surprised to learn that computer science is not the study of computers. A famous computer

scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to

astronomy. The computer is an important tool in computer science, but it is not itself the object of study.

Since a computer can carry out any process that we can describe, the real question is What processes can we

describe? Put another way, the fundamental question of computer science is simply What can be computed?

Computer scientists use numerous techniques of investigation to answer this question. The three main ones

are design, analysis, and experimentation.

One way to demonstrate that a particular problem can be solved is to actually design a solution. That is,

we develop a step-by-step process for achieving the desired result. Computer scientists call this an algorithm.

That’s a fancy word that basically means “recipe.” The design of algorithms is one of the most important

facets of computer science. In this book you will find techniques for designing and implementing algorithms.

One weakness of design is that it can only answer the question What is computable? in the positive. If I

can devise an algorithm, then the problem is solvable. However, failing to find an algorithm does not mean

that a problem is unsolvable. It may mean that I’m just not smart enough, or I haven’t hit upon the right idea

yet. This is where analysis comes in.

Analysis is the process of examining algorithms and problems mathematically. Computer scientists have

shown that some seemingly simple problems are not solvable by any algorithm. Other problems are intractable. The algorithms that solve these problems take too long or require too much memory to be of

practical value. Analysis of algorithms is an important part of computer science; throughout this book we

will touch on some of the fundamental principles. Chapter 13 has examples of unsolvable and intractable

problems.

Some problems are too complex or ill-defined to lend themselves to analysis. In such cases, computer

scientists rely on experimentation; they actually implement systems and then study the resulting behavior.

Even when theoretical analysis is done, experimentation is often needed in order to verify and refine the