计算机科学导论（第7版）（英文影印版）

.chapter review problems
social issues
additional reading

chapter 2 data manipulation
2.1 computer architecture
2.2 machine language
2.3 program execution
2.4 arithmetic/logic instructions
2.5 communicating with other devices
2.6 other architectures
chapter review problems
social issues
additional reading

part two:software
chapter 3 operating systems and networks
3.1 the evolution of operating systems
3.2 operating system architecture
3.3 coordinating the machine's activities
3.4 handling competition among processes
3.5 networks
3.6 network protocols
3.7 security
chapter review problems
social issues
additional reading

chapter 4 algorithms
4.1 the concept of an algorithm
4.2 algorithms representation
4.3 algorithm discovery
4.4 iterative structures
4.5 recursive structures
4.6 efficiency and correctness
chapter review problems
social issues
additional reading

chapter 5 programming languages
5.1 historical perspective
5.2 traditional programming concepts
5.3 procedural units
5.4 language implementation
5.5 object-oriented programming
5.6 programming concurrent activities
5.7 declarative programming
chapter review problems
social issues
additional reading

chapter 6 software engineering
6.1 the software engineering discipline
6.2 the software life cycle
6.3 modularity
6.4 design methodologies
6.5 tools of the trade
6.6 testing
6.7 documentation
6.8 software ownership and liability
chapter review problems
social issues
additional reading

part three:data organization
chapter 7 data structures
7.1 data structure basics
7.2 arrays
7.3 lists
7.4 stacks
7.5 queues
7.6 trees
7.7 customized data types
7.8 pointers in machine language
chapter review problems
social issues
additional reading

chapter 8 file structures
8.1 the role of the operating system
8.2 sequential files
8.3 indexing
8.4 hashing
chapter review problems
social issues
additional reading

chapter 9 database structures
9.1 general issues
9.2 the layered approach to database implementaition
9.3 the relational model
9.4 object-oriented database
9.5 maintaining database integrity
9.6 social impact of database technology
chapter review problems
social issues
additional reading

part four:the potential of machines
chapter 10 artificial intelligence
10.1 intelligence and machines
10.2 understaanding images
10.3 reasoning
10.4 artificial neural networks
10.5 genetic algorithms
10.6 other areas of research
10.7 considering the consequences
chapter review problems
social issues
additional reading

chapter 11 theory of computation
11.1 functions and their computation
11.2 turing machines
11.3 universal programming languages
11.4 a noncomputable function
11.5 complexity of problems
11.6 public key cryptography
chapter review problems
social issues
additional reading

appendixes
a ascii
b circuits to manipulate two's complement representations
c a simple machine language
d high-level language program examples
e the equivalence of iterative and recursive structures
f answers to questions/exercises

index

