計算機算法設計與分析

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

    計算機算法設計與分析 PDF格式下載

---