算法設(shè)計(jì)與分析導(dǎo)論

內(nèi)容概要

　　本書在介紹算法時(shí)，重點(diǎn)介紹用干設(shè)計(jì)算法的策略．非常與眾不同。書中介紹了剪枝搜索、分?jǐn)偡治?、隨機(jī)算法、在線算法以及多項(xiàng)式近似方案等相對(duì)較新的思想和眾多基于分?jǐn)偡治鲂麻_發(fā)的算法，每個(gè)算法都與實(shí)例一起加以介紹，而且每個(gè)例子都利用圖進(jìn)行詳細(xì)解釋。此外，本書還提供了超過400幅圖來幫助初學(xué)者理解。本書適合作為高等院校算法設(shè)計(jì)與分析課程的高年級(jí)本科生和低年級(jí)研究生的教材，也可供相美科技人員和專業(yè)人七參考使用。

作者簡(jiǎn)介

　　R.C.T.Lee（李家同）1939年生于上海，臺(tái)灣大學(xué)電機(jī)系學(xué)士，美國加州伯克利大學(xué)電機(jī)博士。歷任臺(tái)灣清華大學(xué)工學(xué)院院長、教務(wù)長以及代校長，靜宜大學(xué)校長，暨南大學(xué)校長，現(xiàn)任暨南大學(xué)教授。李教授是美國電機(jī)電子學(xué)會(huì)的榮譽(yù)會(huì)士，并且曾擔(dān)任過11種國際學(xué)術(shù)刊物的編輯委員。

書籍目錄

