算法設計與分析

內(nèi)容概要

　　為了適應培養(yǎng)我國21世紀計算機各類人才的需要，結合我國高等學校教育工作的現(xiàn)狀，立足培養(yǎng)學生能跟上國際計算機科學技術的發(fā)展水平，更新教學內(nèi)容和教學方法，提高教學質(zhì)量，《21世紀大學本科計算機專業(yè)系列教材·普通高等教育“十一五”國家級規(guī)劃教材：算法設計與分析（第2版）》以算法設計策略為知識單元，系統(tǒng)地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。
　　另有配套的《算法設計與分析習題解答（第2版）》，對本書的全部習題做了詳盡的解答。
　　《21世紀大學本科計算機專業(yè)系列教材·普通高等教育“十一五”國家級規(guī)劃教材：算法設計與分析（第2版）》內(nèi)容豐富，觀點新穎，理論聯(lián)系實際。不僅可用作高等學校計算機專業(yè)本科生和研究生學習計算機算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。

作者簡介

　　王曉東，男，1957年3月出生，福州大學計算機系教授，福建省計算機學會理事長。研究領域是算法設計與算法評價，基于計算機網(wǎng)絡和信息安全的大規(guī)模問題求解算法與數(shù)據(jù)結構，信息可視化技術。幾何計算，并行和分布式算法設計，計算復雜性理論。先后主持了與算法設計與分析有關的國家自一然科學基金項目、國家優(yōu)秀留學回國人一員基金項目、福建省杰出人才基金項目和省自然科學基金項目等7個研究課題；獲得國家科技進步二等獎1項，省科技進步二等獎3項。主持國家精品課程“算法與數(shù)據(jù)結構”，和福建省優(yōu)質(zhì)碩士學位課程“算法設計與分析”的課程建設，獲2005年福建省教學成果一等獎。在國內(nèi)外重要學術刊物上發(fā)表有創(chuàng)見性的論文50余篇；正式出版《算法設計與分析》等學術著作7部，在算法復雜性研究方面取得了一系列理論研究成果和應用成果。例如，在對著名的凸殼問題的計算復雜性研究成果中推廣了關于判定樹模型下問題的計算復雜性下界的著名的Ben-Or，并應用于分析凸殼問題的計算復雜性，在較_般的情況下改進和完善了國際算法界知名學者Aggarwal、Steele和Yao等提出的關于凸殼問題計算復雜性下界的結果。研究成果得到同行專家的好評并被國內(nèi)權威刊物所引用。

書籍目錄

第1章 算法引論
1.1 算法與程序
1.2 表達算法的抽象機制
1.3 描述算法
1.4 算法復雜性分析
小結
習題
第2章 遞歸與分治策略
2.1 遞歸的概念
2.2 分治法的基本思想
2.3 二分搜索技術
2.4 大整數(shù)的乘法
2.5 Strassen矩陣乘法
2.6 棋盤覆蓋
2.7 合并排序
2.8 快速排序
2.9 線性時間選擇
2.10 最接近點對問題
2.11 循環(huán)賽日程表
小結
習題
第3章 動態(tài)規(guī)劃
3.1 矩陣連乘問題
3.2 動態(tài)規(guī)劃算法的基本要素
3.3 最長公共子序列
3.4 凸多邊形最優(yōu)三角剖分
3.5 多邊形游戲
3.6 圖像壓縮
3.7 電路布線
3.8 流水作業(yè)調(diào)度
3.9 0-1背包問題
3.10 最優(yōu)二叉搜索樹
小結
習題
第4章 貪心算法
4.1 活動安排問題
4.2 貪心算法的基本要素
4.2.1 貪心選擇性質(zhì)
4.2.2 最優(yōu)子結構性質(zhì)
4.2.3 貪心算法與動態(tài)規(guī)劃算法的差異
4.3 最優(yōu)裝載
4.4 哈夫曼編碼
4.4.1 前綴碼
4.4.2 構造哈夫曼編碼
4.4.3 哈夫曼算法的正確性
4.5 單源最短路徑
4.5.1 算法基本思想
4.5.2 算法的正確性和計算復雜性
4.6 最小生成樹
4.6.1 最小生成樹性質(zhì)
4.6.2 Prim算法
4.6.3 Kruskal算法
4.7 多機調(diào)度問題
4.8 貪心算法的理論基礎
4.8.1 擬陣
4.8.2 帶權擬陣的貪心算法
4.8.3 任務時間表問題
小結
習題
第5章 回溯法
第6章 分支限界法
第7章 概率算法
第8章 NP完全性理論
第9章 近似算法
第10章 算法優(yōu)化策略
第11章 在線算法設計
詞匯索引
參考文獻