.　　Web Sites
　　This text is supported by a Web site at http: //www. aw. com/brookshear. This is the text's official site maintained by Addison-Wesley. There you will find materials for both students and teachers such as supporting software (for example, simulators for the machine used as an example in Chapter 2 and described in Appendix C), laboratory manuals, links to additional topics of interest, an instructor's guide, and PowerPoint slides. You may also wish to check out my personal Web site at http: //mscs .mu.edu/-glennb. It is not very formal (and it is subject to my whims), but I tend to keep some information there that you may find helpful.
　　To Students
　　I was introduced to the field of computing during my tour in the US Navy back in the late 1960s and early 1970s. (Yes, that makes me old-but it will happen to you also. Furthermore, being old makes me wise so you should listen to what I say.) I spent most of these Navy days maintaining the system software at the Navy's computer installation in London, England. After my tour was completed, I returned to school and finished my Ph.D. in 1975. I've been teaching computer science and mathematics ever since.
　　A lot has changed in computer science over the years, but a lot has remained the same. In particular, computer science was, and still is, fascinating. There are a lot of awesome things going on out there. The development of the Internet, progress in artificial intelligence, and the ability to collect and disseminate information in unheard of proportions are only some of the things that will affect your life. You live in an exciting, changing world, and you have the opportunity to be a part of the action. Take it!
　　I'm a bit of a nonconformist (some of my friends would say more than a bit) so when I set out to write this text I didn't always follow the advice I received. In particular, many argued that certain material is too advanced for beginning students. But, I believe that if a topic is relevant, then it is relevant even if the academic community considers it an "advanced topic." You deserve a text that presents a complete picture of computer science--not a watered-down version containing artificially simplified presentations of only those topics that have been deemed acceptable for introductory students.
　　Thus, I have not avoided topics. Instead I've sought better explanations. I have tried to provide enough depth to give you an honest picture of what computer science is all about. (There's a difference between the fact that launching the space shuttle makes a lot of noise and the realization that it rattles every bone in your body.) As in the case of spices in a recipe, you may choose to omit some of the topics in the following pages, but they are there for you to taste if you wish-and I encourage you to do so.
　　Finally I should point out that in any course dealing with technology, the details you learn today may not be the details you will need to know tomorrow. The field is dynamic--that's part of the excitement. This book will give you a current picture of the subject as well as a historical perspective. With this background you will be prepared to grow along with technology. I encourage you to start the growing process now by exploring beyond this text. Learn to learn. Thank you for the trust you have placed in me by choosing to read my book. As an author I have an obligation to produce a manuscript that is worth your time. I hope you find that I have lived up to this obligation.
　　To Instructors
　　There is more material in this text than can normally be covered in a single semester so do not hesitate to skip topics that do not fit your course objectives or to rearrange the order as you see fit. I wrote the book to be used as a course resource-not as a course definition. You will find that, although the text follows a plot, the topics are covered in an independent manner that allows you to pick and choose as you desire (see Figure 0.7 for a pictorial summary of the entire text).
　　On the opening page of each chapter I have used asterisks to indicate those sections that I suggest as optional--they delve more deeply into material or branch in directions you may not wish to pursue. But these are merely suggestions. In particular, you will find that the condensed version of the text outlined earlier in this preface omits more than merely the "optional" sections. To clarify, consider Chapter 7, Data Structures. Depending on your course objectives, you may handle this chapter in any of the following ways--all of which I, myself, have done at one time or another. First, in a "computer literacy" course, you may choose to skip the entire chapter. Ifyou merely want to introduce the subject of data structures, you would probably cover only Sections 7.1 and 7.2 (as suggested in the condensed version). If, in addition, you want to present the basic structures themselves, you will need to cover Sections 7.1 through 7.6. Finally, if you want to extend the study to include customized data types or pointers in machine language, you will want to include the "optional" Sections 7.7 and/or 7.8.
　　I also suggest that you consider covering some topics as reading assignments or encourage students to read the material not included in your course. I think we underrate students if we assume that we have to explain everything in class. We should be helping them learn to learn on their own.
　　I have already explained that the text follows a bottom-up, concrete-to-abstract organization, but I want to expand on this a bit. As academics we too often assume that students will appreciate our perspective of a subject-often one that we have developed over years of working in a field. As teachers we do better by presenting material from the student's perspective. This is why the text starts with data representation/storage, machine architecture, and machine language. These are topics to which students readily relate-they can see the computer's components, they can hold them, and most students will have bought and used them. By starting the course with these topics, I see the students discovering answers to many of the "why" questions they have been carrying for years and learning to view the course as practical rather than theoretical. From this beginning it is natural to move on to the more abstract issues of algorithm discovery, design, representation, and complexity that those of us in the field see as the main topics in the course.
　　We are all aware that students learn a lot more than we teach them directly, and the lessons they learn indirectly are often better absorbed than those that are studied explicitly. This is significant when it comes to "teaching" problem solving. Students do not learn to solve problems by studying problem-solving methodologies as an isolated subject. They learn to solve problems by solving problems. So I have included numerous problems throughout the text. I encourage you to use them and to expand on them.
　　Another topic that I place in this same category is that of professionalism, ethics, and social responsibility. I do not believe that this material should be presented as an isolated subject. Instead, it should surface when it is relevant, which is the approach I have taken in this text. You will find that Sections 0.5, 3.7, 6.1, 6.8, 9.6, 10.1, and 10.7 present such topics as security, privacy, liability, and social awareness in the context of networking, database systems, software engineering, and artificial intelligence. You will also find that each chapter includes a collection of questions called Social Issues that challenge students to think about the relationship between the material in the text and the society in which they live.
　　Pedagogical Features
　　This text is the product of many years of teaching. As a result, it is rich in pedagogical aids. Paramount is the abundance of problems to enhance the student's participation-over 1,000 in this seventh edition (1,010 to be precise). These are classified as Questions/Exercises, Chapter Review Problems, and Social Issues. The Questions/Exercises appear at the end of each section. They review the material just discussed, extend the previous discussion, or hint at related topics to be covered later. These questions are answered in Appendix E
　　The Chapter Review Problems appear at the end of each chapter (except for the introductory chapter). They are designed to serve as "homework" problems in that they cover the material from the entire chapter and are not answered in the text.
　　Also at the end of each chapter are the questions in the Social Issues category. They are designed for thought and discussion. Many of them can be used to launch research assignments culminating in short written or oral reports.
　　Each chapter also ends with a list called Additional Reading that contains references to other materials relating to the subject of the chapter. The Web sites, identified earlier in this preface, are also good places to look for related material.
　　Seventh Edition
　　Although this seventh edition maintains the same chapter-by-chapter structure as previous editions of this text, topics have been added, some have been deleted, and much of the remaining material has been rewritten to provide an up-to-date and relevant picture of the science of computing.
　　The most significant distinctions between the sixth and seventh editions are pedagogical in nature. Much of the material has been reorganized and rewritten to improve clarity and simplify explanations. For example, Sections 2.1 and 2.2 (Computer Architecture and Machine Language) have been reorganized, the formal introduction to algorithms in Section 4.1 has been softened, the introduction to data structures (Section 7.1) has been reorganized, Section 7.7 (Customized Data Types) has been streamlined, the material on sequential and text files has been combined into a single section (8.2), the material on computability (Sections 11.1-11.3) has been rewritten. Moreover, numerous figures have been added and the artwork has been improved extensively.
　　There are of course numerous additions of topics as well. These include techniques of encoding sound (Chapter 1), expanded coverage of networking (Chapter 3), open-source development (Chapter 6), additional material on copyrights and patents (Chapter 6), XML (Chapter 8), and associative memory (Section 10.4). Moreover, numerous sidebars that expand the material in the text have been added throughout.
　　You will also find that this seventh edition has a new design and art program that gives the book a more "open" appearance than its predecessors. The goal is to make the material in the text more accessible and less daunting to beginning students. I hope you like it.
　　Acknowledgments
　　I first thank those of you who have supported this book by reading and using it in previous editions. I am honored.
　　With each new edition, the list of those who have contributed to the book as reviewers and consultants grows. Today this list includes J. M. Adams, C. M. Allen, D. C. S. Allison, B. Auernheimer, P. Bankston, M. Barnard, P. Bender, K. Bowyer, P. W. Brashear, C. M. Brown, B. Calloni, M. Clancy, R. T Close, D. H. Cooley, L. D. Cornell, M. J. Crowley, F. Deek, M. Dickerson, M. J. Duncan, S. Fox, N. E. Gibbs, J. D. Harris, D. Hascom, L. Heath, P. B. Henderson, L. Hunt, M. Hutchenreuther, L. A. Jehn, K. Korb, G. Krenz, J. Liu, T J. Long, C. May, W. McCown, S. J. Merrill, K. Messersmith, J. C. Moyer, M. Murphy, J. P Myers, Jr., D. S. Noonan, S. Olariu, G. Rice, N. Rickert, C. Riedesel, J. B. Rogers, G. Saito, W. Savitch, R. Schlafly, J. C. Schlimmer, S. Sells, G. Sheppard, Z. Shen, J. C. Simms, M. C. Slattery, J. Slimick, J. A. Slomka, D. Smith, J. Solderitsch, R. Steigerwald, L. Steinberg, C. A. Struble, C. L. Struble, W. J. Taffe, J. Talburt, P. Tromovitch, E. D. Winter, E. Wright, M. Ziegler, and one anonymous. To these individuals I give my sincere thanks.
　　I also thank the people at Addison-Wesley, Argosy Publishing, and Theurer Briggs Design whose efforts are refected within these pages. A team that goes though the process of publishing a book becomes a family. My publishing family has grown to include more wonderful people during the production of this seventh edition.
　　My wife Earlene and daughter Cheryl have been tremendous sources of encouragement over the years. I thank them for putting up with the author in me. They've seen that "the book" can truly make an absent-minded professor absent minded. It's comforting to be able to drift off into such academic pursuits as writing a book knowing that someone else is keeping in touch with the real world. In particular, on the morning of December 1t, 1998, I survived a heart attack because Earlene got me to the hospital in time. (For those of you in the younger generation I should explain that surviving a heart attack is sort of like getting an extension on a homework assignment.)
　　Finally, I thank my parents, to whom this book is dedicated, for instilling in me the importance of education. I close with the following endorsement whose source shall remain anonymous: "Our son's book is really good. Everyone should read it."
　　J. G. B.