掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
算法分析進階:超越最壞情況分析 版權信息
- ISBN：9787111760184
- 條形碼：9787111760184 ; 978-7-111-76018-4
- 裝幀：平裝-膠訂
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
算法分析進階:超越最壞情況分析 本書特色
算法設計中沒有靈丹妙藥（no silver bullet）——不存在任何一種足夠強大和靈活，能夠解決所有計算問題的算法思想。同樣，算法分析中也沒有靈丹妙藥，因為對算法進行分析的*具啟發性的方法往往取決于問題和應用的細節。然而，典型的算法課程幾乎完全停留在一種單一的分析框架上，即*壞情況分析。本書的目的就是糾正這種不平衡。
算法分析進階:超越最壞情況分析 內容簡介
本書源于斯坦福大學的研究生課程，由40位學者聯袂撰寫，旨在推廣zui壞情況分析的替代方法，以及這些方法的應用，包括聚類、線性規劃和神經網絡訓練等。
算法分析進階:超越最壞情況分析 目錄
譯者序前言作者名單第1章 引言1 1.1 算法的*壞情況分析1 1.1.1 不可比較算法的比較1 1.1.2 *壞情況分析帶來的好處2 1.1.3 算法分析的目標2 1.2 著名的失敗事件和對替代方法的迫切需要3 1.2.1 線性規劃的單純形法3 1.2.2 聚類與NP困難*優化問題3 1.2.3 機器學習的不合理的有效性4 1.2.4 在線算法分析5譯者序前言作者名單第1章 引言1 1.1 算法的*壞情況分析1 1.1.1 不可比較算法的比較1 1.1.2 *壞情況分析帶來的好處2 1.1.3 算法分析的目標2 1.2 著名的失敗事件和對替代方法的迫切需要3 1.2.1 線性規劃的單純形法3 1.2.2 聚類與NP困難*優化問題3 1.2.3 機器學習的不合理的有效性4 1.2.4 在線算法分析5 1.2.5 *壞情況分析的騙局5 1.3 示例：在線分頁問題中的參數化界6 1.3.1 根據引用局部性的參數化6 1.3.2 定理1.1的證明7 1.3.3 討論8 1.4 本書概述9 1.4.1 *壞情況分析的改進9 1.4.2 確定性數據模型10 1.4.3 半隨機模型11 1.4.4 平滑分析12 1.4.5 機器學習和統計學中的應用13 1.4.6 進一步的應用14 1.5 本章注解16 致謝16 參考文獻16 練習題17**部分 *壞情況分析的改進第2章 參數化算法20 2.1 引言20 2.1.1 熱身：頂點覆蓋問題20 2.2 隨機化23 2.2.1 隨機分離：集合拆分問題25 2.2.2 去隨機化26 2.3 結構上的參數化26 2.4 核心化27 2.4.1 熱身：Buss規則27 2.4.2 形式定義以及與FPT的成員關系28 2.4.3 Buss規則在矩陣秩上的推廣29 2.5 困難性和*優性30 2.5.1 W\[1\]困難性30 2.5.2 ETH和SETH31 2.5.3 核心化的困難性和*優性32 2.6 展望：新的范例和應用領域33 2.6.1 FPT-近似和有損核心33 2.6.2 P問題中的FPT35 2.6.3 應用領域36 2.7 總體方向36 2.8 本章注解36 參考文獻37 練習題40第3章 從自適應分析到實例*優性41 3.1 案例研究1：*大點集合問題41 3.1.1 Jarvis步進算法41 3.1.2 Graham掃描算法42 3.1.3 Marriage Before Conquest算法42 3.1.4 垂直熵43 3.1.5 （忽視順序的）實例*優性44 3.1.6 部分有序的輸入46 3.1.7 不可能性的結果46 3.2 案例研究2：實例*優的聚合算法47 3.2.1 實例*優性47 3.2.2 問題的設定48 3.2.3 閾值算法48 3.2.4 閾值算法的實例*優性49 3.2.5 *優性比上的匹配下界49 3.3 對更多結果和技術的綜述50 3.3.1 輸入順序50 3.3.2 輸入結構50 3.3.3 順序與結構之間的協同作用51 3.4 討論51 3.4.1 與參數化算法的比較51 3.4.2 與在線算法的競爭分析的比較52 3.5 開放式問題精選52 3.5.1 高維的情況52 3.5.2 *大點集合的分層52 3.6 關鍵要點53 3.7 本章注解53 致謝53 參考文獻53 練習題54第4章 資源增廣57 4.1 再論在線分頁問題57 4.1.1 模型57 4.1.2 FIF和LRU57 4.1.3 競爭比58 4.1.4 資源增廣界58 4.2 討論59 4.3 自私路由問題61 4.3.1 模型和一個推動研究的示例61 4.3.2 資源增廣保證62 4.3.3 定理4.4的證明（平行邊）62 4.3.4 定理4.4的證明（一般網絡）63 4.4 調度問題中速度的改變64 4.4.1 非預知未來調度64 4.4.2 關于SETF的資源增廣保證65 4.4.3 引理4.8的證明：準備工作66 4.4.4 引理4.8的證明：主要論證67 4.5 松弛競爭算法69 4.6 本章注解71 致謝71 參考文獻71 練習題72第二部分 確定性數據模型第5章 擾動彈性76 5.1 引言76 5.2 組合*優化問題78 5.3 認證算法的設計80 5.4 認證算法示例84 5.5 擾動彈性的聚類問題85 5.5.1 度量擾動彈性蘊含了中心緊鄰性87 5.6 2-擾動彈性實例的算法88 5.7 k-median的（3+ε)-認證的局部搜索算法90 5.8 本章注解91 參考文獻92 練習題94第6章 近似解穩定性與代理目標95 6.1 引言和動機95 6.2 定義和討論96 6.3 k-median問題99 6.3.1 定義99 6.3.2 一些令人關注的結果99 6.3.3 算法和證明100 6.3.4 小簇的處理104 6.4 k-means、min-sum以及其他聚類目標105 6.5 聚類應用105 6.6 納什均衡106 6.7 總體方向107 6.8 開放式問題108 6.9 松弛108 6.10 本章注解108 參考文獻109 練習題110第7章 稀疏恢復111
展開全部
算法分析進階:超越最壞情況分析 作者簡介
蒂姆·拉夫加登（Tim Roughgarden） 哥倫比亞大學計算機科學系教授，之前曾任教于斯坦福大學，主要研究領域包括算法、博弈論以及微觀經濟學。他曾獲得美國青年科學家與工程師總統獎（PECASE），ACM頒發的Grace Murray Hopper獎，世界博弈論學會頒發的Kalai獎，數學優化學會頒發的Tucker獎，以及EATCS-SIGACT頒發的G?del獎。
書友推薦
- >
經典常談
- >
姑媽的寶刀
- >
史學評論
- >
朝聞道
- >
山海經
- >
名家帶你讀魯迅:朝花夕拾
- >
企鵝口袋書系列·偉大的思想20:論自然選擇(英漢雙語)
- >
巴金－再思錄
本類暢銷