章節(jié)摘錄

版權頁：   插圖：   （4）假定現(xiàn)在的目標是要求磁帶的利用率最大，而程序Pi的順序滿足a1≥a2≥…≥an。要求按P1，P2，…，Pl，…的順序考慮選取Pi到Q中，只要磁帶上的剩余空間足夠容納Pi，就應當把Pi選人Q中。按以上策略寫一個算法，并且分析其時間和空間復雜性。 4-9 問題的條件如題4-8，現(xiàn)在的目標是：（1）使子集Q達到最大；（2）在保證Q最大的前提下使帶的利用率達到最大。應當采用什么策略？寫出一個完整的算法并證明其正確性。 4-10 假定要把長為l1，l2，…，ln的n個程序放在磁帶T1和T2上，并且希望按照使最大檢索時間取最小值的方式存放，即如果存放在丁。和T2上的程序集合分別是A和B，則希望所選擇的A和B使得max{∑li，∑li}取最小值。貪心算法：開始將A和B都初始化為空，然后一次考慮一個程序，如果Σi∈Ali=min{∑li，∑li），則將當前正在考慮的那個程序分配給A；否則，分配給B。i∈A i∈B證明無論是按l1≤l2≤…≤ln或是按l1≥l2≥…≥ln的次序來考慮程序，這種方法都不能產(chǎn)生最優(yōu)解。應當采用什么策略？寫出一個完整的算法并證明其正確性。 4-11設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti，1≤i≤n。應如何安排n個顧客的服務次序才能使總的等待時間達到最?。靠偟牡却龝r間是每個顧客等待服務時間的總和。 4-12在題4-11中，如果有S處提供同一服務，應如何安排n個顧客的服務次序？ 4-13 將最優(yōu)裝載問題的貪心算法推廣到2艘船的情形，貪心算法仍能產(chǎn)生最優(yōu)解嗎？ 4-14設T是一棵帶權樹，樹的每一條邊帶一個正權。又設S是T的頂點集，T/S是從樹丁中將S中頂點刪去后得到的森林。如果T/S中所有樹的從根到葉的路長都不超過d，則稱T/S是一個d森林。 （1）設計一個算法求T的最小頂點集S，使T/S是d森林（提示：從葉向根移動）。 （2）分析算法的正確性和計算復雜性。 （3）設T中有n個頂點，則算法的計算時間復雜性應為O(n)。 4-15 將任務安排問題的貪心算法推廣到完成任務i需要ti時間，l≤i≤n的情形。 4-16 一輛汽車加滿油后可行駛咒公里。旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站?？考佑?，使沿途加油次數(shù)最少。并證明算法能產(chǎn)生一個最優(yōu)解。

編輯推薦

《21世紀大學本科計算機專業(yè)系列教材·算法設計與分析(第2版)》充分兼顧理科專業(yè)和工科專業(yè)的特點，基本概念敘述清楚，數(shù)學推導思路清晰，克服學習的各個知識難點，使《21世紀大學本科計算機專業(yè)系列教材·算法設計與分析(第2版)》理解起來更加容易，同時也考慮實際應用問題，以便增強學習興趣和自信心?！?1世紀大學本科計算機專業(yè)系列教材·算法設計與分析(第2版)》適合通信、電子、電氣類以及相關專業(yè)的本科生使用，也可供?？茖W生或有關專業(yè)人員參考。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---