دانلود کتاب ده الگوی نرم افزاری که هر دانش آموزی باید بداند

While working at Ab Initio (a company that builds very high performance software primarily for commercial data processing), I had the good fortune to interview rising seniors for summer internships and new graduates, usually with a bachelor’s degree in computer science, for full-time positions. These were invariably very bright students. Some had significant real-world experience in jobs from programming hearing aids to predicting dairy herd production. Yet despite attending some of the best schools in the United States, I often found gaps in their understanding of basic algorithms and programming concepts. I decided to make a list of algorithms and programming techniques (collectively called software patterns in this book) that I felt every student should know about at least cursorily. There are lots of reasons for a student to be unfamiliar with some of the basic software patterns discussed in this book. Computer Science (which encompasses software engineering) is a very broad field. It includes concepts such as web programming, artificial intelligence techniques (like neural networks), programming graphics cards, highly distributed systems, database systems, and computational complexity. Quantum computing is an emerging topic. The list goes on and on. A certain degree of specialization is required for a student to complete a degree in four years. Nevertheless, there are algorithms and programming models that are at the root of an awful lot of software. There are also approaches to problems that are elegant but not necessarily obvious (finding palindromes using polynomial arithmetic is one example). Just as every English major should be familiar with a variety of literary forms, a computer focused major (such as software engineering or theoretical computer science) should be acquainted with a suite of fundamental software patterns. This book is not comprehensive by any means. There are many more algorithms than can be covered in any single book. Even Donald Knuth’s amazing volumes on algorithms can’t cover everything. Some algorithms are specialized, designed for more esoteric purposes. There are also more clever and more powerful algorithms for some of the tasks presented that are not included in this book, mostly because they exceed the scope of what an undergraduate student can understand in a compressed amount of time. I’ve chosen a set of algorithms and program designs that I have personally encountered multiple times in a nearly 40-year career as a software engineer that I think should be in any canon of algorithms. The goal of each software pattern presentation is to be complete and clear enough that a student could implement the pattern. This book does not include an in-depth analysis of the algorithms presented. For example, the pattern on hash tables does not discuss how to evaluate the efficacy of a hash function. We will touch on the complexity of each algorithm (i.e., how fast the algorithm performs, how much space it will use up). More detailed complexity analyses are left to books focused on that topic. Occasionally more subtle performance implications will be explored, especially when one implementation approach may be more efficient than another in a non-intuitive way. Like reading classic literary works, understanding classic algorithms, even if not used day-to-day, provides a foundation for a deeper understanding of how software is built and optimized. One of the goals of this book is that it could serve as the basis of a college semester class. Each Pattern represents about five hours of lecture with recommended exercises. The goal would be that a student would learn about a topic and program the previous week’s topic’s exercise concurrently. Some topics (such as concurrency control and socket programming) are broader topics that require more than one week to address. By the end of the course a student will have added some new tricks to her programming portfolio and perhaps a greater appreciation for the underpinnings of the more elaborate software such as databases and web application frameworks. The patterns presented here assume that the student will have a non-trivial knowledge of fundamental data structures such as linked lists and queues. This book is not an introduction to data structures. We will present the software patterns using C. The choice of C is because it is relatively simple and low level enough that CPU specific aspects of an algorithm can be expressed. A basic familiarity with the C programming language and how to express elementary data structures (arrays, linked lists) in C is assumed. As mentioned above, I’ve been a software engineer for a long time. I have encountered finite state machines and parsing (see Pattern 2) building an incremental compiler for the Trellis object-oriented language (Schaffert et al., 1986) at Digital Equipment Corporation. While completing my Ph.D. at Harvard (my thesis was Parallel Sets: An Object-Oriented Methodology for Massively Parallel Programming. (Kilian, 1992)) I had the good fortune to meet Michael Rabin and new ways of using algebra to solve non-numeric problems (see Pattern 4). I applied some of my thesis ideas at Kendall Square Research (CBR Staff Writer, 1993) where we built a parallel high-performance object oriented database and computation model that was used for modeling passenger load for all the _lights for a specific airline (see Pattern 7) After Kendall Square Research I built an interpreter for C++ leveraging sophisticated finite state machines and a unique P-code structure used to execute the programs that also leveraged new memory management (Pattern 9). Following this, I helped develop the Centera platform at EMC (eG Innovations, 1993) which featured a new way of accessing content with cryptographically strong hashing (see Pattern 6). At a startup, I worked on a distributed web platform for content management (which became the basis of the Unified Delivery Network for Ericsson) (CIO Applications,2023) again leveraging some of the finite state machine technology described in Pattern 2, the hash tables from Pattern 1 and much of the lessons from Patterns 4 and 5. That was followed by building a large scale, high bandwidth, low latency distributed, highly available, in-memory object repository and compute platform at Ab Initio. Much of the discussions on extensible hash tables (Pattern 1) and message-based concurrency (Pattern 8) derive from my experiences at Ab Initio. Most of the products that I’ve referenced have faded into the technological sunset. The underlying algorithms have not, and the lessons learned from building these systems retain their value. Over the course of nearly 40 years, computers have not changed fundamentally (with the exception of quantum computing). The greatest changes are in the proliferation of multicore processors, a more dramatic shift in memory hierarchies, and a huge increase in speed and capacity. Until quantum computing becomes mainstream, the software patterns presented in this book should apply to computer architectures for many years to come.