算法分析進階：超越最壞情況分析 Beyond the Worst-Case Analysis of Algorithms

Tim Roughgarden 譯 蔡國揚

算法分析進階：超越最壞情況分析

簡體館年度書展｜現貨2書79折3書75折 詳見活動內容 »

簡體館年度書展｜現貨2書79折3書75折 詳見活動內容 »

相關主題

商品描述

本書源自史丹佛大學的研究生課程，由40位學者聯袂撰寫，
旨在推廣最壞情況分析的替代方法，以及這些方法的應用，包括聚類、線性規劃和神經網絡訓練等。
書中涵蓋演算法分析領域的各個方面，強調重要的模型和研究成果。
本書首先討論最壞情況分析的改進，然後介紹確定性資料模型、半隨機模型、平滑分析，
最後介紹這些理論在機器學習、統計學等領域的應用，大部分章節以開放式的研究方向以及適合課堂教學的練習題作為結束。

目錄大綱

譯者序
前言
作者名單
第1章 引言
1.1 演算法最壞的情況分析
1.1.1 不可比較演算法的比較
1.1.2 最壞情況分析帶來的好處
1.1.3 演算法分析的目標
1.2 著名的失敗事件和對替代方法的迫切需要
1.2.1 線性規劃的單純形法
1.2.2 聚類與NP困難最最佳化問題
1.2.3 機器學習的不合理的有效性
1.2.4 線上演算法分析
1.2.5 最壞情況分析的騙局
1.3 範例：線上分頁問題中的參數化界
1.3.1 根據引用局部性的參數化
1.3.2 定理1.1的證明
1.3.3 討論
1.4 本書概述
1.4.1 最壞情況分析的改進
1.4.2 確定性資料模型
1.4.3 半隨機模型
1.4.4 平滑分析
1.4.5 機器學習和統計學中的應用
1.4.6 進一步的應用
1.5 本章註解
致謝
參考文獻
練習題
第一部分 最壞情況分析的改進
第2章 參數化演算法
2.1 引言
2.1.1 熱身：頂點覆蓋問題
2.2 隨機化
2.2.1 隨機分離：集合拆分問題
2.2.2 去隨機化
2.3 結構上的參數化
2.4 核心化
2.4.1 熱身：Buss規則
2.4.2 形式定義以及與FPT的成員關係
2.4.3 Buss規則在矩陣秩上的推廣
2.5 困難性和最優性
2.5.1 W[1]困難性
2.5.2 ETH和SETH
2.5.3 核心化的困難性和最適性
2.6 展望：新的範例與應用領域
2.6.1 FPT-近似和有損核心
2.6.2 P問題中的FPT
2.6.3 應用領域
2.7 總體方向
2.8 本章註解
參考文獻
練習題
第3章 從自適應分析到實例最適性
3.1 個案研究1：最大點集合問題
……
第二部分 確定性資料模型
第三部分 半隨機模型
第四部分 平滑分析
第五部分 機器學習與統計學的應用
第六部分 進一步的應用

類似商品