出版者的話專家指導(dǎo)委員會(huì)譯者序前言第1章　緒論第2章　算法復(fù)雜度與問題的下界　2.1　算法的時(shí)間復(fù)雜度　2.2　最好、平均和最壞情況的算法分析　2.3　問題的下界　2.4　排序的最壞情況下界　2.5　堆排序：在最壞情況下最優(yōu)的排序算法　2.6　排序的平均情況下界　2.7　通過神諭改進(jìn)下界　2.8　通過問題轉(zhuǎn)換求下界　2.9　注釋與參考　2.10　進(jìn)一步的閱讀資料　習(xí)題第3章　貪心法　3.1　生成最小生成樹的Kruka1算法　3.2　生成最小生成樹的Prim算法　3.3　單源最短路徑問題　3.4　二路歸并問題　3.5　用貪心法解決最小圈基問題　3.6　用貪心法解決2終端一對(duì)多問題　3.7　用貪心法解決1螺旋多邊形最小合作警衛(wèi)問題　3.8　實(shí)驗(yàn)結(jié)果　3.9　注釋與參考　3.10　進(jìn)一步的閱讀資料　習(xí)題第4章　分治策略　4.1　求2維極大點(diǎn)問題　4.2　最近點(diǎn)對(duì)問題　4.3　凸包問題　4.4　用分冶策略構(gòu)造Voronoi圖　4.5　voronoi圖的應(yīng)用　4.6　快速傅里葉變換　4.7　實(shí)驗(yàn)結(jié)果　4.8　注釋與參考　4.9　進(jìn)一步的閱讀資料　習(xí)題第5章　樹搜索策略　5.1　廣度優(yōu)先搜索　5.2　深度優(yōu)先搜索　5.3　爬山法　5.4　最佳優(yōu)先搜素策略　5.5　分支限界策略　5.6　用分支限界策略解決人員分配問題　5.7　用分支限界策略解決旅行商優(yōu)化問題　5.8　用分支限界策略解決O，1背包問題　5.9　用分支限界方法解決作業(yè)調(diào)度問題　5.10　A*算法　5.11　用特殊的A*算法解決通道路線問題　5.12　用A*算法解決線性分塊編碼譯碼問題　5.13　實(shí)驗(yàn)結(jié)果　5.14　注釋與參考　5.15　進(jìn)一步的閱讀資料　習(xí)題第6章　剪枝搜索方法　6.1　方法概述　6.2　選擇問題　6.3　兩變量線性規(guī)劃　6.4　圓心問題　6.5　實(shí)驗(yàn)結(jié)果　6.6　注釋與參考　6.7　進(jìn)一步的悶讀瓷料　習(xí)題弟7章　動(dòng)態(tài)規(guī)劃方法　7.1　資源配置問題　7.2　最長公共f序列問題　7.3　2序列比對(duì)問題　7.4　RNA最大堿基對(duì)匹配問題　7.5　0，1背包問題　7.6　最優(yōu)二衛(wèi)樹問題　7.7　樹的帶權(quán)完壘支配問題　7.8　樹的帶權(quán)單步圖邊的搜索問題　7.9　用動(dòng)態(tài)規(guī)劃方法解決1螺旋多邊形m守衛(wèi)路由問題　7.1O　實(shí)驗(yàn)結(jié)果　7.11　注釋與參考　7.12　進(jìn)一步的閱讀資料　習(xí)題第8章　NP完全性理論　8.1　關(guān)十NP完壘性理論的非形式化討論　8.2　判定問題　8.3　可滿足性問題　8.4　NP問題　8.5　庫克定理　8.6　NP完全問題　8.7　證明NP完全性的例子　8.8　2可滿足性問題　8.9　注釋與參考　8.10　進(jìn)一步的閱讀資料　習(xí)題第9章　近似算法　9.1　頂點(diǎn)覆蓋問題的近似算琺　9.2　歐幾里得旅行商問題的近似算法　9.3　特殊瓶頸旅行商問題的近似算琺　9.4　特殊瓶頸加權(quán)K供應(yīng)商問題的近似算法　9.5　裝箱問題的近似算法　9.6　直線m中心問題的最優(yōu)近似算法　9.7　多序列比對(duì)問題的近似算琺　9.8　對(duì)換排序問題的2近似算法　9.9　多項(xiàng)式時(shí)間近似方案　9.10　最小路徑代價(jià)生成樹問題的2近似算法　9.11　最小路徑代價(jià)生成樹問題的Pns　9.12　NP0完全性　9.13　注釋與參考　9.14　進(jìn)一步的閱讀資料　習(xí)題第10章　分?jǐn)偡治觥?O.1　使用勢(shì)能函數(shù)的例子　10.2　斜堆的分?jǐn)偡治觥?0.3　Av1樹的分?jǐn)偡治觥?0.4　自組織順序檢索啟發(fā)式方法的分?jǐn)偡治觥?0.5　配對(duì)堆及其分?jǐn)偡治觥?0.6　不相交集合并算法的分?jǐn)偡治觥?0.7　一些磁盤調(diào)度算法的分?jǐn)偡治觥?0.8　實(shí)驗(yàn)結(jié)果　10.9　注釋與參考　10.10　進(jìn)步的閱讀資料　習(xí)題第11章　隨機(jī)算法　11.1　解決最近點(diǎn)對(duì)問題的隨機(jī)算琺　11.2　隨機(jī)最近點(diǎn)對(duì)問題的平均性能　11.3　素?cái)?shù)測(cè)試的隨機(jī)算法　11.4　模式匹配的隨機(jī)算法　11.5　交互證明的隨機(jī)算法　11.6　最小生成樹的隨機(jī)線性時(shí)間算法　11.7　注釋與參考　11.8　進(jìn)一步的閱讀資料　習(xí)題第12章　在線算法　12.1　用貪心法解決在線歐幾里得生成樹問題　12.2　在線K服務(wù)員問題及解決定義在平面樹上該問題的貪心算法　12.3　基于平衡策略的在線穿越障礙算法　12.4　用補(bǔ)償策略求解在線二分匹配問題　12.5　用適中策略解決在線m臺(tái)機(jī)器調(diào)度問題　12.6　基于排除策略的三個(gè)計(jì)算幾何問題的在線算法　12.7　基于隨機(jī)策略的在線生成樹算法　12.8　注釋與參考　12.9　進(jìn)一步的閱凄資料　習(xí)題參考文獻(xiàn)

圖書封面

圖書標(biāo)簽Tags

無

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

---

    算法設(shè)計(jì)與分析導(dǎo)論 PDF格式下載

---