計算機算法設(shè)計與分析

前言

算法設(shè)計與分析是計算機科學(xué)的一個主要研究領(lǐng)域。本課程是計算機、管理信息系統(tǒng)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)和計算數(shù)學(xué)等專業(yè)高年級學(xué)生和研究生的一門重要專業(yè)課程。它的主要目的是講授在計算機應(yīng)用中常常遇到的實際問題的有效解法，講授設(shè)計和分析各種算法的基本原理、方法和技術(shù)，以培養(yǎng)讀者在選擇或設(shè)計一個算法時，思考下列問題：這個算法是否有效？這個算法有多好？是否還有更好的算法？用什么方法和技巧去獲得更好的算法？從而使得所設(shè)計算法的時空復(fù)雜性最優(yōu)，進(jìn)而為編寫高效的程序、開發(fā)優(yōu)秀軟件奠定基礎(chǔ)。本書旨在全面介紹計算機算法設(shè)計與分析的內(nèi)容。力爭做到取材先進(jìn)、內(nèi)容實用、重點突出、少而精，便于自學(xué)；并注意收錄一些典型問題的最新研究成果。期望讀者通過本課程的學(xué)習(xí)，接受算法設(shè)計基礎(chǔ)研究的初步訓(xùn)練，了解算法設(shè)計的最新應(yīng)用領(lǐng)域，培養(yǎng)獨立開展科研工作的能力和創(chuàng)新意識。本書可作為計算機科學(xué)及相關(guān)專業(yè)高年級學(xué)生和研究生課程的教材；也可供其他從事計算機研究與應(yīng)用的人員參考。全書共分十三章。第一章介紹算法分析的基本概念和基本理論，介紹設(shè)計算法的基本技術(shù)和分析算法復(fù)雜性的基本方法；第二章介紹遞歸技術(shù)，重點講述了遞歸方程的解法；第三章介紹分治策略，它是設(shè)計有效算法最常用的策略，也是必須掌握的方法；第四章介紹動態(tài)規(guī)劃算法，以具體實例詳述動態(tài)規(guī)劃算法的設(shè)計思想以及算法的設(shè)計要點；第五章介紹貪心算法，它是一種重要的算法設(shè)計策略，按其設(shè)計出的許多算法能導(dǎo)致最優(yōu)解；第六章和第七章分別介紹了回溯法和分支限界法，這兩章所介紹的算法適合于處理難解問題，其解題的思想各有特色，值得學(xué)習(xí)和掌握；第八章介紹了NP完全問題及近似算法，重點剖析一些典型、能啟迪人們思維的算法設(shè)計思想；第九章介紹了字符串精確匹配和近似匹配技術(shù)，也重點剖析一些典型、能啟迪人們思維的算法設(shè)計思想；第十章介紹了網(wǎng)絡(luò)路由算法，這是當(dāng)前計算機網(wǎng)絡(luò)應(yīng)用研究中受到廣泛關(guān)注的研究內(nèi)容。

內(nèi)容概要

計算機算法是計算機科學(xué)和計算機應(yīng)用的核心。無論是計算機系統(tǒng)、系統(tǒng)軟件的設(shè)計，還是為解決計算機的各種應(yīng)用課題做的設(shè)計都可歸結(jié)為算法的設(shè)計。    本書以計算機算法設(shè)計策略為知識單元，圍繞算法設(shè)計的基本方法，對計算機應(yīng)用領(lǐng)域中許多常用的非數(shù)值算法做了系統(tǒng)的描述，并分析了這些算法所需的時間和空間。全書共分十三章，前七章介紹了遞歸技術(shù)、分治策略、動態(tài)規(guī)劃、貪心法、回溯法及分支限界法等基本設(shè)計方法，第八到十三章介紹NP完全理論和NP難題、近似算法、字符串匹配、隨機算法、概率算法的相關(guān)知識，并對近年來廣泛受到關(guān)注的網(wǎng)絡(luò)路由算法及生物信息算法的基本設(shè)計方法作了介紹。書中既涉及傳統(tǒng)算法的實例分析，更有算法領(lǐng)域熱點研究課題追蹤，具有較高的實用價值。    本書可作為高等院校計算機及相關(guān)專業(yè)本科生及研究生的教學(xué)用書，也可作為從事計算機科學(xué)、工程和應(yīng)用的工作人員的自學(xué)教材和參考書。

書籍目錄

