編輯推薦

教學主綫清晰，拓撲結構閤理。將算法設計技術分為基本的算法設計技術、基於搜索的算法設計技術、求解NP問題的算法設計技術三個模塊。

將經典問題與算法設計技術相結閤。以經典問題為載體，係統地介紹瞭算法設計技術及其在經典問題中的應用。

以問題求解為主綫，引導思維過程。按照“問題à想法à算法à程序”的模式介紹經典問題的求解過程，並用圖示闡明算法的設計過程。

正確處理算法和程序之間的關係。所有問題都用僞代碼和C++描述兩種形式給齣瞭算法描述，所有程序均在VC++6.0環境下調試通過。

發揮教材的窗口作用，引入智能算法。以通俗易懂的筆觸介紹瞭人工神經網絡、遺傳算法、蟻群算法、粒子群算法和模擬淬火等智能優化算法。

內容簡介

　　《普通高校本科計算機專業特色教材精選·算法與程序設計：算法設計與分析（第2版）》將經典問題和算法設計技術很好地結閤起來，係統地介紹瞭算法設計技術及其在經典問題中的應用。全書共分四部分：第一部分是基礎知識，包括算法設計基礎和算法分析基礎；第二部分是基本的算法設計技術，包括蠻力法、分治法、減治法、動態規劃法和貪心法；第三部分是基於搜索的算法設計技術，包括迴溯法和分支限界法；第四部分是計算的限製，介紹瞭問題的復雜性、近似算法和概率算法。所有問題都用僞代碼給齣瞭算法描述，大多數問題都給齣瞭C++語言的算法實現，並且所有程序均在VC#6.0環境下調試通過。每章均附有一篇閱讀材料，以通俗易懂的方式介紹瞭算法領域的一些新研究成果。

　　《普通高校本科計算機專業特色教材精選·算法與程序設計：算法設計與分析（第2版）》內容豐富，深入淺、齣，結閤應用，圖例豐富，可作為高等院校計算機專業本科和研究生學習算法設計與分析的教材，也可供工程技術人員和自學者學習參考。

內頁插圖

目錄

第一部分 基礎知識
第1章 算法設計基礎
1.1 算法的基本概念
1.1.1 算法及其重要特性
1.1.2 算法的描述方法
1.1.3 算法設計的一般過程
1.2 為什麼要學習和研究算法
1.2.1 算法在問題求解中的地位
1.2.2 算法訓練能夠提高計算思維能力
1.2.3 算法研究是推動計算機技術發展的關鍵
1.3 重要的問題類型
1.3.1 查找問題
1.3.2 排序問題
1.3.3 圖問題
1.3.4 組閤問題
1.3.5 幾何問題
閱讀材料——算法研究與圖靈奬
習題1
第2章 算法分析基礎
2.1 算法的時間復雜性分析
2.1.1 輸入規模與基本語句
2.1.2 算法的漸進分析
2.1.3 最好、最壞和平均情況
2.1.4 非遞歸算法的時間復雜性分析
2.1.5 遞歸算法的時間復雜性分析
2.2 算法的空間復雜性分析
2.3 最優算法
2. 3.1 問題的計算復雜性下界
2.3.2 平凡下界
2.3.3 判定樹模型
閱讀材料——算法的實驗分析
習題2

第二部分 基本的算法設計技術
第3章 蠻力法
3.1 概述
3.1.1 蠻力法的設計思想
3.1.2一個簡單的例子百元買百雞問題
3.2 查找問題中的蠻力法
3.2.1 順序查找
3.2.2 串匹配問題
3.3 排序問題中的蠻力法
3. 3.1 選擇排序
3.3.2 起泡排序
3.4 組閤問題中的蠻力法
3.4.1 0/1背包問題
3.4.2 任務分配問題
3.5 圖問題中的蠻力法
3.5.1 哈密頓迴路問題
3.5.2 TSP問題
3.6 幾何問題中的蠻力法
3.6.1 最近對問題
3.6.2 凸包問題
閱讀材料——KMP算法中next值的計算
習題3
第4章 分治法
4.1 概述
4.1.1 分治法的設計思想
4.1.2一個簡單的例子數字鏇轉方陣
4.2 排序問題中的分治法
4.2.1 歸並排序
4.2.2 快速排序
……

第三部分 基於搜索的算法設計技術
第四部分 計算的限製

附錄A 名詞索引
參考文獻

前言/序言

第2版前言在ACM/IEEE-CS提交的CC2005中，將計算機專業的基本學科能力歸納為計算思維能力、算法設計與分析能力、程序設計與實現能力和係統能力。“算法設計與分析”課程不僅能夠培養學生的算法設計與分析能力，進一步增強程序設計與實現能力，而且能夠引導學生的思維過程，培養計算思維能力。用計算機求解問題的最重要環節就是將人的想法抽象為算法，在描述問題和求解問題的過程中，主要采用抽象思維和邏輯思維。因此，算法訓練就像一種思維體操，能夠鍛煉思維，使思維變得更清晰、更有邏輯。

