计算机程序设计艺术 第1卷 基本算法（第3版）（英文影印版）
点击看大图基本信息
内容简介回到顶部↑
卷1为基础运算法则，该书以基本的编程概念和技术为开始，然后讲述信息结构--计算机内信息的表示法，数据元素间的结构关系以及处理它们的有效方法。主要应用于模拟、数字方法、符号计算、软件和系统设计。许多简单和重要的运算法则和技术已添加到前一版本中，精确的初步计算部分已经修改，以适应当前趋势。
作译者回到顶部↑
本书提供作译者介绍
Donald.E.Knuth(唐纳德.E.克努特，中文名高德纳)是算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者，他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集。这一伟大工程在1962年他还是加利福尼亚理工学院的研究生时就开始了。Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)，美国前总统卡特授予的科学金.. << 查看详细
目录回到顶部↑
chapter 1 basic concepts
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
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 PROCESS of preparing programs for a digital computer is especially attractive, not only because it can be economically and scientifically rewarding, but also because it can be an aesthetic experience much like composing poetry or music. This book is the first volume of a multi-volume set of books that has been (lesigned to train the reader in various skills that go into a programmer's craft.
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
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
加载中...
