算法設(shè)計(jì)手冊(cè)

前言

Most professional programmers that I've encountered are not well prepared to tackle algorithm design problems. This is a pity, because the techniques of algorithm design form one of the core practical technologies of computer science. Designing correct, efficient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge:Techniques - Good algorithm designers understand several fundamental al-gorithm design techniques, including data structures, dynamic programming,depth-first search, backtracking, and heuristics. Perhaps the single most im-portant design technique is modeling, the art of abstracting a messy real-worldapplication into a clean problem suitable for algorithmic attack.Resources - Good algorithm designers stand on the shoulders of giants. Rather than laboring from scratch to produce a new algorithm for every task, they can figure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing imple- mentations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide sufficient source material to model most any application.This book is intended as a manual on algorithm design, providing access tocombinatorial algorithm technology for both students and computer professionals.It is divided into two parts: Techniques and Resources, The former is a generalguide to techniques for the design and analysis of computer algorithms. The Re-sources section is intended for browsing and reference, and comprises the catalogof algorithmic resources, implementations, and an extensive bibliography.

內(nèi)容概要

本書是算法設(shè)計(jì)暢銷書的最新版本，是設(shè)計(jì)實(shí)用且高效算法的最全面指導(dǎo)書。本書揭密了算法的設(shè)計(jì)與分析，以簡(jiǎn)單易懂的寫作風(fēng)格，介紹了各種算法技術(shù)，著重強(qiáng)調(diào)了算法分析，全書包括兩大部分，“技術(shù)”部分介紹了設(shè)計(jì)和分析計(jì)算機(jī)算法的各種方法，“資源”部分給出了大量的參考資源，以及算法實(shí)現(xiàn)的各種資源，此外，在作者的個(gè)人網(wǎng)址http：／／www．CS．sunysb．edu／～algorith／I-還提供了各種教學(xué)資源和參考材料，這些資源對(duì)讀者很有參考價(jià)值。    本書可以作為算法設(shè)計(jì)課程的主教材，也是程序人員、研究人員和學(xué)生的常備參考書。

作者簡(jiǎn)介

作者：(德國)斯基恩納(Steven S.Skiena)

書籍目錄

I  Practical Algorithm Design　1　Introduction to Algorithm Design　　1.1 Robot Tour Optimization　　1.2  Selecting the Right Jobs　　1.3   Reasoning about Correctness　　1.4  Modeling the Problem　　1.5  About the War Stories　　1.6  War Story: Psychic Modeling　　1.7  Exercises　2  Algorithm Analysis　　2.1   The RAM Model of Computation　　2.2  The Big Oh Notation　　2.3  Growth Rates and Dominance Relations　　2.4  Working with the Big Oh　　2.5  Reasoning About Efficiency　　2.6   Logarithms and Their Applications 　　2.7  Properties of Logarithms　　2.8  War Story: Mystery of the Pyramids 　　2.9   Advanced Analysis (*)　　2.10 Exercises　3  Data Structures　　3.1   Contiguous vs. Linked Data Structures.　　3.2   Stacks and Queues　　3.3  Dictionaries　　3.4  Binary Search Trees　　3.5  Priority Queues　　3.6 War Story: Stripping Triangulations　　3.7　Hashing and Strings　　3.8  Specialized Data Structures　　3.9   War Story: String 'em Up　　3.10 Exercises　4 Sorting and Searching　　4.1   Applications of Sorting　　4.2   Pragmatics of Sorting　　4.3  Heapsort: Fast Sorting via Data Structures　　4.4  War Story: Give me a Ticket on an Airplane　　4.5   Mergesort: Sorting by Divide-and-Conquer　　4.6   Quicksort: Sorting by Randomization　　4.7  Distribution Sort: Sorting via Bucketing　　4.8  War Story: Skiena for the Defense　　4.9   Binary Search and Related Algorithms　　4.10 Divide-and-Conquer　　4.11 Exercises  　5  Graph Traversal　　5.1 Flavors of Graphs　　5.2   Data Structures for Graphs　　5.3   War Story: I was a Victim of Moore's Law　　5.4  War Story: Getting the Graph　　5.5  Traversing a Graph　　5.6  Breadth-First Search　　5.7  Applications of Breadth-First Search　　5.8  Depth-First Search　　5.9  Applications of Depth-First Search　　5.10 Depth-First Search on Directed Graphs　　5.11 Exercises　6  Weighted Graph Algorithms　　6.1   Minimum Spanning Trees　　6.2   War Story: Nothing but Nets　　6.3  Shortest Paths　　6.4   Wax Story: Dialing for Documents　　6.5   Network Flows and Bipartite Matching　　6.6  Design Graphs, Not Algorithms　　6.7   Exercises……

章節(jié)摘錄

插圖：3.7.2 Efficient String Matching via HashingStrings are sequences of characters where the order of the characters matters, sinceALGORITHM is different than LOGARITHM. Text strings are fundamental to ahost of computing applications, from programming language parsing/compilation,to web search engines, to biological sequence analysis.The primary data structure for representing strings is an array of characters.This allows us constant-time access to the ith character of the string. Some auxiliaryinformation must be maintained to mark the end of the string　either a specialend-of-string character or （perhaps more usefully） a count of the n characters inthe string.The most fundamental operation on text strings is substring search, namely:Problem: Substring Pattern MatchingInput: A text string t and a pattern string p.Output: Does t contain the pattern p as a substring, and if so where？

編輯推薦

《算法設(shè)計(jì)手冊(cè)(第2版)》：大學(xué)計(jì)算機(jī)教育國外著名教材系列(影印版)

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    算法設(shè)計(jì)手冊(cè) PDF格式下載

---