算法設(shè)計(jì)與分析

內(nèi)容概要

　　本書作為普通高等學(xué)校計(jì)算機(jī)與信息安全專業(yè)本科生的教材，根據(jù)國內(nèi)外計(jì)算機(jī)技術(shù)的最新發(fā)展，闡述計(jì)算機(jī)算法的各種設(shè)計(jì)策略、算法分析和一些經(jīng)典及應(yīng)用問題的算法?！　∪珪?1章，第1章介紹算法引論；第2章闡述了排序算法；第3章介紹了分治算法；第4章介紹了圖的搜索算法；第5章介紹了貪心算法；第6章介紹了動(dòng)態(tài)規(guī)劃算法；第7章介紹了分支限界法；第8章介紹了并行算法；第9 章介紹了NP-完全問題；第10章介紹了近似算法；第11章介紹了概率算法?！　”緯且槐咀⒅叵到y(tǒng)性、科學(xué)性的教材，內(nèi)容豐富、理論性強(qiáng)，可作為計(jì)算機(jī)與信息安全專業(yè)及其他相關(guān)專業(yè)的本科教材，也可作為計(jì)算機(jī)及信息安全領(lǐng)域軟件開發(fā)人員的技術(shù)參考書。

書籍目錄

第1章 算法引論1.1 算法1.2 算法描述1.2.1 算法描述約定1.2.2 一個(gè)簡單問題的求解過程1.3 算法分析基礎(chǔ)1.3.1 算法分析的評(píng)估體系1.3.2 算法的時(shí)間復(fù)雜度1.3.3 算法的空間復(fù)雜度1.3.4 NP-完全問題1.4 基本數(shù)據(jù)結(jié)構(gòu)1.4.1 棧和隊(duì)列1.4.2 樹1.4.3 圖1.5 迭代法1.5.1 遞推法1.5.2 倒推法1.5.3 迭代法解方程1.6 遞歸和消除遞歸1.6.1 遞歸1.6.2 消除遞歸本章小結(jié)習(xí)題1第2章 排序算法2.1 排序2.1.1 排序問題2.1.2 冒泡問題2.1.3 交換排序2.1.4 選擇排序2.1.5 插入排序2.2 堆排序2.2.1 堆2.2.2 建堆2.2.3 堆排序算法2.2.4 堆排序的應(yīng)用2.3 快速排序2.3.1 快速排序的描述2.3.2 快速排序的性能2.3.3 隨機(jī)化的快速排序算法2.3.4 快速排序分析2.4 線性時(shí)間排序2.4.1 排序算法的下界2.4.2 計(jì)數(shù)排序2.4.3 基數(shù)排序2.4.4 桶排序2.5 中數(shù)排序2.5.1 最大和最小元素2.5.2 一般選擇問題本章小結(jié)習(xí)題2第3章 分治法3.1 一般算法3.2 二分檢索3.3 找最大值和最小值3.4 歸并分類3.4.1 基本方法3.4.2 改進(jìn)的歸并算法3.5 快速分類3.5.1 快速分類算法3.5.2 快速分類分析3.6 選擇問題3.6.1 選擇問題算法3.6.2 SELECT2實(shí)現(xiàn)本章小結(jié)習(xí)題3第4章 圖的搜索算法4.1 圖的基本概念4.1.1 圖的定義4.1.2 圖的基本術(shù)語4.2 圖的檢索與遍歷4.2.1 廣度優(yōu)先檢索與遍歷4.2.2 深度優(yōu)先檢索與遍歷4.3 回溯法4.3.1 回溯法的一般方法4.3.2 回溯算法的抽象描述4.3.3 n-皇后問題4.3.4 子集和數(shù)問題4.3.5 0/1背包問題4.3.6 圖的m-著色問題4.3.7 哈密頓環(huán)4.3.8 連續(xù)郵資問題4.3.9 回溯法的效率估計(jì)本章小結(jié)習(xí)題4第5章 貪心算法5.1 算法概述5.1.1貪心選擇性質(zhì)5.1.2 最優(yōu)子結(jié)構(gòu)性質(zhì)5.1.3活動(dòng)安排問題5.2 背包問題5.3 帶有限期的作業(yè)排序5.3.1 帶有限期的作業(yè)排序算法5.3.2 改進(jìn)的帶有限期的作業(yè)排序算法5.4 最優(yōu)歸并模式5.5 哈夫曼編碼5.5.1 前綴碼5.5.2 哈夫曼編碼5.6 最小生成樹5.6.1 Prim算法5.6.2 Kruskal算法5.7 單源點(diǎn)最短路徑本章小結(jié)習(xí)題5第6章 動(dòng)態(tài)規(guī)劃算法6.1 一般方法6.2 多段圖6.3 每對(duì)結(jié)點(diǎn)之間的最短路徑6.4 最優(yōu)二分檢索樹6.5 0/1背包問題6.5.1 0/1背包問題實(shí)現(xiàn)的實(shí)例分析6.5.2 DKP的實(shí)現(xiàn)6.5.3 過程DKNAP的分析6.6 可靠性設(shè)計(jì)6.7 貨郎擔(dān)問題6.8 流水線調(diào)度問題本章小結(jié)習(xí)題6第7章 分支限界法7.1 一般方法7.1.1 FIFO和LIFO-檢索7.1.2 LC-檢索7.1.3 LC-檢索的抽象化描述7.1.4 分支限界法解最優(yōu)化問題7.2 0/1背包問題7.2.1 LC-分支限界求解7.2.2 FIFO –分支限界求解7.3 貨郎擔(dān)問題7.4 效率分析本章小結(jié)習(xí)題7第8章 并行算法8.1 并行計(jì)算機(jī)及并行模型8.1.1 并行計(jì)算機(jī)8.1.2 并行計(jì)算模型8.1.3 并行計(jì)算機(jī)網(wǎng)絡(luò)8.1.4 并行算法的一般術(shù)語8.2 SIMD共享存儲(chǔ)模型的并行算法8.2.1 播送算法8.2.2 求和算法8.2.3 并行k-選擇算法8.2.4 并行桶排序算法8.2.5 有序表搜索并行算法8.3 SIMD互聯(lián)網(wǎng)絡(luò)模型的并行算法8.3.1 網(wǎng)孔上的隨機(jī)序列搜索算法8.3.2 樹機(jī)上的矩陣和向量乘法8.3.3 一維線性陳列上的奇偶轉(zhuǎn)置排序算法8.3.4 樹機(jī)上求最小值算法8.3.5 樹機(jī)上的連通分量算法8.4 MIMD共享存儲(chǔ)模型的并行算法8.4.1 異步枚舉排序算法8.4.2 單源點(diǎn)最短路徑并行算法8.4.3 最小生成樹并行算法8.4.4 Gauss-Seidel算法8.4.5 牛頓求根并行算法8.5 MIMD異步通信模型的并行算法8.5.1 快速排序并行算法8.5.2 二維網(wǎng)孔上的矩陣轉(zhuǎn)置并行算法8.5.3 矩陣并行分塊乘法算法8.5.4 分布式矩陣求逆的并行算法8.5.5 分布式高斯消去并行算法本章小結(jié)習(xí)題8第9章 NP-完全問題9.1 計(jì)算模型9.1.1 有限自動(dòng)機(jī)9.1.2 下推自動(dòng)機(jī)9.1.3 圖靈機(jī)9.2 P類與NP類問題9.2.1 多項(xiàng)式時(shí)間界9.2.2 P類問題9.2.3 NP類問題9.3 NP-完全問題9.3.1 判定NP-完全問題的關(guān)鍵概念9.3.2 NP-完全性9.3.3 Cook定理9.4 典型的NP-完全問題9.4.1 NP-完全性的證明方法9.4.2 典型的NP-完全問題9.4.3 NP-完全問題的計(jì)算機(jī)實(shí)現(xiàn)本章小結(jié)習(xí)題9第10章 近似算法10.1 近似算法的性能10.2 啟發(fā)式算法10.2.1 圖著色問題10.2.2 旅行商問題10.3 任務(wù)安排的近似算法10.4 覆蓋問題的近似算法10.4.1 頂點(diǎn)覆蓋問題的近似算法10.4.2 集合覆蓋問題的近似算法10.5 旅行售貨員問題近似算法10.5.1 具有三角不等式的旅行售貨員問題10.5.2 一般旅行售貨員問題10.6 背包問題10.7 子集合問題的近似算法10.7.1 解子集合問題的指數(shù)時(shí)間算法10.7.2 子集合問題的完全多項(xiàng)式時(shí)間近似格式本章小結(jié)習(xí)題10第11章 概率算法11.1 概率算法概述11.2 偽隨機(jī)數(shù)11.3 數(shù)值概率算法11.3.1 用隨機(jī)投點(diǎn)法計(jì)算圓周率值11.3.2 計(jì)算定積分11.3.3 解非線性方程組11.4 Sherwood算法11.4.1 線性時(shí)間選擇算法11.4.2 搜索有序表11.4.3 跳躍表11.5 Las Vegas算法11.5.1 n后問題11.5.2 整數(shù)因子分解11.6 Monte Carlo算法11.6.1 Monte Carlo算法的基本思想11.6.2 主元素問題11.6.3 素?cái)?shù)性測(cè)試本章小結(jié)習(xí)題11主要參考文獻(xiàn)

編輯推薦

這是一本注重系統(tǒng)性、科學(xué)性的教材，內(nèi)容豐富，理論性強(qiáng)。根據(jù)國內(nèi)外計(jì)算機(jī)技術(shù)的最新發(fā)展，闡述計(jì)算機(jī)算法的各種設(shè)計(jì)策略、算法分析和一些經(jīng)典及應(yīng)用問題的算法。本書可作為普通高等學(xué)校計(jì)算機(jī)與信息安全專業(yè)本科生教材。

圖書封面

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

---

    算法設(shè)計(jì)與分析 PDF格式下載

---