第一章　導(dǎo)論　第一節(jié)　算法與程序  第二節(jié)　算法的描述  第三節(jié)　算法的評價與優(yōu)化  第四節(jié)　算法的復(fù)雜度  習(xí)題第二章　遞歸技術(shù)  第一節(jié)　遞歸過程  第二節(jié)　遞歸技術(shù)  第三節(jié)　遞歸過程的實現(xiàn)  第四節(jié)　遞歸函數(shù)  第五節(jié)　遞歸方程  第六節(jié)　遞歸方程求解  第七節(jié)　遞歸消除  習(xí)題第三章　分治策略  第一節(jié)　分治法的基本思想  第二節(jié)　二分搜索技術(shù)  第三節(jié)　大整數(shù)的乘法  第四節(jié)　Strassen矩陣乘法  第五節(jié)　棋盤覆蓋  第六節(jié)　合并排序  第七節(jié)　快速排序  第八節(jié)　找最大和最小元素  習(xí)題第四章　動態(tài)規(guī)劃  第一節(jié)　一般方法  第二節(jié)　矩陣連乘問題　第三節(jié)　動態(tài)規(guī)劃算法的基本要素　第四節(jié)　最長公共子序列　第五節(jié)　最大子段和　第六節(jié)　電路布線　第七節(jié)　流水作業(yè)調(diào)度　第八節(jié)　0-1背包問題　第九節(jié)　整數(shù)規(guī)劃問題　第十節(jié)　流動推銷員（或旅行商）問題　習(xí)題第五章　貪心法　第一節(jié)  引言　第二節(jié)　背包問題　第三節(jié)　最小生成樹　第四節(jié)　單源最短路徑問題　第五節(jié)　文件存儲問題　第六節(jié)　有期限的任務(wù)安排問題　習(xí)題第六章　回溯法　第一節(jié)　回溯法的一般方法　第二節(jié)　n皇后問題　第三節(jié)　圖的著色問題　第四節(jié)　流水作業(yè)車間調(diào)度　第五節(jié)　裝載問題　第六節(jié)　0-1背包問題　第七節(jié)　馬的遍歷問題　習(xí)題第七章　分支限界法　第一節(jié)　分支限界法的基本思想　第二節(jié)　旅行推銷員問題　第三節(jié)　單源最短路徑問題　第四節(jié)　布線問題　第五節(jié)　0-1背包問題　第六節(jié)　裝載問題　習(xí)題第八章　P、NP和NP完全問題第九章　字符串匹配第十章　網(wǎng)絡(luò)路由算法第十一章　隨機地第十二章　概率算法·數(shù)論算法·計算幾何第十三章　生物信息處理算法參考文獻(xiàn)

章節(jié)摘錄

插圖：第一章 導(dǎo)論計算機算法是計算機科學(xué)和計算機應(yīng)用的核心，無論是計算機系統(tǒng)、系統(tǒng)軟件和解決計算機的各種應(yīng)用課題都可歸結(jié)為算法的設(shè)計。通常，給了一個問題，我們關(guān)心三件事：1．怎樣找到解決此問題的有效算法？2．如何比較解決同一問題的不同算法？3．如何判斷一個算法的優(yōu)點？簡單地說，解決這三個問題就是應(yīng)該掌握常規(guī)的或經(jīng)典的算法設(shè)計方法，掌握算法分析的基本手段。第一節(jié) 算法與程序一、算法的概念及特性對于計算機科學(xué)來說，算法(Algorithm)的概念是至關(guān)重要的。例如在一個大型軟件系統(tǒng)的開發(fā)中，設(shè)計出有效的算法將起決定性的作用。通俗地講，算法是指解決問題的一種方法或一個過程。更嚴(yán)格地講，算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法，且滿足下述幾條性質(zhì)：1．輸入：有零個或多個由外部提供的量作為算法的輸入。2．輸出：算法產(chǎn)生至少一個量作為輸出。3．確定性：組成算法的每條指令是清晰的、無歧義的。4．可行性：算法中有待實現(xiàn)的運算都相當(dāng)基本（都是基本運算），每種運算至少在原理上能由人用紙和筆在有限的時間內(nèi)完成。整數(shù)算術(shù)運算是可行性運算的一個例子，而實數(shù)算術(shù)運算則不是可行的，因為某些實數(shù)值只能由無限長的十進(jìn)制數(shù)展開式來表示，像這樣的兩個數(shù)相加就違背可行性這一特性。

編輯推薦

《計算機算法設(shè)計與分析》由中國鐵道出版社出版。

圖書封面

評論、評分、閱讀與下載

---

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

---