文件名称:
《The Art of Computer Programming》 TAOCP 高清 PDF
开发工具:
文件大小: 162mb
下载次数: 0
上传时间: 2019-07-07
详细说明：经典数据结构与算法书，历经几十年仍然经典！虽使用古老的汇编语言，但是历久常新。好书！
啥？！看完了？大犇！！！去自己创业吧。Volume 1/Fundamental Algorithms
THE ART OF
COMPUTER PROGRAMMING
Reading, Massachusetts. Menlo Park, California. London. Don Mills, Ontario
This book is in the
ADDISON-WESLEY SERIES IN
COMPUTER SCIENCE AND INFORMATION PROCESSING
RICHARD S. VARGA and MICHAEL A. HARRISoN Editors
Second Printing 1969
coPYRIGHT 1968 BY ADDISON-WESLEY PUBLISHING COMPANY, INC. ALL RIGHTS
RESERVED. NO PART OF THIS PUBLICATION MAY BE REPRODUCED, STORED IN A RE-
TRIEVAL SYSTEM, OR TRANSMITTED, IN ANY FORM OR BY ANY MEANS, ELECTRONIC,
MECHANICAL, PHOTOCOPYING, RECORDING, OR OTHERWISE, WITHOUT THE PRIOR WRIT-
TEN PERMISSION OF THE PUBLISHER. PRINTED IN THE UNITED STATES OF AMERICA
PUBLISHED SIMULTANEOUSLY IN CANADA. LIBRARY OF CONGRESS CATALOG CARD NO.
67-26020.
PREFACE
Here is your book the one your thousands of letters have asked us to
publish It has taken us years to do, checking and rechecking countless
1 recipes to bring you only the best, only the interesting, only the perfect.
low we can say, without a shadow of a doubt, that every single one of them,
if you follow the directions to the letter, will work for you exactly as well
as it did for us, even if you have never cooked before.
-Mc Call's Cookbook (1963)
The process of preparing programs for a digital computer is especially attractive
because it not only can be economically and scientifically rewarding, it can also
be an aesthetic experience much like composing poetry or music. This book
is the first volume of a seven-volume set of books that has been designed to train
the reader in the various skills which go into a programmer, s craft
The following chapters are not meant to serve as an introduction to com-
puter programming; the reader is supposed to have had some previous ex-
perience. The prerequisites are actually very simple, but a beginner requires
time and practice before he properly understands the concept of a digital com
puter. 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. Previous exposure to machine
language will be helpful
b)An ability to put the solutions to problems into such explicit terms that a
computer can"understand"them. (These machines have no common sense
they have not yet learned to"think, and 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
looping (performing a set of instructions repeatedly), the use of subroutines,
and the use of index registers
d) a little knowledge of common computer jargon, e.g. memory, " registers,
bits,'“ Hoating point,”“ overflow.” 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 require
ment 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 books which summarize the
knowledge which has been acquired in several important fields. They can also
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 furnished 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 casual
interested in computers, yet it is by no means only for the computer specialist
Indeed, one of the main goals has been to make these programming techniques
more accessible to the many people working in other fields who can make fruitful
use of computers, yet who cannot afford the time to locate all of the necessary
information which is buried in the technical journals
The subject of these books might be called "nonnumerical analysis
Although 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. topics like this are not treated here except
in passing. Numerical computer programming is a very interesting and rapidly
expanding field, and many books have been written about it. In recent years
however, a good deal of interesting work has been done using computers for
essentially nonnumerical problems, such as sorting, translating languages,
solving mathematical problems in higher algebra and combinatorial analysis
theorem proving, the development of software(programs to facilitate the
writing of other programs), and the simulation of various processes from every-
day life. Numbers occur in such problems only by coincidence, and the com-
puter's decision-making capabilities are being used rather than its ability to do
arithmetic. In nonnumerical problems, we have some use for addition and
subtraction, but we rarely feel any need for multiplication and division. Note
however, that even a person who is primarily concerned with numerical com
puter programming will benefit from a study of the nonnumerical techniques
for these are present in the background of numerical programs as well.
The results of the recent research in nonnumerical analysis are scattered
throughout numerous technical journals, and at the time of writing they are
in a somewhat chaotic and disorganized state. The approach used here has
been to study those techniques which are most basic, in the sense that they can
be applied to many types of programming situations; I have attempted to
coordinate these into more or less of a theory and to bring the reader up to
the present frontiers of knowledge in these areas. Applications of these basic
techniques to the design of software programs are also given
Of course nonnumerical analysisis a terribly negative name for this
field of study, and it would be much better to have a positive, descriptive term
which 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 appro.
priate name for the subject matter covered in these books; as explained more
fully in the books themselves, this name is meant to imply the theory of the
properties of particular computer algorithms.
It is generally very difficult to keep up with a field that is economicall
profitable, and so it is only natural to expect that many of the techniques
described here will eventually be superseded by better ones. It has, of course,
been impossible for me to keep"two years ahead of the state of the art, and
the frontiers mentioned above will certainly change. I have mixed emotions in
this respect, since i certainly hope this set of books will stimulate further re
search, yet not so much that the books themselves become obsolete!
Actually the majority of the algorithms presented here have already been
in use for five years or more by quite a number of different people, and so in
a sense these methods have matured to the point where they are now reasonably
well understood and are presumably in their best form. It is no longer premature
therefore to put them into a textbook and to expect students to learn about
them
The complete seven-volume 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 8. Seminumerical algorithns
Chapter 3. Random Numbers
Chapter 4. Arithmetic
Volume 3. Sorting and Searching
Chapter 5. Sorting Techniques
Chapter 6. Searching Techniques
Volume 4. Combinatorial algorithms
Chapter 7. Combinatorial Searching
Chapter 8. Recursion
Volume 5. Syntactical algorithms
Chapter 9. Lexical Scanning
Chapter 10. Parsing Techniques
Volume 6. Theory of Languages
Chapter 11. Mathematical Linguistics
Volume 7. Compilers
Chapter 12. Programming Language Translation
I started out in 1962 to write a single book with this sequence of chapters, but
I soon found that it was more important to treat the subjects in depth rather
than to skim over them lightly, The resulting length of the text has meant
that each chapter by itself contains enough material for a one-semester college
course, so it has become sensible to publish the series in separate volumes instead
of making it into one or two huge tomes. (It may seem strange to have only one
or two chapters in an entire book, but i have decided to retain this chapter num-
bering to facilitate cross-references A shorter version of volumes 1 through 5
will soon be published, intended specifically to serve as a more general textbook
for undergraduate computer courses. Its contents will be a" of the
material in these books, with the more specialized information omitted; I
intend to use the same chapter numbering in this abridged edition.
The present volunie may be considered as the "intersection"of the entire
set of books. in the sense that it contains the basic material which is used in all
the other volumes. Volumes 2 through 7, on the other hand, may be read in-
dependently of each other, except perhaps for some strong connections between
Volumes 5 and 7. Volume 1 is not only a reference book to be used in connection
with Volumes 2 through 7; it may also be used in college courses or for self-
study as a text on the subject of data structures(emphasizing the material of
Chapter 2), or as a text on the subject of discrete mathematics(emphasizing the
material of Sections 1.1, 1. 2, 1.3.3, and 2.3.4), or as a text on the subject of
machine-language programming(emphasizing the material of Sections 1.3 and
The point of view I have adopted while writing these twelve chapters
differs from that taken in many contemporary books about computer program
ming in that i am not trying to teach the reader how to use somebody else's
subroutines; I am concerned rather with teaching the reader how to write better
subroutines himself!
a few words are in order about the mathematical content of this set of
books, The material has been organized so that persons with no more than a
knowledge of high school algebra may read it skimming briefly over the more
mathematical portions; yet a reader who is mathematically inclined will learn
about many interesting mathematical techniques related to"discrete mathe-
matics. "This dual level of presentation has been achieved in part by assigning
ratings"to each of the exercises so that those which are primarily mathematical
are marked specifically as such, and also by arranging most sections so that the
main mathematical results are stated before their proofs. The proofs are either
left as exercises (with answers to be found in a separate section) or they are
given at the end of a section.
A reader who is interested primarily in programming rather than in the
associated mathematics may stop reading each section as soon as the mathe
matics becomes recognizably difficult. On the other hand, a mathematically
oriented reader will find a wealth of interesting material collected here. Much
of the published mathematics about computer programming has been very
faulty, and one of the purposes of this book is to instruct readers in proper
mathematical approaches to this subject. Since i myself profess to be a mathe
matician, it is my duty to maintain mathematical integrity as well as i can
A knowledge of elementary calculus will suffice for most of the mathematics
in these books, since most of the other theory that is needed is developed herein;
there are some isolated places, however, in which deeper theorems of complex
variable theory probability theory, number theory, etc. are quoted when
appropriate
Even though computers are widely regarded as belonging to the domain of
"applied mathematics, "there are "pure mathematicians"such as myself who
have found many intriguing connections between computers and abstract.
mathematics. From this standpoint, parts of these books may be thought of
as"a pure mathematicians view of computers, y
To a layman, the electronic computer has come to symbolize the importance
of mathematics in today's world, yet few professional mathematicians are now
closely acquainted with the machines. One reason for this surprising(and
unfortunate)situation is that computers seem to have made some thingstoo
easy, ' in the sense that people who no longer have to do so many things with
pencil and paper never discover the mathematical simplifications which would
aid the work. Some mathematicians occasionally resent the intrusion of com
puters, not because they are afraid they will lose their jobs to automation, but
because they fear there will perhaps be less necessity to give birth to invention
On the other hand, there are obvious relations between computers and mathe-
matics in the fields of numerical analysis, number theory, and statistics
I wish to show that the connection between computers and mathematics is
far deeper and more intimate than these traditional relationships would imply
The construction of a computer program from a set of basic instructions is very
similar to the construction of a mathematical proof from a set of axioms. further
more, pure mathematical problems historically have always developed from
the study of practical problems arising in another field, and the advent of
computers has brought a number of these with it. Some of the problems in-
vestigated in these books which are essentially of this type are(a)the study of
stochastic properties of particular algorithms: determination of how well they
may be expected to perform;(b)the construction of optimal algorithms, e.g
for sorting or for evaluating polynomials; and (c) the theory of languages
Besides the interesting application of mathematical tools to programming
problems, there are also interesting applications of computers to the exploration
of mathematical conjectures, e. g. in combinatorial analysis and algebra; and
in many of these cases there is considerable interplay between programming and
classical mathematics. Attempts at mechanization of mathematics are also
very important, since they lead to a greater understanding of concepts we
thought we knew(until we had to explain them to a computer). I believe the
connections between computers and pure mathematics which have been
enumerated in this paragraph will become increasingly important
The hardest decision which I had to make while preparing these books
concerned the manner in which to present the various techniques. The ad-
vantages of flowcharts and of an informal step-by-step description of an
algorithm 'are well known; for a discussion of this, see the article"Computer
Drawn Flowcharts"in the ACM Communications, Vol. 6 (September, 1963)
pages 555-563. Yet a formal, precise language is also necessary to specify any
computer algorithm, and I needed to decide whether to use an algebraic language,
such as alGOL or Fortran, or to use a machine-oriented language for this
purpose. Perhaps many of todays computer experts will disagree with my
decision to use a machine-oriented language, but i have become convinced that
it was definitely the correct choice, for the following reasons:
a) Algebraic languages are more suited to numerical problems than to the
nonnumerical problems considered here; although programming lan
guages are gradually improving, today s languages are not yet appropriate
for topics such as coroutines, input-output buffering, generating random
numbers, multiple-precision arithmetic, and many problems involving
packed data, combinatorial searching, and recursion, which appear
throughout
b)a programmer is greatly infuenced by the language in which he writes
his programs; there is an overwhelming tendency to prefer constructions
which are simplest in that language, rather than those which are best for
the machine By writing in a machine-oriented language, the programmer
will tend to use a much more suitable method it is much closer to reality.
c)The programs we require are with a few exceptions, all rather short, so
with a suitable computer there will be no trouble understanding the
programs.
d)a person who is more than casually interested in computers should be
well schooled in machine language, since it is a fundamental part of a
computer
e) Some machine language would be necessary anyway as
software programs described in Chapters 1, 9, 10, and i output of the
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
