掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
闖進數學世界――探秘歷史名題
-
>
中醫基礎理論
-
>
當代中國政府與政治(新編21世紀公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫內科學·全國中醫藥行業高等教育“十四五”規劃教材
現代算法設計與分析 版權信息
- ISBN：9787111679554
- 條形碼：9787111679554 ; 978-7-111-67955-4
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
現代算法設計與分析 本書特色
適讀人群 ：高校計算機相關專業學生，業界技術人員隨著大數據和人工智能等領域的發展，算法領域也在不斷涌現新概念、新方法和新應用。本書在傳統算法技術的基礎上融入了對當前新技術方向的討論，更具現代性和前瞻性。全書內容簡潔明快，為每個概念都提供了嚴格的數學證明，并配有豐富的習題和拓展閱讀資料。本書要求讀者已掌握基本的數據結構知識和編程技能，適用于將“數據結構”與“算法”分為兩門課程的教學。本書特色關注新研究和新技術。引入了降維技術、并行算法、隨機算法、層次化存儲結構算法和流算法等新內容，對傳統算法的講解則采用了大量不同于同類書的新穎示例，從而幫助讀者把握技術熱點及發展趨勢。強調計算模型和計算環境。不再局限于一致化開銷的隨機存取機模型，而是考慮真實環境，提出“算法=問題的定義+模型”，并圍繞并行計算等重要的計算環境深入討論了以模型為中心的算法設計。采用新視角和新方法。充分利用概率分析和隨機化技術——當前眾多新研究中的關鍵技術，這是同類書較少涉及的。此外，還在協調和彌合離散方法與連續方法方面做了嘗試，以應用代數方法解決數值問題。
現代算法設計與分析 內容簡介
本書不僅講解傳統的算法設計策略和技巧，而且關注算法領域不斷涌現的新概念、新方法和新應用，幫助讀者把握技術熱點及發展趨勢。書中引入了降維技術、并行算法、隨機算法、層次化存儲結構算法和流算法等新內容，大量使用概率分析和隨機化技術，并包含眾多新穎的示例，特別是強調計算模型和計算環境，不再局限于理想化的隨機存取機模型。全書內容簡潔明快，并配有豐富的習題和拓展閱讀資料，適合作為高等院校計算機相關專業的教材，也適合業界技術人員閱讀參考。
現代算法設計與分析 目錄
出版者的話 譯者序 前言 致謝 第1章 模型與分析1 1.1 計算斐波那契數1 1.2 快速乘法3 1.3 計算模型3 1.4 隨機算法簡介4 1.4.1 另一種隨機算法6 1.5 其他計算模型8 1.5.1 外部存儲器模型8 1.5.2 并行模型8 拓展閱讀10 習題10 第2章 概率基礎與尾部不等式13 2.1 概率基礎13 2.2 尾部不等式17 2.3 生成隨機數20 2.3.1 生成具有任意分布的隨機變量21 2.3.2 由順序文件生成隨機變量21 2.3.3 生成隨機置換23 拓展閱讀25 習題25 第3章 熱身問題27 3.1 計算*大公因子的歐幾里得算法27 3.1.1 擴展歐幾里得算法27 3.1.2 在密碼學中的應用28 3.2 尋找第k小的元素28 3.2.1 選擇隨機的劃分元29 3.2.2 中位數的中位數30 3.3 詞的排序32 3.4 可歸并的堆34 3.4.1 歸并二項堆35 3.5 一個簡單的半動態詞典35 3.5.1 勢能法與平攤分析36 3.6 下界37 拓展閱讀39 習題39 第4章 優化Ⅰ：蠻力法與貪婪策略42 4.1 啟發式搜索方法42 4.1.1 博弈樹44 4.2 貪婪算法的框架46 4.2.1 *大支撐樹49 4.2.2 尋找*小權值子集49 4.2.3 一個調度問題50 4.3 *小支撐樹算法的高效數據結構51 4.3.1 并查集的一種簡單數據結構52 4.3.2 更快的方案53 4.3.3 增長*慢的函數54 4.3.4 整合55 4.3.5 僅做道路壓縮56 4.4 其他不同形式的貪婪策略57 4.5 與貪婪策略的折中58 4.6 梯度下降59 4.6.1 應用63 拓展閱讀65 習題66 第5章 優化Ⅱ：動態規劃69 5.1 背包問題70 5.2 上下文無關文法的解析71 5.3 *長單調子序列72 5.4 函數逼近74 5.5 *大似然估計的Viterbi算法75 5.6 樹中的*大權獨立集76 拓展閱讀76 習題77 第6章 查找80 6.1 跳表--一個簡單的字典80 6.1.1 跳表的構造80 6.1.2 分析81 6.1.3 更強的尾部估計82 6.2 樹堆：隨機查找樹83 6.3 全域哈希86 6.3.1 全域哈希函數的存在性88 6.4 完美哈希函數88 6.4.1 將期望界轉換為*差情況的界89 6.5 一個復雜度為log log N的優先級隊列89 拓展閱讀91 習題92 第7章 多維查找與幾何算法94 7.1 區間樹與范圍樹94 7.1.1 一維范圍查找94 7.1.2 二維范圍查找96 7.2 kd樹97 7.3 優先級查找樹99 7.4 平面凸包101 7.4.1 Jarvis March算法102 7.4.2 Graham掃描算法102 7.4.3 排序與凸包103 7.5 快速凸包算法104 7.5.1 分析105 7.5.2 期望運行時間106 7.6 使用持久化數據結構的點定位107 7.7 增量構造法109 拓展閱讀111 習題111 第8章 字符串匹配與指紋函數114 8.1 RabinKarp指紋字符串查找算法114 8.2 KMP算法117 8.2.1 KMP算法的分析120 8.2.2 模式分析120 8.3 字典樹及其應用121 拓展閱讀123 習題123 第9章 快速傅里葉變換及其應用125 9.1 多項式求值與插值125 9.1.1 多項式相乘126 9.2 CooleyTukey算法126 9.3 蝶形網絡128 9.4 SchonageStrassen快速乘法算法129 9.5 廣義字符串匹配131 9.5.1 基于卷積的方法131 拓展閱讀133 習題133 第10章 圖算法135 10.1 深度優先搜索135 10.2 深度優先搜索的應用138 10.2.1 強連通分支138 10.2.2 雙連通分支140 10.3 道路問題142 10.3.1 BellmanFord單源*短道路算法143 10.3.2 Dijkstra單源*短道路算法143 10.3.3 任意兩點之間的*短道路算法145 10.4 計算賦權圖中的支撐子145 10.5 全局*小割148 10.5.1 收縮算法149 10.5.2 *小割的概率149 拓展閱讀150 習題151 第11章 *大流及其應用153 11.1 *大流的性質與算法155 11.1.1 *大流與*小割155 11.1.2 FordFulkerson算法156 11.1.3 EdmondKarp可增廣道路策略157 11.1.4 單調性引理及迭代次數的界158 11.2 *大流的應用159 11.2.1 邊不相交的道路159 11.2.2 二部圖的匹配159 11.2.3 環流問題162 11.2.4 項目規劃164 拓展閱讀165 習題165 第12章 NP完全性與近似算法168 12.1 分類與可歸約性170 12.2 CookLevin定理172 12.3 常見的NP完全問題173 12.4 NP完全性的證明175 12.4.1 頂點覆蓋及相關問題175 12.4.2 圖的3著色問題176 12.4.3 背包問題及相關問題177 12.5 其他重要的復雜度類179 12.6 使用近似算法處理困難性181 12.6.1 *大背包問題182 12.6.2 *小集合覆蓋183 12.6.3 幾何旅行商問題184 12.6.4 3著色問題185 12.6.5 *大割問題185 拓展閱讀186 習題186 第13章 降維188 13.1 隨機投影與JohnsonLindenstrauss引理188 13.2 高斯消元法191 13.3 奇異值分解及其應用192 13.3.1 矩陣代數與SVD定理192 13.3.2 使用SVD的低秩近似194 13.3.3 低秩近似的應用196 13.3.4 聚類問題197 13.3.5 SVD定理的證明199 拓展閱讀200 習題200 第14章 并行算法201 14.1 并行計算模型201 14.2 排序和比較問題202 14.2.1 尋找*大值202 14.2.2 排序204 14.3 并行前綴208 14.4 基本的圖算法212 14.4.1 列表排名212 14.4.2 連通分支214 14.5 基本的幾何算法216 14.6 并行模型之間的關系217 14.6.1 網格上的路由218 拓展閱讀220 習題220 第15章 層次化存儲結構及高速緩存223 15.1 層次化存儲模型223 15.2 矩陣轉置224 15.2.1 矩陣乘法225 15.3 在外部存儲器中進行排序226 15.3.1 我們可以改進這個算法嗎227 15.4 高速緩存參數無關的算法設計228 15.4.1 參數無關的矩陣轉置229 拓展閱讀231 習題232 第16章 流數據模型233 16.1 引言233 16.2 查找流中的頻繁元素233 16.3 流中的相異元素236 16.4 頻數矩問題及其應用238 16.4.1 均值的中位數241 16.4.2 二階頻數矩的特例241 16.5 流模型下界的證明243 拓展閱讀244 習題245 附錄A 遞推關系與生成函數247 參考文獻253
展開全部
現代算法設計與分析 作者簡介
---作者簡介---桑迪普?森（Sandeep Sen） 印度理工學院德里分校計算機科學與工程系教授，印度國家科學院院士，印度科學院院士，研究領域包括隨機算法、計算幾何、動態圖算法和計算模型等。曾在IBM研究實驗室、微軟研究實驗室、北卡羅萊納大學教堂山分校等機構擔任訪問研究員。阿米特?庫瑪爾（Amit Kumar） 印度理工學院德里分校計算機科學與工程系教授，印度科學院院士，研究領域包括組合優化、調度、圖論和聚類等。曾任職于貝爾實驗室，并曾在微軟印度研究院和IBM印度研究院擔任訪問教授。曾榮獲2018年印度Shanti Swarup Bhtanagar數學科學獎。---譯者簡介---劉鐸 于清華大學計算機科學與技術系獲工學博士學位，現為北京交通大學軟件學院副教授。主要研究方向為應用密碼學、信息安全、組合算法的設計與分析。主持和參與、省部級科研項目多項，以第一作者身份在各類重要刊物和會議上發表論文20余篇，目前主持建設并講授的“離散數學”課程被評為首批（線上）一流本科課程。
書友推薦
- >
羅曼·羅蘭讀書隨筆-精裝
- >
月亮虎
- >
山海經
- >
詩經-先民的歌唱
- >
隨園食單
- >
經典常談
- >
我從未如此眷戀人間
- >
羅庸西南聯大授課錄
本類暢銷