本書在保持第1版基本體例不變的基礎上，進行瞭如下修改。

(1) 將算法設計技術重新進行分類，本書共分為四部分：基礎知識、基本的算法設計技術、基於搜索的算法設計技術和計算的限製，知識單元的拓撲結構如圖1所示。

圖1 知識單元的拓撲結構

(2) 按照“問題→想法→算法→程序”的模式介紹經典問題的設計與實現過程，所有問題都用僞代碼給齣瞭算法描述，大多數問題都給齣瞭C++語言的算法實現，並且所有程序均在VC++6.0環境下調試通過。讀者可嚮作者或齣版社索要程序源碼。

(3) 重寫瞭閱讀材料，以通俗易懂的筆觸介紹瞭人工神經網絡、遺傳算法、蟻群算法、粒子群算法和模擬淬火等智能優化算法，每種算法均給齣一個簡單的應用舉例。

本書由王紅梅和鬍明共同執筆，王濤老師收集和整理瞭閱讀材料，鬍潔同學參與瞭代碼調試與校對工作，參加本書編寫的還有王晶春、黨源源、許建潮、逄煥利、姚慶安、肖巍等老師。

由於作者的知識和寫作水平有限，書稿雖幾經修改，仍難免有缺點和錯誤。熱忱歡迎同行專傢和讀者批評和指正，使本書在使用中不斷改進、日臻完善。

作 者2012年8月

算法設計與分析(第2版)

第1版前言算法設計與分析是計算機科學技術中處於核心地位的一門專業基礎課，越來越受到重視，CC2001和CCC2002都將“算法和復雜性”列為主領域，將算法設計策略、基本可計算性理論、P和NP問題類等算法設計技術和復雜性分析方法列為核心知識單元。

無論是計算科學還是計算實踐，算法都在其中扮演著重要角色，算法被公認為是計算機科學的基石。翻開重要的計算機學術刊物，算法都占有一席之地，沒有算法，計算機程序將不復存在。對於計算機專業的學生，學會讀懂算法、設計算法，應該是一項最基本的要求，而發明算法則是計算機學者的最高境界。

提高學生的問題求解能力是高等教育的一個主要目標，在計算機科學的課程體係中，安排一門關於算法設計與分析的課程是非常必要的，因為這門課程能夠引導學生的思維過程，告訴學生如何應用一些特定的算法設計策略來解決問題。學習算法還能夠提高學生分析問題的能力。算法可以看作是解決問題的一類特殊方法--它不是問題的答案，而是經過精確定義的、用來獲得答案的求解過程。因此，無論是否涉及計算機，特定的算法設計技術都可以看作是問題求解的有效策略。

本書將計算機經典問題和算法設計技術很好地結閤起來，係統地介紹瞭算法設計技術及其在經典問題中的應用。通過同一算法設計技術在不同問題中的應用進行比較，牢固掌握算法設計技術的基本策略；通過不同的算法設計技術在同一問題中的應用進行比較，更容易體會到算法設計技術的思想方法，收到融會貫通的效果。所以，本書采用瞭模塊化的設計思想，讀者除瞭按本書組織的章節學習外，還可以將每種算法設計技術的問題提取齣來，比較解決相同問題的不同解決方法。隨著本書內容的不斷展開，讀者也將感受到綜閤應用多種算法設計技術有時可以更有效地解決問題。

全書共12章，第1章介紹瞭算法的基本概念和算法分析方法，第2章從算法的觀點非形式化地介紹瞭NP完全理論，第3章~第11章分彆介紹瞭蠻力法、分治法、減治法、動態規劃法、貪心法、迴溯法、分支限界法、概率算法和近似算法等算法設計技術，第12章基於圖靈機計算模型介紹瞭計算復雜性理論。

書中所有問題均給齣瞭若乾應用實例，每章還設有一個實驗項目，通過設計提高學生創造性思維的培養。每章均附有一篇閱讀材料，以通俗易懂的筆觸介紹瞭算法領域的一些最新研究成果，保證知識的先進性。書中所有算法均給齣瞭僞代碼，大部分算法還給齣瞭C++描述。在算法介紹上，注重對問題求解過程的理解，注重算法設計思路和分析過程的講解，體現瞭“授之以漁”的教學理念。

王濤老師收集和整理瞭本書的閱讀材料，參加本書編寫的還有鬍明、許建潮、孫衛佳、逄煥利、劉鋼、陳誌雨等老師，研究生張倩、魏卓調試瞭本書的全部算法。

由於作者的知識和寫作水平有限，書稿雖幾經修改，仍難免有缺點和錯誤。熱忱歡迎同行專傢和讀者批評指正，使本書在使用中不斷改進、日臻完善。

作 者2006年2月

不錯，內容豐富易懂！

速度快物品質量好

不錯，質量可以，包裝也好

書好舊。。這得在倉庫放多長時間瞭，雖然是新書，但是一點都不新

不錯，正版書籍

高。。。。。。。。。。。

很快

老師要求用的書，應該不錯

我們算法課的指導用書，很不錯