### 基本信息

- 原书名：Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)
- 原出版社： Pearson Education,Inc.

### 内容简介

### 作译者

### 目录

1.1. algorithms

1.2. mathematical preliminaries

1.2.1. mathematical induction

1.2.2. numbers, powers, and logarithms

1.2.3. sums and products

1.2.4. integer functions and elementary number theory

1.2.5. permutations and factorials

1.2.6. binomial coefficients

1.2.7. harmonic numbers

1.2.8. fibonacci numbers

1.2.9. generating functions

1.2.10. analysis of an algorithm

*1.2.11. asymptotic representations

*1.2.11.1. the o-notation

*1.2.11.2. euler's summation formula

*1.2.11.3. some asymptotic calculations

1.3. mix 124

1.3.1. description of mix

1.3.2. the mix assembly language

### 前言

The following chapters are not meant to serve as an introtluction to computer programming; the reader is supposed to bave had some previous experience. The prerequisites are actuaDy very simple, but a beginner requires time and practice in order to understand the concept of a digital computer. The reader should possess :

a) Some idea of how a stored-program digital computer works; not necessarily the electronics, rather the manner in which instructions can be kept in the machine's memory and successively executed.

b) An ability to put the solutions to problems into such explicit terms that a computer can "uuderstand" them. (These machines have no common sense; they do exactly as they are told, no more and no less. This fact is the hardest concept to grasp when one first tries to use a computer.)

c) Some knowledge of the most elementary computer techniques, such as loop ing (performing a set of instructions repeatedly), the use of subroutines, and the use of indexed variables.

d) A little knowledge of common computer jargon- "memory," "registers," "bits," "floating point," "overflow," "software." Most words not defined in the text are given brief definitions in the index at the close of each volume.

These four prerequisites can perhaps be summed up into the single requirement that the reader should have already written and tested at least, say, four programs for at least one computer.

I have tried to write this set of books in such a way that it will fill several needs. In the first place, these books are reference works that summarize the knowledge that has been acquired in several important fields. In the second place, they can be used as textbooks for self-study or for college courses in the computer and information sciences. To meet both of these objectives, I have incorporated a large number of exercises into the text and have furnisbed answers for most of them. I have also made an effort to fill the pages with facts rather than with vague, general commentary.

This set of books is intended for people who will be more than just casually interested in computers, yet it is by no means only for the computer specialist.

Indeed, one of my main goals has been to make these programming techniques more accessible to the many people working in other fields who can make buitful use of computers, yet who cannot afford the time to locate all of the necessary information that is bmied in tecbnical journals.

We might call the subject of these books "nonnumerical analysis." Computers have traditionally been associated with the solution of numerical problems such as the calculation of the roots of an equation, numerical interpolation and integration, etc., but such topics are not treated here except in passing.

Numerical computer programming is an extremely interesting and rapidly expanding field, and many books have been written about it. Since the early 1960s, however, computers have been used even more often for problems in which numbers occur only by coincidence; the computer's decision-making capabilities are being used, rather than its ability to do arithmetic. We have some use for addition and subtraction in nonnumerical problems, but we rarely feel any need for multiplicakion and division. Of course, even a person who is primarily

concerned with numerical computer programming will benefit from a study of the nonnumerical techniques, for they are present in the background of numerical programs as well.

The results of research in nonnumerical analysis are scattered throughout numerous technical journals. My approach has been to try to distill this vast literature by studying the techniques that are most basic, in the sense that they can be applied to many types of programming situations. I have attempted to coordinate the ideas into more or less of a "theory," as well as to show how the theory applies to a wide variety of practical problems. Of course, "nonnumerical analysis" is a terribly negative name for this field of study; it is much better to have a positive, descriptive term that characterizes the subject. "Information processing" is too broad a designation for the material I am considering, and "programming techniques" is too narrow. Therefore I wish to propose analysis of algorithms as an appropriate name for the subject matter covered in these books. This name is meant to imply "the theory of the properties of particular computer algorithms."

The complete set of books, entitled The Art of Computer Programming, has the following general outline:

Volume 1. Fundamental Algorithms

Chapter 1. Basic Concepts

Chapter 2. information Structures

Volume 2. Seminumerical Algorithms

Chapter 3. Random Numbers